4 ms·

I think malloc/free at least are certainly far from simple to implement..

by njs12345 13y ago

pjmlp 13y ago
Simple does not mean easy.
- zxcdw 13y ago
  What's the definition of "hard to implement" if not complexity?
  - pjmlp 13y ago
    If you are targeting an existing OS, malloc/free can be simple wrappers to OS syscalls for memory allocation. Not very efficient, but pretty straightforward to implement. If targeting direct hardware, any CS student should have learned how to implement a memory allocator on their compiler design, data structures or OS classes. Back when I graduated, this would be a home work exercise. If you want to implement a high performance memory allocator that works under pressure in a multi-core context, then yes it is complex to implement. Now something that allocates/releases memory with a general purpose algorithm? That is quite simple and many compiler design books even provide such examples.
    - ahomescu1 13y ago
      > If you are targeting an existing OS, malloc/free can be simple wrappers to OS syscalls for memory allocation. Not really, there's no such thing as malloc/free syscalls. On Linux, you have mmap/munmap (at page granularity) and brk/sbrk (which only extend the current heap). You could implement malloc as either a mmap() of one or more pages, or by using sbrk() to extend the heap by exactly the memory you need, but then freeing that memory becomes much harder.
      - srgpqt 13y ago
        To take the example of Windows, wouldn't this qualify as a malloc/free syscall equivalent? http://msdn.microsoft.com/en-us/library/windows/desktop/aa366597(v=vs.85).aspx http://msdn.microsoft.com/en-us/library/windows/desktop/aa36...
        marshray 13y ago
        In fact, I believe modern versions of msvcrt.dll just call HeapAlloc(GetProcessHeap(), ...) in the usual case.
        deleted 13y ago
        [deleted]
      - pjmlp 13y ago
        That is what I meant by OS syscalls. Should I write a full tutorial on an HN post how to write memory allocators when anyone can easily search for one?
        ahomescu1 13y ago
        > Should I write a full tutorial on an HN post how to write memory allocators when anyone can easily search for one? No, but a memory allocator is more that "simple wrappers". My point was that OS kernels (Linux/BSDs at least) don't actually provide malloc/free as syscalls, and that you need to implement an allocator in userspace if you want these functions (even if it's a trivial allocator that wastes memory).
        pjmlp 13y ago
        Of course they don't, why should they?! malloc/free are part of the C language runtime, not OS syscalls. A compiler writer can build the memory allocator on top of what the OS provides as syscalls or take a shortcut and use the C runtime library instead while adding a dependency to it. I never mentioned malloc/free were syscalls.

I think malloc/free at least are certainly far from simple to implement..

pjmlp 13y ago

Simple does not mean easy.

zxcdw 13y ago
What's the definition of "hard to implement" if not complexity?
- pjmlp 13y ago
  If you are targeting an existing OS, malloc/free can be simple wrappers to OS syscalls for memory allocation. Not very efficient, but pretty straightforward to implement. If targeting direct hardware, any CS student should have learned how to implement a memory allocator on their compiler design, data structures or OS classes. Back when I graduated, this would be a home work exercise. If you want to implement a high performance memory allocator that works under pressure in a multi-core context, then yes it is complex to implement. Now something that allocates/releases memory with a general purpose algorithm? That is quite simple and many compiler design books even provide such examples.
  - ahomescu1 13y ago
    > If you are targeting an existing OS, malloc/free can be simple wrappers to OS syscalls for memory allocation. Not really, there's no such thing as malloc/free syscalls. On Linux, you have mmap/munmap (at page granularity) and brk/sbrk (which only extend the current heap). You could implement malloc as either a mmap() of one or more pages, or by using sbrk() to extend the heap by exactly the memory you need, but then freeing that memory becomes much harder.
    - srgpqt 13y ago
      To take the example of Windows, wouldn't this qualify as a malloc/free syscall equivalent? http://msdn.microsoft.com/en-us/library/windows/desktop/aa366597(v=vs.85).aspx http://msdn.microsoft.com/en-us/library/windows/desktop/aa36...
      - marshray 13y ago
        In fact, I believe modern versions of msvcrt.dll just call HeapAlloc(GetProcessHeap(), ...) in the usual case.
        deleted 13y ago
        [deleted]
    - pjmlp 13y ago
      That is what I meant by OS syscalls. Should I write a full tutorial on an HN post how to write memory allocators when anyone can easily search for one?
      - ahomescu1 13y ago
        > Should I write a full tutorial on an HN post how to write memory allocators when anyone can easily search for one? No, but a memory allocator is more that "simple wrappers". My point was that OS kernels (Linux/BSDs at least) don't actually provide malloc/free as syscalls, and that you need to implement an allocator in userspace if you want these functions (even if it's a trivial allocator that wastes memory).
        pjmlp 13y ago
        Of course they don't, why should they?! malloc/free are part of the C language runtime, not OS syscalls. A compiler writer can build the memory allocator on top of what the OS provides as syscalls or take a shortcut and use the C runtime library instead while adding a dependency to it. I never mentioned malloc/free were syscalls.