3 ms·
What are these surprisingly large numbers you've seen? I thought that linear scan optimizations are typically reserved for pretty small maps, like dozens or may
by tshaddox 2mo ago
What are these surprisingly large numbers you've seen? I thought that linear scan optimizations are typically reserved for pretty small maps, like dozens or maybe hundreds of elements.
- inigyou 2mo agoHundreds sounds about right, maybe up to a thousand. But nobody expects that. Hashmap is supposed to be faster once you have, like, ten elements. That's what was promised to us.
- zellyn 2mo agoYeah, I found hundreds surprising (although not on reflection).
- __s 2mo agoDepends on comparison function. In clickhouse-c for type name lookup it's strcmp so I use generated hash table with no collisions & reusing cityhash function since we have it handy: https://github.com/ClickHouse/clickhouse-c/blob/4bdd89a02438d1e81ba7cf95dc111af8a23e313b/clickhouse.h#L1234 https://github.com/ClickHouse/clickhouse-c/blob/4bdd89a02438... Benchmarked an order of magnitude faster than linear scan or binary search. I agree with your general sentiment tho, which is why I measured
- swiftcoder 2mo agoMaybe more than that if you have a sub-optimal hash map implementations. There are a bunch of those floating around - for example, Java's build-in HashMap has traditionally been kneecapped by lack of value types, and if you are not careful you can incur 2x cache misses per lookup...
- __s 2mo agoSame with c++ stl unordered_map