In that case, since you are already de-duping "externally", you might play with `setopt HIST_IGNORE_ALL_DUPS HIST_IGNORE_DUPS HIST_SAVE_NO_DUPS` combinations. It's been many years since I looked at it, but I think these conspire with large saved histories to slow things down a lot at startup/initial history parse.

I don't even recall if it's necessary or was just the simple algorithm. So, you might actually be able to get Zsh fixed if there is some quadratic thing that can be turned linear with a hash table. The Zsh mailing list is quite accommodating in my experience.