9 ms·
Malloc Challenge
- esaym 10y agoLooks like fun. Wish I had time to join in :(
- codr4life 10y agoOh come on, there's always time for fun :)
- vvanders 10y agoAwesome challenge. 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.
- codr4life 10y agoGood call, writing C/C++ without having a grip on memory allocation is a recipe for exactly the kind of disaster we're in right now :)
- MichaelMoser123 10y agoDepends on the domain - i suspect that this question would cut off qualified application programmers who are not perfectly familiar with lower level/infrastructure code.
- codr4life 10y agoNot if they're writing C/C++; it doesn't really matter how hard you try to hide memory management when the whole language is designed around memory and pointers. What kind of programmer is that, anyway? Who can only program specific api's, as long as they don't touch the wrong parts of the language.
- MichaelMoser123 10y agoThere are different strategies for handling perf problems of memory allocation - you can cache blocks of the same size in some linked list within the application (free list) or you can reconsider the allocator/allocation strategy. Both get the job done. Preferance of the first solution does not make you a worse programmer.
- codr4life 10y agoWhat you're describing is essentially a pool, which could be thought of as a kind of allocator since it provides an allocation strategy. There's even one in the challenge that does just that. Nothing makes you a worse programmer except refusing to learn.
- deleted 10y ago[deleted]
- vvanders 10y agoI would argue that except in the case of legacy software there's no reason to be using C/C++ for something that doesn't care about performance or memory overhead. Even then it's useful to know how sentinel values and other features work if you don't dig into the performance aspect.
- codr4life 10y agoWhat kind of software doesn't care about performance or memory overhead? And why would anyone want to use it?
- tedkalaw 10y agoat UIUC, there's a project in the systems class (CS241) that is exactly this. there's a leaderboard with projects and how it compares to the system malloc for a variety of metrics 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 ;)
- kjdal2001 10y agoI agree. That assignment was one of my favorites. It was a lot of fun because it was fairly easy to get something that functioned, and as you came up with ideas for making it better (or just got ideas from reference implementations), you could watch your metrics get better or worse.
- codr4life 10y agoExactly the experience I'm trying to provide with the challenge. For the price of forking the repository you get a framework for trying out and comparing your own allocation strategies.
- morio123 10y agoWhat's the incentive? Credits? Give me a break. 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.
- codr4life 10y agoPushing the state of the art in application level memory management? Too lofty? Come on, it's fun :)
- codr4life 10y agoFurther, the complexity and need for flexibility is exactly the problems that I'm trying to deal with here. That's why the challenge encourages splitting the allocator up in Unix-like pieces and stacking them to get the desired features.
- gbarboza 10y agoAll past 15-213 students go in search of their malloc lab solution.
- anaccountwow 10y agoCurrent 15-213 student here in the middle of malloc lab, my current solution is probably worse than anything in that link (left unclicked).
- codr4life 10y agoGive it a spin, you might learn something. Your class is probably focusing on general purpose, system level allocators; a much thornier problem without any really good answers. As How to Solve It states; if you can't solve the given problem, try to solve a simpler version of the problem.
- bichiliad 10y agoIn retrospect, that class was amazing. At the time, I hated it.
- jwatte 10y agoHow about: mmap() a few terabytes of virtual space let malloc() be pointer addition and let free() be a no-op?
- MichaelMoser123 10y agoExcept if the program needs to run for a non trivial duration or you need many instances of it at the same time/run at the same time as other processes. 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.
- codr4life 10y agoSure, the idea is that you can have several allocators around for different purposes. One allocator per http handler that reserves enough memory and resets the pointer between request makes the idea more feasible than insisting on the centralized general purpose perspective.
- jasone 10y agoGiven the evaluation criteria, this sounds like a winner to me.
- sparky_ 10y agoSomebody out there is doing this in production. I guarantee it.
- userbinator 10y agoBefore I read the article or the comments I thought it would be about rewriting code to not use dynamic allocation, which is IMHO a far more interesting (and challenging to some) exercise. Contrary to common expectations, it often doesn't mean e.g. restricting the lengths of inputs, and can result in simpler, more efficient, and less buggy code. From my experience it is usually those with a background in higher-level languages who overuse malloc().
- codr4life 10y agoYou should have a look at the repository README. libc4life bends over backwards to provide stack allocation and value semantics wherever possible. Right now I'm working on an ordered map that allows user defined key/value sizes which lets it allocate all the memory it needs in one block and provide value semantics.
- strictfp 10y agoAny tips or links on how to do this?
- greenshackle2 10y ago>[libc4life] is aiming for simplicity and leverage; and it makes a real effort to get there by playing on C's strengths, rather than just inventing yet another buggy Lisp. Ouch, right in the feels, I've been working on https://buildyourownlisp.com 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.
- xenadu02 10y agoI'm sure it inflates one's ego but the chances that they've avoided writing any exploitable security vulnerabilities is almost zero.
- codr4life 10y agoShow me a software stack without those kinds of bugs; they're all written in C somewhere down the line; enormous amounts of complicated C, written by coders of varying competence. At least in my stack I can keep it simple and fix anything that needs fixing.
- nothrabannosir 10y agoHe/she meant: two programmers of equal skill and security conscientiousness will create less exploitable security vulnerabilities per "unit of functionality", using C and <memory safe language> respectively, ceteris paribus. "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.
- pheo 10y agoLet's all just agree to use Perl. It's just dynamic, functional, OOPy C isn't it? 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.
- codr4life 10y agoBeen there, done that. Even went to YAPC EU in Pisa and had a whiff of Larry. Not for me, that's all I can say. It's too loose, too much shooting from the hip. There's a lot of good ideas in there though. 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.
- otabdeveloper 10y agoA malloc benchmark that doesn't measure multithreaded performance is worse than useless.
- codr4life 10y agoOnly if you insist on clinging to a general purpose, system level perspective on memory allocation. No amount of thinking and reasoning about these issues is useless.
- chrisseaton 10y agoDoesn't the benchmark also just allocate and then immediately free? I think I could specialise for that particular use pattern and make it very fast just for the benchmarks. Will that not work for some reason? A good benchmark might be a replayed set of allocate and free operations from a large real application.
- codr4life 10y agoIt does, but with random sizes. If think you have a way to make that run faster than the provided implementations, then please show us.
- chrisseaton 10y agoChallenge accepted (if I can find the free time)!
- huhtenberg 10y agoWhile OP might've phrased it more politely, he's got a point - allocators that aren't designed for multithreaded use are ultimately oversimplified toy projects. 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.
- deleted 10y ago[deleted]
- throwaway4891a 10y agoSee also: - http://locklessinc.com/benchmarks_allocator.shtml http://locklessinc.com/benchmarks_allocator.shtml ($, use as a minimum performance target) - http://www.nedprod.com/programs/portable/nedmalloc/ http://www.nedprod.com/programs/portable/nedmalloc/ - http://phk.freebsd.dk/pubs/malloc.pdf http://phk.freebsd.dk/pubs/malloc.pdf [PDF] (phkmalloc) - https://github.com/gperftools/gperftools https://github.com/gperftools/gperftools (tcmalloc) - https://github.com/ivmai/bdwgc/blob/master/malloc.c https://github.com/ivmai/bdwgc/blob/master/malloc.c - https://github.com/jemalloc/jemalloc https://github.com/jemalloc/jemalloc - http://gee.cs.oswego.edu/dl/html/malloc.html http://gee.cs.oswego.edu/dl/html/malloc.html (dlmalloc)
- codr4life 10y agoThank you, but that's not the problem I'm solving. Any one of those could be used to feed any implementation from the challenge. The idea I'm pushing is using local knowledge to customize memory management, instead of trying to find the perfect one-size-fits-all solution.
- mathgenius 10y agoAha, I see.. Very nice. Like the following implementation of free() as commonly used in HFT: void free(void *mem) {}
- codr4life 10y agoThat's a totally valid solution to some problems :) Having access to a decent allocator protocol lets you do that and more.
- EdSharkey 10y agoI recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes. 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?
- JoshTriplett 10y ago> 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.
- EdSharkey 10y agoThis is so rad.
- codr4life 10y agoThe slab reference allocator from the challenge does that, but adds a segmented approach where the memory is allocated in N sized blocks. Go has decent support for doing these kinds of tricks; but nothing really runs faster since there's still too much magic behind the scenes. I suspect the story is the same in Rust land but I honestly never got passed the lifetime hump, too much ceremony for me.
- Jweb_Guru 10y ago
- wfunction 10y agoWhat if I want to write a malloc that requires the size to be stored separately? (i.e. one that needs to be paired with free(ptr, length) rather than just free(ptr) for good performance.) Wouldn't that provide more flexibility in the challenge and be more useful (e.g. for C++'s std::allocator)?
- codr4life 10y agoThe pool reference allocator does just that internally. It prefixes each allocation with a block containing the size among other things. Either base your implementation on top of that or take the idea and run with it.
- wfunction 10y agoYou totally missed the point of my question. I was NOT asking "I have an allocator that doesn't store the buffer size; how can I use it?" 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?"
- ben_bai 10y agoI would not do that. Userspace Apps have way to many ways to screw up memory managment already. Allowing them to buf=malloc(128); free(buf, 256); seems dangerous, if free can't check the size. But kernels sometimes do just that ( free(ptr, size) ), for performance reasons and because "kernel writers know what they are doing".
- codr4life 10y agoThat's a pretty nasty requirement on top of an allocator protocol; I wouldn't want to use it, or debug it for that matter, yikes. 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.
- nujabes 10y agoI'm trying to build it in MacOS but I'm inundated with errors. For example malloc_perf.c:39:3: error: implicit declaration of function 'clock_gettime' is invalid in C99 [-Werror,-Wimplicit-function-declaration] BENCHMARK("basic", &c4malloc); ^
- david-given 10y agoLooking at the implementation of libc4life, I think it's full of gcc-isms. C4DEFER() is this: #define _C4DEFER(code, _def) \ void _def() code; \ bool _def_trigger __attribute__((cleanup(_def))) \ #define C4DEFER(code) \ _C4DEFER(code, C4GSYM(def)) \ So, nested functions and gcc attributes. 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-nested-functions 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.
- codr4life 10y agoI had to draw a line somewhere, and C99 with GNU extensions is where it is. Cleanup attributes and anonymous functions are just too useful to leave behind. And since I'm using clang to develop this, I'm pretty sure it supports nested functions just fine.
- david-given 10y agoHm. Sounds like they added them --- nested functions certainly weren't supported the last time I looked (because, as you say, they're far too useful, and I hated having to give them up). Have you had any reports about problems on, e.g., OpenBSD, related to needing an executable stack?
- 102100101 10y agoGitHub apparently infests every code snippet in existence. People work for free and GitHub gets the credit/branding.
- codr4life 10y agoToo be fair, they're also providing a decent service for free.
- jheriko 10y agoits an interesting exercise for learning but the code style is awful. 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...
- zzzcpan 10y agoCoding style never saved anyone's C code from being insecure. So it's not something to be concerned about, C code is generally awful on its own.
- codr4life 10y agoWhat's awful with C on it's own? You can write all sorts of code in C.
- codr4life 10y agoThe naming discussion stops here; if you have nothing more constructive to add, I suggest silence. They are not mistakes, they are born out of 30 years of experience with naming things. We will never come to an agreement on this, and it's ok. Why not skip ahead to the more interesting discussions that actually lead anywhere?
- deleted 10y ago[deleted]