4 ms·

> Writing a memory allocator without obvious (and not so obvious) bugs is really hard. Actually, I disagree. Putting aside the implication you had that writing

> Writing a memory allocator without obvious (and not so obvious) bugs is really hard. Actually, I disagree. Putting aside the implication you had that writing bugless software is possible, I think that memory allocation is straightforward. The interface is simple and the gotchas haven't changed since memory protection standardized. Writing a correct allocator amounts to a checklist of allocation and free behavior, plus some extra stuff like "how hard/probable is it to detect use after free" &c. Correctness, property calculation itself, and proving (theoretical) performance of your algorithm is not so hard. Now writing a general purpose one that doesn't trigger catastrophic performance against one app of many is really hard.

jacquesm 9y ago
I'm going to have to disagree with you. Your average programmer isn't going to be able to write a linked list implementation that is correct, let alone a whole allocator and free mechanism. I've seen enough code by now to be strongly convinced of this and it will take something fairly momentous to get me convinced of the opposite.
- fish_fan 9y ago
  Well, that seems to be more of a problem with C familiarity than memory allocation. If you can write correct data structures in C, you have rudimentary knowledge of linkers and mprotect (or whatever is analagous on Windows), you'll be fine.
  - jacquesm 9y ago
    That's what you'd think. And then you go and review code written by people who know their stuff. And you find fault after fault after fault. A well known HN'er commisioned a very simple little bit of code as a test and got sent a lot of submissions to evaluate (100+). A very large number of those contained obvious bugs, and this is from a group that would likely consider themselves to be 'above average'. I've got 30+ years of C under my belt and I still would be very careful to make the claim that I could write a fault-free allocator on the first try. Three years ago or so this exact problem came up in one of my jobs and I reviewed the code of someone who was pretty good by most measures. The number of bugs was embarrassing. So, maybe my experience is totally different than yours and this is all at the level of anecdotal evidence but it appears to me that writing bug free code is hard, in any language.
- fao_ 9y ago
  > Your average programmer isn't going to be able to write a linked list implementation that is correct, let alone a whole allocator and free mechanism. Are... linked lists really that difficult to fuck up? How??

jacquesm 9y ago

I'm going to have to disagree with you. Your average programmer isn't going to be able to write a linked list implementation that is correct, let alone a whole allocator and free mechanism. I've seen enough code by now to be strongly convinced of this and it will take something fairly momentous to get me convinced of the opposite.

fish_fan 9y ago
Well, that seems to be more of a problem with C familiarity than memory allocation. If you can write correct data structures in C, you have rudimentary knowledge of linkers and mprotect (or whatever is analagous on Windows), you'll be fine.
- jacquesm 9y ago
  That's what you'd think. And then you go and review code written by people who know their stuff. And you find fault after fault after fault. A well known HN'er commisioned a very simple little bit of code as a test and got sent a lot of submissions to evaluate (100+). A very large number of those contained obvious bugs, and this is from a group that would likely consider themselves to be 'above average'. I've got 30+ years of C under my belt and I still would be very careful to make the claim that I could write a fault-free allocator on the first try. Three years ago or so this exact problem came up in one of my jobs and I reviewed the code of someone who was pretty good by most measures. The number of bugs was embarrassing. So, maybe my experience is totally different than yours and this is all at the level of anecdotal evidence but it appears to me that writing bug free code is hard, in any language.
fao_ 9y ago
> Your average programmer isn't going to be able to write a linked list implementation that is correct, let alone a whole allocator and free mechanism. Are... linked lists really that difficult to fuck up? How??