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

71–80 of 158 posts

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

#71

Post by geocar »

kbenson wrote: post #63
geocar wrote: post #53

Earlier quoted context omitted.

> or the needs of software packagers. They address the needs of users. I don't care about software packagers at all, except insofar as they can address the needs of users. > 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…

You example script with python2 is not about pathing, but a separate problem or multiple binaries with the same name, and is exactly why you want to let package managers deal with this. As a developer, you can't know all the different setups you users will have, or for example what the default python will be. As a package manager, you know Exactly this for the systems you are packaging for. If needed, they will patch…

> You example script with python2 is not about pathing, but a separate problem or multiple binaries with the same name, and is exactly why you want to let package managers deal with this.

> for example what the default python will be

Except that package maintainers created this problem. It's not a real problem!

Python's source code downloaded packages call itself python3.

Some package managers decided to call it "python" creating the incompatibility, and thus creating the problem for everyone who writes python programs for now until all those systems go away.

As a result, everyone who wants to write python programs has to deal with the fact that python is sometimes called python and sometimes called python2 -- depending on what the package manager did.

> As a developer, you can't know all the different setups you users will have,

You can know what you're willing to support

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

#72

Post by carapace »

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

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

#73

Post by tazjin »

w8rbt wrote: post #55
tazjin wrote: post #40

Earlier quoted context omitted.

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 are…

Go is strongly typed. https://en.wikipedia.org/wiki/Comparison_of_programming_lang... It also has an error checking system that is very simple and easy to use.

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 [2]: http://haskellbook.com/ [3]: https://doc.rust-lang.org/book/ [4]: https://learnyousomeerlang.com/

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

#74

Post by nrclark »

numbsafari wrote: post #60
geocar wrote: post #53

Earlier quoted context omitted.

> or the needs of software packagers. They address the needs of users. I don't care about software packagers at all, except insofar as they can address the needs of users. > 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…

Also, is cross-compilation even a goal for a software library written with the clear caveat that it makes use of specific CPU features?

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.

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

#75

Post by rkeene2 »

dilap wrote: post #67
jedisct1 wrote: post #62

Earlier quoted context omitted.

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.

(i guess i should say i'm a dev as well as a user. but my exposure to configure is as a user.) so here's why i'm not a fan of configure: (1) it's slow (2) if something goes wrong, it's a fucking nightmare to try to diagnose -- it's just an endless barage of crap that doesn't actually have anything to do with the app at hand, and the actual build process is like 2 or 3 layers away from running the configure script. (o…

Simple Makefiles almost never work for portable software that needs to interface with a system. There is a reason GNU autoconf was created -- it solves a real problem. Different kinds of systems are different in a LOT of ways. Almost all of these ways need to be determined at compile-time and without testing for those ways, there is no good way to do this. The older way (before GNU autoconf) that tools like "xmkmf" used was to have a massive database of features for each system and then you could just query that database for the features*platform you were compiling for to get the information -- this did not scale at all, platforms changed, features were added faster than the database could be distributed, and generally it was terrible.

Things not covered by a simple Makefile include almost all tasks related to building software: 1. How do you build a shared object (.so, .sl, .dylib, .dll, .a on AIX) ? Can you even do that (MINIX) ? 2. For the platform being compiled for (i.e., nothing to do with the platform you are compiling on) how large is an "int" ? Is there a type that exists for uint_least_32_t ? If not (because the compiler doesn't support stdint.h), is there an unsigned integer type that is atleast 32-bits wide ? 3. How do you link against an entire archive, not just the symbols you currently reference ? Is it -Wl,--whole-archive or -Wl,-z,allextract ? 4. For symbol versioning for your library, how do you set the soname ? How do you specify versions of functions ? Can you ? How do you filter out symbols that are not part of your ABI ?

You could start over and mandate a consistent toolset and exclude the majority of platforms (Rust, Go, etc)... or... you could write your own, inferior, version of GNU autoconf, or you could use GNU autoconf...

Good luck !

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

#76

Post by nrclark »

ur-whale wrote: post #68
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…

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

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

#77

Post by lorenzhs »

numbsafari wrote: post #57
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…

Is this software that he presently wants to see disseminated randomly, or is it provided here for academic purposes at this time? I don't know if it's his intention to have this library become part of a bunch of linux or BSD distros or not. But, it seems kind of presumptuous on your part to assume that he does.

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?

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

#78

Post by puzzle »

jeffreyrogers wrote: post #70
puzzle wrote: post #58

Earlier quoted context omitted.

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.

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.

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

#79

Post by ur-whale »

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…

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

Others just cant.

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

#80

Post by linsomniac »

viraptor wrote: post #37
hawkice wrote: post #14

Earlier quoted context omitted.

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.

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 :-(

I was talking to another person in the community, now this was well over a decade ago, maybe two, with the initials "DJB". He said: "I went onto IRC once. I was mistaken for Daniel Bernstein. It was the most awful 15 minutes of my life."

I spoke to another fairly famous person a few years later, let's say author of the authoritative book on one of the alternatives for one of djb's software packages. He said something along the lines of: It's a shame djb gets along so poorly with other people, because he has a lot of good ideas.

So, agreed: Authenticity but not humility.

Post reply on HN