Djbsort: A new software library for sorting arrays of integers • Hacker News Board

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

#131

Post by masklinn » Wed, Jul 11, 2018, 9:02 PM UTC

lisper wrote: post #124

masklinn wrote: post #91

Earlier quoted context omitted.

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

I hear people raise this concern a lot, but I think it is without foundation. If something is in the public domain in the U.S. then anyone can use it for any purpose, including releasing it under whatever license they want. Of course, any constraints imposed by that license will be unenforceable since any user of the software can claim to be using it under the terms of some other license or, of course, as part of the…

> If something is in the public domain in the U.S. then anyone can use it for any purpose, including releasing it under whatever license they want

In the US. Public domain dedications have no legal standing in most of mainland Europe's IP regimes. A public domain dedication is the equivalent of no license at all.

And because a public domain dedication has no legal standing, a third-party slapping a license on the code does not make it legally licensed as far as european IP courts are concerned, they don't have that right, their "license" is worth as much as you deciding to license Windows under GPLv3.

> But if you think you need it licensed, you can have it licensed.

Unless djb offers to provide a fallback license (which incidentally is exactly what CC0 does and why it's legally sensible and valid[0]), then no, you can't "have it licensed".

[0] https://rd-alliance.org/sites/default/files/cc0-analysis-kre...

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

#132

Post by mcguire » Wed, Jul 11, 2018, 9:05 PM UTC

geocar wrote: post #46

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…

> Why do I need ... assumptions about system paths? > what is the rationale for a build flow that involves: It solves problems. https://cr.yp.to/compatibility.html https://cr.yp.to/slashpackage/studies.html https://cr.yp.to/slashpackage/finding.html https://cr.yp.to/slashpackage/sharability.html > Would it really be that much harder to give us a git repo and a ./configure or a CMakeLists.txt? Yes.

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

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

#133

Post by masklinn » Wed, Jul 11, 2018, 9:06 PM UTC

lisper wrote: post #127

johannes1234321 wrote: post #126

Earlier quoted context omitted.

Anybody under U.S. jurisdiction can follow U.S. law. However if me and my company and everything is in Europe and I use/redistribute the code in Europe I must follow applicable European law. If that doesn't accept that form of public domain the author (rights owner) could sue me and it were upon the judge, who sensible they are. (This is mostly theoretical - if the author decides to put it in public domain per U.S. l…

That was a completely different situation. In that case, the material was still under copyright in Germany. In this case, the material has been placed in the PD by the original author and so no one in the world can possibly have any legal claim on it. But if this really concerns you, I would be happy to provide you -- or anyone else -- with a licensed copy of any of DJB's code for a modest processing fee.

> In that case, the material was still under copyright in Germany.

Which is exactly the case of djb's work here.

> In this case, the material has been placed in the PD by the original author and so no one in the world can possibly have any legal claim on it.

Wrong. djb and any possible heir of his does, because you can't place things in the public domain in mainland europe.

> But if this really concerns you, I would be happy to provide you -- or anyone else -- with a licensed copy of any of DJB's code for a modest processing fee.

Unless djb specifically gave you license to do so, your "licensed copy" is worth exactly as much as the original public domain dedication is. As far as european law is concerned, you have no rights to the work, and thus certainly don't have the rights to relicense it.

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

#134

Post by masklinn » Wed, Jul 11, 2018, 9:14 PM UTC

johannes1234321 wrote: post #126

lisper wrote: post #124

Earlier quoted context omitted.

I hear people raise this concern a lot, but I think it is without foundation. If something is in the public domain in the U.S. then anyone can use it for any purpose, including releasing it under whatever license they want. Of course, any constraints imposed by that license will be unenforceable since any user of the software can claim to be using it under the terms of some other license or, of course, as part of the…

Anybody under U.S. jurisdiction can follow U.S. law. However if me and my company and everything is in Europe and I use/redistribute the code in Europe I must follow applicable European law. If that doesn't accept that form of public domain the author (rights owner) could sue me and it were upon the judge, who sensible they are. (This is mostly theoretical - if the author decides to put it in public domain per U.S. l…

> If that doesn't accept that form of public domain the author (rights owner) could sue me and it were upon the judge, who sensible they are. (This is mostly theoretical - if the author decides to put it in public domain per U.S. law they most likely don't want to restrict to U.S.)

Generally speaking, the risk is less the author themselves (though they could always do an about-face for whatever reason, it's hardly unprecedented[0]) and more eventual heirs of them who could always decide to cash in.

[0] https://en.wikipedia.org/wiki/Alexander_Grothendieck#Retirem...

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

#135

Post by [deleted] » Wed, Jul 11, 2018, 9:29 PM UTC

mcguire wrote: post #129

viraptor wrote: post #37

Earlier quoted context omitted.

Authenticity, sure. Humility - not after his approach to the students issue in recent years where he was more interested in being correct then helping people :-(

" ...where he was more interested in being correct then helping people " That does describe him pretty well.

[deleted]

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

#136

Post by carapace » Wed, Jul 11, 2018, 9:32 PM UTC

KirinDave wrote: post #105

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.

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

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

#137

Post by [deleted] » Wed, Jul 11, 2018, 9:40 PM UTC

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.

[deleted]

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

#138

Post by rphlx » Wed, Jul 11, 2018, 9:40 PM UTC

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.

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.

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

#139

Post by rphlx » Wed, Jul 11, 2018, 9:47 PM UTC

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…

FWIW Haswell - on which this was benchmarked - does not downclock on AVX2; it just boosts vcore and thermal throttles if the cooling solution can't keep the die below ~100C (which of course, the crappy TIM plus bundled desktop heatsink have essentially zero chance of doing with many extended workloads). To preclude thermal throttling the auto-downclock-on-AVX2 was added later, I think for Skylake.

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

#140

Post by rphlx » Wed, Jul 11, 2018, 9:57 PM UTC

bluetech wrote: post #65

I liked this bit, using the fastest compiler for each primitive: > ./do tries a list of compilers in compilers/c, keeping the fastest working implementation of each primitive. Before running ./do you can edit compilers/c to adjust compiler options or to try additional compilers.

It is sadly necessary; 30%+ performance regressions from, say, gcc 4 to gcc 6 are not uncommon w/ vector intrinsics.