4 ms·
std::vector<std::string> is a pointer-chase cache-miss every compare. In my testing unordered_map is faster so long as numberOfStrings > stringLength. This tru
by forrestthewoods 8y ago
std::vector<std::string> is a pointer-chase cache-miss every compare.
In my testing unordered_map is faster so long as numberOfStrings > stringLength. This true for any size string greater than roughly 4. As stringLength grows the unordered_set advantage grows.
Original post says vector is faster until 75 elements. By my test the unordered_set is 4x faster with 64 char strings/75 elements. At 250 numberOfStrings its ~10x faster.
Sorted vectors + binary search are very very good though. Author said vector faster until 20,000 elements. My testing finds the numberOfStrings > stringLength limit is still basically true. But the unordered_set's advantage grows only to 1.9x by 20,000 numberOfStrings.
This advantage will grow as number of matches / near-matches grows. Random strings are not a great test case. Data sets matter!
Author is fixing a couple of bugs and will be updating their post. Curious to see if his updated results match mine. :)
- Someone 8y ago”std::vector<std::string> is a pointer-chase cache-miss every compare” Nitpick: that is (almost certainly) true for strings of length 64 on any system, but not necessarily so. On existing systems, it isn’t true for short strings (with ‘short’ being implementation dependent), due to “short string optimization” (See https://stackoverflow.com/a/10319672 https://stackoverflow.com/a/10319672, https://stackoverflow.com/a/28003328 https://stackoverflow.com/a/28003328). There’s nothing in the standard that forbids putting extra room in the base object to accommodate larger strings (but of course, it would surprise many users, possibly lead to stack overflows in lots of code, etc)