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

21–30 of 158 posts

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

#21

Post by jwilk »

robin_reala wrote: post #5

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

This is bizarre. Why not just give users link to the source?

https://sorting.cr.yp.to/djbsort-20180710.tar.gz

And it's certainly not about good security practices:

* The page teaches users to paste stuff copied from web into a terminal, whereas many terminals are still vulnerable to this: https://thejh.net/misc/website-terminal-copy-paste

* The page teaches users to use su to lower privileges, whereas many (most?) su implementations are vulnerable to tty hijacking.

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

#23

Post by whazor »

eggie wrote: post #22

It's nice when things fit in RAM. But very often they don't. When you want to sort arbitrary-sized binary records on disk look no further than bsort: https://github.com/pelotoncycle/bsort

When sorting on disk, there are actually limitations in sorting linear time. Has to do with being able to read blocks in memory and write them back to disk. As everything is in blocks, you are limited to O(n/B log(n/B)) with B being the amount of items per block. For more speed, a merge sort that keeps in mind the block size works quite well. Search for external sorting.

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

#24

Post by jwr »

yoklov wrote: post #13

The problem with AVX2 accelerated code (and much of AVX) is that unless you have a lot of it to run you end up with a substantial speed hit that comes from the cost of switching to a different power bin (which often takes 1 or 2ms!) and then running at a lower clock speed. This often still ends up being an improvement over scalar code (at the cost of higher power usage), but for occasional workloads that don't need t…

See also the excellent writeup at: https://gist.github.com/rygorous/32bc3ea8301dba09358fd2c64e0...

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

#25

Post by ben0x539 »

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.

Some of the stuff that makes it work is unfortunately apparent later than the warts. Try to think of it as a domain-specific language for implementing simple http endpoints. ¯\_(ツ)_/¯

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

#26

Post by tazjin »

throwaway77384 wrote: post #10
banachtarski wrote: post #8

Earlier quoted context omitted.

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.

There's an indexed list of posts about Go's flaws here: https://github.com/ksimka/go-is-not-good

In my opinion, don't use Go at all if you can avoid it - it may be acceptable for a tiny CLI project but anything of significant complexity needs a language that can scale.

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

#27

Post by thenrich99 »

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.

Go is a language that's easy to use, but a challenge for beginners to use well, especially if you try to force [insert another language] constructs into it.

I see programmers that are new to Go often struggle with trying to apply their object-oriented mindset into a language that's not object-oriented and run into trouble, complain about the language, and call it rubbish. Or, focus on the lack of generics and other part of the language they don't like (e.g. slice manipulation).

Go is certainly far from perfect but after spending the better part of 7 years with it, it's usually the first tool I reach for.

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

#28

Post by thenrich99 »

tazjin wrote: post #26
throwaway77384 wrote: post #10

Earlier quoted context omitted.

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

There's an indexed list of posts about Go's flaws here: https://github.com/ksimka/go-is-not-good In my opinion, don't use Go at all if you can avoid it - it may be acceptable for a tiny CLI project but anything of significant complexity needs a language that can scale.

What does it mean to have a "language that can scale"?

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

#29

Post by exDM69 »

Ono-Sendai wrote: post #19
SiempreViernes wrote: post #18

Earlier quoted context omitted.

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.

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.

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.

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

#30

Post by Sean1708 »

thenrich99 wrote: post #28
tazjin wrote: post #26

Earlier quoted context omitted.

There's an indexed list of posts about Go's flaws here: https://github.com/ksimka/go-is-not-good In my opinion, don't use Go at all if you can avoid it - it may be acceptable for a tiny CLI project but anything of significant complexity needs a language that can scale.

What does it mean to have a "language that can scale"?

Usually when people say that they mean that it works well for small projects and small teams, but doesn't work as well for big projects or big teams.
Post reply on HN