Wow, this is jam-packed with interesting information. Thanks for writing it! (Also thanks for all of your other great open source work!)
Are there plans to upstream this into the Zig std library? Seems like it could be useful for more than just the cryptography package, since the benchmarks at the end have it often being faster than std pdqsort. I just checked the issue trackers on Codeberg and GitHub, and didn't see anything mentioning djbsort or NTRU Prime, which leads me to believe there aren't (official) plans to upstream this (yet).
ozgrakkurt•1h ago
The blocksort in stdlib can be faster than pqdsort too in my experience
tialaramex•42m ago
> often being faster than std pdqsort.
pdqsort is a generic comparison sort. Want to sort employee names, customer email addresses, JSON blobs, or Zebras? No problem, pdqsort just needs an ordering, in both Zig and C++ you write this as a single boolean "less" predicate.
DJB's speed-up relies on vectorization, which works great for integers or things you can squint at and see an integer - but obviously can't sort your employee names, customer email addresses, JSON blobs or Zebras. You could write these branchless network designs anyway but I'm pretty sure they'd be markedly slower, at least for some common inputs.
jstrieb•2d ago
Are there plans to upstream this into the Zig std library? Seems like it could be useful for more than just the cryptography package, since the benchmarks at the end have it often being faster than std pdqsort. I just checked the issue trackers on Codeberg and GitHub, and didn't see anything mentioning djbsort or NTRU Prime, which leads me to believe there aren't (official) plans to upstream this (yet).
ozgrakkurt•1h ago
tialaramex•42m ago
pdqsort is a generic comparison sort. Want to sort employee names, customer email addresses, JSON blobs, or Zebras? No problem, pdqsort just needs an ordering, in both Zig and C++ you write this as a single boolean "less" predicate.
DJB's speed-up relies on vectorization, which works great for integers or things you can squint at and see an integer - but obviously can't sort your employee names, customer email addresses, JSON blobs or Zebras. You could write these branchless network designs anyway but I'm pretty sure they'd be markedly slower, at least for some common inputs.