Re:Mapping Strings in C++
by Animats on Wednesday April 12, 2017 @05:51PM
(#14102095)
Why is the time for map lookup going up so fast for large numbers of strings? Is he running out of memory and thrashing? Is the implementation of map broken? Does the benchmark include growing the map? (If you include growth time, map insertion is O(N log N, because you need log N recopies of size N.)
[ Parent
| on HN ]
Re:Mapping Strings in C++
by martincmartin on Wednesday April 12, 2017 @06:03PM
(#14102173)
Update: The author is always using a collection of 1,000,000 entries. The horizontal axis is the number of lookups, into a collection of 1,000,000 entries, e.g. always ~ 20 entries in the tree. So the x-axis is logrithmic, but the y axis is linear and we expect the graph to be linear.
Original comment: Good question. The x-axis is logrithmic, the y axis is linear. Without cache effects, std::map and lower_bound should take logrithmic time, so should be a straight line on the graph. Also, unordered_map should be constant time, independent of size. So its either cache effects (including swapping / thrashing), or there's some other overhead that's dominating the whole thing, and the author isn't measuring what they think.
> Is he running out of memory and thrashing?
Sort of. It's probably the level below that: these results look fairly typical of a data structure growing larger than the cache, which is usually 8 MiB now.