5 ms·

>no memory management is the memory management policy in 9cc. We allocate memory using malloc() but never call free(). >I know that people find the policy odd,

>no memory management is the memory management policy in 9cc. We allocate memory using malloc() but never call free(). >I know that people find the policy odd, but this is actually a reasonable design choice for short-lived programs such as compilers. I'm strongly disagree at this point. Memory management is important even for short-lived programs. It would bring burden to the OS if you invoke this kind of "short-lived, memory-management-free" programs multiple times. >This policy greatly simplifies code and also eliminates use-after-free bugs entirely Not facing it is definitely not a good way to solve a problem. It's a bad attitude as a programmer be honestly.

cperciva 8y ago
> Memory management is important even for short-lived programs. It would bring burden to the OS if you invoke this kind of "short-lived, memory-management-free" programs multiple times. All the memory is freed when the process exits. Why does it matter if you run the program multiple times?
- sifoobar 8y ago
  It will put more pressure on the allocator when running, doing that a lot will likely have some kind of cumulative consequence down the line. I know from experience [0] that even reusing allocated memory rather than bouncing it back to malloc can have dramatic effects. [0] https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h
  - cperciva 8y ago
    Sure, but if you're not freeing memory you don't need a real malloc. You allocation function can be just "top += allocsize".
    - wrs 8y ago
      Yes, that's commonly known as "arena allocation" and has been used for decades in programs that have well-defined phases that create lots of connected objects with the same lifetime, like compiler passes, RPC serialization layers, or query planners.
  - tptacek 8y ago
    Wait, doesn't it do the opposite? The big thing that "pressures" an allocator is fragmentation, which you don't get at all if you never free.
    - bakul 8y ago
      With no freeing, memory used is the sum of all allocations. With freeing, it is max of the allocation for active objects at any given time. The former can ask for much more memory from the OS for some programs that generate a lot of temp garbage. Though this probably doesn’t matter for a C compiler - unless it is required to compile megabytes of generated code!
      - tptacek 8y ago
        An allocation you don't have to free is, at the margin, a simple pointer increment. It's the need to free memory that makes allocators expensive, not the amount of memory they allocate. This is why performance-sensitive programs use pools, arenas, and other preallocation strategies.
        bakul 8y ago
        What I was getting at is that non-freeing programs would use much more memory. This doesn't increase the "pressure" on the allocator for such a program but does increase the pressure on the OS (that has to handle memory requests for many concurrently running programs).
  - wtracy 8y ago
    Malloc doesn't interact with the kernel at all. The kernel sees pages, not the data structures that malloc manages. The kernel doesn't even know whether you free()'d the memory by the time the process exits. There is exactly zero difference from the operating system's perspective between freeing and not freeing the memory before program termination (except that one might have a higher peak memory usage). The classic implementations of several standard Unix utilities deliberately never deallocated memory for performance reasons. If there was a problem with this practice, I would expect Bell Labs--of all places--to know not to do it.
    - dexen 8y ago
      >There is exactly zero difference from the operating system's perspective (...) Close, but not quite: in case of larger allocations, malloc() tends to use mmap( , , , | MAP_ANON) rather than brk() to request memory from the OS. For example, the glibc's malloc() uses mmap() when requested size exceeds MMAP_THRESHOLD, which is 128kB by default. The mmap() approach gives large, continuous memory blocks that can also be easily free()'d via munmap() with little to no bookkeeping needed[1] - not being subject to the same fragmentation woes as memory allocated via brk() - as long as your address space is significantly larger than allocated memory. That aside, I fully agree with the author of 9cc. [1] in fact a simplistic libc memory allocator could directly wrap malloc() around mmap(), free() around munmap() and realloc() around mrealloc(), leveraging the in-kernel allocator at the cost of one syscall with at least two context switches at each call - i.e., slowww
      - cperciva 8y ago
        Using mmap/munmap isn't quite that trivial: You need to remember how large each allocation is in order to know how many pages to unmap.
      - wtracy 8y ago
        An implementation certainly could return memory to the OS on calls to free(), but to my knowledge none of the widely used implementations do so. (I would be interested to learn of counterexamples!)
ychen306 8y ago
Generally speaking a chunk of memory you free is simply marked "free" for reuse but not given back to the OS. So in this regard, it is not a burden to the OS.
- desertrider12 8y ago
  It looks like by default, the GNU libc won't return pages to the OS until 128 KiB are free at the top of the heap segment. The compiler has to make many small allocations, so even if it freed memory at every opportunity I doubt the heap trimming would happen very often. Source: https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#746 https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#...
randyrand 8y ago
IMO it depends on how much memory is expected to be consumed. If its only at most tens on MBs, then I think not doing memory management is not just smart, but more performant.
snops 8y ago
I remember from the excellent book "Expert C Programming: Deep C Secrets", that the Sun C compiler also took a similar approach to using malloc, so it isn't unheard of for compilers specifically. I disagree with your characterisation of this as bad practice and "not facing it", it is an informed decision rather than ignorance, and brings considerable benefits. With a C complier, some reasonable estimates can be made of the input data length/complexity and hence allocation sizes, and having poor performance if someone tries to feed in a million line file is perfectly acceptable, especially in a complier designed to be simple like the OP. I think recognising the special set of circumstances that justify making an unusual tradeoff that wouldn't normally be acceptable is actually a mark of maturity as a programmer, not a bad attitude. The phrase "Don't let perfect be the enemy of good" comes to mind. Finally, why would it bring burden to the OS if you invoke this multiple times sequentially? malloc/free is implemented in the C library, not in the kernel, it's a mechanism for sharing bigger chunks fetched/given-back from/to the kernel with sbrk(). The kernel would just reclaim the pages on program exit, as it would have to anyway, as it cannot rely on programs being well behaved enough to call free() (which rarely would give the memory back to the kernel immediately anyway). Since the kernel uses virtual memory, its not actually moving the contents about, just manipulating page tables, so it should be quite fast, and zeroing memory is not as time consuming as you think due to Zero Fill On Demand (ZFOD), and hence the kernel does about the same amount of work regardless of if the program called free() or not. Sure it's using more peak memory than it could be, but I reckon compared to say, a web browser, it's still a very small fraction of the total.
ksherlock 8y ago
Not everybody wants to wait around all day for their utilities to free up their memory before exiting. http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012.html http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012...
tptacek 8y ago
I think you're reacting more to the words that the author chose than the actual design decision, which is simply an instance of arena allocation.
zzo38computer 8y ago
Sometimes this is true, sometimes not. It depends on how many blocks of memory you allocate and for what purposes, I think. For short-lived programs it can make sense that some things are never freed (they will be automatically freed when the program terminates), but still there might be some things which should be managed anyways. It also depends on the program, and on other things.
Asooka 8y ago
This is also how the Apache httpd server works, last I checked. Not the entire server, of course - it's a long-lived program with lots of memory to manage, however when servicing a request, it uses the arena pattern to allocate memory and the entire arena is freed at the end of the request. In fact, its entire memory management model is based on a hierarchy of memory arenas that can only grow and get freed once whatever it was that required their liveness ends. I've had the pleasure to write a plugin for it to handle a certain custom upload protocol.

cperciva 8y ago

> Memory management is important even for short-lived programs. It would bring burden to the OS if you invoke this kind of "short-lived, memory-management-free" programs multiple times. All the memory is freed when the process exits. Why does it matter if you run the program multiple times?

sifoobar 8y ago
It will put more pressure on the allocator when running, doing that a lot will likely have some kind of cumulative consequence down the line. I know from experience [0] that even reusing allocated memory rather than bouncing it back to malloc can have dramatic effects. [0] https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h https://gitlab.com/sifoo/snigl/blob/master/src/snigl/pool.h
- cperciva 8y ago
  Sure, but if you're not freeing memory you don't need a real malloc. You allocation function can be just "top += allocsize".
  - wrs 8y ago
    Yes, that's commonly known as "arena allocation" and has been used for decades in programs that have well-defined phases that create lots of connected objects with the same lifetime, like compiler passes, RPC serialization layers, or query planners.
- tptacek 8y ago
  Wait, doesn't it do the opposite? The big thing that "pressures" an allocator is fragmentation, which you don't get at all if you never free.
  - bakul 8y ago
    With no freeing, memory used is the sum of all allocations. With freeing, it is max of the allocation for active objects at any given time. The former can ask for much more memory from the OS for some programs that generate a lot of temp garbage. Though this probably doesn’t matter for a C compiler - unless it is required to compile megabytes of generated code!
    - tptacek 8y ago
      An allocation you don't have to free is, at the margin, a simple pointer increment. It's the need to free memory that makes allocators expensive, not the amount of memory they allocate. This is why performance-sensitive programs use pools, arenas, and other preallocation strategies.
      - bakul 8y ago
        What I was getting at is that non-freeing programs would use much more memory. This doesn't increase the "pressure" on the allocator for such a program but does increase the pressure on the OS (that has to handle memory requests for many concurrently running programs).
- wtracy 8y ago
  Malloc doesn't interact with the kernel at all. The kernel sees pages, not the data structures that malloc manages. The kernel doesn't even know whether you free()'d the memory by the time the process exits. There is exactly zero difference from the operating system's perspective between freeing and not freeing the memory before program termination (except that one might have a higher peak memory usage). The classic implementations of several standard Unix utilities deliberately never deallocated memory for performance reasons. If there was a problem with this practice, I would expect Bell Labs--of all places--to know not to do it.
  - dexen 8y ago
    >There is exactly zero difference from the operating system's perspective (...) Close, but not quite: in case of larger allocations, malloc() tends to use mmap( , , , | MAP_ANON) rather than brk() to request memory from the OS. For example, the glibc's malloc() uses mmap() when requested size exceeds MMAP_THRESHOLD, which is 128kB by default. The mmap() approach gives large, continuous memory blocks that can also be easily free()'d via munmap() with little to no bookkeeping needed[1] - not being subject to the same fragmentation woes as memory allocated via brk() - as long as your address space is significantly larger than allocated memory. That aside, I fully agree with the author of 9cc. [1] in fact a simplistic libc memory allocator could directly wrap malloc() around mmap(), free() around munmap() and realloc() around mrealloc(), leveraging the in-kernel allocator at the cost of one syscall with at least two context switches at each call - i.e., slowww
    - cperciva 8y ago
      Using mmap/munmap isn't quite that trivial: You need to remember how large each allocation is in order to know how many pages to unmap.
    - wtracy 8y ago
      An implementation certainly could return memory to the OS on calls to free(), but to my knowledge none of the widely used implementations do so. (I would be interested to learn of counterexamples!)

ychen306 8y ago

Generally speaking a chunk of memory you free is simply marked "free" for reuse but not given back to the OS. So in this regard, it is not a burden to the OS.

desertrider12 8y ago
It looks like by default, the GNU libc won't return pages to the OS until 128 KiB are free at the top of the heap segment. The compiler has to make many small allocations, so even if it freed memory at every opportunity I doubt the heap trimming would happen very often. Source: https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#746 https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#...

randyrand 8y ago

IMO it depends on how much memory is expected to be consumed. If its only at most tens on MBs, then I think not doing memory management is not just smart, but more performant.

snops 8y ago

I remember from the excellent book "Expert C Programming: Deep C Secrets", that the Sun C compiler also took a similar approach to using malloc, so it isn't unheard of for compilers specifically. I disagree with your characterisation of this as bad practice and "not facing it", it is an informed decision rather than ignorance, and brings considerable benefits. With a C complier, some reasonable estimates can be made of the input data length/complexity and hence allocation sizes, and having poor performance if someone tries to feed in a million line file is perfectly acceptable, especially in a complier designed to be simple like the OP. I think recognising the special set of circumstances that justify making an unusual tradeoff that wouldn't normally be acceptable is actually a mark of maturity as a programmer, not a bad attitude. The phrase "Don't let perfect be the enemy of good" comes to mind. Finally, why would it bring burden to the OS if you invoke this multiple times sequentially? malloc/free is implemented in the C library, not in the kernel, it's a mechanism for sharing bigger chunks fetched/given-back from/to the kernel with sbrk(). The kernel would just reclaim the pages on program exit, as it would have to anyway, as it cannot rely on programs being well behaved enough to call free() (which rarely would give the memory back to the kernel immediately anyway). Since the kernel uses virtual memory, its not actually moving the contents about, just manipulating page tables, so it should be quite fast, and zeroing memory is not as time consuming as you think due to Zero Fill On Demand (ZFOD), and hence the kernel does about the same amount of work regardless of if the program called free() or not. Sure it's using more peak memory than it could be, but I reckon compared to say, a web browser, it's still a very small fraction of the total.

ksherlock 8y ago

Not everybody wants to wait around all day for their utilities to free up their memory before exiting. http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012.html http://lists.gnu.org/archive/html/coreutils/2014-08/msg00012...

tptacek 8y ago

I think you're reacting more to the words that the author chose than the actual design decision, which is simply an instance of arena allocation.

zzo38computer 8y ago

Sometimes this is true, sometimes not. It depends on how many blocks of memory you allocate and for what purposes, I think. For short-lived programs it can make sense that some things are never freed (they will be automatically freed when the program terminates), but still there might be some things which should be managed anyways. It also depends on the program, and on other things.

Asooka 8y ago

This is also how the Apache httpd server works, last I checked. Not the entire server, of course - it's a long-lived program with lots of memory to manage, however when servicing a request, it uses the arena pattern to allocate memory and the entire arena is freed at the end of the request. In fact, its entire memory management model is based on a hierarchy of memory arenas that can only grow and get freed once whatever it was that required their liveness ends. I've had the pleasure to write a plugin for it to handle a certain custom upload protocol.