Leaderboard

So, if anyone would like to contribute something to this topic, stay here, you're good. If you have something to say about umm... Hashing Dictionaries and such, this is not the place to be While you weren't looking it got split to here:

I was recently asked what it might take to move off of a solid, stable Delphi-based platform and replace it with something written in, say, C# and all of the latest wiz-bang frameworks that Microsoft supports. I've seen plenty of such efforts in the past 20+ years, and not a single one of them came in anywhere near time or budget! Yet management remained committed to pouring in exorbitant amounts just to ditch a well-functioning platform written in Delphi. I don't get this. My experience over the past 15 years is that upper management loathes allowing devs to refactor code. "Cleaning up code" is what it's frequently called, and they see it as incredibly risky. While I'd tend to agree if there aren't any unit tests in place, the alternative of totally rewriting the whole thing in another language and platform with a different architecture and set of frameworks isn't my idea of "less risky". Is it just Delphi that people see as somehow incapable of continuing to work? I don't get this bias so many upper managers have against a platform that has been working reliably and relatively bug-free for YEARS.

We can recommend Alexander's components. Very good working components and also very good support!

Implementing a fast hash table has way more and more important implications than picking the proper size and grow factor. Oh and proving that something is faster than another thing is far from trivial (as with most benchmarks). Interesting read: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

/blush

This is not the final name for the thread, it's just all I came up with in my ignorance. I am open for improvements.

Thank you!

You missed my point (I blame the language barrier): I was saying that comparing different implementations for some algorithms (such as hash tables) are not trivial to benchmark and compare - I have seen (and written before I knew better) too many biased benchmarks testing only fractions, ignoring certain aspects, using specific data, simply comparing apples and oranges or last but not least being fooled by hardware effects like branch predictors or cache behavior. And that is regardless the programming language.

Food for @Daniel

Strange way round. Wouldn't it be normal for you to prove your prime claim?

The capacity implementation of the RTL dictionary is a bit stupid. Typically the capacity is the number of items you can store in a collection without a reallocation/grow happening. However that is not the case here (in Spring4D we actually implemented it that way - so if you want to store 100 items without a grow happening you pass capacity 100 - the internal mechanism handles overallocating to satisfy the max fill factor). The RTL implementation takes the passed value, calculates the next power of 2 greater than the passed value, allocates as many buckets and sets the grow threshold to 75% of that value. In the benchmark code above that means from the passed 200 it calculates 256 and sets the threshold to 192 which means you can store 192 items before it will grow.

@Tommi Prami I guess you found out about Lemire in our latest commits - see e.g. https://github.com/synopse/mORMot/commit/a91dfbe2e63761d724adef0703140e717f5b2f00 🙂 @Stefan Glienke It is to be used with a prime size - as with our code - which also reduces memory consumption since power of 2 tables are far from optimal in this regard (doubling the slot numbers can become problematic). With a prime, it actually enhances the distribution, even with a weak hash function, especially in respect to anding a power of 2. Lemire reduction is as fast as anding a power of 2 since a multiplication is done in 1 cycle on modern CPUs. Note that Delphi Win32 is not so good at compiling 64-bit multiplcation as involved with Lemire's, whereas FPC has no problem using the i386 mul opcode - which already gives 64-bit results.

I don't agree with that. A good coder can express something in 5 lines what a poor coder takes 25 lines to say. And the poor coder might not be able to make heads or tails of the 5-line version. And six months after writing the 5-line version, the author might not even recognize it! Code you write "now" is ALWAYS "self-explanatory". That's not why one writes comments -- you don't need them in 5 minutes ... you damn well might need them in 5 months, however! I'm going through a bunch of code right now for the first time, and even though the names of things are quite long and the code is well-organized, there are no comments anywhere, and it's really challenging trying to figure out what's going on. Actually, I take that back ... there are some /// comments above some classes and methods in the interface section intended to be used to create some rough documentation. What's missing is any sort of "big picture" explanation other than one method near the bottom that calls 15 different things declared above it, and none of them pass any parameters, yet they seem to be working on several "global" vars (in the class) that are then revised and refined and used among the methods. Well ... some are, some aren't. Being an "expert" sometimes means knowing that "if it ain't broke, don't fix it" applies. Refactoring increases the risk of breaking things that have invisible side-effects. If there are no unit tests, then it's a crap-shoot. I like to put "big picture" comments at the top of units, but I'm frequently criticized for it. They're as much for my benefit as others. I worked at a place once where a colleague would put needless comments like "getter" and "setter" next to the read and write parts of property statements (on 3 lines) and delete comments where I was explaining parameters on procedure and functions. Makes you scratch your head sometimes.