5 ms·

> Allocating all required memory during startup has been idiomatic for database architectures as long as I can remember. The obvious benefits to doing things th

> Allocating all required memory during startup has been idiomatic for database architectures as long as I can remember. The obvious benefits to doing things this way are wide-ranging. Allocating all required memory is, IMHO, a great practice for almost any type of program. Heap memory allocators are a type of performance optimization, they allow re-use of existing memory, but only if you are careful to not run out of memory. Heap's of course also allow for more efficient utilization of memory, if some software module isn't using that bit of RAM right now, let another bit of code use it. But like all performance optimizations, they make code messier, and they also lead to less reliable and harder to follow code. In the embedded world, code statically allocates all memory it needs up front. This means that code that reads from the external world has a fixed buffer size, and also likely a related max throughput, regardless of system conditions (e.g. lots of free memory laying around). But, this is also a good thing! It forces programmers to think about their limits up front, and it also forces thinking about error handling when those limits are broken! Sure it can require creative coding, loading large blobs of binary data requires more work when you stop assuming malloc can return infinite memory, but, hot take here, programs should stop assuming malloc can return infinite memory anyway.

_vvhw 4y ago
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.
- Twisol 4y ago
  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.
  - _vvhw 4y ago
    Ah, missed that, thanks! I've updated the comment.
- pierrebai 4y ago
  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?
girvo 4y ago
> 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?
- nine_k 4y ago
  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.
  - girvo 4y ago
    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
- com2kid 4y ago
  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.
astrange 4y ago
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 https://en.wikipedia.org/wiki/Crash-only_software
- jandrewrogers 4y ago
  > 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?
  - astrange 4y ago
    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.
    - jandrewrogers 4y ago
      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.
moring 4y ago
> 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.
- PythagoRascal 4y ago
  Two great resources are: - https://www.gingerbill.org/series/memory-allocation-strategies/ https://www.gingerbill.org/series/memory-allocation-strategi... - https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
  - moring 4y ago
    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."
    - throwaway17_17 4y ago
      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.

_vvhw 4y ago

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.

Twisol 4y ago
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.
- _vvhw 4y ago
  Ah, missed that, thanks! I've updated the comment.
pierrebai 4y ago
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?

girvo 4y ago

> 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?

nine_k 4y ago
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.
- girvo 4y ago
  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
com2kid 4y ago
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.

astrange 4y ago

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 https://en.wikipedia.org/wiki/Crash-only_software

jandrewrogers 4y ago
> 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?
- astrange 4y ago
  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.
  - jandrewrogers 4y ago
    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.

moring 4y ago

> 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.

PythagoRascal 4y ago
Two great resources are: - https://www.gingerbill.org/series/memory-allocation-strategies/ https://www.gingerbill.org/series/memory-allocation-strategi... - https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
- moring 4y ago
  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."
  - throwaway17_17 4y ago
    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.