Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Memory Allocators 101 – Write a simple memory allocator (2016)

arjunsreedharan.org

Post reply on HN
Print view View original

31–40 of 56 posts

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#31

Post by apankrat »

It's worth noting that

    realloc(ptr, 0)
behavior is undefined. The vast majority of modern C libraries will implement it as

    return free(ptr), NULL;
and it will be documented on man pages as such, but there are systems where this will be equivalent to

    return free(ptr), malloc(0);
Furthermore, in theory, this is also permitted:

    return NULL;
so as tempting as realloc() might be as a single override for implementing custom allocators, there are some worms.

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#33

Post by wongarsu »

badminton1 wrote: post #4

Good for didactic purposes but in the real world you may want to try an allocator like tcmalloc or jemalloc.

In the past I've sometimes achieved 20% or better speedups by writing custom allocators (speedup on overall performance, not just malloc performance). tcmalloc or jemalloc are great for the general case, but sometimes you know invariants about object sizes, alloc patterns and free patterns that allow much more performant allocation.

The simplest case is if you know that you will free everything at once, or nothing at all. This allows you to eliminate most bookkeeping and allows a completely lock-free architecture. But there are also more complex cases where you can still get big benefits from exploiting known invariants.

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#34

Post by tom_ »

apankrat wrote: post #31

It's worth noting that realloc(ptr, 0) behavior is undefined. The vast majority of modern C libraries will implement it as return free(ptr), NULL; and it will be documented on man pages as such, but there are systems where this will be equivalent to return free(ptr), malloc(0); Furthermore, in theory, this is also permitted: return NULL; so as tempting as realloc() might be as a single override for implementing custo…

Realloc's behaviour is well-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3.5p3

If the size of the space requested is zero, the behavior is implementation-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#35

Post by [deleted] »

tom_ wrote: post #34
apankrat wrote: post #31

It's worth noting that realloc(ptr, 0) behavior is undefined. The vast majority of modern C libraries will implement it as return free(ptr), NULL; and it will be documented on man pages as such, but there are systems where this will be equivalent to return free(ptr), malloc(0); Furthermore, in theory, this is also permitted: return NULL; so as tempting as realloc() might be as a single override for implementing custo…

Realloc's behaviour is well-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3.5p3 If the size of the space requested is zero, the behavior is implementation-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3

[deleted]

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#36

Post by noselasd »

paavoova wrote: post #9
simcop2387 wrote: post #5

Earlier quoted context omitted.

Not quite, (void *) is special in this regard IIRC, specifically for cases like this. It's a valid pointer but you're required to ensure that any platform requirements like alignment and size will match the requirements of what you're doing.

So UB, then? All complaint solutions I could find to this use memcpy() instead. Some use __attribute__ ((__packed__)) for structs, but that seems to have its own gotchas ( https://stackoverflow.com/a/7956942 ), but not relevant here.

The piece of memory was previously allocated with a struct header_t at sizeof(struct header_t) bytes below the passed in block pointer.

So just recovering and using a pointer to that struct header_t from the block pointer in this way is fine.

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#37

Post by richardwhiuk »

tom_ wrote: post #34
apankrat wrote: post #31

It's worth noting that realloc(ptr, 0) behavior is undefined. The vast majority of modern C libraries will implement it as return free(ptr), NULL; and it will be documented on man pages as such, but there are systems where this will be equivalent to return free(ptr), malloc(0); Furthermore, in theory, this is also permitted: return NULL; so as tempting as realloc() might be as a single override for implementing custo…

Realloc's behaviour is well-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3.5p3 If the size of the space requested is zero, the behavior is implementation-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3

Being implementation defined is hardly well defined.

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#38

Post by tom_ »

richardwhiuk wrote: post #37
tom_ wrote: post #34

Earlier quoted context omitted.

Realloc's behaviour is well-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3.5p3 If the size of the space requested is zero, the behavior is implementation-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3

Being implementation defined is hardly well defined.

No... maybe? It's probably arguable, even if it's not an interesting argument.

Either way, realloc's behaviour is well-defined when the pointer is null.

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#39

Post by nemetroid »

burfog wrote: post #30
tomp wrote: post #29

Earlier quoted context omitted.

Is there a way then to write compliant/non-UB/non-buggy memory allocator/GC in C/C++?

The moment you call sbrk or mmap, you're outside of standard C, so no. Treating a pointer as an integer in order to mess with the bits is also a violation. Aside from that, the style used here is probably OK. It is hard to say what exactly would trigger the gcc bugs, but I'm pretty sure that a recent gcc would be OK for this code.

> Treating a pointer as an integer in order to mess with the bits is also a violation.

Violation of what exactly? Converting a pointer to an integer, and vice versa, is implementation defined. As long as you're not trying to write implementation-independent code, it's perfectly fine.

Re: Memory Allocators 101 – Write a simple memory allocator (2016)

#40

Post by apankrat »

richardwhiuk wrote: post #37
tom_ wrote: post #34

Earlier quoted context omitted.

Realloc's behaviour is well-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3.5p3 If the size of the space requested is zero, the behavior is implementation-defined: https://port70.net/~nsz/c/c11/n1570.html#7.22.3

Being implementation defined is hardly well defined.

Well, it's the return value in realloc(ptr, 0) case that is implementation-specific, but its behavior _is_ well-defined - it is expected to "deallocate the old object".

My point was that in reality the behavior varies. "Undefined" in a common tongue sense, not in the terms of the C standard.

Post reply on HN