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

101–110 of 158 posts

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

#101

Post by nrclark »

Panino wrote: post #97
nrclark wrote: post #41

My job involves a lot of packaging/cross-compilation, and djb's libraries always seem consistently hostile to the lowly packaging engineer. Would it really be all that much work to package in autotools or CMake? Why do I need his special-snowflake build system with its hard-coded assumptions about system paths? I know that the cult of djb will downvote this into oblivion, but seriously, what is the rationale for a bu…

I've been using DJB's stuff for ~20 years and I don't like his recent build systems either. Without defending it, I'd just like to offer a theory on why he packages things the way he does. Back in the day, his build processes were atypical but still much more "normal" than now. He also released his software without licenses. During this time of heavy software development, DJB was concerned about people screwing aroun…

Appreciate the response! Interesting to read.

The Libsodium guys wound up doing exactly what you're suggesting, because of the impossibility of trying to package NaCl as-is.

So they essentially had to re-do/duplicate all of his build work just to make it packageable. And now there are two competing implementations (three if you count tweetnacl). And a bit of a confusing mess in the documentation department.

It seems a little selfish for djb to take the "works on my machine" attitude, because it means that a bunch of other people have to reverse-engineer all that stuff just to make it portable.

But I guess OTOH it's his software, so it's his choice. And maybe he doesn't care whether people choose to use his stuff or not, as long as he's publishing.

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

#102

Post by textmode »

jwilk wrote: post #21
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…

"The page teaches users to use su to lower privileges ..."

In the example, he could have used his own utilities for dropping privileges (setuidgid, envuidgid from daemontools).

If I am not mistaken, busybox includes their own copies of setuidgid and envuidgid, meaning it is found in myriad Linux distributions. I believe OpenBSD has their own program for dropping privileges. Maybe there are others on other OS.

Instead he picked a ubiquitous choice for the example, su.

It is interesting to see someone express disdain for the version.txt idea. I had the opposite reaction. To me, it is beautiful in its simplicity.

As a user I like the idea of accessing a tiny text file, version.txt, similar to robots.txt, etc., that contains only a version number and letting the user insert the number into an otherwise stable URL.

This is currently how it works for libpqcrypto.

https://libpqcrypto.org/install.html

I would actually be pleased to see this become a "standard" way of keeping audiences up to date on what software versions exist.

By simplifying "updates" in this way, any user can visit the version.txt page or write scripts that retrieve version.txt to check for updates, in the same way any user can visit/retrieve robots.txt to check for crawl delay times, etc.

It is not necessary to "copy and paste" from web pages. Save the "installation" page containing the stable URL as text, open it in an editor, insert the desired version number into the stable URL.

Save the file. Repeat when version number changes, appending to the file.

I like to keep a small text file containing URLs to all versions so I can easily retrieve them again at any time.

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

#103

Post by nrclark »

blattimwind wrote: post #88
dilap wrote: post #81

Earlier quoted context omitted.

I don't think most software needs to care about these weird exotic systems anymore (MINIX? seriously?). Maybe if that's really a goal of your software, it's reasonable to use autotools.

I think the most annoying issue is that for larger software with lots of options and dependencies, running configure just takes a long time (especially before SSDs where a thing), and will terminate with exactly one error. Getting past ./configure could take literally all day.

Agreed that this is an annoyance. Autoconf-generated configure scripts are definitely slow, mostly because they test a ton of things that probably don't still need to be tested.

The overall system still provides a ton of value and a lot of relevant tests in addition to the not-so-relevant ones. After years of writing increasingly complex Makefiles to test for this-and-that, Autoconf was a breath of fresh air for me when I made the switch a couple of years ago (even with all of its crustiness).

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

#104

Post by throwanem »

ur-whale wrote: post #79
nrclark wrote: post #76

Earlier quoted context omitted.

Why would somebody release software that they didn't want to see used? To your other point, Autotools is little crusty for sure. It's Yet Another Language to learn (and so is CMake), but it's really not as bad as people make it out to be. There are many thousands of examples in the wild, good and bad. Yes, Autoconf tests for a bunch of stupid things that don't matter. But so what? You can add the tests you _do_ care…

I have tried working with autotools. Many times. I guess it's down to mindset: some people don't mind working on top of a pile of manure and don't really see what the big deal is. Others just cant.

> the autotools steaming monstrosity which in 20 years of using opensource software I've never dared to touch

> I have tried working with autotools. Many times.

Well - which is it?

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

#105

Post by KirinDave »

carapace wrote: post #72

(Kind of a tangent, but if you're into sorting check out: "Generic top-down discrimination for sorting and partitioning in linear time" https://www.cambridge.org/core/journals/journal-of-functiona... Abstract: "We introduce the notion of discrimination as a generalization of both sorting and partitioning, and show that discriminators (discrimination functions) can be defined generically, by structural recursion on re…

I've tried so many times to frontpage that, but I've failed. Maybe we should have another go?

Nothing in djbsort's approach is inapplicable to another sorting algorithm, so maybe we can hope for better primitive support for discrimination sort implementations (or at least american flag sort implementations). I seem to recall reading that discrimination sorts are inherently content-independent.

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

#106

Post by [deleted] »

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…

[deleted]

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

#107

Post by wruza »

blattimwind wrote: post #88
dilap wrote: post #81

Earlier quoted context omitted.

I don't think most software needs to care about these weird exotic systems anymore (MINIX? seriously?). Maybe if that's really a goal of your software, it's reasonable to use autotools.

I think the most annoying issue is that for larger software with lots of options and dependencies, running configure just takes a long time (especially before SSDs where a thing), and will terminate with exactly one error. Getting past ./configure could take literally all day.

This made me think back then that someone could fix autotools by caching tests results for a specific system. Why not me? So I opened its sources... and closed it. No positive outcome could recapture the time required to even understand what’s going on in these scripts.

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

#108

Post by JdeBP »

Panino wrote: post #97
nrclark wrote: post #41

My job involves a lot of packaging/cross-compilation, and djb's libraries always seem consistently hostile to the lowly packaging engineer. Would it really be all that much work to package in autotools or CMake? Why do I need his special-snowflake build system with its hard-coded assumptions about system paths? I know that the cult of djb will downvote this into oblivion, but seriously, what is the rationale for a bu…

I've been using DJB's stuff for ~20 years and I don't like his recent build systems either. Without defending it, I'd just like to offer a theory on why he packages things the way he does. Back in the day, his build processes were atypical but still much more "normal" than now. He also released his software without licenses. During this time of heavy software development, DJB was concerned about people screwing aroun…

The underpinnings of that argument are flawed. You're accepting the premise that there were relatively "normal" build processes "back in the day" and "abnormal" ones now. This is not in fact the truth of the matter at all.

M. Bernstein's own build system was redo. But he never actually published a redo tool. Other people did that. There are traces of a precursor to redo in one of his packages. But even they were not the actual build system for it as released to the public. Again, it was other people who took them and fleshed them out into a working build system. The slashpackage system, similarly, only existed in (another) one of his packages. And again, it was other people who extended it to other packages.

* http://jdebp.info./FGA/introduction-to-redo.html

* http://jdebp.info./FGA/slashpackage.html

* http://jdebp.info./Softwares/djbwares/

The reality is that the build system evident in djbsort is not a sudden inconsistency. The various packages over the years are all inconsistent. One can in fact derive from them a timeline both of development of ways of building packages and evolution of the various "DJB libraries". But they are all snapshots of these processes at different points. They aren't a coherent single system across multiple packages. I, Paul Jarc, and others had to make that part. (-:

So do not deduce that there's been a change. Deduce, rather, that build systems have always been a lower priority and an unfinished loose end. As such, this is nothing to do with the announcement at Sage Days 6 and the like, nor to do with people "screwing around" as you put it. Indeed, the clear motivations of redo expressed in M. Bernstein's own writings on the subject have nothing to do with either copyright or preventing modifications to packages, and everything to do with problems of make and indeed autotools. Observe the motivations of "honest" dependencies from the build instruction files themselves, from the command-line tools and their options, and from things like the absence of header files.

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

#109

Post by ur-whale »

southern_cross wrote: post #82

I haven't read the algorithm here yet nor all of the comments, so this may have already been covered, but in many cases when it comes to sorting integers and such you don't really need to sort them at all - you just need to count them.

Yeah, except that when the integers are very large, that tends to fail. Also, as pointed out by many others, the point of this work is to sort in constant time to avoid side-channel attacks. I doubt the histogram sort (which I think you're referring to) has this property.

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

#110

Post by tinus_hn »

dilap wrote: post #81
rkeene2 wrote: post #75

Earlier quoted context omitted.

Simple Makefiles almost never work for portable software that needs to interface with a system. There is a reason GNU autoconf was created -- it solves a real problem. Different kinds of systems are different in a LOT of ways. Almost all of these ways need to be determined at compile-time and without testing for those ways, there is no good way to do this. The older way (before GNU autoconf) that tools like "xmkmf" u…

I don't think most software needs to care about these weird exotic systems anymore (MINIX? seriously?). Maybe if that's really a goal of your software, it's reasonable to use autotools.

Minix happens to be one of the most used operating systems because it turns out Intels Management Engine, the secret computer inside your processor, runs Minix.
Post reply on HN