Re:Why databases use ordered indexes but programming uses ha...
by adrianN on Monday December 09, 2019 @11:41PM
(#21749640)
Also std::unordered_map suffers from a design flaw that forces a poor implementation.
[ Parent
| on HN ]
Re:Why databases use ordered indexes but programming uses ha...
by yuushi on Tuesday December 10, 2019 @01:44AM
(#21750264)
Depending on what you required, it can still be significantly faster than std::map. Any tree-based data structure is going to play havoc with cache. Also, it will perform an allocation for every single node inserted, which can become rather expensive (unless you're using some customized allocator for this).
Honestly, sorted vectors can often be a good replacement, depending on the workload, if you must have ordered data (this is what boost flat_map uses). All 3 (map, unordered_map, sorted vector) can have their uses, depending on what you are doing with the data.
If you need a better performing hash map, there's always Abseil as well.
Re:Why databases use ordered indexes but programming uses ha...
by adrianN on Tuesday December 10, 2019 @02:58AM
(#21750561)
Unfortunately unordered_map also requires lots and lots of allocations, because it's forced to use linked-list buckets.
Re:Why databases use ordered indexes but programming uses ha...
by taneq on Tuesday December 10, 2019 @01:04AM
(#21750058)
Would you be willing to expand on that? I couldn't find any obvious well-known issues with a quick search.
Re:Why databases use ordered indexes but programming uses ha...
by abhishekjha on Tuesday December 10, 2019 @01:16AM
(#21750111)
Apparently the standard imposes a set of requirements that the implementation must abide by thus making it a lot slower.
[0] : https://www.reddit.com/r/programming/comments/5pwgtn/hash_ma...
[1] : https://stackoverflow.com/questions/42588264/why-is-stdunord...
Re:Why databases use ordered indexes but programming uses ha...
by adrianN on Tuesday December 10, 2019 @01:18AM
(#21750122)
The interface forces an implementation as a map with linked-list buckets which is suboptimal for many use cases. So people who care about performance usually just implement their own hash map or use a library.