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

91–100 of 158 posts

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

#91

Post by masklinn »

Tepix wrote: post #34
pushcx wrote: post #31

The library doesn't have a license on the site or in the tarball. From djb's previous writing and software, he probably intends it to be license-free software, which is an uncommon situation worth investigating before use: https://en.wikipedia.org/wiki/License-free_software (Trying to describe this neutrally because I've seen enough bickering about it over the last ~20 years and don't have strong feelings about it.)

Three of the source code files contain a notice that they are in the public domain: * cpucycles/mips/cpucycles.c * cpucycles/cortex_vct/cpucycles.c * cpucycles/cortex/cpucycles.c Regarding the missing license: I guess if you download the software from his website you are not allowed to distribute it yourself. Is that correct?

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

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

#92

Post by blattimwind »

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

Earlier quoted context omitted.

1. You're assuming the software is intended to be deployed 2. Writing anything sane with autotools or CMakes is an exercise in frustration that borders on torture. Not to mention how either of these systems chafes on one's sense of aesthetics. 3. I've installed a few of djb's package over the years. While indeed non standard, unlike either of the solutions you've mentioned, djb's stuff: a) works b) is usually very si…

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…

> Why would somebody release software that they didn't want to see used?

With djb: There is literally an independent project around that was founded just to have a distributable version of NaCl.

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

#93

Post by jeffreyrogers »

puzzle wrote: post #78
jeffreyrogers wrote: post #70

Earlier quoted context omitted.

You need a context switch to use AVX?

No, unless you have a special setup where one process on the whole machine can use AVX. That might make sense for special, controlled environments. What I meant is that there are more registers to shuffle around at context switch time, when multiple processes use the extensions.

Ah got it, thanks.

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

#94

Post by yoklov »

puzzle wrote: post #58
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…

You also have penalties from context switches, although you can reduce their impact by performing them in a lazy fashion. AVX512 is even worse, of course.

That's true, these are always costly though.

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

#95

Post by AstralStorm »

herf wrote: post #64
Ono-Sendai wrote: post #7

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…

My single-threaded floating point sort is also twice as fast as djbsort: 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.

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.

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

#96

Post by aseipp »

geocar wrote: post #84
nrclark wrote: post #74

Earlier quoted context omitted.

Let's say I'm writing firmware for a TV. Why wouldn't I want to use the chip's CPU to the fullest extent at runtime? That doesn't mean I want to compile my TV firmware _on_ the TV.

> Why wouldn't I want to use the chip's CPU to the fullest extent at runtime? Because you'd rather use GNU autoconf? If you wanted the fastest possible performance, you'd try each algorithm, profile them, then select the one that works best. This build process can do that automatically. GNU autoconf cannot. You can tell autoconf which to use, but the package maintainer can't be trusted to do this. Then the user will…

> If you wanted the fastest possible performance, you'd try each algorithm, profile them, then select the one that works best. This build process can do that automatically. GNU autoconf cannot.

Except doing it at build time is a terrible idea anyway. That is because the set of CPUs it will be used on is actually unknown, unless it's literally not meant for anyone else to use that compiled object. But that's not how people actually develop at all. They distribute the software objects and users link against it on their CPUs, which the original build system cannot possibly have knowledge of.

Requiring AVX2 or whatever by default really has nothing to do with this. High speed software that's actually usable for developers and users selects appropriate algorithms at runtime based on the characteristics of the actual machine they run on (for example, Ryzen vs Skylake, which have different throughput and cycle characteristics.) This is the only meaningful way to do it unless you literally only care about ever deploying to one machine, or you just don't give a shit about usability.

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

#97

Post by Panino »

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 around with the internals of his software, hurting security or reliability, and then blaming the software rather than the modifications. So his build systems were, I think, designed to lead to the result he wanted, where software behaved and was administered in the same way on various platforms.

In the mid-2000s he re-licensed existing software as public domain and began publishing all new code as public domain as well. Around this time, build systems began to get more wonky. Also, his public work that garnered the most attention shifted away from software toward cryptography. He did some attacks on existing crypto and authored Curve25519, Salsa20, etc.

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.

So given these points, I think the explanation for his unfriendly build systems is

  A) a very strong aversion to people modifying his stuff where he gets blamed if modifications do harm;
  B) a shift away from software development, where people generally care more about build systems anyway;
  C) a huge level of productivity which results in very atypical Pareto principle choices/tradeoffs;
  D) his public-domain licensing.
Given these 4 points, I think DJB is unwilling to take time away from crypto and other work and put it into build systems he doesn't enjoy that will take more time upfront and more babysitting down the road. Fewer people will package it, but the software is public domain and competent people can just add their own build system. This squares with his available time and interests.

So, I don't like his build systems either, but I think I understand where they come from.

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

#98

Post by nrclark »

geocar wrote: post #84
nrclark wrote: post #74

Earlier quoted context omitted.

Let's say I'm writing firmware for a TV. Why wouldn't I want to use the chip's CPU to the fullest extent at runtime? That doesn't mean I want to compile my TV firmware _on_ the TV.

> Why wouldn't I want to use the chip's CPU to the fullest extent at runtime? Because you'd rather use GNU autoconf? If you wanted the fastest possible performance, you'd try each algorithm, profile them, then select the one that works best. This build process can do that automatically. GNU autoconf cannot. You can tell autoconf which to use, but the package maintainer can't be trusted to do this. Then the user will…

You could absolutely write an Autoconf script that runs those tests by default, but has overrideable behavior. You can make custom Autoconf macros to detect whatever arbitrary thing you want. At the core, an Autoconf macro is just a chunk of shell script that sets some environment variables with the result.

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

#100

Post by rurban »

mwcampbell wrote: post #66
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…

There's also a world beyond Unix. Prof. Bernstein may not be interested in targeting Windows. But for library developers in general, I'd recommend CMake. Microsoft has adopted CMake as its standard cross-platform C/C++ build system, and has built a cross-platform library package manager [1] on top of it. [1]: https://github.com/Microsoft/vcpkg

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.

Post reply on HN