Normalization is not that expensive if you only care to do normalization-insensitive string comparison and string hashing.
The reason it's not that expensive is: a) this requires no memory allocation, and b) most characters in most strings require no normalization!
Notionally you just look at pairs of next codepoints, and if the second one isn't combining and the first one is canonical for the chosen NF (a very fast check for ASCII!), then there's no need to normalize the first, otherwise you gather the combining codepoints and normalize, producing one normalized character and restarting the process where you left off. Most of the time the first codepoint requires no normalization, so the fast path is fast -- not as fast as a normal strcmp() or memcmp(), but still pretty fast.
The reason it's not that expensive is: a) this requires no memory allocation, and b) most characters in most strings require no normalization!
Notionally you just look at pairs of next codepoints, and if the second one isn't combining and the first one is canonical for the chosen NF (a very fast check for ASCII!), then there's no need to normalize the first, otherwise you gather the combining codepoints and normalize, producing one normalized character and restarting the process where you left off. Most of the time the first codepoint requires no normalization, so the fast path is fast -- not as fast as a normal strcmp() or memcmp(), but still pretty fast.