Unix's original malloc took a memory map and a size — and it was better
The lost malloc()
Digging through the Unix V4 source, the author finds Dennis Ritchie's malloc.c: malloc() and mfree() take an explicit memory map (coremap or swapmap) and mfree() also receives the size being freed. That interface makes it trivial to partition memory, cap third-party allocations, and discard a whole region at once. Earlier code used a simple linear allocator that calls sbrk() and never frees. The post traces allocation from V4 through V8, including early ALLOC and new macros.
Those are just infinitely-times better interfaces than traditional malloc()/free(). Imagine using a library that has such an interface. You could deallocate all its memory resources by just discarding the entire region you delegated to it.
- adrian_b
The author did not really find from where SIMULA 67 had taken "new".
In November 1965, C.A.R. Hoare published an extremely influential paper: "Record Handling". This was a proposed extension for the successor of ALGOL 60.
Almost all of the features that were added in SIMULA 67 over its predecessor, the SIMULA language, come directly from the paper of Hoare, with two big exceptions: class inheritance and the "virtual" procedures, which were invented by the SIMULA 67 creators (Kristen Nygaard & Ole-Johan Dahl) and which are essential for object-oriented programming.
The SIMULA 67 keywords "class" and "new" were taken from Hoare's paper (Hoare actually had taken "class" from COBOL 60, which used a very different terminology in comparison with ALGOL 60, among the many differences being the use of "class" instead of the "type" used by ALGOL 60).
Hoare's paper discussed a lot of programming language features, most of which were new, including defining structured types with constructors and destructors, discriminated unions (taken from John McCarthy), enumerations, the NULL pointer and many others.
SIMULA 67 was one of the first languages which implemented many of the features proposed by Hoare. Other languages that implemented some of the proposed features were IBM PL/I, ALGOL 68, then a couple of years later, in 1970-11, Pascal.
The keyword "new" had already been used for the first time by Niklaus Wirth, but at Wirth it had a different meaning than at Hoare. It declared a variable […]
- OskarS
> Not only that, mfree() receives the size of the object it is deallocating, as it should.
I've always thought that one of the biggest tiny mistakes in the history of this industry. It means, more or less, that you're forcing the memory allocator to keep track of these sizes when it shouldn't have to. There's virtually no sensible case where the person calling free() doesn't know the size of the allocation, so now we're keeping that book-keeping twice, in "user-space" and inside the memory allocator. Like, think about the cases when you'd call malloc:
* For allocating a single object of type T, the size is just `sizeof(T)`, so you can just pass that to free()
* For allocating an array of objects, the size is `count * sizeof(T)`, and I can't think of a single time where you DON'T know what `count` is. It's either statically sized (in which case it's just a constant), or if you have a dynamically growing array, you need to keep track of the reserved space to know when you reallocate. If nothing else, you need it for bounds-checking.
* For chunks of raw memory, you also presumably know when deallocating what the size of the raw memory you allocated is, for the same reasons as the previous point. Like, just having a raw char* pointer lying around with no size information is just terrible C practice.
If you truly don't know the size of your allocation (very hard to imagine when this would ever happen), you should be forced on the user-side to keep track of it somehow, not delegate […]
- veltas
I don't associate with the author that well here because I'm not hyped about 'arena allocators' and I don't really care that free doesn't receive a size. I think the interface was okay.
Also 'arena allocators' (this meant something different like 20 years ago so I think the name just got rebranded) are not that good, they make some things easier and improve performance sometimes, they also are liable to use more memory and cause more fragmentation if not used with care. That is one of the many reasons why we slowly evolved away from the old linear allocators, but also because we just wanted a simple and flexible interface to hide complexity.
- fjfaase
The sbrk system call in linux is still available to get more heap from the operating system. So, memory is still allocated in a linear fasion and never released again. Maybe now functions like mmap change this. I used sbrk to implement malloc for a very limited standard libary implementation.
- jdw64
When I was a college student (15 years ago), I first encountered C through A Book on C, and C seems like a language that is simple but can really do a lot. Looking at how old this language is, and how many concepts already used in modern languages were tried during its development history, is surprising. It's surprising that the concepts I thought were modern techniques today were already being tried decades ago—that is, before I was even born.
It's amazing that a method like the Bump Allocator was already tried.
How were the senior programmers able to do all of this? I'm just amazed.