Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Djbsort: A new software library for sorting arrays of integers

sorting.cr.yp.to

Post reply on HN
Print view View original

1–10 of 158 posts

Re: Djbsort: A new software library for sorting arrays of integers

#4

Post by Ono-Sendai »

MrBuddyCasino wrote: post #3

The 2.5 cycles/byte compared to the 32 cycles/byte that Intel managed pulled off seems like an improbably large improvement over the current state of the art? Is this real?

Well, that's for a very small and particular size. (1024 elements) Intel's library might have more overhead at that size.

Re: Djbsort: A new software library for sorting arrays of integers

#5

Post by robin_reala »

Why might the installation instructions require the creation of a new user specific to the sorting program? Purely for security of the normal user given that the installation is using a wget / shell script process? https://sorting.cr.yp.to/install.html

Re: Djbsort: A new software library for sorting arrays of integers

#6

Post by bdukic »

MrBuddyCasino wrote: post #3

The 2.5 cycles/byte compared to the 32 cycles/byte that Intel managed pulled off seems like an improbably large improvement over the current state of the art? Is this real?

My guess is that the "catch" comes in the form of the list of limitations.

Re: Djbsort: A new software library for sorting arrays of integers

#7

Post by Ono-Sendai »

The median sort time for sorting 1048576 elements wth djbsort is 61467822 cycles: 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

A serial radix sort should still be similar or faster to djbsort.

Re: Djbsort: A new software library for sorting arrays of integers

#8

Post by banachtarski »

ibuildoss wrote: post #2

That's pretty cool, are there any bindings for e.g. Go out there?

Unrelated to the article I recently learned Go just as a side-interest. I was appalled by how terrible the language is. Usually, language warts aren't apparent until you use it a bit but here annoyances were present on day 1 and never went away.

Re: Djbsort: A new software library for sorting arrays of integers

#9

Post by Cyphase »

MrBuddyCasino wrote: post #3

The 2.5 cycles/byte compared to the 32 cycles/byte that Intel managed pulled off seems like an improbably large improvement over the current state of the art? Is this real?

The cycles/byte for all the sizes listed in the table on the Speed page[0], courtesy of copy-paste and a one-liner in the Python REPL:

  size      cycles/byte (based on median)
  1         6.0
  2         3.375
  4         11.625
  8         9.625
  16        7.984375
  32        7.515625
  64        6.0390625
  128       4.31640625
  256       2.4873046875
  512       2.29443359375
  1024      2.5048828125
  2048      2.77893066406
  4096      3.0791015625
  8192      3.89566040039
  16384     5.23690795898
  32768     6.35472106934
  65536     7.55914306641
  131072    9.23189163208
  262144    10.789557457
  524288    12.4885950089
  1048576   14.6550707817
[0] https://sorting.cr.yp.to/speed.html

Re: Djbsort: A new software library for sorting arrays of integers

#10

Post by throwaway77384 »

banachtarski wrote: post #8
ibuildoss wrote: post #2

That's pretty cool, are there any bindings for e.g. Go out there?

Unrelated to the article I recently learned Go just as a side-interest. I was appalled by how terrible the language is. Usually, language warts aren't apparent until you use it a bit but here annoyances were present on day 1 and never went away.

Care to elaborate? I am also looking into it, so would be interested to hear what the issues are.
Post reply on HN