Tangential, but the complexity and over-head of the malloc abstraction is precisely what made me very intrigued by "stack-only" languages, such a recently published Goose. There is something very elegant and exciting about the idea of (almost) completely getting rid of it. Just as modern programming languages have developed good ergonomics that replaces a garbage collector, the same could hopefully be done to replace heap-allocated memory.
> the complexity and over-head of the malloc abstraction is precisely what made me very intrigued by "stack-only" languages, such a recently published Goose.<p>Goose's stack<i>s</i> have quite some complexity themselves. They preallocate a ton of memory. The compiler has to magically match your code to each stack. You are not allowed to have nested growing types (e.g. creating an adjacency list is not so easy). And after all for some usecases you still end up using an allocator (Goose's linked list example ends up building a pool allocator for the linked list nodes!)
If your takeaway from this was "wow malloc has so much overhead" then you may want to notice the part where they benchmark against glibc malloc and glibc is somewhere between 20-150x faster than their implementation. And that's fine, this exposition is basically what you would learn in an undergraduate systems programming course, but production allocators are able to significantly cut down the amount of work needed to grab an allocation, especially for small ones that occur frequently.
This is actually what first drew me to zig. Most people talk about error handling, but the explicit allocator handling and making choosing an allocator a deliberate consideration has pushed me to better coding habits in general. I don't think it is possible or practical to completely abandon heap-allocated memory, but explicitly choosing between allocation types and styles that most precisely fit a job has great potential for meeting that spirit.
Embedded programming has taught me that almost anything can be a stack-only language if you want it to be, even C++. :)
Avoiding the heap entirely isn't required and will prevent you from working with substantial amounts of data. The real key is to allocate all the memory you need up front and use that large block for a long duration.
> Avoiding the heap ... will prevent you from working with substantial amounts of data<p>This isn't really true of Goose, it's avoiding 'the heap' in the C sense, not in the OS allocated pages of memory sense. One is a programming abstraction provided by the other, but GP is <i>only</i> talking about the programming abstraction. I have never encountered a program that couldn't have memory be explicitly tied to lexical scope, but it can result in less efficient use of it in some cases.<p>Goose is almost, but not exactly the "allocate all your stuff at the beginning" the programming language. It's honestly the most exciting language I've seen in quite some time.
> I have never encountered a program that couldn't have memory be explicitly tied to lexical scope, but it can result in less efficient use of it in some cases.<p>> Goose is honestly the most exciting language I've seen in quite some time.<p>I took a look at its home page [1] and I immediately see red flags:<p>- Over sixteen benchmarks Goose runs at 3.3x the speed of idiomatic C++, 1.16x hand-optimized C++ and 1.12x the best safe Rust, and uses 1.9x, 1.3x and 1.2x less memory (results). These gains come from Goose's data layouts and memory model.<p>- push returns a reference to the new element, so a program can link elements while building the array. A vector<T> or Vec<T> may reallocate and cannot provide this guarantee. Stable references account for several benchmark gains.<p>You're suggesting a performance loss (as expected), but they're claiming a (rather incredible) performance gain?<p>And they're claiming their vector stable and doesn't reallocate, yet without a performance loss, which makes no sense... it's not a vector anymore. And if you want a non-vector then you can do that in C++ too.<p>The whole LLM vibe doesn't help inspire confidence either, but even ignoring that, the technical claims themselves are incredible and bizarre, and I'm only a few paragraphs in.<p>[1] <a href="https://aardappel.github.io/goose/" rel="nofollow">https://aardappel.github.io/goose/</a>
I just want to point out that the author of Goose has plenty of technical cred, having authored flatbuffers and lots of other cool stuff.
Goose is a weird language. It uses a pile of pre-allocated datastacks, enforces lexical lifetimes for all data, and has first-class syntactic support for capped, growable, and shrinkable arrays. It also spits out a pile of C that gets all the optimization benefits of <insert C compiler of choices>.<p>Goose in particular excites me because I have done similar design work over the years.
Most stack oriented languages <i>also</i> have a heap.
the stack is just a bump allocator. the unique thing about stack-only languages is lifetime management, not really how they allocate.
If you want to study how modern allocators work I'd recommend something like mimalloc, which has a reasonably approachable codebase. No brk/sbrk in sight, btw (or boundary tags, or splitting/merging...).
mental reminder to finish my history of malloc writeup. It's almost 20 llm-less pages with context and examples. goes through general purpose malloc like dlmalloc, mimalloc, tcmalloc, jemalloc and others, while also mentioning some purpose-specific ones like scudo.
When getting into wasm when it was new and had clang support, I wrote my own libc and malloc, which was so a great learning all these low level functions and tricks (free lists for example), I also like that I can read wasm quite well, and tooling is good to just return a .wat and read it.
Good learning resource for this (and related) topics: <a href="https://cs61.seas.harvard.edu/site/2026/" rel="nofollow">https://cs61.seas.harvard.edu/site/2026/</a>
I found this one very well explained time ago, for those looking for more details: <a href="https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/" rel="nofollow">https://sploitfun.wordpress.com/2015/02/10/understanding-gli...</a>
Malloc() is sloooow. Even more if you also use free(). Consider allocating a single array and scratching there if possible.
This shows you how you could "secure" memory code in C by using more robust implementations of these functions. But it doesn't show you that you don't even need them anyway. I think in my entire career I've only used dynamic memory in C twice. The rest of the time I use functions with static allocations, buffers, unrolled loops, etc. Maybe it's paranoia, or habits from embedded programming, or being a control freak... But my C programs don't get memory leaks or crash from memory issues.
<p><pre><code> One of my pet peeves is when people, trying to make a
point, use code that doesn't compile. I mean, it's fine
when you're sketching out code on a white board. But on
an article you've had time to prepare, it's a little
annoying.
Take for instance, this code fragment:
.. static void *ptrs[1000];
..
.. int main(void) {
.. for (int i = 0; i < 1000; i++)
.. ptrs[i] = malloc(16);
.. }
.. }
I'm pretty sure what they //meant// to write was:
.. #include <stdlib.h>
..
.. static void *ptrs[1000];
..
.. int main(void) {
.. for (int i = 0; i < 1000; i++)
.. ptrs[i] = malloc(16);
.. }
.. return( 0 );
.. }
I understand why the author produced the code on top
instead of the code at the bottom. The code on the bottom
includes features extraneous to the conversation. The
include directive and return statement only serve to
distract from the point the author is making.
If you read far enough down, you'll see he has links to a
broken GitHub repo presumably with code fragments. (or
maybe GitHub itself is broken today or it decided it
didn't like me trying to access the repo from an AT&T
fiber line.)
I'm sure when GitHub decides to behave and serve bits like
it's supposed to, there will be compilable code so readers
can understand the author's intent within the context it
was intended to be viewed.
Which is to say:
1. It's probably okay to have only code fragments in the
main part of your discussion. Please provide a note
that there is code which shows your snippet in the
context of a compilable program. And put that note
somewhere near the code fragment.
Or... consider putting a note at the beginning of the
article saying something like "Compilable versions of
code fragments in this article are available at a
GitHub repository referenced at the bottom of the
page."
2. Do not depend on GitHub to hold your code fragments.
You do not know when it will be down or which readers
it will randomly decide to block.
3. I really do think you should include more of the
"layout" code. When reading "The Address Space"
section, it was unclear where the initialized,
uninitialized and local came from. I initially thought
the author was using a version of C I had not yet
encountered that defined these symbols.
4. Since the code uses ``sbrk()``, the author should
probably have cautioned readers the code isn't POSIX
compliant, but should compile and run on Linux systems
using gcc. There's a comment about demonstrating it
with glibc, but I think that's not a strong enough
warning since you can compile programs with clang that
are intended to link against glibc.
I doubt there are many QNX users out there who expect
random code from the internet to run on their systems
without alteration, but it seems good form to describe
the environment you are targeting.
Now I'm wondering if this is expected to work on Darwin
as well as Linux.
5. It might be a decent idea to order the SHOW()
statements in the code in "The Address Space" section
to follow the order of the diagram at the bottom of
that section:
.. SHOW( "local (stack)", &local );
.. SHOW( "printf (libc)", printf );
.. SHOW( "program break", sbrk(0) );
.. SHOW( "malloc(16) (heap)", malloc(16) );
.. SHOW( "uninitialised (bss)", &uninitialised);
.. SHOW( "initialised (data)", &initialised );
.. SHOW( "main(text)", main );
6. In the "Chunks and Headers" section, it may be
interesting to mention what the flags in the allocation
headers actually mean.
7. glibc does late fill, right? I can't remember. If it
does, it might be useful to mention in the Demand
Paging section since it affects the program logic.
Now that I've yelled at the cloud a bit, allow me to say,
I enjoyed the article. Things I liked:
1. The author used the exact strace command they used to
produce the output discussed in the text of the
article.
2. The graphics are quite nice.
3. Despite grousing about fragments being fragments, they
do a good job of illustrating points made in the text.
EDIT: After complaining about GitHub not being available,
it's finally come back. The web interface is still borked
for me, but I can clone the repo mentioned at the bottom
of the page and view the local copy of the source.</code></pre>
[flagged]
[flagged]
[flagged]
If the DRAM scarcity continues, not much.
It's a consumer market scarcity. Since you're supposed to run everything on rented hardware, own nothing and be happy, I'd expect the malloc to be the right place to invest into once it is IPO.
like many C functions you must remember that C is not low level, you won’t learn how memory is allocated by inspecting malloc() anymore than you would learn how characters are printed to the screen by reading printf() or how a file is written by reading write().<p>you will only learn about the thin or heavy wrapper that C is responsible for, the real magic is happening in the kernel and the device firmware
Notwithstanding that most kernels today are written almost entirely in C anyway, you'll see learn a great deal about memory allocation by inspecting malloc().<p>The usual division of labour in most operating systems is the kernel manages the virtual memory and physical pages and provides a mechanism for coarse page-aligned allocation of virtual address for userland. These coarse mappings userland (malloc or something else) is responsible for carving up, and in that is much design space. Just look at mimalloc for example.<p>The kernel's own page allocation is often very simple (many get by with a simple freelist, some use buddies.) The allocators for the kernel's own datastructures are usually relatively simple at least conceptually. Bonwick explains the slab allocator - the almost universally acknowledged queen of all kernel memory allocators and mother of those of Linux, BSD, and beyond - in a 12-page paper.<p>As for the firmware there's basically nothing of an ongoing role for it after the kernel is in charge. Its role is limited for the most part to providing the kernel with a map of the physical addres space.<p>By reading malloc() you will not learn everything about allocation - that is a problem that spans multiple layers - but you will certainly learn a lot about it. To call it a mere wrapper is not reasonable.
Disagree, I found malloc source useful, and writing a toy allocator especially useful because you learn about the brk() syscall which is a great breadcrumb into kernel land and a great bridge to connect the memory mapping lessons from computer architecture with application code.
Depending on how low-level you're going, you don't even need to call brk.<p>My toy stop/copy GC and allocation routines just have this:<p><pre><code> %define HEAP_SIZE (4 * 1024 * 1024 * 1024)
.section bss
;;
;; Two heaps so we can flip-flop between them
;;
heap_a:
resb HEAP_SIZE
heap_a_end:
heap_b:
resb HEAP_SIZE
heap_b_end:
</code></pre>
Of course there are other syscalls involved in my compiler/runtime, but for memory allocations the static area sufficed for me.
These days brk and sbrk have fallen from grace (and I think even some Unix-likes no longer provide them as general mechanisms, at least I don't think macOS does) - mmap is usually favoured.
> and writing a toy allocator especially useful because you learn about the brk() syscall<p>Nobody in their right mind (except musl) use brk(2) nowadays; mmap(2) is pretty much universally accessible, and brk() has been non-portable for more than 20 years already (POSIX ditched it in 2001) anyhow. For goodness sake, stop keeping this stupid API from VM-lacking PDP-7 alive, and let it go away!<p>Edit: also, I have no idea how musl even uses it:<p><pre><code> uintptr_t new = ctx.brk + pagesize;
int need_guard = 0;
if (!ctx.brk) {
need_guard = 1;
ctx.brk = brk(0);
// some ancient kernels returned _ebss
// instead of next page as initial brk.
ctx.brk += -ctx.brk & (pagesize-1);
new = ctx.brk + 2*pagesize;
}
if (brk(new) != new) {
ctx.brk = -1;
} else {
if (need_guard) mmap((void *)ctx.brk, pagesize,
PROT_NONE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
ctx.brk = new;
ctx.avail_meta_areas = (void *)(new - pagesize);
ctx.avail_meta_area_count = pagesize>>12;
need_unprotect = 0;
}
</code></pre>
That's... not what brk() returns; it returns 0 on success and -1 on failure. Huh?
When you call brk() from a user program you use the lib wrapper, and that does indeed return 0 on success and -1 on failure. But the actual Linux system call, which I presume is what musl calls, returns the current break on failure instead of -1.<p>See the NOTES section in man brk(2):<p>> C library/kernel differences<p>> The return value described above for brk() is the behavior provided by the glibc wrapper function for the Linux brk() system call. (On most other implementations, the return value from brk() is the same; this return value was also specified in SUSv2.) However, the actual Linux system call returns the new program break on success. On failure, the system call returns the current break. The glibc wrapper function does some work (i.e., checks whether the new break is less than addr) to provide the 0 and -1 return values described above.
Malloc needs the kernel to obtain memory, but in any reasonable implementation (you do not want to make a syscall for every malloc and free) is mostly user space, and studying that will tell you a lot about how your malloc works.
Well, yes, but its low level , no matter what, I mean whats left thats lower?