4 ms·

Regarding speed of the C++ version: The fundamental mistake is to use std::unordered_map. The standard library map and set implementations (both ordered -> tree

Regarding speed of the C++ version: The fundamental mistake is to use std::unordered_map. The standard library map and set implementations (both ordered -> tree-based and unordered -> hash-based) are almost never the correct choice if you care about performance. That's definitely a flaw in the language, but like with C you would just use a different implementation for this purpose.

jjnoakes 6y ago
To expand on this a bit, the C++ unordered map (hash table) uses basically a linked list to track the entries in each bucket (separate chaining for collisions) because the standard requires that operations that may resize the map don't invalidate iterators. You pay for this with extra memory allocations and non-contiguous memory access. In most low level benchmarks, other collision mechanisms (probing, etc) perform much better.
usefulcat 6y ago
Although std::unordered_map is definitely not nearly as fast as a hash map can be in c++, that's probably not the main problem here. I would bet on iostreams and/or tolower being bigger problems. Note that tolower is called for every /character/. I don't know everything it does, but I know it's doing some semi-esoteric locale stuff, and in general it's doing a lot more than a naive ascii implementation would. I seem to recall it's even doing a dynamic_cast in there somewhere. For each character of input. I was curious, so I ran callgrind on it. Here are the top 10 offenders (by Ir, 'instructions retired'). For clarity I have elided many details. Total Ir is 5,647,099,795, so the stuff below accounts for greater than 50% of all Ir. 1,079,594,033 std::istream& operator>>(std::istream&, std::string&) 553,657,533 std::istream::sentry::sentry(std::istream&, bool) 550,159,646 __cxxabiv1::__vmi_class_type_info::__do_dyncast(...) 426,992,280 __dynamic_cast 413,240,330 std::_Hash_bytes(void const*, unsigned long, unsigned long) 383,294,340 tolower 230,374,111 std::string::_M_append(char const*, unsigned long) 223,653,549 /usr/include/c++/9/bits/stl_algo.h:main 172,438,098 __strcmp_avx2 164,226,680 std::ctype const& std::use_facet(std::locale const&)

jjnoakes 6y ago

To expand on this a bit, the C++ unordered map (hash table) uses basically a linked list to track the entries in each bucket (separate chaining for collisions) because the standard requires that operations that may resize the map don't invalidate iterators. You pay for this with extra memory allocations and non-contiguous memory access. In most low level benchmarks, other collision mechanisms (probing, etc) perform much better.

usefulcat 6y ago

Although std::unordered_map is definitely not nearly as fast as a hash map can be in c++, that's probably not the main problem here. I would bet on iostreams and/or tolower being bigger problems. Note that tolower is called for every /character/. I don't know everything it does, but I know it's doing some semi-esoteric locale stuff, and in general it's doing a lot more than a naive ascii implementation would. I seem to recall it's even doing a dynamic_cast in there somewhere. For each character of input. I was curious, so I ran callgrind on it. Here are the top 10 offenders (by Ir, 'instructions retired'). For clarity I have elided many details. Total Ir is 5,647,099,795, so the stuff below accounts for greater than 50% of all Ir. 1,079,594,033 std::istream& operator>>(std::istream&, std::string&) 553,657,533 std::istream::sentry::sentry(std::istream&, bool) 550,159,646 __cxxabiv1::__vmi_class_type_info::__do_dyncast(...) 426,992,280 __dynamic_cast 413,240,330 std::_Hash_bytes(void const*, unsigned long, unsigned long) 383,294,340 tolower 230,374,111 std::string::_M_append(char const*, unsigned long) 223,653,549 /usr/include/c++/9/bits/stl_algo.h:main 172,438,098 __strcmp_avx2 164,226,680 std::ctype const& std::use_facet(std::locale const&)