Another Potential CPU Optimization For Mesa: Quadratic Probing

[indepe]

I think this means that the algorithm needs a full table before conflicting hashes occur. Over all I think this sounds like a reasonable fix.

In this case I hope it will be double-checked before relying on it. And if true, I'd be very interested. In any case, I fully agree with the second sentence.

[indepe]

hjahre is spot on. It just means that the hashtable can be filled to the brim without failing. That does not mean that it should be filled to the brim. Currently our load factor is 70% for a big table, but slightly higher when it is tiny.

Perhaps some misunderstanding. I'm assuming at 70% you will frequently need to resolve hash collisions, but still be able to do so until the table is full?

[davidbepo]

Rust, Java, etc. are for sleeping people. A person who creates buffer overflows and null pointer assignments should not be in the industry. When you compile C, it is closest to the assembly language than any other human readable programming language. That is why C is popular in the driver development, for example arduino is quite new platform and you use C.

arduino also supports some c++

[Ancurio]

It's really sad that this is the kind of optimization that people have to write, just because every nontrivial C project still has to write their own data structure implementations (which can have their own bugs and all), mostly because C is so poorly suited to generic programming. To be clear, this would not be a problem if this were a specific hashmap used in a specific part of code with special requirements, but this is the hash table used in all of mesa.

How do I tune the probing algorithm in std::unordered_map?

[Hibbelharry]

When you compile C, it is closest to the assembly language than any other human readable programming language.

Mostly true: When you compile anything, it's close to machine language.

[haplo602]

Noob, having absolutely no clue you of course missed the point and instead got it totally backwards. It isn't that C is just so powerful it takes a great mystical guru to unleash its glory. To the contrary, the point here is that C is ancient and severely lacking, and that there are more modern and featureful alternatives.

No, I do get it correctly ... your point was that you have to actually code in C what is available in more "modern" languages. It's not like you are NOT able to do those things in C.
That's why I replied how I did ...

[helland]

Perhaps some misunderstanding. I'm assuming at 70% you will frequently need to resolve hash collisions, but still be able to do so until the table is full?

Yes, that sounds about right. I'm probably not wording it very well. With quadratic probing you can have a table of size 64, with 64 entries in it. Inserting an entry will not fail to find an empty spot as long as there is room. However, we choose to never fill our table to more than 70%. When we reach that threshold we make a new table of double the size and migrate the entries. That way we keep collisions at an acceptable level. We will still experience collisions, as is unavoidable, possibly even with only 20% or lower loading. However, as the table gets fuller collisions happen more often, so a trade-off between memory consumption, number of times you want to resize the table, and the cost of resolving collisions will have to be made.

[indepe]

Yes, that sounds about right. I'm probably not wording it very well. With quadratic probing you can have a table of size 64, with 64 entries in it. Inserting an entry will not fail to find an empty spot as long as there is room. However, we choose to never fill our table to more than 70%. When we reach that threshold we make a new table of double the size and migrate the entries. That way we keep collisions at an acceptable level. We will still experience collisions, as is unavoidable, possibly even with only 20% or lower loading. However, as the table gets fuller collisions happen more often, so a trade-off between memory consumption, number of times you want to resize the table, and the cost of resolving collisions will have to be made.

Sounds good, thanks for the clarification!

[funfunctor]

Rust, Java, etc. are for sleeping people. A person who creates buffer overflows and null pointer assignments should not be in the industry. When you compile C, it is closest to the assembly language than any other human readable programming language. That is why C is popular in the driver development, for example arduino is quite new platform and you use C.

LOL, derp!

It is quite interesting when language debates come up everyone who has never programmed before comes out the woodwork with equally rubbish assertions. Its weird, I don't understand the human behavior, why not just take the time to learn the thing your obviously interested in?

[unixfan2001]

Rust, Java, etc. are for sleeping people. A person who creates buffer overflows and null pointer assignments should not be in the industry. When you compile C, it is closest to the assembly language than any other human readable programming language. That is why C is popular in the driver development, for example arduino is quite new platform and you use C.

Somehow I highly suspect that people writing rubbish like that are the very people whose code suffers the most from null pointer assignments and buffer overflows, as well as a severe lack of code style guidelines.