Malloc Challenge
vicsydev.blogspot.com
vicsydev.blogspot.com
Ouch, right in the feels, I've been working on https://buildyourownlisp.com in my spare time. (EDIT: I was looking for a name for the repo, YABLisp it is.)
> coding in C is a welcome therapy after seemingly wasting years exploring various ways of pretending the hidden complexity in my stack was someone else's problem
I've noticed several older talented programmers express similar feelings. I was watching Casey Muratori's Handmade Hero stream, where he writes a game in C from scratch, and he said, I don't know who would watch this except aging C programmers.
I'm less than 30 but I already feel like an aging C programmer. Most OOP seems like a morass; I've switched to writing my own projects in C and my prototypes in C-like Python. But I wonder what hope there is for people like us in the industry, which seems to be moving ever further away from this type of programming.
"Easier languages attract less skilled devs", "higher level languages allow you to create more complex programs", yada yada. Could all be true, but it's besides the point.
For the armchair discourse it's beside the point, but for real-world development, it's what matters the most.
And even if it did, rates matter.
I went back to C and Lisp in my spare time because I'm already invested in those languages, between C itself, and CPython.
The common feeling I've seen repeated is doing OOP for a while then getting tired of it, and casting it off.
> I'm sure it inflates one's ego
I'm sure that's true for some, but it would be shortsighted to think all programmers who dislike OOP are just full of themselves and don't have any valid insights.
I'm not sure it's a sane thing to do, arguably I should just write the thing in C in the first place, but I have more experience with Python so it's still easier to me.
Rewriting a for..in as a for with counters is relatively trivial, compared to re-implementing a complex class hierarchy in C.
You can write procedural Python, and it will look kinda like C if you squint. Cython even lets you use C types directly, with a simple syntax. As I said, maybe not the sanest thing to do, everything is an object in Python so you can never really get away from it's object-oriented nature.
Python is also not a functional language.
Python provides language structures that allow you to use both styles of programming OOP and functional as-if-it-was.
All I meant is that everything is an object. It doesn't have strong encapsulation, but you can't get away from its weak encapsulation, since the basic types are objects.
C is still very popular (along with Asm) in embedded systems. ARM cores and large memories are certainly getting very cheap, but still not at the level of many of the 8 and 16-bit microcontrollers.
I find OOP often overused too, but it can be genuinely useful in certain situations where there is a very strong association between some data and the operations on it. For this reason, I tend to use a subset of C++ in a style that would probably enrage a lot of the "C++ is not C" advocates.
Am I wrong? Hope so.
The last time I was looking for a job, I had been doing non-embedded, including kernel and low-level for 8 years or so, and I had the darnedest time finding embedded positions to apply for, let alone get calls back from.
Startups that do embedded seem to mostly get the embedded done in the MVP stage, and by the time they're looking to grow, they've got a (small) team already doing that work.
In fairness, this is partially self-inflicted; iRobot has been on the monthly whoishiring threads for as long as I've been looking for jobs in the Boston area, but I decided long ago that I'd never work in defense (or finance).
Recently, I've added to that list "companies whose business model is selling their users' information" (many of them these days), and "companies whose entire sales pitch plays on your fears" (a recruiter tried to put me in touch with a company that does baby monitors that measure some basic health parameters, and their promotional video was appalling to me).
I kind of stuck a toe across the first line, and tried talking to somebody Fitbit-esque, but never got a call back. I also wound up with a connection into an electronic paper company, but that went cold after submitting a resume. Ditto a company that does automotive suspension stuff.
I realize that being out of the community for a while makes it hard to get consideration if there are other candidates who have current experience, so I started a personal project building a clock out of VFD tubes, and added a github link to my resume before submitting several of those. That didn't seem to help.
I got hired doing non-embedded before I finished the clock project. I'm at the point of needing to learn EAGLE, lay out boards and get them made. That was a year and a bit ago; right now I've got other projects that take up my weekend time.
To respond directly to your point, I'm willing to bet that there are two factors at work: 1. Supply and demand. If demand exceeded supply, I would think that I'd at least be able to get a call back with my background. 2. Hardware is a hard row to hoe. There's a lot less capital invested in a hotness.js project that flops, and it's a lot easier to scale if it takes off. No, it's not necessarily easy, but there's a wide gap between "provision more instances on EC2 and fix the bottlenecks in the architectures" and "the factory is already at capacity and the supplier for the key part is backordered for 3 months". The money that doesn't need to go to covering those risks can go into your pockets.
Embedded now has plenty of that 'large end' work now, since SOC/SOM prices have come way down.
As for iRobot, I actually called them. They split in half; their whoishiring entry is the Roomba people not the military people. But they're strangely still putting 5 tiny controllers in each vacuum instead of one hefty processor. And they're an east-coast Boston company, quite a bit different from a west-coast startup.
Re: Eagle. My college roommate wrote a board-layout package with some friends called Eagle years ago. He's from Austria. I wonder if its any relation to the modern product?
We have an embedded systems team at work but they barely have enough work to keep the current small dev team busy.
- http://locklessinc.com/benchmarks_allocator.shtml ($, use as a minimum performance target)
- http://www.nedprod.com/programs/portable/nedmalloc/
- http://phk.freebsd.dk/pubs/malloc.pdf [PDF] (phkmalloc)
- https://github.com/gperftools/gperftools (tcmalloc)
- https://github.com/ivmai/bdwgc/blob/master/malloc.c
- https://github.com/jemalloc/jemalloc
- http://gee.cs.oswego.edu/dl/html/malloc.html (dlmalloc)
void free(void *mem) {}
One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you describe as a slab allocator, because they never free()'d their allocations, they just recycled the pool after each frame had been rendered.
I kindof see slab allocator as a happy middle ground between allocating temporary memory from the stack and full-blown free-list allocator (or whatever your classic malloc implementation is.)
Are there any high level languages that have the ability to provision fast memory allocation pools like a slab where garbage collection occurs when the slab is no longer accessible, for instance?
Rust has several slab allocation libraries, such as the "slab" crate. They use lifetimes to ensure that the slab outlives the objects stored in it.
I think the most you can say of an arena is that it's usually a contiguous region of memory from which smaller allocations are made, and which can be efficiently freed as a whole. An arena may only support fixed-size allocations, or a range of sizes; it may or may not support deallocation. However, in many cases it's natural to require multiple regions to satisfy all allocation requests for a particular context (task, generation, etc), so don't be surprised if an implementation labels a collection of contiguous regions an "arena".
The term pool is similarly ambiguous, but usually implies support for deallocation and recycling of memory. It does not necessarily imply a contiguous region, but that's a natural optimization in a language like C.
Slab is less ambiguous because it has a very specific origin in SunOS--allocation and deallocation of fixed-size, often typed objects (to optimize initialization).
https://gcc.gnu.org/onlinedocs/libiberty/Obstacks.html
Obstacks provide objects by drawing them from a linear piece of memory incrementally. Additionally, this is treated like a stack: you can free an object, but that also pops all objects allocated since that one.
Maybe a register could be used to keep track of the current pointer into this pool, and every time you called into a new function the call could increment the pointer enough for all the usage in a function, and when the function returns it could set it back, automatically deallocating the usage with almost no cost at all?
When the minor heap is exhausted you then take the hit of scanning the heap for objects which are still live and moving those to the major heap. If you're doing it right then most objects on the minor heap will be dead by this point so only a few will need to be moved.
A fairly common trick for games or any code with little tolerance for GC pauses is to size the minor heap large enough that every allocation required in a single frame can be satisfied from the minor heap, and then do an explicit sweep of that heap at the end of the frame / before waiting for a network message / while waiting for user interaction.
This might be the talk you're referring to.
Back when I worked in a C/C++ shop we'd use this as an in-person interview question for senior positions. The candidate was never expected to finish but more as a springboard to talk about the pro/cons and issues they'd seen with performance/etc of various approaches.
Preferance of the first solution does not make you a worse programmer.
Even then it's useful to know how sentinel values and other features work if you don't dig into the performance aspect.
Still you have obstacks where free is a no op - here you allocate off the stack (assuming that you dont need to store pointers after you are done). Ngnix and apache allocate a chunk of memory per connection and free it all when the connection is finished - but this results in high memory fragmentation, also this is not so good if connections take a long time.
J/K. I think this is an interesting problem in that its a sandbox for allocation and GC in pretty much any dynamic interpreter's implementation. My qualm is that it would be "easy" to tune for the test. Consider the difference between dynamic blocks of a small but fixed size, getting alloc'd/freed in an asynchronous way (a network stack?) versus a pool of variable byte length strings getting shuffled around (a key/value store?). Those are simple, but drastically different, strategies for your heap. There won't be a "best" answer besides the limits of your problem domain.
Agreed. Which is why the 'one size fits all' approach might not be the best way to go. The main reason I decided to launch the challenge, and encourage a more combinatory approach with local special purpose allocators.
It's really not that much of a challenge to knock together a (slab + heap + free list) allocator that will perform really well single-threadedly. However it will be nearly impossible to adapt it to the multithreaded context. It is a considerably more complex task and the end result will end up looking like a rocket ship compared to a simpleton that even the best single-threaded allocator will look like.
this is definitely one of the best projects i ever did in school and a great coming of age project. worst case, there's always an implementation at the back of K&R ;)
It's fairly easy to beat the given examples but in the end heap management is heavily dependent on application, client code, platform, hardware and many other criteria. It's a very complex problem space and what matters here is how existing important code behaves and continues to behave given that existing code has most likely made assumptions how the heap is managed.
glibc is a good example of a perfectly fine compromise not optimized for any particular use case. Anyone who has had performance issues with it has most likely already implemented their own solution for their problem set.
It might much more worthwhile to develop a set of malloc like implementations a developer can chose from instead of going for a fits all approach.
I was asking, "I don't think an allocator should need to store the buffer size internally; why not formulate the challenge so that the block size doesn't need to be stored?"
buf=malloc(128);
free(buf, 256);
But kernels sometimes do just that ( free(ptr, size) ), for performance reasons and because "kernel writers know what they are doing".
And you don't need to store the size. The slab allocator doesn't store any information except how far into the current slab it's already dished out memory.
#define _C4DEFER(code, _def) \
void _def() code; \
bool _def_trigger __attribute__((cleanup(_def))) \
#define C4DEFER(code) \
_C4DEFER(code, C4GSYM(def)) \
Nested functions awesome, but they're a gcc extension, and only supported on some architectures anyway, and AFAIK only work if you have an executable stack, which is frowned on these days (because they have to create a callable thunk to stash the nested function's context pointer).
http://stackoverflow.com/questions/8179521/implementation-of...
My understanding is that clang doesn't support nested functions, but it does have its own non-standard extension, blocks. But of course that's still not standard C.
I'm currently writing clunky C89 code for an old compiler (and occasionally, K&R C!), and I got really excited by this library for a moment, but... nope. Non-standard. Can't use it.
Have you had any reports about problems on, e.g., OpenBSD, related to needing an executable stack?
Nothing, but I seldom hang around in the BSD crowd these days.
freel instead of freelist? ffs.
abbreviating memory to mem is enough of a mistake in the standard library without going further to m like malloc does and some of the examples here.
still, much respect, to the coder4life for making such a good effort and having such an awesome name...