Djbsort: A new software library for sorting arrays of integers

You need a context switch to use AVX?

That's true, these are always costly though.

Transferring SIMD/FPU regs to/from memory is actually fast - a modest fraction of the typical context switch cost - on modern x86_64 thanks to XSAVE.

> Three of the source code files contain a notice that they are in the public domain:

Making it legally dodgy to dangerous in mainland europe, either way certainly not reliably licensed.

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.

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.

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).

I actually really like the authenticity and humility of DJB including that in the instructions. I think it's likely many people trust his code (and he's certainly written a lot of extremely security sensitive stuff), but of course it's a much better practice to not trust him quite so much.

"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.

It was probably you I heard about it from! Submission upvoted. ;-)

FWIW, I read through each of your links. They don't address cross-compilation at all, or the needs of software packagers.

I can 100% promise you that somebody packaging this library for any Linux distro (or for a Yocto/Buildroot system) would grind their teeth in frustration at everything in the those links.

The solution to having inconsistent packaging paths isn't to introduce _yet another_ packaging path system, but this one specific to djb stuff. It's to use a standard build system with overrideable paths, and not to assume the author knows better than the packager.

Bear in mind that steps 1, 3, 4, 6, and 7 are not related to slashpackage. nrclark has got step #2 wrong, as all that it yields is the current source package version number not a URL and there's no real parsing going on (except for the shell stripping the trailing newline); and xyr step #8 is xyr own invention and not actually in the build instructions as given.

That leaves step #5. What that does is both fairly obvious and documented in the instructions. It tries out a whole bunch of compilers, compiler options, and implementations in turn to see which results in the best code. Ironically, it is probably the sort of thing that autotools might be persuaded to do. But in practice no-one would, or it would be buried under reams of copied-and-pasted cargo cult tests for things that the actual source at hand cannot in fact do without in the first place.

This is of course a long-recognized fly in any let's-just-use-autotools ointment, discussed over many years. (-:

* https://news.ycombinator.com/item?id=5276876

* https://queue.acm.org/detail.cfm?id=2349257

* http://freshmeat.sourceforge.net/articles/stop-the-autoconf-...

* https://news.ycombinator.com/item?id=1499738

* https://news.ycombinator.com/item?id=4407486

Reading those complaints cold, I would suspect DJB to be between 16 and 22 years old; old enough to have seen more than his own system, but young enough to be absolutely certain his off-the-cuff solution is better than any of those other idiots can come up with. It helps to be the smartest person in any room, I guess.

"When oaf was integrated into ``the system,'' it was moved to /usr/bin/oaf, and its files moved to /usr/share/oaf, because FHS doesn't let ``the system'' touch /usr/local. What happened in this case is that oaf didn't find files that were put into /usr/local/share/oaf by another package."

Once upon a time, I worked as a sysadmin for a major university computer science department. We supported a half-dozen or so different architectures. We built a long list of software, including all of the X and Gnu programs, so that our users had the same environment essentially everywhere. Oh, and we all built it to live under /lusr, because our convention started before "/usr/local" was a thing. (The weird looks when you started babbling about "slash-loser" were just a fringe benefit.)

imake was a giant pain in the rear. Autotools were also a giant pain in the rear. But everything else, except in very, very simple cases, was much worse. DJB's software would come under the header of "sorry, not supportable without unreasonable effort."

The most important thing is to put all the compiler flags behind standard variables. This is 80% of what autoconf/automake does. The standard variables for C programs are

  CPPFLAGS = # e.g. -I and -D preprocess options
  CFLAGS = # various ad hoc compiler switches
  LDFLAGS = # e.g. -L options
  LDLIBS = # e.g. -l options
  SOFLAGS = # -shared or -bundle -undefined dynamic_lookup 

(NOTE: SOFLAGS is less standard--i.e. not in GNU style guide or GNU make manual--but perfectly fits the pattern and extremely useful to specify independently. You'll often find a variable like this used, if not the same name. IME SOFLAGS it the most common name.)

Library dependencies should follow a similar pattern:

  LIBFOO_CPPFLAGS = # e.g. -I/usr/local/foo/include
  LIBFOO_CFLAGS =
  LIBFOO_LDFLAGS = # e.g. -L/usr/local/foo/lib
  LIBFOO_LDLIBS = -lfoo

To make it easier to control feature-specific options without overriding all other defaults, you should do likewise for feature groups:

  PIC_CFLAGS = -fPIC
  ...
  PTHREAD_LDLIBS = -lpthread
  ...
  WARN_CFLAGS = -Wall -Wextra

If you want to get really fancy, you can use top-level MY* variables so people can easily append flags without overriding existing variables.

Then for most basic target recipes you can pre-compose all the flags to make your rules simpler:

  ALL_CPPFLAGS = $(PIC_CPPFLAGS) $(LIBFOO_CPPFLAGS) $(WARN_CPPFLAGS) $(CPPFLAGS) $(MYCPPFLAGS)
  ALL_CFLAGS = $(PIC_CFLAGS) $(LIBFOO_CFLAGS) $(WARN_CFLAGS) $(CFLAGS) $(MYCFLAGS)
  ALL_LDFLAGS = $(PIC_LDFLAGS) $(LIBFOO_LDFLAGS) $(WARN_LDFLAGS) $(LDFLAGS) $(MYLDFLAGS)
  ALL_LDLIBS = $(MYLDLIBS) $(LDLIBS) $(LIBFOO_LDLIBS) $(WARN_LDLIBS) $(PTHREAD_LDLIBS)

  .o.c:
    $(CC) $(ALL_CFLAGS) $(ALL_CPPFLAGS) -c -o $@ $<

Because of the ubiquity of GCC and clang, and because of the commonality across most modern Unix platforms (e.g. SOFLAGS will be "-shared" on all BSD- and SysV-derived systems, including Linux, and "-bundle -undefined dynamic_lookup" on macOS), the above will allow people to build your software without modifying the actual Makefile in almost all scenarios. It will certainly make packagers' jobs easier.

For installation you should always use the standard prefixes

  DESTDIR = # temporary root to assist in packaging 
  prefix = /usr/local
  bindir = $(prefix)/bin
  datadir = $(prefix)/share
  includedir = $(prefix)/include
  libdir = $(prefix)/lib
  sysconfdir = $(prefix)/etc

and install targets should be written like

  $(DESTDIR)$(libdir)/libacme.so: libacme.so
    ...

This may seem like alot of boilerplate, but the important thing is that it's very simple and time-tested. Autogenerating just this basic boilerplate is overkill and adds unnecessary indirection and complexity. You can get fancier than this scheme, but avoid the temptation as much as you can unless it's an obvious win--remedies a regular, concrete issue that is actually resulting in significant wasted effort. For complex builds (e.g. multiple targets where flags might not have the same semantics across target rules), consider splitting the build into multiple Makefiles. You can create a convenience wrapper, but at least the sub Makefiles will be reusable by packagers or contributors without having to modify anything directly. It's not ideal but there is no ideal solution. (I once heavily advocated non-recursive make, but these days I'm much more averse to complexity.)

There's no easy answer for Windows, particularly because NMake uses significantly different syntax for some constructs. For really basic builds the above might actually work as long as you stick to NMake-compatible syntax. With the advent of Windows Subsystem for Linux (WSL) you could consider requiring WSL for the build (so you have access to POSIX-compatible shell and Make) and perhaps providing a wrapper Makefile with more convenient defaults for compiling with Visual Studio (which is very much still a command-line driven compiler). Requiring clang-cl might be even easier.

For simple stuff IME autotools and CMake are just overkill.[1] For complex stuff they often won't be sufficient, anyhow.[2] So the important thing is to layer your build so the maximum amount of build code can be reused by somebody with unforeseen needs; and reused in a way that is obvious and transparent so their tweaks can be simple. Stick to convention as much as possible. Even if you don't use autotools, autotools has created de facto conventions wrt build variables that will be intuitive to all packagers. Please don't invent your own naming scheme! (It's annoying when someone uses 'PREFIX' instead of 'prefix'. There's logic to the autotools scheme. Uppercase variable are for [build] flags used in rule recipes, lowercase for [installation] paths used to define rule targets and dependencies. Exceptions like DESTDIR are well-known and few.)

Always be mindful of the needs of people doing embedded work--cross-compiling, complex build flags, etc. But don't bend over backwards. All you really need to do is remove obstructions and the necessity to patch. They're used to writing build wrappers, but patching is a maintenance nightmare and impedes tracking upstream.

Ideally you would support out-of-tree builds, but in reality few packages support this properly (even autotools or CMake projects), and if you're not regularly doing out-of-tree builds your build probably won't work out-of-the-box anyhow. That's why I didn't mention the use of macros like VPATH, top_srcdir, etc, in your rules. Do that at your discretion, but beware of descending down the rabbit hole.

The same thing applies to automatic feature detection--unless you're regularly building on esoteric targets your feature detection is unlikely to work out of the box, and bit rot happens quickly as platforms evolve.[3] Don't put too much effort into this; just make sure it's easy to manually toggle feature availability and that the defaults work on the most common platforms and environments. Maximize benefits, minimize costs, but don't think you can automate everything away.

All those fancy builds people tout are ridiculously brittle in reality. People just don't realize it because they're only using the builds on what are in fact relatively homogenous environments. Most of the effort is wasted, and build complexity (including bespoke build environments) is a big reason why people don't reuse software as much as they could.

[1] Indeed, for simple builds it's not much of a burden to provide and maintain a POSIX build and a Visual Studio project file build.

[2] For CMake this is especially true. For feature detection CMake often requires actually updating your version of CMake. That's a gigantic PITA. Anyhow, most feature detection can be done inline using the preprocessor, or by simply defaulting to being available (this is 2018, not 1988--there's much more commonality today.) And as long as your feature-detection macros are controllable from build-time flags, people can easily work around issues by explicitly toggling availability. Thus, the autotools convention of using "#ifdef FEATURE_FOO" for feature flags is bad advice. Always use boolean flags like "#if FEATURE_FOO", and only define FEATURE_FOO in config.h-like files if not already defined. That allows people to do, e.g., "MYCPPFLAGS=-DFEATURE_FOO=0" to override feature detection as necessary.

[3] Autoconf's feature checking (check the feature, not the version) sounds robust in practice, but you'd be surprised how many ways it can break, or how difficult writing a properly robust feature check is. Plus, especially on Linux people expect a feature to work at run-time if the kernel supports it, regardless of whether glibc had a wrapper at build time or has it at run time. These issues are where you'll spend much of your time, and this can't be automated. You can't foresee all these issues! Focus on making it easy to supplement or work around your build!

I'm a PhD student in theoretical computer science and have an academic interest in this sorter. But his build system is just too much of a pain to deal with voluntarily.

Not to mention that his cpu cycle counting doesn't actually seem to compile on Linux, which doesn't have sysctlbyname? Or maybe build errors are expected behaviour?

As a user, I'm super happy with `./configure`, that works the same way across all applications using it, and has been for the past 20 years.

You don't want to look at the actual script, but as a user, it is very convenient. I don't have to read installation guides to know how to change compilation options, compilers, cross-compile, installation paths, run the test suite, etc.

As you see in the code this is linux only: CLOCK_MONOTONIC, HW_CPUSPEED, -soname, -rpath, linux/perf_events.h,

Even on linux it would fail: sort.c:386:21: error: always_inline function '_mm256_loadu_si256' requires target feature 'sse4.2', but would be inlined into function 'djbsort_int32' that is compiled without support for 'sse4.2'

-march=native or -msse4.2 would be needed.

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 about, and take advantage of the directory control and compiler control aspects.

If you've never actually worked with Autotools (which you just said you haven't), I'd encourage you to actually try it out. It's not as bad as you think.

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.

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.

"He's also been putting out a tremendous volume of work in multiple categories. I bet he'd rather work on this stuff than on user-friendly build systems."

I don't know about that part...a halfway normal build process would be considerably less work to set up than this monstrosity.

To clarify for anyone who doubts autotools has problems - it is true that the documentation mentions cross compiling options, but it appears that the vast majority of tests in use today do not actually use these values (host/target arch, etc).

Some users recommend compiling with qemu-user to avoid fixing the tests, but besides being very slow, that methodology will still generate garbage. What is the point of running feature detection code on a desktop that will be used to configure code compiled to run on e.g. a small ARM system?

The fix is to explicitly set configuration parameters or, even better, to detect features at runtime. However if you try to contact any given project using autotools to help solve these configuration problems you will likely receive "that's not our problem" and no help from the maintainers.

Autotools is in practice less work for me than alternatives, at least while using a FOSS operating system. On Windows CMake is very well developed but handling dependencies is always a chore.

"Configure often detects features by compiling a binary and executing it" — I am not sure, where this impression comes from. Autotools as whole have excellent cross-compilation support. Autoconf has feature-detection routines, checking for presence of headers, exported symbols and pkg-config files. None of those trigger "execute the binary" part when cross-compiling. In addition, custom-written host-side checks can easily be skipped when cross-compiling (either by code of check itself or by user via environent-variable overrides). Do you you know of any build system, that handles this better?

Cmake and several other buildsystems either don't support cross-compilation at all (because their primary audience is Windows) or use pkg-config only. Few others are nightmarish parody of autotools with much worse support. Most don't have ounce of autotools features.

I know many projects, that offer horrible autotools "support": for example, glib2 autotools scripts can't be cross-compiled to Android without ample application of hacks. But those issues are caused by incompetence and lack of testing, not some innate fault of Autotools. When such projects migrate to something else, their cross-compilation process becomes WORSE.