3 ms·

The median sort time for sorting 1048576 elements wth djbsort is 61467822 cycles: https://sorting.cr.yp.to/speed.html https://sorting.cr.yp.to/speed.html On a

The median sort time for sorting 1048576 elements wth djbsort is 61467822 cycles: https://sorting.cr.yp.to/speed.html https://sorting.cr.yp.to/speed.html On a say 3.6 Ghz processor that would be around 17ms. So the number of elements sorted per second would be around 61.4 M elements/s. My parallel radix sort can sort floats (a little harder than integers) at around 165 M elements/s: http://forwardscattering.org/post/34 http://forwardscattering.org/post/34 A serial radix sort should still be similar or faster to djbsort.

SiempreViernes 8y ago
Do you also sort in constant time at fixed array size, like djbsort claims it does? For the 1024 array their cycle count quartiles differ from the median at the 3 promille level, but I don't know if this counts as "constant" for timing attack purposes.
- Ono-Sendai 8y ago
  Hmm, interesting question. Radix sorts, by their nature, execute the same code regardless of the contents of their elements. ( I think, I haven't thought about this before). However you will see some variation in execution time based on varying memory access patterns.
  - exDM69 8y ago
    No, it's not constant time. Depending on implementation details, you end up putting different elements in different buckets in different cache lines and that creates side channels. Radix sort will perform differently for an input that is 1,1,1,... and 1,2,3,...,n. I have not read up on how djbsort deals with this issue, but it's the problem it's trying to solve.
    - Veedrac 8y ago
      It's a sorting network, which means it only uses conditional swaps in a fixed pattern, which can be made constant time.
herf 8y ago
My single-threaded floating point sort is also twice as fast as djbsort: http://stereopsis.com/radix.html http://stereopsis.com/radix.html This one uses 11-bit radix to save memory bandwidth. Without all the floating-point stuff it would be faster.
- AstralStorm 8y ago
  The point of djbsort is to be constant time while not being super slow. Of course a fast directly implemented radix sort will be faster, especially if you sprinkle SIMD on top.
- herf 8y ago
  Actually, there is only an advantage to radix after 100,000 elements - djb is much faster for small arrays. Also, while radix is cpu constant time, you'd need to do some kind of secure shuffle in advance to make it truly constant-time (considering memory locality timing).

SiempreViernes 8y ago

Do you also sort in constant time at fixed array size, like djbsort claims it does? For the 1024 array their cycle count quartiles differ from the median at the 3 promille level, but I don't know if this counts as "constant" for timing attack purposes.

Ono-Sendai 8y ago
Hmm, interesting question. Radix sorts, by their nature, execute the same code regardless of the contents of their elements. ( I think, I haven't thought about this before). However you will see some variation in execution time based on varying memory access patterns.
- exDM69 8y ago
  No, it's not constant time. Depending on implementation details, you end up putting different elements in different buckets in different cache lines and that creates side channels. Radix sort will perform differently for an input that is 1,1,1,... and 1,2,3,...,n. I have not read up on how djbsort deals with this issue, but it's the problem it's trying to solve.
  - Veedrac 8y ago
    It's a sorting network, which means it only uses conditional swaps in a fixed pattern, which can be made constant time.

herf 8y ago

My single-threaded floating point sort is also twice as fast as djbsort: http://stereopsis.com/radix.html http://stereopsis.com/radix.html This one uses 11-bit radix to save memory bandwidth. Without all the floating-point stuff it would be faster.

AstralStorm 8y ago
The point of djbsort is to be constant time while not being super slow. Of course a fast directly implemented radix sort will be faster, especially if you sprinkle SIMD on top.
herf 8y ago
Actually, there is only an advantage to radix after 100,000 elements - djb is much faster for small arrays. Also, while radix is cpu constant time, you'd need to do some kind of secure shuffle in advance to make it truly constant-time (considering memory locality timing).