[kccqzy]

The default hash functions in most C++ implementations are surprisingly slow—implementations tend to aim for hash quality rather than speed.

I can be totally wrong, but I suggest trying a simpler hash such as FNV. It might outperform the sort-based approach.

I also suggest replacing the hash table implementation with something better, such as absl::flat_hash_map. The C++ std::unordered_map is hampered by compatibility requirements: the designers wanted these unordered containers to be a good substitute for the preexisting std::map, and necessitated certains design decisions such as pointer stability which is not necessary for most applications.

[chillee]

Actually, I believe the default hash functions have terrible hash quality - they're literally the identity function for integers.

I do agree that unordered_map is extremely slow.

[aidenn0]

A slow hash-function doesn't explain the increasing time-per-element as the hash table grows though. A poor fit between the keys and hash-function might though.