I'm surprised that hash maps can stray far enough from O(1) to become unusable in hard real-time. Is it because RT systems have to use lower-quality PRNGs?
I'm surprised that hash maps can stray far enough from O(1) to become unusable in hard real-time. Is it because RT systems have to use lower-quality PRNGs?
But the categorization of real-time depends on the requirements of the problem, not how difficult it is to meet them. If your problem tolerates a few missed deadlines every now and then and your hardware is such that a naive implementation misses deadlines so frequently that it's useless, and so you need to optimize it thoroughly to get the misses under control, it's still soft real-time. It doesn't become soft real-time when technology advances enough that even an inefficient implementation will tolerably a deadline only occasionally.
The malicious version of this is hash DoS, where an attacker chooses the values inserted into the hash table so they have the same hash (or at least same bucket). Randomized hashing using a secure hash mitigates this somewhat, but the attack is still possible to some degree, especially if the hash secret is long lived.
Another issue is that inserting into hash tables is usually only amortized O(1), with the collection growing exponentially when it's full. So most insert operations are cheap, but occasionally you get an O(n) insertion. However it doesn't sound like this is what the article is talking about.
https://www.sciencedirect.com/science/article/abs/pii/019667748790040X
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 and a formula based one from that above paper inside https://github.com/c-blake/suggest
This is all more about the "attack" scenario than the "truly hard" real-time scenario, of course.
And worst case is the only thing that matters in a hard real time system.
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