15 ms·

Djbsort: A new software library for sorting arrays of integers

284 points by xmmrm 8y ago

ibuildoss 8y ago
That's pretty cool, are there any bindings for e.g. Go out there?
- banachtarski 8y ago
  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.
  - throwaway77384 8y ago
    Care to elaborate? I am also looking into it, so would be interested to hear what the issues are.
    - tazjin 8y ago
      There's an indexed list of posts about Go's flaws here: https://github.com/ksimka/go-is-not-good 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.
      - thenrich99 8y ago
        What does it mean to have a "language that can scale"?
        Sean1708 8y ago
        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.
      - w8rbt 8y ago
        That's very odd. Go was purposefully designed to scale and be used by 1000s of engineers collaborating on a project. https://www.quora.com/Will-the-Golang-code-become-unmaintainable-for-large-code-bases https://www.quora.com/Will-the-Golang-code-become-unmaintain...
        tazjin 8y ago
        The type of codebase scaling Google does is very different from other companies. They have huge numbers of junior developers right out of university (those that Rob Pike, one of the main authors of Go, likes to claim aren't good enough to learn advanced concepts) and their coding style is not focused on correctness and simple implementations - do something, do a lot of it, write a lot of tests. For companies that aren't the size of Google, that don't work the same way (monorepos etc.), and that simply don't have the same set of resources available it will often end up being much easier to use a language that either prevents flaws (via a strong type system, like in Haskell or Rust, which Go does not have) or gracefully handles flaws (via an error handling strategy, like in Erlang or Elixir, which Go does not have).
        w8rbt 8y ago
        Go is strongly typed. https://en.wikipedia.org/wiki/Comparison_of_programming_languages_by_type_system https://en.wikipedia.org/wiki/Comparison_of_programming_lang... It also has an error checking system that is very simple and easy to use.
        tazjin 8y ago
        Go is statically typed (this means that the compiler performs its checks at compile time and hard-fails the compilation process in the presence of type errors), but there is no single definition of what "strong" means. Programming language theory is a field that is in development and notions of "strong" type systems that were valid in the 80s (in which Go certainly would have been considered strongly typed) are no longer relevant. The list you linked seems to cite the Go website itself as the source, by the way. At the very least a modern language that wants to claim to have a strong type system should provide user-defined sum types, exhaustiveness checking and parametric polymorphism. Go has none of those. When it comes to error handling, Go's "concept" of it is that "there may be a thing that can be turned into a string, in which case there was probably an error, but it's up to the developer to check - we won't help you". You may as well just use C then. There is nothing to short-circuit failed computations, check whether errors have in fact been handled, restart / terminate computations gracefully and so on. It's all manual labour that the developers need to remember and boilerplate over and over again. I would recommend you to spend some time with the languages that are "above Blub"[1] (ctrl+f "the blub paradox") - good candidates for learning some modern PLT concepts are Haskell[2], Rust[3] and Erlang[4]. Even if you don't end up using those languages in your professional life, knowing the concepts they introduce will improve your code in "Blub-languages" (Go, Java, etc.), too. [1]: http://www.paulgraham.com/avg.html http://www.paulgraham.com/avg.html [2]: http://haskellbook.com/ http://haskellbook.com/ [3]: https://doc.rust-lang.org/book/ https://doc.rust-lang.org/book/ [4]: https://learnyousomeerlang.com/ https://learnyousomeerlang.com/
      - thenrich99 8y ago
        I'd hardly call Kubernetes, Docker daemon and tooling, etcd, CockroachDB, geth, and nsq tiny CLI projects. If anyone has any reservations about learning Go, don't judge the language based on a list of flaws written by some programmers who used it for a few months, became frustrated, and wrote a blog post. Go has tradeoffs just like any other language and plenty of programmers leverage it for its positives: https://github.com/avelino/awesome-go https://github.com/avelino/awesome-go
  - ben0x539 8y ago
    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. ¯\_(ツ)_/¯
    - josteink 8y ago
      > Try to think of it as a domain-specific language for implementing simple http endpoints. But to that type-safe and well, you probably want Generics.
  - thenrich99 8y ago
    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.
    - jerf 8y ago
      "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." Strongly agreed. There's a lot of languages out there with very rich feature sets, and the way you get jobs done is to go find the right feature you need for your current problem. With Go, you need to learn the language and extract every last drop out of every language feature. This is exacerbated by the fact that the feature set isn't what people expect, e.g., object composition is not what they are used to, and while interfaces are simple there's still some art to using them properly. Despite the vast, vast distance between Go and Haskell on the general-purpose programming language landscape, I found my experiences in Haskell to be quite useful in Go, because while they were specifically inapplicable to an imperative language, the general practice I got from Haskell of taking a bizarre set of programming tools and learning how to make sensible programs out of them even so was quite useful. (It isn't necessarily the first language I reach for for personal tasks, but it is a superb professional programming language, offering a nearly-unique blend of the ability to get the job done you usually need to do for a wide variety of standard programming tasks (but not all!) while resulting in source code that is still comprehensible to almost every programmer. It isn't my favorite overall, but it's the best professional choice of language I have in my belt, which is often precisely because it does not permit me to indulge in flights of clever fancy that solves a problem in 25 impenetrable-to-the-next-guy lines of code. I know a lot of people may not love to hear that, but it's a factor you really have to consider when you are being paid to solve problems.)
  - jy3 8y ago
    It's kinda hilarious to see that as more and more successful projects and companies use Go in their stacks, the number of comments like these increases in HN.
    - vinceguidry 8y ago
      Stack adoption is orthogonal to maturity or ease of use. Recent experiences have indicated to me that the main factor in which stack a company uses is basically the whim of whatever developer was tasked with the initial project creation. Nobody's going to tell him no and there's not going to be significant discussion about the merits and even if there was, there's no best practices to lean on to make the decision rely on anything other than pure emotion.
    - aidenn0 8y ago
      "There are only two kinds of languages: the ones people complain about and the ones nobody uses." - Bjarne Stroustrup
    - wnoise 8y ago
      Stack adoption makes people have to actually use them, which then gives them something to complain about (whereas before they could just ignore something not to their taste).
MrBuddyCasino 8y ago
The 2.5 cycles/byte compared to the 32 cycles/byte that Intel managed pulled off seems like an improbably large improvement over the current state of the art? Is this real?
- Ono-Sendai 8y ago
  Well, that's for a very small and particular size. (1024 elements) Intel's library might have more overhead at that size.
- bdukic 8y ago
  My guess is that the "catch" comes in the form of the list of limitations.
- Cyphase 8y ago
  The cycles/byte for all the sizes listed in the table on the Speed page[0], courtesy of copy-paste and a one-liner in the Python REPL: size cycles/byte (based on median) 1 6.0 2 3.375 4 11.625 8 9.625 16 7.984375 32 7.515625 64 6.0390625 128 4.31640625 256 2.4873046875 512 2.29443359375 1024 2.5048828125 2048 2.77893066406 4096 3.0791015625 8192 3.89566040039 16384 5.23690795898 32768 6.35472106934 65536 7.55914306641 131072 9.23189163208 262144 10.789557457 524288 12.4885950089 1048576 14.6550707817 [0] https://sorting.cr.yp.to/speed.html https://sorting.cr.yp.to/speed.html
robin_reala 8y ago
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 https://sorting.cr.yp.to/install.html
- VMG 8y ago
  I thought this guy was joking > djb presents djbsort, a constant-time djbsolution to a djbproblem you probably don't have. To install, just unpack djbsort.djb and run the ./djb script. Make sure you have djbtools installed first https://twitter.com/bascule/status/1016904259848192000 https://twitter.com/bascule/status/1016904259848192000
- F30 8y ago
  Yes, presumably to run the build as a user which is as unprivileged as possible. Which is a reasonable idea, though it might seem paranoid in today's `curl | sudo sh` world.
  - hawkice 8y ago
    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.
    - judofyr 8y ago
      > humility of DJB Really? This is software where the author named it after himself, claims that it holds a new speed record with no comparisons benchmarks (just references a single number from a paper in 2015), uses the word "easily" FOUR times in the limitation-section without any links or explanations, and doesn't reference any other libraries/resources/software/solutions.
      - 8y ago
Ono-Sendai 8y ago
The median sort time for sorting 1048576 elements wth djbsort is 61467822 cycles: https://sorting.cr.yp.to/speed.html 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 http://forwardscattering.org/post/34 A serial radix sort should still be similar or faster to djbsort.
- SiempreViernes 8y ago
  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.
  - Ono-Sendai 8y ago
    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.
    - exDM69 8y ago
      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.
      - Veedrac 8y ago
        It's a sorting network, which means it only uses conditional swaps in a fixed pattern, which can be made constant time.
yoklov 8y ago
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 to do multiple milliseconds of AVX instructions you tend to have better results from 4-wide vectors, which don't have this cost.
- jwr 8y ago
  See also the excellent writeup at: https://gist.github.com/rygorous/32bc3ea8301dba09358fd2c64e02d774 https://gist.github.com/rygorous/32bc3ea8301dba09358fd2c64e0...
- stochastic_monk 8y ago
  So in a sense, using wider vectors should be done at times when you’re certain to need heavy lifting, much like a GPU, but at a smaller timescale. I should update my vectorization library so that it doesn’t simply use the widest possible.
- puzzle 8y ago
  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.
  - jeffreyrogers 8y ago
    You need a context switch to use AVX?
    - puzzle 8y ago
      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.
lixtra 8y ago
The main feature of the algorithm is to sort fast in constant time (for fixed n) for cryptographic purposes [0]. [0] https://ntruprime.cr.yp.to/ntruprime-20170816.pdf https://ntruprime.cr.yp.to/ntruprime-20170816.pdf P. 48
atesti 8y ago
Direct download link (if you don't want to run the script) https://sorting.cr.yp.to/djbsort-20180710.tar.gz https://sorting.cr.yp.to/djbsort-20180710.tar.gz
eggie 8y ago
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 https://github.com/pelotoncycle/bsort
- whazor 8y ago
  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.
pushcx 8y ago
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 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.)
- Tepix 8y ago
  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?
  - masklinn 8y ago
    > 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.
    - lisper 8y ago
      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 public domain. But if you think you need it licensed, you can have it licensed.
      - johannes1234321 8y ago
        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. law they most likely don't want to restrict to U.S.) For an example see the recent case about project Gutenberg https://news.ycombinator.com/item?id=16511038 https://news.ycombinator.com/item?id=16511038
nrclark 8y ago
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 build flow that involves: 1. Downloading a text file 2. Parsing it to get a URL 3. Making a new user 4. Symlinking the user's HOME directory into the build tree 5. Run an extremely non-standard build system. 6. Hope you're not trying to cross-compile, because good luck with that. 7. Guess at where the files came out (hint: it probably won't be in FHS locations) 8. Copy the output yourself once you find it. Would it really be that much harder to give us a git repo and a ./configure or a CMakeLists.txt?
- geocar 8y ago
  > 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/compatibility.html https://cr.yp.to/slashpackage/studies.html https://cr.yp.to/slashpackage/studies.html https://cr.yp.to/slashpackage/finding.html https://cr.yp.to/slashpackage/finding.html https://cr.yp.to/slashpackage/sharability.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.
  - nrclark 8y ago
    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.
    - 8y ago
jonlandrum 8y ago
Am I the only one who thought the name had something to do with Djibouti?
- eesmith 8y ago
  Probably one of the few. On HN, a search for "djb" results in about 60 submissions where "djb" is in the submission title. There are about 6 for Djibouti. Also, the airport code "DJB" is for Sultan Thaha Airport. The Djibouti–Ambouli International Airport code is JIB.
JdeBP 8y ago
> Other modern Linux/BSD/UNIX systems should work with minor adjustments to the instructions. I can report that I got it to build and run on slightly out of date FreeBSD by deleting all of the -m32 variants, and deleting all of the -march=haswell variants. I haven't looked into whether this is down to the version of GCC that comes in ports and the version of Clang that comes in base, or something else. No other changes were needed to the build process, though. JdeBP /package/prog/djbsort % /tmp/djbsort/command/int32-speed int32 implementation int32/portable4 int32 version - int32 compiler clang -fPIC -Wall -O2 -fomit-frame-pointer -fwrapv int32 1 72 72 72 ... int32 1048576 1979077401 1979993070 1983745962
amorousf00p 8y ago
Create a user and env to run a one-off build + application. DJB cracks me up. He may have the right thing in mind but this type of prophylactic approach is no longer proof against anything.
bluetech 8y ago
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.
- rphlx 8y ago
  It is sadly necessary; 30%+ performance regressions from, say, gcc 4 to gcc 6 are not uncommon w/ vector intrinsics.
carapace 8y ago
(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-functional-programming/article/generic-topdown-discrimination-for-sorting-and-partitioning-in-linear-time/B85E48EFC0B4D2BDDDE9A3885094FDD7 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 representations of ordering and equivalence relations. Discriminators improve the asymptotic performance of generic comparison-based sorting and partitioning, and can be implemented not to expose more information than the underlying ordering, respectively equivalence relation. For a large class of order and equivalence representations, including all standard orders for regular recursive first-order types, the discriminators execute in the worst-case linear time. The generic discriminators can be coded compactly using list comprehensions, with order and equivalence representations specified using Generalized Algebraic Data Types. We give some examples of the uses of discriminators, including the most-significant digit lexicographic sorting, type isomorphism with an associative-commutative operator, and database joins. Source code of discriminators and their applications in Haskell is included. We argue that built-in primitive types, notably pointers (references), should come with efficient discriminators, not just equality tests, since they facilitate the construction of discriminators for abstract types that are both highly efficient and representation-independent.")
- KirinDave 8y ago
  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.
  - carapace 8y ago
    It was probably you I heard about it from! Submission upvoted. ;-)
southern_cross 8y ago
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.
- ur-whale 8y ago
  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.
rurban 8y ago
beware, Linux only. Needs the usual BSD/macOS patches for HW_CPUSPEED and CLOCK_MONOTONIC and do away with for linux/perf_event.h. Unfortunately I have no idea how he deals with patches, I don't think he does.
deleted 8y ago
[deleted]

284 points by xmmrm 8y ago

ibuildoss 8y ago

That's pretty cool, are there any bindings for e.g. Go out there?

banachtarski 8y ago
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.
- throwaway77384 8y ago
  Care to elaborate? I am also looking into it, so would be interested to hear what the issues are.
  - tazjin 8y ago
    There's an indexed list of posts about Go's flaws here: https://github.com/ksimka/go-is-not-good 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.
    - thenrich99 8y ago
      What does it mean to have a "language that can scale"?
      - Sean1708 8y ago
        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.
    - w8rbt 8y ago
      That's very odd. Go was purposefully designed to scale and be used by 1000s of engineers collaborating on a project. https://www.quora.com/Will-the-Golang-code-become-unmaintainable-for-large-code-bases https://www.quora.com/Will-the-Golang-code-become-unmaintain...
      - tazjin 8y ago
        The type of codebase scaling Google does is very different from other companies. They have huge numbers of junior developers right out of university (those that Rob Pike, one of the main authors of Go, likes to claim aren't good enough to learn advanced concepts) and their coding style is not focused on correctness and simple implementations - do something, do a lot of it, write a lot of tests. For companies that aren't the size of Google, that don't work the same way (monorepos etc.), and that simply don't have the same set of resources available it will often end up being much easier to use a language that either prevents flaws (via a strong type system, like in Haskell or Rust, which Go does not have) or gracefully handles flaws (via an error handling strategy, like in Erlang or Elixir, which Go does not have).
        w8rbt 8y ago
        Go is strongly typed. https://en.wikipedia.org/wiki/Comparison_of_programming_languages_by_type_system https://en.wikipedia.org/wiki/Comparison_of_programming_lang... It also has an error checking system that is very simple and easy to use.
        tazjin 8y ago
        Go is statically typed (this means that the compiler performs its checks at compile time and hard-fails the compilation process in the presence of type errors), but there is no single definition of what "strong" means. Programming language theory is a field that is in development and notions of "strong" type systems that were valid in the 80s (in which Go certainly would have been considered strongly typed) are no longer relevant. The list you linked seems to cite the Go website itself as the source, by the way. At the very least a modern language that wants to claim to have a strong type system should provide user-defined sum types, exhaustiveness checking and parametric polymorphism. Go has none of those. When it comes to error handling, Go's "concept" of it is that "there may be a thing that can be turned into a string, in which case there was probably an error, but it's up to the developer to check - we won't help you". You may as well just use C then. There is nothing to short-circuit failed computations, check whether errors have in fact been handled, restart / terminate computations gracefully and so on. It's all manual labour that the developers need to remember and boilerplate over and over again. I would recommend you to spend some time with the languages that are "above Blub"[1] (ctrl+f "the blub paradox") - good candidates for learning some modern PLT concepts are Haskell[2], Rust[3] and Erlang[4]. Even if you don't end up using those languages in your professional life, knowing the concepts they introduce will improve your code in "Blub-languages" (Go, Java, etc.), too. [1]: http://www.paulgraham.com/avg.html http://www.paulgraham.com/avg.html [2]: http://haskellbook.com/ http://haskellbook.com/ [3]: https://doc.rust-lang.org/book/ https://doc.rust-lang.org/book/ [4]: https://learnyousomeerlang.com/ https://learnyousomeerlang.com/
    - thenrich99 8y ago
      I'd hardly call Kubernetes, Docker daemon and tooling, etcd, CockroachDB, geth, and nsq tiny CLI projects. If anyone has any reservations about learning Go, don't judge the language based on a list of flaws written by some programmers who used it for a few months, became frustrated, and wrote a blog post. Go has tradeoffs just like any other language and plenty of programmers leverage it for its positives: https://github.com/avelino/awesome-go https://github.com/avelino/awesome-go
- ben0x539 8y ago
  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. ¯\_(ツ)_/¯
  - josteink 8y ago
    > Try to think of it as a domain-specific language for implementing simple http endpoints. But to that type-safe and well, you probably want Generics.
- thenrich99 8y ago
  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.
  - jerf 8y ago
    "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." Strongly agreed. There's a lot of languages out there with very rich feature sets, and the way you get jobs done is to go find the right feature you need for your current problem. With Go, you need to learn the language and extract every last drop out of every language feature. This is exacerbated by the fact that the feature set isn't what people expect, e.g., object composition is not what they are used to, and while interfaces are simple there's still some art to using them properly. Despite the vast, vast distance between Go and Haskell on the general-purpose programming language landscape, I found my experiences in Haskell to be quite useful in Go, because while they were specifically inapplicable to an imperative language, the general practice I got from Haskell of taking a bizarre set of programming tools and learning how to make sensible programs out of them even so was quite useful. (It isn't necessarily the first language I reach for for personal tasks, but it is a superb professional programming language, offering a nearly-unique blend of the ability to get the job done you usually need to do for a wide variety of standard programming tasks (but not all!) while resulting in source code that is still comprehensible to almost every programmer. It isn't my favorite overall, but it's the best professional choice of language I have in my belt, which is often precisely because it does not permit me to indulge in flights of clever fancy that solves a problem in 25 impenetrable-to-the-next-guy lines of code. I know a lot of people may not love to hear that, but it's a factor you really have to consider when you are being paid to solve problems.)
- jy3 8y ago
  It's kinda hilarious to see that as more and more successful projects and companies use Go in their stacks, the number of comments like these increases in HN.
  - vinceguidry 8y ago
    Stack adoption is orthogonal to maturity or ease of use. Recent experiences have indicated to me that the main factor in which stack a company uses is basically the whim of whatever developer was tasked with the initial project creation. Nobody's going to tell him no and there's not going to be significant discussion about the merits and even if there was, there's no best practices to lean on to make the decision rely on anything other than pure emotion.
  - aidenn0 8y ago
    "There are only two kinds of languages: the ones people complain about and the ones nobody uses." - Bjarne Stroustrup
  - wnoise 8y ago
    Stack adoption makes people have to actually use them, which then gives them something to complain about (whereas before they could just ignore something not to their taste).

MrBuddyCasino 8y ago

The 2.5 cycles/byte compared to the 32 cycles/byte that Intel managed pulled off seems like an improbably large improvement over the current state of the art? Is this real?

Ono-Sendai 8y ago
Well, that's for a very small and particular size. (1024 elements) Intel's library might have more overhead at that size.
bdukic 8y ago
My guess is that the "catch" comes in the form of the list of limitations.
Cyphase 8y ago
The cycles/byte for all the sizes listed in the table on the Speed page[0], courtesy of copy-paste and a one-liner in the Python REPL: size cycles/byte (based on median) 1 6.0 2 3.375 4 11.625 8 9.625 16 7.984375 32 7.515625 64 6.0390625 128 4.31640625 256 2.4873046875 512 2.29443359375 1024 2.5048828125 2048 2.77893066406 4096 3.0791015625 8192 3.89566040039 16384 5.23690795898 32768 6.35472106934 65536 7.55914306641 131072 9.23189163208 262144 10.789557457 524288 12.4885950089 1048576 14.6550707817 [0] https://sorting.cr.yp.to/speed.html https://sorting.cr.yp.to/speed.html

robin_reala 8y ago

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 https://sorting.cr.yp.to/install.html

VMG 8y ago
I thought this guy was joking > djb presents djbsort, a constant-time djbsolution to a djbproblem you probably don't have. To install, just unpack djbsort.djb and run the ./djb script. Make sure you have djbtools installed first https://twitter.com/bascule/status/1016904259848192000 https://twitter.com/bascule/status/1016904259848192000
F30 8y ago
Yes, presumably to run the build as a user which is as unprivileged as possible. Which is a reasonable idea, though it might seem paranoid in today's `curl | sudo sh` world.
- hawkice 8y ago
  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.
  - judofyr 8y ago
    > humility of DJB Really? This is software where the author named it after himself, claims that it holds a new speed record with no comparisons benchmarks (just references a single number from a paper in 2015), uses the word "easily" FOUR times in the limitation-section without any links or explanations, and doesn't reference any other libraries/resources/software/solutions.
    - 8y ago

Ono-Sendai 8y ago

The median sort time for sorting 1048576 elements wth djbsort is 61467822 cycles: https://sorting.cr.yp.to/speed.html 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 http://forwardscattering.org/post/34 A serial radix sort should still be similar or faster to djbsort.

SiempreViernes 8y ago
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.
- Ono-Sendai 8y ago
  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.
  - exDM69 8y ago
    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.
    - Veedrac 8y ago
      It's a sorting network, which means it only uses conditional swaps in a fixed pattern, which can be made constant time.

yoklov 8y ago

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 to do multiple milliseconds of AVX instructions you tend to have better results from 4-wide vectors, which don't have this cost.

jwr 8y ago
See also the excellent writeup at: https://gist.github.com/rygorous/32bc3ea8301dba09358fd2c64e02d774 https://gist.github.com/rygorous/32bc3ea8301dba09358fd2c64e0...
stochastic_monk 8y ago
So in a sense, using wider vectors should be done at times when you’re certain to need heavy lifting, much like a GPU, but at a smaller timescale. I should update my vectorization library so that it doesn’t simply use the widest possible.
puzzle 8y ago
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.
- jeffreyrogers 8y ago
  You need a context switch to use AVX?
  - puzzle 8y ago
    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.

lixtra 8y ago

The main feature of the algorithm is to sort fast in constant time (for fixed n) for cryptographic purposes [0]. [0] https://ntruprime.cr.yp.to/ntruprime-20170816.pdf https://ntruprime.cr.yp.to/ntruprime-20170816.pdf P. 48

atesti 8y ago

Direct download link (if you don't want to run the script) https://sorting.cr.yp.to/djbsort-20180710.tar.gz https://sorting.cr.yp.to/djbsort-20180710.tar.gz

eggie 8y ago

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 https://github.com/pelotoncycle/bsort

whazor 8y ago
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.

pushcx 8y ago

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

Tepix 8y ago
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?
- masklinn 8y ago
  > 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.
  - lisper 8y ago
    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 public domain. But if you think you need it licensed, you can have it licensed.
    - johannes1234321 8y ago
      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. law they most likely don't want to restrict to U.S.) For an example see the recent case about project Gutenberg https://news.ycombinator.com/item?id=16511038 https://news.ycombinator.com/item?id=16511038

nrclark 8y ago

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 build flow that involves: 1. Downloading a text file 2. Parsing it to get a URL 3. Making a new user 4. Symlinking the user's HOME directory into the build tree 5. Run an extremely non-standard build system. 6. Hope you're not trying to cross-compile, because good luck with that. 7. Guess at where the files came out (hint: it probably won't be in FHS locations) 8. Copy the output yourself once you find it. Would it really be that much harder to give us a git repo and a ./configure or a CMakeLists.txt?

geocar 8y ago
> 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/compatibility.html https://cr.yp.to/slashpackage/studies.html https://cr.yp.to/slashpackage/studies.html https://cr.yp.to/slashpackage/finding.html https://cr.yp.to/slashpackage/finding.html https://cr.yp.to/slashpackage/sharability.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.
- nrclark 8y ago
  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.
  - 8y ago

jonlandrum 8y ago

Am I the only one who thought the name had something to do with Djibouti?

eesmith 8y ago
Probably one of the few. On HN, a search for "djb" results in about 60 submissions where "djb" is in the submission title. There are about 6 for Djibouti. Also, the airport code "DJB" is for Sultan Thaha Airport. The Djibouti–Ambouli International Airport code is JIB.

JdeBP 8y ago

> Other modern Linux/BSD/UNIX systems should work with minor adjustments to the instructions. I can report that I got it to build and run on slightly out of date FreeBSD by deleting all of the -m32 variants, and deleting all of the -march=haswell variants. I haven't looked into whether this is down to the version of GCC that comes in ports and the version of Clang that comes in base, or something else. No other changes were needed to the build process, though. JdeBP /package/prog/djbsort % /tmp/djbsort/command/int32-speed int32 implementation int32/portable4 int32 version - int32 compiler clang -fPIC -Wall -O2 -fomit-frame-pointer -fwrapv int32 1 72 72 72 ... int32 1048576 1979077401 1979993070 1983745962

amorousf00p 8y ago

Create a user and env to run a one-off build + application. DJB cracks me up. He may have the right thing in mind but this type of prophylactic approach is no longer proof against anything.

bluetech 8y ago

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.

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

carapace 8y ago

(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-functional-programming/article/generic-topdown-discrimination-for-sorting-and-partitioning-in-linear-time/B85E48EFC0B4D2BDDDE9A3885094FDD7 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 representations of ordering and equivalence relations. Discriminators improve the asymptotic performance of generic comparison-based sorting and partitioning, and can be implemented not to expose more information than the underlying ordering, respectively equivalence relation. For a large class of order and equivalence representations, including all standard orders for regular recursive first-order types, the discriminators execute in the worst-case linear time. The generic discriminators can be coded compactly using list comprehensions, with order and equivalence representations specified using Generalized Algebraic Data Types. We give some examples of the uses of discriminators, including the most-significant digit lexicographic sorting, type isomorphism with an associative-commutative operator, and database joins. Source code of discriminators and their applications in Haskell is included. We argue that built-in primitive types, notably pointers (references), should come with efficient discriminators, not just equality tests, since they facilitate the construction of discriminators for abstract types that are both highly efficient and representation-independent.")

KirinDave 8y ago
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.
- carapace 8y ago
  It was probably you I heard about it from! Submission upvoted. ;-)

southern_cross 8y ago

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.

ur-whale 8y ago
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.

rurban 8y ago

beware, Linux only. Needs the usual BSD/macOS patches for HW_CPUSPEED and CLOCK_MONOTONIC and do away with for linux/perf_event.h. Unfortunately I have no idea how he deals with patches, I don't think he does.

deleted 8y ago

[deleted]