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 o

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 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 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/15bffc20ed8da26e68c88bb776b18d19e959453f/lib/pure/collections/tables.nim#L1524 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 https://github.com/nim-lang/Nim/issues/13559