18 ms·

C means rolling your own quick and practical hash table in 250 lines without tests, whenever you need it. Kinda answers the question of why people are looking f

by kubb 4y ago

C means rolling your own quick and practical hash table in 250 lines without tests, whenever you need it. Kinda answers the question of why people are looking for a better alternative to C that was discussed here recently. I wish we had a name for this, like "required non-innovative effort penalty" for using C, so that we can abstract some of these discussions that end up happening every time C is mentioned.

mananaysiempre 4y ago
That’s one of the few places that genuinely itch in my C experience, but I haven’t seen it solved anywhere, even partially. The hard part is, there are a myriad tiny variations of each data structure, especially the simplest ones (even prehistoric Knuth vol 1 lists a dozen of versions of a linked list); the C practice is generally to write the most appropriate one in each case (because there is no reason to value a premade one if you don’t have any, and because manual implementation makes to want and appreciate those small affordances that pointer-to-head / dummy-head / cyclic pointer-to-head / cyclic dummy-head / etc. give you). This does not always work well, both because it forces you to optimize with little data, and because natural laziness can lead you to avoid a marginally more complex data structure for longer than you really should (and possibly have the laziness-induced inefficiency be lost and forgotten). But it does give working with data structures in C a certain feel and style that I haven’t seen reproduced with reusable implementations. When a language uses those, it’s either by choosing a small set of structures and running with them (Lua, Awk, Python, perhaps Tcl as a more interesting example) or by parametrizing everything to the hilt (C++ and D). Even in C, the language more steers you towards rolling your own than forces it (cue qsort & bsearch, BSD and Linux macros, etc.). Yet the small set is frequently too small, and the One Implementation to rule them all is bloated far beyond the mental capacity of a single person and still too inflexible. Honestly, if there is something I’d like from a C successor, it’s reproducing the hand-rolled-data-structure style without the actual hand rolling (in most cases), and that’s as much a library feature as a language one. I can name a lot of other things I’d like to see in my low-level language, but if I had to choose one improvement, that would be it. So far, I haven’t seen a convincing attempt.
- anonymoushn 4y ago
  The Zig standard library includes some commonly used data structures, and the perfect time to add your favorites or to improve the APIs of the existing ones is before 1.0 :)
  - kubb 4y ago
    Blog post idea: how to build a zig library with an extern C API that provides access to a Zig data structure, build it, link it in a C program and use it from C.
  - tialaramex 4y ago
    One of the things Gankra (I think it was her?) did a long time ago for Rust before 1.0 was pull out all the more esoteric data structures which had lived in its standard library and banish them to separate crates. Does somebody need an LRU cache? Yes. But unlike say, a HashSet most people will never need one even if you explain what it's for. The standard library has a high maintenance cost. It's only worth it to pay that cost for data structures people need all the damn time, and for vocabulary types. Fewer people will ever need ControlFlow than HashSet, but having it in the standard library means everybody is agreed that's ControlFlow, there's no risk two popular things invent their own. If two popular Rust crates invent their own LRU cache nobody's day is ruined. Because C is really old, it's understandable that K&R went really light on the standard library. I can't forgive their terrible string, or the garbage built-in array type, but I can totally imagine in the 1970s it's a lot to ask that the standard library should have say, hash tables. Today it isn't and your language should have them.
Jtsummers 4y ago
There is a phrase: accidental complexity. Systems can be broken down into two sets of complexity: Accidental and Essential. Accidental complexity is there because of something to do with the system, but is not, strictly, inherent to the problem being solved. That would be essential complexity. Fred Brooks' essay "No Silver Bullet": http://worrydream.com/refs/Brooks-NoSilverBullet.pdf http://worrydream.com/refs/Brooks-NoSilverBullet.pdf And a good paper on the topic is Out of the Tarpit (http://curtclifton.net/papers/MoseleyMarks06a.pdf http://curtclifton.net/papers/MoseleyMarks06a.pdf) and a good writeup on that is here: https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/ https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/
- kubb 4y ago
  You added two definitions but I think you forgot to make a point?
  - donkeybeer 4y ago
    > I wish we had a name for this, like "required non-innovative effort penalty"
    - kubb 4y ago
      It's not the same thing though, accidental/incidental complexity is a much broader term.
zbird 4y ago
On the other extreme there are environments like Rust/Cargo and JS/Node, where you pull the hash table and you get 20 additional packages of untested who-knows-what that nobody asked for and that are recently vectors for malware. Shall we call it 'non-required pseudo-innovative non-effort penalty'?
- teakettle42 4y ago
  Can you name a modern language that doesn’t ship with a map collection type in its standard library? Rust does. C++ does. Swift does. It’s basic table stakes.
- kubb 4y ago
  This is counter factual information, you might want to double check if you use it to make decisions. All you need in Rust is the standard library that is well tested and doesn't pull in any crates. In JS a hash table is built into the language and doesn't require any packages.

by kubb 4y ago

mananaysiempre 4y ago

That’s one of the few places that genuinely itch in my C experience, but I haven’t seen it solved anywhere, even partially. The hard part is, there are a myriad tiny variations of each data structure, especially the simplest ones (even prehistoric Knuth vol 1 lists a dozen of versions of a linked list); the C practice is generally to write the most appropriate one in each case (because there is no reason to value a premade one if you don’t have any, and because manual implementation makes to want and appreciate those small affordances that pointer-to-head / dummy-head / cyclic pointer-to-head / cyclic dummy-head / etc. give you). This does not always work well, both because it forces you to optimize with little data, and because natural laziness can lead you to avoid a marginally more complex data structure for longer than you really should (and possibly have the laziness-induced inefficiency be lost and forgotten). But it does give working with data structures in C a certain feel and style that I haven’t seen reproduced with reusable implementations. When a language uses those, it’s either by choosing a small set of structures and running with them (Lua, Awk, Python, perhaps Tcl as a more interesting example) or by parametrizing everything to the hilt (C++ and D). Even in C, the language more steers you towards rolling your own than forces it (cue qsort & bsearch, BSD and Linux macros, etc.). Yet the small set is frequently too small, and the One Implementation to rule them all is bloated far beyond the mental capacity of a single person and still too inflexible. Honestly, if there is something I’d like from a C successor, it’s reproducing the hand-rolled-data-structure style without the actual hand rolling (in most cases), and that’s as much a library feature as a language one. I can name a lot of other things I’d like to see in my low-level language, but if I had to choose one improvement, that would be it. So far, I haven’t seen a convincing attempt.

anonymoushn 4y ago
The Zig standard library includes some commonly used data structures, and the perfect time to add your favorites or to improve the APIs of the existing ones is before 1.0 :)
- kubb 4y ago
  Blog post idea: how to build a zig library with an extern C API that provides access to a Zig data structure, build it, link it in a C program and use it from C.
- tialaramex 4y ago
  One of the things Gankra (I think it was her?) did a long time ago for Rust before 1.0 was pull out all the more esoteric data structures which had lived in its standard library and banish them to separate crates. Does somebody need an LRU cache? Yes. But unlike say, a HashSet most people will never need one even if you explain what it's for. The standard library has a high maintenance cost. It's only worth it to pay that cost for data structures people need all the damn time, and for vocabulary types. Fewer people will ever need ControlFlow than HashSet, but having it in the standard library means everybody is agreed that's ControlFlow, there's no risk two popular things invent their own. If two popular Rust crates invent their own LRU cache nobody's day is ruined. Because C is really old, it's understandable that K&R went really light on the standard library. I can't forgive their terrible string, or the garbage built-in array type, but I can totally imagine in the 1970s it's a lot to ask that the standard library should have say, hash tables. Today it isn't and your language should have them.

Jtsummers 4y ago

There is a phrase: accidental complexity. Systems can be broken down into two sets of complexity: Accidental and Essential. Accidental complexity is there because of something to do with the system, but is not, strictly, inherent to the problem being solved. That would be essential complexity. Fred Brooks' essay "No Silver Bullet": http://worrydream.com/refs/Brooks-NoSilverBullet.pdf http://worrydream.com/refs/Brooks-NoSilverBullet.pdf And a good paper on the topic is Out of the Tarpit (http://curtclifton.net/papers/MoseleyMarks06a.pdf http://curtclifton.net/papers/MoseleyMarks06a.pdf) and a good writeup on that is here: https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/ https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/

kubb 4y ago
You added two definitions but I think you forgot to make a point?
- donkeybeer 4y ago
  > I wish we had a name for this, like "required non-innovative effort penalty"
  - kubb 4y ago
    It's not the same thing though, accidental/incidental complexity is a much broader term.

zbird 4y ago

On the other extreme there are environments like Rust/Cargo and JS/Node, where you pull the hash table and you get 20 additional packages of untested who-knows-what that nobody asked for and that are recently vectors for malware. Shall we call it 'non-required pseudo-innovative non-effort penalty'?

teakettle42 4y ago
Can you name a modern language that doesn’t ship with a map collection type in its standard library? Rust does. C++ does. Swift does. It’s basic table stakes.
kubb 4y ago
This is counter factual information, you might want to double check if you use it to make decisions. All you need in Rust is the standard library that is well tested and doesn't pull in any crates. In JS a hash table is built into the language and doesn't require any packages.