adix VS tiny_sqlite

Note: Just concatenating the bibles keeps your hash map artificially small...which matters because as you correctly note the big deal is if you can fit the histogram in the L2 cache as noted elsewhere and this really matters if you go parallel where N CPUsL2 caches can speed things up a lot -- until* your histograms blow out CPU-private L2 cache sizes. https://github.com/c-blake/adix/blob/master/tests/wf.nim (or a port to your favorite lang) might make it easy to play with these ideas.

which is notably logarithmic - not unlike a B-Tree.

When these expectations are exceeded you can at least detect a DoS attack. If you wait until such are seen, you can activate a "more random" mitigation on the fly at about the same cost as "the next resize/re-org/whatnot".

All you need to do is instrument your search to track the depth. There is some example such strategy in Nim at https://github.com/c-blake/adix for simple Robin-Hood Linear Probed tables.

Knuth-McIlroy comes up a lot. Previous discussion [1]. For this example I can make a Nim program run almost exactly the same speed as `wc -w`, yet the optimized C program runs 1.2x faster not 3.34x slower - a whopping 4x discrepancy - much bigger than many of the ratios in the table. So, people should be very cautious about conclusions from any of this.

[1] https://news.ycombinator.com/item?id=24817594

[2] https://github.com/c-blake/adix/blob/master/tests/wf.nim

I did some work on Nim's hash tables back in 2020, specifically with OrderedTable, comparable to a Python dict where insertion order is preserved. I stumbled on this table module in a roundabout way, via Nim's database module, db_sqlite. The db_sqlite module was much slower than Python for simple tests, and on investigation, I found that it didn't automatically handled prepared statement caching like Python's sqlite3 module. There were some other issues with db_sqlite, like blob handling and null handling, which led me to a different SQLite interface, tiny_sqlite. This was a big improvement, handling both nulls and blobs, and the developer was great to work with. But it also didn't support prepared statement caching. I filed an issue and he implemented it, using Nim's OrderedTable to simulate an LRU cache by adding a new prepared statement and deleting the oldest one if the cache was too big:

https://github.com/GULPF/tiny_sqlite/issues/3

Performance was hugely improved. There was another LRUCache implementation I played with, and when using that for the statement cache, performance was 25% faster than OrderedTable. That didn't make much sense to me for a 100-entry hash table, so I started running some tests comparing LRUCache and OrderedTable. What I discovered is that OrderedTable delete operations created an entirely new copy of the table, minus the entry being deleted, on every delete. That seemed pretty crazy, especially since it was already showing up as performance problems in a 100-entry table.

The tiny_sqlite developer switched to LRUCache, and I did some work on the OrderedTable implementation to make deletes O(1) as expected with hash table operations:

https://github.com/nim-lang/Nim/pull/14995

After spending a lot of time on this, I finally gave up. The problems were:

- the JSON implementation used OrderedTables and never did deletes. JSON benchmark performance was rather sacred, so changing OrderedTables to be slightly slower/larger (I used a doubly-linked list) was not desirable, even if it changed delete performance from O(n) to O(1)

- the Nim compiler also used OrderedTables and never did deletes

- Nim tables allowed multiple values for the same key (I did help get that deprecated).

- alternatives were proposed by others that maintained insertion order until a deleted occurred, but then it could become unordered. That made no sense to me.

The TLDR is, if you use Nim tables, don't use OrderedTable unless you can afford to make an copy of the table on every deleted.

Current Nim OrderedTable delete code: https://github.com/nim-lang/Nim/blob/15bffc20ed8da26e68c88bb...

Issue for db_sqlite not handling nulls, blobs, statement cache: https://github.com/nim-lang/Nim/issues/13559