Re: [TUHS] Memory management in Dennis Ritchie's C Compiler

[Paul Winalski <paul.winalski@gmail.com>]

On 8/17/20, Jim Geist <velocityboy@gmail.com> wrote:
> You beat me to my response. malloc/free are great for long running
> processes where memory can't just infinitely increase, but there's a ton of
> stuff in a compiler -- types, expressions, symbols -- that survives until
> the process exits. There's benefit in both space (because you don't have to
> add headers to the blocks as malloc() does, so free() can work) and time to
> doing it this way.
>
The other issue is locality of reference.  Data structures such as the
symbol table get built up gradually as the compilation processes each
routine.  Typically the symbol table is stored as a hash table where
each entry is a pointer to the actual symbol table entry data
structure.  If you malloc() each symbol table entry individually, they
can end up scattered all over the virtual address space.  It's not as
important these days, when main memory is measured in gigabytes, but
back when machines had less real memory, the scattering could lead to
excessive page faulting.  Much better to allocate symbol table entries
in chunks, and the easiest way to do that is to give the symbol table
its own mini-heap.

VMS implemented the mini-heap concept (VMS calls them zones) back in
its first release in 1978.  Dave Cutler took the concept to Windows NT
(Microsoft calls them private heaps).  Lots of applications have built
their own mini-heap system on top of sbrk(), but has a library of
mini-heap-type APIs ever been distributed on Unix?

-Paul W.