3 ms·

Not it won't for this small strings. A 64 byte string likely fits in a cache line so you're doing a cache line comparison which may even have a microop in the C

Not it won't for this small strings. A 64 byte string likely fits in a cache line so you're doing a cache line comparison which may even have a microop in the CPU. Alternatively using SSE or AVX to vector compare the strings which is still really fast. I suspect the author made critical mistakes too. If you are actually hitting a match or do many operations with warmed cache, vector may actually win big time even compared to unordered_set as there may be no pointer chasing involved. (since both all keys and all values are in cache) The vector scan essentially boils down to a memcmp for a sufficiently smart compiler. Computing the hash may or may not be faster than this.

iainmerrick 8y ago
64-byte strings are pointers.
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)

iainmerrick 8y ago

64-byte strings are pointers.

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)