Hacker News Reader

Static allocation has also made TigerBeetle's code cleaner, by eliminating branching at call sites where before a message might not always have been available. With static allocation, there's no branch because a message is always guaranteed to be available.

It's also made TigerBeetle's code more reliable, because tests can assert that limits are never exceeded. This has detected rare leaks that might otherwise have only been detected in production.

I think the grandparent was saying that dynamic allocation is a form of optimization, which also makes the code harder to follow. Your anecdote seems exactly in line with their suggestion.

Ah, missed that, thanks! I've updated the comment.

I don't get your characterization. The statically sized arrays can never be fully used? That is doubtful. I suppose that if data X and only ever used 1:1 with data Y and you got a Y, then you are guaranteed to have an X, but that requires complete static analysis of the code base and certainty that no future code change will ever affect that 1:1 relationship. That seems fragile.

I mean it's not like memory exhaustion is a common occurrence nowadays. These kind of compromises, where one trades an almost non-existent failure mode for a fragile assumption-ridden code base does not sounds like a wise choice.

I mean, if the particular process is so tightly-integrated that you can know that you have a 1:1 relationship between X and Y, you can also tie those together with dynamic allocations. I find it hard to believe that you can easily statically show that X and Y allocations are tied in a static allocation scheme but that it would not be so under dynamic allocation?

> Allocating all required memory is, IMHO, a great practice for almost any type of program.

Do you know any good resources to get into that mode of thinking, including common patterns, for sombody who is used to malloc everything? I could easily come up with lots of examples in my current project where "it isn't that easy" and "you cannot know this up-front", even when re-designing the whole architecture, and trying to solve those problems feels like re-inventing a hundred wheels that have been invented before.

Two great resources are:

- https://www.gingerbill.org/series/memory-allocation-strategi...

- https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...

I could only read the second article for now (the first one is blocked at work), but while interesting it's not quite what my question was aiming at. That is, it solves the malloc/free hassle in an elegant way, but it doesn't solve the fundamental problem to know in advance how much memory you'll need.

That is, the second article basically says: (pre-arena) It would be so easy if we could just allocate everything on the stack, because lifetimes are nestable. But the article doesn't say how to know the required size of the stack in advance, to prevent stack overflows. That was the part I was interested in.

edit: I could read the first article through a proxy, but it also just talks about different allocators. I'd like to achieve what com2kid was talking about: "Allocating all required memory is, IMHO, a great practice for almost any type of program."

Late reply, but the most common ‘advice’ (usually in the form of post-mortums) I have seen is that knowing the total allocation size for a program is an engineering analysis based on memory availability for a given system and estimated worst-case bounds for memory usage. The system is then designed to work within the constraints generated by that analysis.

Pre-allocating certainly requires a system/application designer to consider the most likely worst case resource usage and then enforce that estimate throughout the design.

Further, for systems that have modern memory sized resources (i.e. 16gb and up) the system is designed to work as though memory was a stack and then that stack is allocated from system resources using something like a growable array, or slab style allocator. So that if the estimated wort case usage is reached, the ‘static memory allocation’ can be relocated and enlarged or added onto with a new slab.

Your comments imply the sticking point may be the estimate of program memory usage, and that is a very fact/situational analysis.

> Do you know any good resources to get into that mode of thinking, including common patterns, for sombody who is used to malloc everything? I could easily come up with lots of examples in my current project where "it isn't that easy" and "you cannot know this up-front", even when re-designing the whole architecture, and trying to solve those problems feels like re-inventing a hundred wheels that have been invented before.

At some point you have to accept you will have hard limits in place. You have to signal back to whoever is sending you data that you cannot receive any more, they need to chunk it up smaller.

But, key lesson, you should already be doing that, but 99.999% of the time we get away without doing that because memory on modern systems is so large.

Drop down to embedded, and now your bit of code gets a 512 byte buffer to work with, and your paycheck depends on making it work, well, you will figure out a way to make it work.

For data coming in over the wire, generally it consists of packet size fields. It also means waiting for data to be processed until you accept more.

For data being passed around locally, well someone somewhere has a buffer. Careful tracking of ownership means you reduce unnecessary copying of data, especially if data is going to be processed and then discarded.

Strings are a separate problem, typically you will have some sort of string allocator dedicated just to strings because strings suck. But even then you will have a max length, but string sizes vary so much just using max length for every string on a screen will blow your memory budget away.

It took me awhile to get into the proper headspace, and it hurt my heart a little bit when I went back to GC'd languages where memory is thrown away willy nilly!

> In the embedded world, code statically allocates all memory it needs up front.

Except for things like the ESP32, which uses malloc pretty liberally within ESP-IDF. Networking is hard without it, it seems?

Networking can use allocators other than malloc. You mostly need arbitrary allocation for stuff like packet payload which can be arbitrary size (within limits). Many other structures, like IP headers, etc, can use much simpler, faster, safer allocators.

I know LwIP is pretty good around that sort of thing. It was just a little bit of a shock to see a lot of usage of malloc throughout ESP-IDF. But then it does have to handle Wi-fi, Bluetooth and more. It runs well though! And it does somewhat amortise its use of malloc to setup functions where possible.

One of the challenges I’ve had in the firmware work we’ve been doing, is the sheer amount of network-received runtime configuration. Makes statically allocating everything difficult. Not impossible of course, but our memory usage ends up sky high because we end up allocating buffers for the 70% of code that isn’t even going to be executed! So using “dynamic” allocation once when the runtime config determines this functionality is actually needed has worked reasonably well

Though it really reminds me of avoiding the GC in garbage collected languages, which is a little amusing to think about

Thankfully TCP/IP packets max out at 64K.

Most old school formats have max size limits for good reasons, and the really good protocols allow the receiver to specify the maximum amount of data to send at a time!

Of course if your device has 256K of memory, reserving 64K for a max size TCP/IP packet is incredibly wasteful.

But if you can receive one of those packet at any time, realistically you need to have 64K available at any time so....

I'm not sure about newer stuff. Last time I did embedded things like Bluetooth were sectioned off into their own bit of memory, malloc was used, and it was a source of bugs that we weren't happy about.

Imagine my disappointment after working on a fixed-allocation HTTP server stack to discover that even `esp_log.h` does several malloc() calls [1] per log output line... thankfully that was only on the ESP8266_RTOS_SDK, and esp-idf isn't quite as bad.

[1] https://github.com/espressif/ESP8266_RTOS_SDK/blob/89a3f254b...

If you're running on a regular OS, you can't escape it by just not calling malloc.

You'll still get lower performance if the system is low on memory, because you got swapped out - it doesn't have much if anything to do with how much you allocated. Wiring it is a different story, and if you're an audio app maybe you should allocate and mlock(), but not a database.

> hot take here, programs should stop assuming malloc can return infinite memory anyway.

Assuming this is a perfectly fine way to make reliable software.

https://en.wikipedia.org/wiki/Crash-only_software

> Wiring it is a different story, and if you're an audio app maybe you should allocate and mlock(), but not a database.

Why wouldn't you wire database memory?

If you're the only one on the system then nobody's going to swap you out, so it won't do anything. If you aren't the only one on the system, then you're probably not the most important process.

No reason to fight the OS unless you're a hard realtime process, which a database usually isn't.

Many databases wire their memory because swapping would be operationally catastrophic and they position themselves as being designed for "mission-critical" applications. I've seen databases get swapped a couple times many years ago, it isn't pretty. Databases have a roughly fixed memory footprint, so sensible configurations don't contribute to memory pressure experienced by other processes.

Database implementations are capable of swapping most of their address space themselves, independent of and better than the OS -- it is a large part of their function. As such, optimization is heavily dependent on both memory and storage being physical. This being true is precondition for most architectural macro-optimizations to work.