Hi, I’m crooked.
Some time ago, I saw a technical video on B website, the title is “Some solutions under the scenario of high ticket price and Concurrent”.
Qunar is the technical base of Qunar, also known as “Qunar”.
The video link is here:
www.bilibili.com/video/BV1eX…
At that time, I was actually attracted by his picture (12 QPS should be 12K QPS) :
He described two core systems that saved 204C and 2160C of server resources respectively after a “data compression” operation.
The total is 2364C of server resources.
If you go with the standard 4C8G server, boy, that’s 591 machines saved, and you can think of the savings in a year.
The video introduces several data compression schemes, one of which uses high-performance collections:
Because their system design makes a lot of use of “local caches”, and local caches mostly use Hashmaps to help.
So they replaced HashMap with the better performing IntObjectHashMap class, which comes from Netty.
Why do you save so many resources by changing a class?
In other words, what makes IntObjectHashMap perform better?
I don’t know, so I did some research.
Pull the source code
The first step is definitely to find the corresponding source code.
You can go to a Netty dependency and find IntObjectHashMap.
I happen to have the local Netty source code I pulled down before, just need to synchronize the latest code on the line.
When I look for this class in the 4.1 branch, I can’t find it. I just see a Benchmark class:
There is no IntObjectHashMap class:
I don’t know why, but I’m just going to let it go. I just want to find an IntObjectHashMap class.
4.1 If there is no branch, then check on 4.0:
So I cut to the 4.0 branch for a search, and found the corresponding class and test class very smoothly:
Being able to see the test classes is actually why I like to pull the project source code down. If you find the corresponding class by introducing Netty’s Maven dependencies, you won’t see the test class.
Sometimes with the test class to see the source code, get twice the result with half the effort, a look at the source code tips, for you.
One of the most important reasons I want to pull source code is actually this:
It is important to be able to see the commit record of the class and observe the evolution of the class.
Since a commit almost always corresponds to a bug fix or performance optimization, that’s where we should be concerned.
For example, we can see that the hashIndex method has been submitted three times:
Before diving into the IntObjectHashMap source code, let’s take a look at a method that only focuses on hashIndex locally.
First, the code for this place now looks like this:
I know that this method is used to get the index of a key of type int in the array keys.
So why is this line of code submitted three times?
Let’s look at the first submission:
The original code on the left is very clear. If the key is negative, then the index returned is negative, which is obviously illogical.
So someone handed in the code on the right, adding the length of the array to the negative hash value, and finally getting a positive number.
Soon, the guy who submitted the code found a better way to write it and did an optimized commit:
I took away the less than zero judgment. Regardless of whether the key%length evaluates to a positive or negative value, the result is added to an array length and the array length % is run again.
So that’s guaranteed to be a positive index.
The code submitted for the third time is easy to understand. Substitute in the variable:
So, the final code looks like this:
return (key % keys.length + keys.length) % keys.length;
Isn’t it more elegant and better performance than saying less than zero? And this is a routine optimization.
If you can’t see the code commit record, you can’t see the evolution of this method. My point is that there is much more valuable information to be found in the code submission record than in the source code.
Another tip. Here you go.
IntObjectHashMap
Let’s explore the mystery of IntObjectHashMap.
There are actually two related classes for this Map:
IntObjectMap is an interface.
They don’t depend on anything other than the JDK, so once you understand how it works, if you find a suitable scenario for your business scenario, you can paste these two classes into your own project and use them without changing a line of code.
After studying the official test cases and code submission records, I chose to paste out the two classes and write my own code to debug them, which has the advantage of being able to modify the source code at any time for our study.
IntObjectHashMap javadoc IntObjectHashMap javadoc
IntObjectHashMap’s solution to key conflicts is explained in the first sentence:
It uses the Open Addressing, or open addressing, strategy for keys.
Why use open addressing instead of a linked list like a HashMap?
To minimize the memory footprint is To minimize the memory footprint.
How do you reduce your memory footprint?
If you use a linked list, do you need to have at least one pointer to next? Does maintaining this thing take up space?
So without further ado, back to open addressing.
Open addressing is a strategy that can be implemented in many ways, such as:
- Linear Probing
- Quadratic detection
- Double hashing
IntObjectHashMap uses linear probing as shown in the last sentence of the underlined part.
Now we have a basic understanding of the IntObjectHashMap map solution for hash collisions.
Now, let’s do a test case. The code is very simple, just an initialization, a put method:
With just a few lines of code, it looks at first glance like a HashMap. But on closer thought, there was a hint.
If we were using HashMap, the initialization would look like this:
HashMap<Integer,Object> hashMap = new HashMap<>(10);
What about the IntObjectHashMap class definition?
There is only one Object:
This Object represents the value in the map.
So what is Key and where did it go? Is that the first question?
When I look at the put method, I see that key is an int:
That is, the class already restricts key to being a value of type int, so it cannot specify a generic key at initialization.
This class is also explicitly named: I am IntObjectHashMap, key is int, and value is the HashMap of Object.
So why did I use the word “unexpectedly”?
Because look what the HashMap key is:
Is of type Object.
That is, we can’t initialize a HashMap if we want to:
We can put ints like this because the “boxing” operation is hidden:
Therefore, there is an ancient eight-part essay asking: “Can a HashMap key use a basic type?”
Don’t even think about it. No!
Key goes from wrapper type to basic type, which is a point of performance optimization. As we all know, the base type takes up less space than the wrapper type.
Next, let’s start with how it is constructed, focusing on what I’ve framed:
First of all, there are two if judgments to verify the validity of parameters.
(1) (1) (1) (1) (2) (1)
As you can see from the comments in the code and method, we want to set the capacity to an odd number. For example, if I give 8, it will give me 9:
As for why the volume cannot be even, the comment gives an explanation:
Even capacities can break probing.
This means that an even volume breaks the probing, which is the linear probing we mentioned earlier.
Er…
I haven’t figured out why an even number of capacities would disrupt linear detection, but it doesn’t matter.
You can see from the label ② that this is a data initialization operation. Key [] and values[] have the same capacity as each other:
After the two arrays are initialized in the constructor, they look like this:
We will focus on the size change and the key[] and values[] arrays.
Now that the constructor is ready for you, let’s look at the put method, which is a little silky:
The put method has few lines of code and is very clear to analyze.
The first is labeled ①, and the hashIndex method, which gets the index of the put key in the key[] array.
This method was analyzed at the beginning of this article, and we even know the evolution of this method without further elaboration.
And then you go into a for(;;) Cycle.
Value [] == null; value[] == null; value[] == null;
I specially emphasized one sentence and drew a picture for you:
The key[] and values[] arrays have the same capacity.
Why not check whether the index exists in key[] first?
Yes, but consider that if value[] is null, then nothing is maintained at this location. The location of the key and value are one-to-one, so you don’t need to care whether the key exists or not.
If value[index] == null is true, it indicates that the key has not been maintained before, and the corresponding values are maintained directly, and the key[] and values[] arrays need to be maintained separately.
Suppose, for example, that the fourth loop ends like this:
After maintenance, determine whether the current capacity needs to be expanded:
The code for growSize looks like this:
In this method, we can see that IntObjectHashMap expands by a factor of 2.
Additional sentence: this place is a little low, the source code inside two times must be superior operation, with length << 1 just right.
Before capacity expansion, the following conditions must be met: size > maxSize
Size, we know, means how many values are in the current map.
So what is maxSize?
This value is initialized in the constructor. For example, in my sample code maxSize is equal to 4:
That is, if I insert another element, it will expand. For example, if I insert a fifth element, the array will be 19:
Value [index] == null is true. What if it’s false?
So we’re at number three.
Check if the index of key[] is the current key.
If yes, override. The logic is simple to take out the value in the original position and then directly overwrite it and return the original value.
But what if it’s not this key?
What does that mean?
The index position for this key is already occupied by another key.
Is this a hash conflict?
What if a hash conflict occurs?
So here we are at number ③, and look at this comment:
Conflict, keep probing … Conflict, continue detection…
To continue probing, see what the next position of the currently conflicting index is.
If I were to write it, it would be easy, and the next position, which I can type with my foot with my eyes closed, would be index plus 1.
But let’s look at the source code:
We do see index+1, but there is one more prerequisite: index! = values. Length – 1.
If the above expression is true, it is easy to use index+1.
If the above expression is not true, the current index is the last position in the values[] array, then 0 is returned, which is the first index of the array.
To trigger this scenario, you need a hash conflict scenario. Let me write a code to show you:
The above code will only put things into IntObjectHashMap if the calculated subscript is 8, which will result in a hash collision at 8.
For example, within 100, the numbers with subscript 8 are:
After the first loop it looks like this:
The second loop, with key 17, finds that the subscript 8 is already occupied:
So, we come to this judgment:
Returns index=0, so it lands here:
It looks like a ring, right?
Yes, it’s a ring.
But take a closer look at this judgment:
After each index calculation, it also determines whether it is equal to the startIndex of the loop. If it is equal, the empty seat has not been found, and the “Unable to insert” exception is thrown.
Some friends jumped out immediately: wrong, not meeting after using half space, with 2 times capacity expansion? Should have been expanded long before the capacity was full right?
You’re very smart, my friend, and your question is the same one I had when I first saw this place. We’re all good, thoughtful kids.
Note, however, that the source code gives a comment where the exception is thrown:
Can only happen if the map was full at MAX_ARRAY_SIZE and couldn’t grow. This happens only when the Map is full and cannot be expanded.
Expansion, that must also have a ceiling on, and then look at the expansion of the source code:
The maximum capacity is integer. MAX_VALUE – 8, which indicates that there is an upper limit.
But wait, integer. MAX_VALUE I get it. What happens when you subtract 8?
Well, I know, but I’m not talking about it. That’s not the point of this article. If you are interested, explore it yourself, and I will give you a screenshot:
What if I want to verify “Unable to insert”?
Isn’t that easy? I have all the source code.
One is to modify the source code for the growSize() method to change the maximum length limit to a specified value, such as 8.
The second option is to directly prohibit expansion, commenting this line of code to it:
Then run the test case:
You will notice that the “Unable to insert” exception is thrown when the 10th value is inserted.
The 10th value, 89, looks like this, turning around and returning to startIndex:
If this condition is met, an exception is thrown:
(index = probeNext(index)) == startIndex
So I’m done with the put method. You learn about its data structure, and you learn about how it works.
Do you remember the question I’m following in writing this article?
What makes IntObjectHashMap perform better?
One point mentioned earlier is that keys can use the native int type instead of the wrapped Integer type.
Now I want to reveal the second point: value is not a mess, value is a pure value. Whatever you put in there is what it is.
If you think about the structure of a HashMap, it contains a Node that encapsulates the Hash, key, value, and next attributes:
This is what IntObjectHashMap has saved, and this is where the bulk of it is saved.
You shouldn’t look down on a little memory footprint. In the face of a huge base, any small optimization, can be magnified countless times.
I don’t know if you remember this example from understanding the Java Virtual Machine:
Improper data structure leads to excessive memory usage. This problem, you can use Netty’s LongObjectHashMap data structure to solve, just need to change the class, can save a lot of resources.
It’s the same thing.
Extra point
Finally, I’ll give you an additional bonus from my reading of the source code.
Deletions implement compaction, so cost of remove can approach O(N) for full maps, which makes a small loadFactor recommended. Deleting compacts a compaction, so the cost of deleting a full map can be close to O(N), so we recommend using a smaller loadFactor.
It has two words in it, compaction and loadFactor.
The loadFactor attribute is initialized in the constructor:
Why must loadFactor be a number between (0,1)?
The first thing to look at is when loadFactor is used:
This is only used when calculating maxSize. The current capacity is multiplied by this coefficient.
If the coefficient is greater than 1, then the resulting value, maxSize, will be greater than capacity.
If loadFactor is set to 1.5 and capacity is set to 21, then maxSize is calculated to be 31.
LoadFactor is used to calculate maxSize, and maxSize is used to control expansion conditions. That is, the smaller loadFactor is, the smaller maxSize is, and the easier it is to trigger expansion. Conversely, the larger the loadFactor is, the harder it is to expand. The default value of loadFactor is 0.5.
Let me explain that one of the words in the previous comment is this:
It can be interpreted as “compression”, but “deletion achieves compression” is abstract.
Take your time. I’ll tell you.
Let’s look at the delete method first:
The logic of the deletion method is a bit complicated and confusing if I had to rely on my description to make it clear to you.
So, I decided to just show you the results, and you take the results and go back to the source code.
First of all, the previous comment says: dude, I recommend you use a smaller loadFactor.
LoadFactor: 1 loadFactor: 1 loadFactor: 1 loadFactor: 1 loadFactor
That is, when the map is full, adding something to it will trigger expansion.
For example, I initialize it like this:
New IntObjectHashMap < > (8, 1);
The current map has an initial capacity of 9 elements, and only when you place the 10th element will you trigger the expansion operation.
Alas, I just want to put 9 elements, I don’t want to trigger expansion. And my 9 elements all have hash conflicts.
The code is as follows:
These values should all be dropped at 8, but after linear detection, the array in the map should look like this:
At this point, we remove the key 8, which normally looks like this:
But the truth is this:
All values displaced by hash conflicts will be moved back.
This process, AS I understand it, is referred to in the comment as “compaction.”
The actual output of the above program looks like this:
It fits the picture I drew earlier.
However, I should note that my code has been tweaked:
Without making any changes, the output should look like this:
Key =8 is not the last one, because this process involves a rehash operation, and adding rehash to an interpretation of “compaction” can complicate your interpretation of what happens when this compaction happens.
There is also a comment in the removeAt method that mentions this:
This algorithm is essentially what I describe as a “compaction.”
I searched globally for the keyword and found it in both IdentityHashMap and ThreadLocal:
But, you pay attention to the but.
With ThreadLocal, we use “Unlike”.
ThreadLocal also uses linear detection for hash collisions, but the details are a little different.
Without going into details, if you are interested in exploring it, I just want to express that this part can be studied by comparison.
This section is titled “One Extra Point.” Because I didn’t plan this part, but WHEN I looked through the submission record, I saw this:
Github.com/netty/netty…
There is a lot of discussion in this issue, based on this discussion, it is equivalent to IntObjectHashMap for a great transformation.
For example, IntObjectHashMap used “Double hashing” for hash collisions before switching to linear detection.
The suggestion to use a smaller loadFactor and the algorithm used in removeAt are based on this modification:
To quote a dialogue from this issue:
M: “I’ve got carried away.
In my opinion, this is not even a “major improvement”, this is a rewrite.
What does “I’ve got carried away” mean?
Teaching English, late but still:
Remember this phrase when you take the TOEFL Speaking test.
Netty 4.1
At the beginning of the article, I said I didn’t find IntObjectHashMap in Netty 4.1.
I was lying. I found it. I just hid it a little deep.
In fact, I only wrote int in this article, but the basic types can be modified based on this idea, and their code should be similar.
So in 4.1 we use a groovy wrapper:
After compiling the template:
To see what we are looking for in the target directory:
However, if you look closely at the compiled IntObjectHashMap, you’ll notice something a little different.
For example, the capacity adjustment method in the constructor looks like this:
We also know from the method name that we’re looking for the nearest multiple of 2 of the current value.
Wait, a multiple of 2, isn’t it an even number?
In the 4.0 branch of code, the size adjustment must be an odd number:
Remember I mentioned earlier that I hadn’t figured out why an even number of volumes would break linear detection?
But you can see from this that even numbers are ok.
That’s what got me confused.
In the 4.0 code, adjustCapacity doesn’t have this comment in adjustCapacity:
Adjusts the given capacity value to ensure that it’s odd. Even capacities can break probing.
I don’t hesitate to think that this place can be odd or even. But his emphasis on “odd” made me a little uneasy.
Forget it, I can’t do it. I doubt it!
