8 ms·

Minimalist C Libraries

364 points by Cmerlyn 8y ago

nwmcsween 8y ago
The no malloc within the library cannot be overstated, let the user of the library decide what is best and do not do some junk like `some_fn()` and require an implicit `some_free()`
- dvh 8y ago
  But what if "some" is not subject of my program and I want to offload it's complexity away so that I can concentrate on actual subject of my program? In that case wouldn't it be better to have some_alloc, some_foo, some_free rather than to need each user to make their own, probably buggy and slow allocator? If I'm making image editor, allocating bitmaps myself is fine, if I'm writing crud app, not so much.
  - saagarjha 8y ago
    > need each user to make their own, probably buggy and slow allocator What's wrong with malloc?
    - dvh 8y ago
      Nothing I was thinking about allocations of more complex structures (that at the end use malloc)
    - flohofwoe 8y ago
      At least in game development, custom allocation code is often used to either provide more debugging and profiling capabilities, or otherwise add functionality to the generic C or C++ allocator. Every good middleware library provides a way to hook into memory allocation, and ideally annotates each allocation with some sort of tag or label, so it's possible to track from the outside what an allocation was used for.
    - maccard 8y ago
      We use wrappers where I work, as we track all allocations. We can provide application context if something goes wrong, we can track usage (per thread, per subsystem, over time), and probably most importantly, we know the allocation pattern of our applications better.
      - q3k 8y ago
        glibc malloc provides a way of hooking into memory management calls without having to use wrappers: https://www.gnu.org/software/libc/manual/html_node/Hooks-for-Malloc.html https://www.gnu.org/software/libc/manual/html_node/Hooks-for...
  - astrobe_ 8y ago
    A library is not a framework. A library provides the basic bricks and typically the users build a layer that fit their needs. It could be, for instance, C++ classes. Furthermore if the authors of the library think they know better with regard to allocation, they can provide an allocator as a separate addition to the library.
- torstenvl 8y ago
  I disagree. This is an artificial limitation that severely hampers the library's capabilities. That kind of discipline may be fine for normal linear string-crunching, but it's cumbersome to an asinine degree if your library needs to do any sort of complex ADT manipulation.
  - jgtrosh 8y ago
    It calls to mind Fortran-style function docs which would give a formula to compute the size of a work array for the caller to provide. That really ties the implementation to the header. It was really boring to work with, though it often pushed you to understand what was going on inside.
    - pletnes 8y ago
      This kind of interface was common in fortran 77. I’m guessing you’ve used BLAS/LAPACK? In more modern fortran, it’s not so usual. Also, Fortran is much more high level than C, and how memory is allocated etc is compiler dependent to a much larger degree than for C. I’d recommend writing a Fortran 95 wrapper which creates work arrays for you if you really need to use such routines.
  - enriquto 8y ago
    Most often you do not need any sort of "complex ADT"; in that case the no-malloc advice is good but harmless. Sometimes, you can probably do without any "complex ADT"; in that case, the no-malloc advice forces you to find the clean solution without complex ADT, thus it is really great. In the rare cases when you intrinsically need a complex ADT, then you do it. The advice is a spirit, not an unbreakable constraint. Just like not using goto.
  - marssaxman 8y ago
    It's also necessary if you want to use the library at all in situations where you can't assume that a heap allocator is available.
  - stochastic_monk 8y ago
    If you need aligned memory (e.g., for SIMD operations), it can be better to assume control of allocation.
- tedunangst 8y ago
  Although it may work for the integer hash set, forcing the application to deal with potential resizing when adding to a generic hash table is painful. I'll note too that the growable buffer example linked at the end violates the no malloc rule.
baybal2 8y ago
This man deserves a monument. The number of such disciplined C coders who can articulate what a proper C coding is is dwindling with each year.
- collective_intl 8y ago
  Sad that the best talent is moving on to other languages like Rust, which don't have the simplicity of C.
- mjburgess 8y ago
  Its a style of programming C was built for, and not many other languages. It's almost the opposite of good style elsewhere: aggressively procedural code with an elegant boundary. I'd say it would be a good lesson to many who are down the or pure functional rabbit holes: perhaps there is some other sense of modularity that goes missing when "single purpose" is applied too narrowly.
  - masklinn 8y ago
    > Its a style of programming C was built for, and not many other languages. Rust seems well adapted for it: > (1) Small number of functions, perhaps even as little as one. One annoyance with that kind of stuff is that you'll get many small dependencies rather than a few big ones. Having a simple and easy way to acquire & maintain these dependencies is useful, and Cargo provides that. > (2) No dynamic memory allocations. > (3) No input or output. That's pretty much what a #[no_std] (libcore-only) library is[0]. > (4) Define at most one structure, and perhaps even none. That's the bit I disagree most about, but if that's what you want the language won't stop you. [0] unless it's requires nightly and uses alloc directly but that's not too common right now I think
  - pjmlp 8y ago
    True, there were not so many choices back in the early 70's. Beyond NEWP, PL/I, BLISS, Concurrent Pascal, PL/S, PL/8, PL/M, XPL, Mesa that is.
panic 8y ago
These “single-file libraries” share a lot of the same ideals: https://github.com/nothings/single_file_libs https://github.com/nothings/single_file_libs
stochastic_monk 8y ago
It's worth pointing out that his two favorite RNGs (xoroshiro128+/xorshift128+) both fail BigCrush. According to [0] and the associated github [1], for a statistically strong RNG which is still fast, AES-CTR or splitmix64/lehmer64 are probably your best bet, unless you have AVX512, in which case an SIMD-accelerated PCG is the way to go [2]. (The other methods cap out at 1 cycle per byte, while the AVX512 PCG is 1 cycle per 32-bit integer, 4x as fast as the fastest previously tested.) While I don't doubt it could be further accelerated, I've added STL compatibility, templated unrolling, and provided some extra utilities (including random access) in a package based off code from [1] (provided by Samuel Neves) which I now use in most of my projects, and which is available at [3]. [0] https://lemire.me/blog/2017/09/08/the-xorshift128-random-number-generator-fails-bigcrush/ https://lemire.me/blog/2017/09/08/the-xorshift128-random-num... [1] https://github.com/lemire/testingRNG https://github.com/lemire/testingRNG [2] https://lemire.me/blog/2018/06/07/vectorizing-random-number-generators-for-greater-speed-pcg-and-xorshift128-avx-512-edition/ https://lemire.me/blog/2018/06/07/vectorizing-random-number-... [3] https://github.com/dnbaker/aesctr https://github.com/dnbaker/aesctr
- acqq 8y ago
  The way the mentioned PRNGs "fail" is when testing just the lower bits (search for the occurrences of "lsb" in [1] above) and this may be important in your use cases or not. The same [1] claims in "Visual Summary" that the "cycles/byte" is 1 for various PRNGs but http://xoshiro.di.unimi.it/ http://xoshiro.di.unimi.it/ seems to show that the reason splitmix64 is not preferred everywhere is that xoroshiro128+ is roughly two times faster than splitmix64 . Regarding having lower bits poor statistically, it was known since forever that that is the case for the huge class of simple PRNGs (effectively all that are faster than the alternatives, unless maybe if there's some specialized instruction in the CPU), the question is if that is critical or not for your purposes. The author of xoroshiro128+ is of course aware of that issue, and he also writes: "For general usage, one has to consider that its lowest bits have low linear complexity and will fail linearity tests; however, low linear complexity can have hardly any impact in practice, and certainly has no impact at all if you generate floating-point numbers using the upper bits (we computed a precise estimate of the linear complexity of the lowest bits)." In short, if you don't know how you're going to use the PRNG and you don't have problems related to speed, sure, use the safest one. Note that "safety" is still differently understood in different use cases, e.g. take care to note that most of fast PRNGs still aren't cryptographically secure: https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator https://en.wikipedia.org/wiki/Cryptographically_secure_pseud... and that sometimes even "standardized" "cryptographically secure" turn out to be something else, e.g. the subtitle on that wikipedia page: "NSA kleptographic backdoor in the Dual_EC_DRBG PRNG" Also other considerations come into play when you have some specific needs and you understand the consequences: then it's not only black-and-white "safe" v.s. "not safe." For some purposes (as the mentioned generation of the floating-point numbers in some use cases) speed matters enough to sacrifice some "perfectness."
Mankaninen 8y ago
With respect to the bmp example: 1. Removing the bmp_get implies that the application needs to implement a shadow image if it needs to check the color o a certain pixel. Or even worse, take a direct peek in its void memory area. 2. void pointers instead of bmp_pointers makes it easier to create a mess, the compiler will not tell you that you called the bmp library with a pointer to a jpg memory area. 3. Not doing range checking in the library - but imposing that burden on the caller - is a bad practice. If the caller does the same - expects his caller to do the checking - we end up with a sequrity risk. Trying to minimize the library by pushing work to the application is wrong every time you expect the library to be used more than once. Despite these objections, I like libraries that are free of IO and mallocs!
- spc476 8y ago
  When I fell down into the rabbit hole of DNS, I wrote code to just encode and decode DNS packets [1]. All the existing libraries [2] had a complex API that provided a separate function for querying a few record types (A, AAAA, MX, TXT, SRV, maybe NS and SOA), leaving the rest unimplemented. They also tend to have complex network architectures to handle retries, caching, and parallel queries which could be hard to integrate into a project that had an existing network framework. Mine? Just two functions: dns_encode() and dns_decode(). No I/O. No malloc(). [1] https://github.com/spc476/SPCDNS https://github.com/spc476/SPCDNS [2] The ones I was looking at are written in C.
  - lifthrasiir 8y ago
    > No malloc(). ...by having your own arena allocator! I do agree that it is quite doable in this particular case, but I always remember that a custom memory allocator of OpenSSL made Heartbleed much more devastating.
    - spc476 8y ago
      ... of memory passed in by the user! So it's up to the caller to make sure memory contains unclassified information.
- 8y ago
sytelus 8y ago
Please do not do this! There is so much bad advice in this article. Remember the rule: Your code should be simple, but not simpler. There is absolutely no need to abandon great facilities afforded by language and libraries to make things unreadable, undebugable and unmaintainable.
- abiox 8y ago
  could you be a bit more specific about what you feel is "bad advice"?
- masklinn 8y ago
  Abandoning some facilities does not "make things unreadable, undebugable and unmaintainable" and can allow them being used much more widely. The limitations seem similar to #[no_std] in Rust, and while that's not something to strive for at all costs if you can do without it allows e.g. embedded developers or kernel/OS developers to use the work.
  - berti 8y ago
    > e.g. embedded developers or kernel/OS developers to use the work. I certainly agree that's one of the strongest reasons to avoid allocating memory etc. It's pretty clear that not many commenters have done any work outside a hosted environment... but I guess that makes the point that we're in fairly specialised territory.
- chris_wot 8y ago
  I don't think he's saying to do this in every library, it's just an interesting technique he uses for very minimalist libraries.
- matheusmoreira 8y ago
  >great facilities afforded by language Sometimes those aren't so great. For example, C has errno, a thread-local variable that gets set to the error code of the last function you called. Why can't the function just return the error code? I think it's strange how all the Linux system calls do return error codes but the standard library puts them in errno anyway. I really like writing freestanding C because I can avoid most of the legacy.
vortico 8y ago
Most things here are reasonable, but I don't see a point about having only one struct. If your state is better organized in lots of hierarchical structs, within lists, within other structs, your data will be easier to move around, copy, and zero in smaller chunks, and you can write functions which processes isolated segments of data rather than a huge global state.
- matthiasv 8y ago
  The point was about the user-facing side not the internal representation of state.
  - vortico 8y ago
    Even then, it seems weird to prefer a big flat state rather than a state made of heirarchical sub-structures and arrays.
    - yason 8y ago
      As the user of the library I probably don't care about the hierarchies. If I want X the library can provide me a function to get X by looking up its internal substructures and arrays so that I don't have to.
- deleted 8y ago
  [deleted]
- enriquto 8y ago
  This is very sound advice. The interface of the library is intended to help the user of the library, not the developer of the library. The simplest interface is the best for the user, who does not want to know anything about the implementation details. In the ideal case, the developer and the api designer will be different persons who are not in good terms to each other. The more the developer hates the api designer, the better.
goofballlogic 8y ago
Love reading this stuff. When I grow up I want to be a C programmer.
tushartyagi 8y ago
I just want to understand that given the mostly negative reaction that's here at HN to the npm ecosystem which is based on the same "minimalist libraries" idea, how is this different? I'd appreciate if the response is not about JS and/or C, but about the minimalist libraries in JS, C, or any other language. Should I use a large number of small libraries? Should I wrap up some of the code which I use into a libraries even if that code is just a couple of functions without any data structure? Moreover, I'd admit that I'm a great fan of Chris Wellons blog posts which are pretty technical and original, and use some of his emacs libraries on a daily basis.
- panic 8y ago
  I think the difference is the network of dependencies. Even small libraries on npm often depend on other libraries (e.g., the is-odd library linked in the article depends on is-number).
- jstimpfle 8y ago
  The difference is that there is no package tool. These libraries are not dependencies that can disappear or whose API will break. You are expected to copy them into your source tree, or even use only the idea and make your own version. Also, as my sibling poster points out, they are self-contained.
- coldtea 8y ago
  >I just want to understand that given the mostly negative reaction that's here at HN to the npm ecosystem which is based on the same "minimalist libraries" idea, how is this different? It's different in that in C you don't pull in 200 dependencies which in-turn bring in another 10+ dependencies each. You just use 2-3 libs you need (and that they, in turn, don't require anything, or at best the POSIX standard libs), and that's it.
- khawkins 8y ago
  I think in recent years dogmatic minimalism has shown itself to be destructive. Time is wasted refactoring code and features are removed, reducing usability, all in service of an aesthetic that has lost sight of its purpose. Each of the guidelines listed independently represent good practices, in general, when applicable. It's worth considering the design choices when developing a library. But promoting a definition of minimalism implicitly promotes an all-or-nothing approach to development. The choice to not include memory allocation should be entirely independent of the choice not to include I/O. Pretending otherwise indicates that the choices aren't driven by pragmatism.
loup-vaillant 8y ago
I'm happy to say my crypto library¹ satisfies most of his criteria: It has 50 functions. That's too much, but it could be reduced to 10 if the user stick to the highest level facilities. There is no dynamic memory allocation, and no I/O (actually, it doesn't even depend on libc). The structures are defined in the header to allow the user to allocate them on the stack, but looking inside is unneeded and discouraged. [1]: https://monocypher.org https://monocypher.org
kstenerud 8y ago
This basically echoes my library building philosophy. The two biggest things are: 1. User-facing complexity: Keep the user interface just big enough to get the job done. Put the "90% of people" interface first and foremost and if you need to cover the other 10%, expose a different interface that's CLEARLY marked "Advanced. You probably don't need to use this". Don't get sucked into chrome plating everything. 2. Internal complexity: Keep your structures simple. Make your functions do one thing and exactly that thing, well. Keep your side effects to a minimum. And keep your dependencies low, because you can't trust that other people have done the same in their libraries.
xtrapolate 8y ago
> "The library mustn’t call malloc() internally. It’s up to the caller to allocate memory for the library. What’s nice about this is that it’s completely up to the application exactly how memory is allocated. Maybe it’s using a custom allocator, or it’s not linked against the standard library." OP's approach will indeed work for most "minimalist"/single-header libraries, but, I personally feel it pollutes the API you're exposing to your users. Depending on the specific situation, I may sometimes choose to expose a MODULE_CreateObject() and a MODULE_CreateObjectEx(custom_allocator, custom_deallocator). Internally, MODULE_CreateObject() calls MODULE_CreateObjectEx(), passing the module's default allocators and deallocators (ie. HeapAlloc and HeapFree). This strikes me as a more balanced approach. One caveat here, is that you must enforce consistency across usage - you don't want some API calls to use malloc() for allocation, whilst others use HeapFree() for deallocation, that would be a recipe for disaster. To ensure that, I would often set the allocators and deallocators once, when the object is first created. They may be set through the object's initialization function, and they persist as part of the object itself.
- ajross 8y ago
  > I personally feel it pollutes the API you're exposing to your users. Pollution is in the eye of the beholder. There are many circumstances where a project or subset of a project needs to work without a heap, they just don't necessarily overlap with the "application layer code in a virtual memory process" world your intuition is calibrated against. And sometimes this stuff needs to read a JSON object or decode base64 or utf8 too, and can't because the library is too thick.
  - deckiedan 8y ago
    At this level, surely it's better to leave it to the "user" of the library - who can always write a wrapper for all their used libraries to the same style API for use in the rest of the program
  - xtrapolate 8y ago
    > "Pollution is in the eye of the beholder. There are many circumstances where a project or subset of a project needs to work without a heap, they just don't necessarily overlap with the "application layer code in a virtual memory process" world your intuition is calibrated against." That's an argument in favor of offloading allocation/deallocation to the library's users, which is exactly the core of my, and OP's, proposals. We're saying the same thing here - developers should be able to determine/control how memory is allocated and deallocated. > "And sometimes this stuff needs to read a JSON object or decode base64 or utf8 too, and can't because the library is too thick." I'm losing you here. I honestly feel that my proposal is all about keeping the API as simple as humanely possible, without compromising the library's flexibility when it comes to the scenarios your mentioned earlier. In your case: BASE64DECODER_Decode(...) BASE64DECODER_DecodeEx(..., allocator, deallocator) BYTE * BASE64DECODER_GetDecodedBuffer(handle) BASE64DECODER_Free(handle)
joveian 8y ago
Personally, I'd add "don't write to your own memory" (with various stack use rules based on expected library use) and relax the "no structures" rule to encourage code that can be used from multiple threads simultaneously. Make the first argument always be the internal use data.
jokoon 8y ago
I don't think there are languages similar to C in term of simplicity, close to the metal and speed. C++ is good enough for me, but it's so slow to compile, and I don't use its most advanced features. I wish there was a language between C and C++, without the complex semantics you can find in rust and other exotic syntax. I don't necessarily love C or C++ in term of feature, but the syntax is just what i need. Why can't language designers write a language that is closer to C, with fancy features that don't change the language so much?
- felixangell 8y ago
  Maybe you would like the BetterC mode in the D programming language... if you mean you like C for it's syntax too. A lot of modern systems prog. languages seem to adopt a more modern syntax, i.e. types after the names rather than before, no semi-colons, etc. D stays true to C in this regard and offers a lot of fancy features. And the BetterC mode sounds suited to your requirements in that the language features doesn't over complicate things.
- Aardappel 8y ago
  https://ziglang.org/ https://ziglang.org/ is almost exactly what you're asking for.
- Bulat-Ziganshin 8y ago
  I personally prefer Nim. there is also Zig and D.
sevensor 8y ago
Maybe I'm just noticing it more, but I think there's more discussion of how to write C well than there used to be. I speculate that the attention Rust has brought to safe systems programming has caused an uptick in interest in closer-to-the-metal languages in general, and spurred C programmers to show that there are reasonable ways to write C as well. It may be an unanticipated result of Rust's popularity that the quality of C programming improves. (Or perhaps that was the plan all along?)
- Gibbon1 8y ago
  What I've noticed is the lead time for all sorts of things used in small embedded systems has gotten terrifyingly long. What says to me that there is a lot of embedded work going on. Also in the last 5 years people have abandoned the JVM as a end all be all platform which puts you squarely back into native code again.
hedora 8y ago
I’d argue these APIs could be further minimized by using a struct with a void * and a size_t in it, along with bounds checking accessors. This would eliminate most of the ugliness in the post-allocation calls, allow for the deletion of most error checking code in each library, and would harden BMP parsing “for free”.

364 points by Cmerlyn 8y ago

The no malloc within the library cannot be overstated, let the user of the library decide what is best and do not do some junk like `some_fn()` and require an implicit `some_free()`

dvh 8y ago
But what if "some" is not subject of my program and I want to offload it's complexity away so that I can concentrate on actual subject of my program? In that case wouldn't it be better to have some_alloc, some_foo, some_free rather than to need each user to make their own, probably buggy and slow allocator? If I'm making image editor, allocating bitmaps myself is fine, if I'm writing crud app, not so much.
- saagarjha 8y ago
  > need each user to make their own, probably buggy and slow allocator What's wrong with malloc?
  - dvh 8y ago
    Nothing I was thinking about allocations of more complex structures (that at the end use malloc)
  - flohofwoe 8y ago
    At least in game development, custom allocation code is often used to either provide more debugging and profiling capabilities, or otherwise add functionality to the generic C or C++ allocator. Every good middleware library provides a way to hook into memory allocation, and ideally annotates each allocation with some sort of tag or label, so it's possible to track from the outside what an allocation was used for.
  - maccard 8y ago
    We use wrappers where I work, as we track all allocations. We can provide application context if something goes wrong, we can track usage (per thread, per subsystem, over time), and probably most importantly, we know the allocation pattern of our applications better.
    - q3k 8y ago
      glibc malloc provides a way of hooking into memory management calls without having to use wrappers: https://www.gnu.org/software/libc/manual/html_node/Hooks-for-Malloc.html https://www.gnu.org/software/libc/manual/html_node/Hooks-for...
- astrobe_ 8y ago
  A library is not a framework. A library provides the basic bricks and typically the users build a layer that fit their needs. It could be, for instance, C++ classes. Furthermore if the authors of the library think they know better with regard to allocation, they can provide an allocator as a separate addition to the library.
torstenvl 8y ago
I disagree. This is an artificial limitation that severely hampers the library's capabilities. That kind of discipline may be fine for normal linear string-crunching, but it's cumbersome to an asinine degree if your library needs to do any sort of complex ADT manipulation.
- jgtrosh 8y ago
  It calls to mind Fortran-style function docs which would give a formula to compute the size of a work array for the caller to provide. That really ties the implementation to the header. It was really boring to work with, though it often pushed you to understand what was going on inside.
  - pletnes 8y ago
    This kind of interface was common in fortran 77. I’m guessing you’ve used BLAS/LAPACK? In more modern fortran, it’s not so usual. Also, Fortran is much more high level than C, and how memory is allocated etc is compiler dependent to a much larger degree than for C. I’d recommend writing a Fortran 95 wrapper which creates work arrays for you if you really need to use such routines.
- enriquto 8y ago
  Most often you do not need any sort of "complex ADT"; in that case the no-malloc advice is good but harmless. Sometimes, you can probably do without any "complex ADT"; in that case, the no-malloc advice forces you to find the clean solution without complex ADT, thus it is really great. In the rare cases when you intrinsically need a complex ADT, then you do it. The advice is a spirit, not an unbreakable constraint. Just like not using goto.
- marssaxman 8y ago
  It's also necessary if you want to use the library at all in situations where you can't assume that a heap allocator is available.
- stochastic_monk 8y ago
  If you need aligned memory (e.g., for SIMD operations), it can be better to assume control of allocation.
tedunangst 8y ago
Although it may work for the integer hash set, forcing the application to deal with potential resizing when adding to a generic hash table is painful. I'll note too that the growable buffer example linked at the end violates the no malloc rule.

baybal2 8y ago

This man deserves a monument. The number of such disciplined C coders who can articulate what a proper C coding is is dwindling with each year.

collective_intl 8y ago
Sad that the best talent is moving on to other languages like Rust, which don't have the simplicity of C.
mjburgess 8y ago
Its a style of programming C was built for, and not many other languages. It's almost the opposite of good style elsewhere: aggressively procedural code with an elegant boundary. I'd say it would be a good lesson to many who are down the or pure functional rabbit holes: perhaps there is some other sense of modularity that goes missing when "single purpose" is applied too narrowly.
- masklinn 8y ago
  > Its a style of programming C was built for, and not many other languages. Rust seems well adapted for it: > (1) Small number of functions, perhaps even as little as one. One annoyance with that kind of stuff is that you'll get many small dependencies rather than a few big ones. Having a simple and easy way to acquire & maintain these dependencies is useful, and Cargo provides that. > (2) No dynamic memory allocations. > (3) No input or output. That's pretty much what a #[no_std] (libcore-only) library is[0]. > (4) Define at most one structure, and perhaps even none. That's the bit I disagree most about, but if that's what you want the language won't stop you. [0] unless it's requires nightly and uses alloc directly but that's not too common right now I think
- pjmlp 8y ago
  True, there were not so many choices back in the early 70's. Beyond NEWP, PL/I, BLISS, Concurrent Pascal, PL/S, PL/8, PL/M, XPL, Mesa that is.

panic 8y ago

These “single-file libraries” share a lot of the same ideals: https://github.com/nothings/single_file_libs https://github.com/nothings/single_file_libs

stochastic_monk 8y ago

It's worth pointing out that his two favorite RNGs (xoroshiro128+/xorshift128+) both fail BigCrush. According to [0] and the associated github [1], for a statistically strong RNG which is still fast, AES-CTR or splitmix64/lehmer64 are probably your best bet, unless you have AVX512, in which case an SIMD-accelerated PCG is the way to go [2]. (The other methods cap out at 1 cycle per byte, while the AVX512 PCG is 1 cycle per 32-bit integer, 4x as fast as the fastest previously tested.) While I don't doubt it could be further accelerated, I've added STL compatibility, templated unrolling, and provided some extra utilities (including random access) in a package based off code from [1] (provided by Samuel Neves) which I now use in most of my projects, and which is available at [3]. [0] https://lemire.me/blog/2017/09/08/the-xorshift128-random-number-generator-fails-bigcrush/ https://lemire.me/blog/2017/09/08/the-xorshift128-random-num... [1] https://github.com/lemire/testingRNG https://github.com/lemire/testingRNG [2] https://lemire.me/blog/2018/06/07/vectorizing-random-number-generators-for-greater-speed-pcg-and-xorshift128-avx-512-edition/ https://lemire.me/blog/2018/06/07/vectorizing-random-number-... [3] https://github.com/dnbaker/aesctr https://github.com/dnbaker/aesctr

acqq 8y ago
The way the mentioned PRNGs "fail" is when testing just the lower bits (search for the occurrences of "lsb" in [1] above) and this may be important in your use cases or not. The same [1] claims in "Visual Summary" that the "cycles/byte" is 1 for various PRNGs but http://xoshiro.di.unimi.it/ http://xoshiro.di.unimi.it/ seems to show that the reason splitmix64 is not preferred everywhere is that xoroshiro128+ is roughly two times faster than splitmix64 . Regarding having lower bits poor statistically, it was known since forever that that is the case for the huge class of simple PRNGs (effectively all that are faster than the alternatives, unless maybe if there's some specialized instruction in the CPU), the question is if that is critical or not for your purposes. The author of xoroshiro128+ is of course aware of that issue, and he also writes: "For general usage, one has to consider that its lowest bits have low linear complexity and will fail linearity tests; however, low linear complexity can have hardly any impact in practice, and certainly has no impact at all if you generate floating-point numbers using the upper bits (we computed a precise estimate of the linear complexity of the lowest bits)." In short, if you don't know how you're going to use the PRNG and you don't have problems related to speed, sure, use the safest one. Note that "safety" is still differently understood in different use cases, e.g. take care to note that most of fast PRNGs still aren't cryptographically secure: https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator https://en.wikipedia.org/wiki/Cryptographically_secure_pseud... and that sometimes even "standardized" "cryptographically secure" turn out to be something else, e.g. the subtitle on that wikipedia page: "NSA kleptographic backdoor in the Dual_EC_DRBG PRNG" Also other considerations come into play when you have some specific needs and you understand the consequences: then it's not only black-and-white "safe" v.s. "not safe." For some purposes (as the mentioned generation of the floating-point numbers in some use cases) speed matters enough to sacrifice some "perfectness."

Mankaninen 8y ago

With respect to the bmp example: 1. Removing the bmp_get implies that the application needs to implement a shadow image if it needs to check the color o a certain pixel. Or even worse, take a direct peek in its void memory area. 2. void pointers instead of bmp_pointers makes it easier to create a mess, the compiler will not tell you that you called the bmp library with a pointer to a jpg memory area. 3. Not doing range checking in the library - but imposing that burden on the caller - is a bad practice. If the caller does the same - expects his caller to do the checking - we end up with a sequrity risk. Trying to minimize the library by pushing work to the application is wrong every time you expect the library to be used more than once. Despite these objections, I like libraries that are free of IO and mallocs!

spc476 8y ago
When I fell down into the rabbit hole of DNS, I wrote code to just encode and decode DNS packets [1]. All the existing libraries [2] had a complex API that provided a separate function for querying a few record types (A, AAAA, MX, TXT, SRV, maybe NS and SOA), leaving the rest unimplemented. They also tend to have complex network architectures to handle retries, caching, and parallel queries which could be hard to integrate into a project that had an existing network framework. Mine? Just two functions: dns_encode() and dns_decode(). No I/O. No malloc(). [1] https://github.com/spc476/SPCDNS https://github.com/spc476/SPCDNS [2] The ones I was looking at are written in C.
- lifthrasiir 8y ago
  > No malloc(). ...by having your own arena allocator! I do agree that it is quite doable in this particular case, but I always remember that a custom memory allocator of OpenSSL made Heartbleed much more devastating.
  - spc476 8y ago
    ... of memory passed in by the user! So it's up to the caller to make sure memory contains unclassified information.
8y ago

sytelus 8y ago

Please do not do this! There is so much bad advice in this article. Remember the rule: Your code should be simple, but not simpler. There is absolutely no need to abandon great facilities afforded by language and libraries to make things unreadable, undebugable and unmaintainable.

abiox 8y ago
could you be a bit more specific about what you feel is "bad advice"?
masklinn 8y ago
Abandoning some facilities does not "make things unreadable, undebugable and unmaintainable" and can allow them being used much more widely. The limitations seem similar to #[no_std] in Rust, and while that's not something to strive for at all costs if you can do without it allows e.g. embedded developers or kernel/OS developers to use the work.
- berti 8y ago
  > e.g. embedded developers or kernel/OS developers to use the work. I certainly agree that's one of the strongest reasons to avoid allocating memory etc. It's pretty clear that not many commenters have done any work outside a hosted environment... but I guess that makes the point that we're in fairly specialised territory.
chris_wot 8y ago
I don't think he's saying to do this in every library, it's just an interesting technique he uses for very minimalist libraries.
matheusmoreira 8y ago
>great facilities afforded by language Sometimes those aren't so great. For example, C has errno, a thread-local variable that gets set to the error code of the last function you called. Why can't the function just return the error code? I think it's strange how all the Linux system calls do return error codes but the standard library puts them in errno anyway. I really like writing freestanding C because I can avoid most of the legacy.

vortico 8y ago

Most things here are reasonable, but I don't see a point about having only one struct. If your state is better organized in lots of hierarchical structs, within lists, within other structs, your data will be easier to move around, copy, and zero in smaller chunks, and you can write functions which processes isolated segments of data rather than a huge global state.

matthiasv 8y ago
The point was about the user-facing side not the internal representation of state.
- vortico 8y ago
  Even then, it seems weird to prefer a big flat state rather than a state made of heirarchical sub-structures and arrays.
  - yason 8y ago
    As the user of the library I probably don't care about the hierarchies. If I want X the library can provide me a function to get X by looking up its internal substructures and arrays so that I don't have to.
deleted 8y ago
[deleted]
enriquto 8y ago
This is very sound advice. The interface of the library is intended to help the user of the library, not the developer of the library. The simplest interface is the best for the user, who does not want to know anything about the implementation details. In the ideal case, the developer and the api designer will be different persons who are not in good terms to each other. The more the developer hates the api designer, the better.

goofballlogic 8y ago

Love reading this stuff. When I grow up I want to be a C programmer.

tushartyagi 8y ago

I just want to understand that given the mostly negative reaction that's here at HN to the npm ecosystem which is based on the same "minimalist libraries" idea, how is this different? I'd appreciate if the response is not about JS and/or C, but about the minimalist libraries in JS, C, or any other language. Should I use a large number of small libraries? Should I wrap up some of the code which I use into a libraries even if that code is just a couple of functions without any data structure? Moreover, I'd admit that I'm a great fan of Chris Wellons blog posts which are pretty technical and original, and use some of his emacs libraries on a daily basis.

panic 8y ago
I think the difference is the network of dependencies. Even small libraries on npm often depend on other libraries (e.g., the is-odd library linked in the article depends on is-number).
jstimpfle 8y ago
The difference is that there is no package tool. These libraries are not dependencies that can disappear or whose API will break. You are expected to copy them into your source tree, or even use only the idea and make your own version. Also, as my sibling poster points out, they are self-contained.
coldtea 8y ago
>I just want to understand that given the mostly negative reaction that's here at HN to the npm ecosystem which is based on the same "minimalist libraries" idea, how is this different? It's different in that in C you don't pull in 200 dependencies which in-turn bring in another 10+ dependencies each. You just use 2-3 libs you need (and that they, in turn, don't require anything, or at best the POSIX standard libs), and that's it.
khawkins 8y ago
I think in recent years dogmatic minimalism has shown itself to be destructive. Time is wasted refactoring code and features are removed, reducing usability, all in service of an aesthetic that has lost sight of its purpose. Each of the guidelines listed independently represent good practices, in general, when applicable. It's worth considering the design choices when developing a library. But promoting a definition of minimalism implicitly promotes an all-or-nothing approach to development. The choice to not include memory allocation should be entirely independent of the choice not to include I/O. Pretending otherwise indicates that the choices aren't driven by pragmatism.

loup-vaillant 8y ago

I'm happy to say my crypto library¹ satisfies most of his criteria: It has 50 functions. That's too much, but it could be reduced to 10 if the user stick to the highest level facilities. There is no dynamic memory allocation, and no I/O (actually, it doesn't even depend on libc). The structures are defined in the header to allow the user to allocate them on the stack, but looking inside is unneeded and discouraged. [1]: https://monocypher.org https://monocypher.org

kstenerud 8y ago

This basically echoes my library building philosophy. The two biggest things are: 1. User-facing complexity: Keep the user interface just big enough to get the job done. Put the "90% of people" interface first and foremost and if you need to cover the other 10%, expose a different interface that's CLEARLY marked "Advanced. You probably don't need to use this". Don't get sucked into chrome plating everything. 2. Internal complexity: Keep your structures simple. Make your functions do one thing and exactly that thing, well. Keep your side effects to a minimum. And keep your dependencies low, because you can't trust that other people have done the same in their libraries.

xtrapolate 8y ago

> "The library mustn’t call malloc() internally. It’s up to the caller to allocate memory for the library. What’s nice about this is that it’s completely up to the application exactly how memory is allocated. Maybe it’s using a custom allocator, or it’s not linked against the standard library." OP's approach will indeed work for most "minimalist"/single-header libraries, but, I personally feel it pollutes the API you're exposing to your users. Depending on the specific situation, I may sometimes choose to expose a MODULE_CreateObject() and a MODULE_CreateObjectEx(custom_allocator, custom_deallocator). Internally, MODULE_CreateObject() calls MODULE_CreateObjectEx(), passing the module's default allocators and deallocators (ie. HeapAlloc and HeapFree). This strikes me as a more balanced approach. One caveat here, is that you must enforce consistency across usage - you don't want some API calls to use malloc() for allocation, whilst others use HeapFree() for deallocation, that would be a recipe for disaster. To ensure that, I would often set the allocators and deallocators once, when the object is first created. They may be set through the object's initialization function, and they persist as part of the object itself.

ajross 8y ago
> I personally feel it pollutes the API you're exposing to your users. Pollution is in the eye of the beholder. There are many circumstances where a project or subset of a project needs to work without a heap, they just don't necessarily overlap with the "application layer code in a virtual memory process" world your intuition is calibrated against. And sometimes this stuff needs to read a JSON object or decode base64 or utf8 too, and can't because the library is too thick.
- deckiedan 8y ago
  At this level, surely it's better to leave it to the "user" of the library - who can always write a wrapper for all their used libraries to the same style API for use in the rest of the program
- xtrapolate 8y ago
  > "Pollution is in the eye of the beholder. There are many circumstances where a project or subset of a project needs to work without a heap, they just don't necessarily overlap with the "application layer code in a virtual memory process" world your intuition is calibrated against." That's an argument in favor of offloading allocation/deallocation to the library's users, which is exactly the core of my, and OP's, proposals. We're saying the same thing here - developers should be able to determine/control how memory is allocated and deallocated. > "And sometimes this stuff needs to read a JSON object or decode base64 or utf8 too, and can't because the library is too thick." I'm losing you here. I honestly feel that my proposal is all about keeping the API as simple as humanely possible, without compromising the library's flexibility when it comes to the scenarios your mentioned earlier. In your case: BASE64DECODER_Decode(...) BASE64DECODER_DecodeEx(..., allocator, deallocator) BYTE * BASE64DECODER_GetDecodedBuffer(handle) BASE64DECODER_Free(handle)

joveian 8y ago

Personally, I'd add "don't write to your own memory" (with various stack use rules based on expected library use) and relax the "no structures" rule to encourage code that can be used from multiple threads simultaneously. Make the first argument always be the internal use data.

jokoon 8y ago

I don't think there are languages similar to C in term of simplicity, close to the metal and speed. C++ is good enough for me, but it's so slow to compile, and I don't use its most advanced features. I wish there was a language between C and C++, without the complex semantics you can find in rust and other exotic syntax. I don't necessarily love C or C++ in term of feature, but the syntax is just what i need. Why can't language designers write a language that is closer to C, with fancy features that don't change the language so much?

felixangell 8y ago
Maybe you would like the BetterC mode in the D programming language... if you mean you like C for it's syntax too. A lot of modern systems prog. languages seem to adopt a more modern syntax, i.e. types after the names rather than before, no semi-colons, etc. D stays true to C in this regard and offers a lot of fancy features. And the BetterC mode sounds suited to your requirements in that the language features doesn't over complicate things.
Aardappel 8y ago
https://ziglang.org/ https://ziglang.org/ is almost exactly what you're asking for.
Bulat-Ziganshin 8y ago
I personally prefer Nim. there is also Zig and D.

sevensor 8y ago

Maybe I'm just noticing it more, but I think there's more discussion of how to write C well than there used to be. I speculate that the attention Rust has brought to safe systems programming has caused an uptick in interest in closer-to-the-metal languages in general, and spurred C programmers to show that there are reasonable ways to write C as well. It may be an unanticipated result of Rust's popularity that the quality of C programming improves. (Or perhaps that was the plan all along?)

Gibbon1 8y ago
What I've noticed is the lead time for all sorts of things used in small embedded systems has gotten terrifyingly long. What says to me that there is a lot of embedded work going on. Also in the last 5 years people have abandoned the JVM as a end all be all platform which puts you squarely back into native code again.

hedora 8y ago

I’d argue these APIs could be further minimized by using a struct with a void * and a size_t in it, along with bounds checking accessors. This would eliminate most of the ugliness in the post-allocation calls, allow for the deletion of most error checking code in each library, and would harden BMP parsing “for free”.