Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by nom on Monday May 08, 2017 @11:59PM
(#14297639)
For very small number of elements, an array or a list can be more efficient than hash maps. My rule of thumb is to avoid hash maps if you know you'll never have more than 100 entries, and then try to find the bottleneck later on. Using hash maps for everything isn't always the best solution.
[ Parent
| on HN ]
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by oconnor0 on Tuesday May 09, 2017 @12:10AM
(#14297677)
Using a sequence instead of a map is fine if you know it will never be more than some small number of entries, but so often we are wrong about how many entries will be in a table that the N-squared use of a sequence as a map kills performance unexpectedly.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by adrianN on Tuesday May 09, 2017 @02:01AM
(#14298025)
But that's what profiling is for.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by arjie on Tuesday May 09, 2017 @06:55AM
(#14298960)
That argument favours hashmaps by default, though. After all, they're all right at small sizes and much better at big sizes.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by usefulcat on Tuesday May 09, 2017 @09:32AM
(#14299813)
Profiling won't tell you what the chances are that the collection will someday need to contain more than N elements.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by adrianN on Tuesday May 09, 2017 @11:30AM
(#14300847)
You don't replace every map in your code with a distributed Key-Value store, in case it might need to store terabytes in the future. Most of the time you have a pretty good idea whether a map has to store a hundred, or a hundred thousand elements.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
by Veedrac on Wednesday May 10, 2017 @10:36AM
(#14308511)
If you're looking for elements by identity, that's going to be really slow. Hash maps are designed precisely to handle that scenario, and devolving to linear scans is only going to make things worse.