3 ms·

These results don't make any sense and I don't believe them. The author is generating random strings of length 64. They then generate N random string and searc

These results don't make any sense and I don't believe them. The author is generating random strings of length 64. They then generate N random string and search for them. The probability of finding a match is effectively zero. > Interestingly, up to about 75 elements, the vector actually outperforms both sets. No way. The unordered_set will perform one hash, one lookup, and return false. That is not going to be slower than SEVENTY FIVE string comparisons. Looking at the code I _think_ that randString() for each of the N search strings is included in the timing code. That, uh, is not good? Line 29: https://github.com/akshaynanavati/benchmarks/blob/master/benchmarks/lookup_string.cpp https://github.com/akshaynanavati/benchmarks/blob/master/ben... I don't know how Google Benchmark works. So I wrote my own simple test. I could not find any combination of string length and num searches where a vector was faster than an unordered_set. https://pastebin.com/raw/mfBmGa5B https://pastebin.com/raw/mfBmGa5B Example results: String length: 8 Num Elements: 75 Num Searches: 10000 Gen Time: 1.94252 Vec Time: 4.12721 Set Time: 0.144987 Num Found: 0

AstralStorm 8y ago
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)

AstralStorm 8y ago

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)