Fast, predictable memory allocator for embedded stuff

[DiTBho]

That's what engineering is :-)

query("engineering is")
-> "engineering is merely the slow younger brother of physics, watch and learn gentlemen. Do either of you know how to open the tool box?"

(quote, Sheldon Cooper, engineer jokes
  )

[DiTBho]

If a system implements multiple tasks that are using dynamic memory allocation (like malloc()), it would be better to organize the architecture in a such way that each task would also manage its own, separate heap.

That's what I did for the industrial sewing machine. But they are all stalloc (~ pool) methods. There are three bitmaps to manage free blocks; inserting, deleting and searching for free-blocks are time consuming linearly, o (n), but that's okay because "n" is small, ~ <200.

I also have a Btree-like based application that needs to map a large amount of texture patterns, about ~ 35,000 elements to be passed in turn to the engine. The Btree internally uses a linear stalloc to allocate nodes, which is slow, then pre-allocated all items at startup, so the tree is already balanced and needs no future processing at run-time and the search is as fast as ~ o (log (n)) vs ~ o (n).

Hybrid solution, on large pieces of ram. I also changed the hardware to map 512Mbyte instead of 128Mbyte to have no further compromises.

[SiliconWizard]

And I'm definitely not criticizing, just pointing out that at one end of the toolbox are the GC's, at the other end static allocations only, and a whole plethora of tools in the middle.  I myself am very interested in the tools in the middle, and enjoy the discussion; just thought it was prudent to mention the GC end since the static end has already been mentioned.

Well, mentioning GCs in the discussion made sense. But I again do not think they are a good idea in the specific context I'm dealing with here. Beyond the predictability issues, another big issue, as I already said, is that they promote a "lazy" kind of approach for allocating memory, while I do think enforcing particular allocation patterns through the use of specific allocators is a better approach here.

As an example, let's say I'm writing a smart display appliance based on Teensy 4.x ($20) or NXP MIMXRT1062, running at up to 600 MHz, with 512k of tightly coupled RAM, another 512k on the MCU, let's say 8M of PSRAM, (...)

That's pretty "funny"... I am actually working on implementing a MIDI Synth on a Teensy 4.1 board, and after implementing all the base functions, I was thinking about ways to make efficient use of the external PSRAM! So that's kind of what triggered the whole thing here. But then of course I began thinking of all the potential applications of using dynamic allocations for typical embedded development while trying to avoid the usual pitfalls.

[T3sl4co1l]

Ah yeah, that's another reason library built-ins can't be used, at least as-is: when allocating additional address spaces.

Similar thoughts have crossed my mind for things like simple file storage.  Which might not be too bad embedded, a stack of presets for example can just pack into a struct, slot it into an array and you're good.  Harder if you want to do wear leveling.  If you want to have named, variable length and structured things, I suppose at some point you just want to put in a file system of whatever sort.

Tim

[Nominal Animal]

I am actually working on implementing a MIDI Synth on a Teensy 4.1 board, and after implementing all the base functions, I was thinking about ways to make efficient use of the external PSRAM! So that's kind of what triggered the whole thing here. But then of course I began thinking of all the potential applications of using dynamic allocations for typical embedded development while trying to avoid the usual pitfalls.

That's why I liked Kalvin's post regarding multiple heaps so much: it nicely tied in my example on the Teensy with my point about using (one) reallocated block, with multiple heaps.

The dynamically resized buffer I occasionally need, is better thought of as a separate (temporary) heap.  Even the patterns of use differ in similar manner as using e.g. the different regions of Teensy RAM.

(I'm actually thinking of using 8+8MiB PSRAM on my 4.1, since I don't need any more Flash, just RAM.  And boy, do I wish I had the skills to do proper MAPBGA designs – never done more than 2-layer boards! – to do a Teensy 4.x variant with 18+ contiguous FlexBus1/2 pins exposed, for parallel DMA I/O.  PJRC sells the preprogrammed MKL02 chips that do all the Teensyduino magic from bootup to firmware updates for $6.25, so for a couple of DIY boards for use as a USB-connected framebuffer display to use with Linux SBCs and routers, it'd be very affordable, with the nasty bootup side already well worked out.  I just haven't got a reply yet as to what they prefer wrt. derivative schematic and board files licensing/openness.)

Similar thoughts have crossed my mind for things like simple file storage.  Which might not be too bad embedded, a stack of presets for example can just pack into a struct, slot it into an array and you're good.  Harder if you want to do wear leveling.

If you have a sufficiently large, say 64-bit monotonic sector generator counter at the beginning of each sector (or multi-sector struct), it only takes 3+ceil(log₂N) reads, IIRC, to find the oldest and the newest sector when using the entire N-sector device as a circular buffer. Also, one does not need to read the entire sector either, just the initial data (which doesn't speed up the search, but simplifies the code), unless I remember wrong.
That gives perfect wear levelling, and all you need to do to initialize a new media is to clear it to all zeroes or all ones.

If your updates are sector-aligned, you can increment the sector counter one extra time before writing the first sector of each set.  This does mean finding the newest sector set will then have to do additional sector reads to find the initial sector of the set, and you won't know if the oldest sector set is complete or not.

If your updates are sector-aligned, and at most M sectors long, you can use the lowest k=ceil(log₂M) bits of the counter as the index within the set, and increment the counter by 2^k between first sectors in consecutive sector sets.  This has the benefit of not slowing down the latest sector set search, since if you read sector i = s<<k + p , you know that the first sector of that set is at i-p .  Finding the oldest sector set, and the end of any sector set, does need 1+k additional sector reads, though, but that should be okay.
(Note: the contents are still in consecutive sectors, it is just the counter that is no longer consecutive.)

[DiTBho]

using (one) reallocated block, with multiple heaps.

I don't know, personally to simplify the testing activity I don't *re-use* but rather increase the ram to keep things isolated and segregated.

I have too many difficulties otherwise

[SiliconWizard]

I am actually working on implementing a MIDI Synth on a Teensy 4.1 board, and after implementing all the base functions, I was thinking about ways to make efficient use of the external PSRAM! So that's kind of what triggered the whole thing here. But then of course I began thinking of all the potential applications of using dynamic allocations for typical embedded development while trying to avoid the usual pitfalls.

That's why I liked Kalvin's post regarding multiple heaps so much: it nicely tied in my example on the Teensy with my point about using (one) reallocated block, with multiple heaps.

If you have read carefully what I said all along in this thread, this one point would be implied.
In all my "musings" about allocators, not *once* have I even considered using the "standard" approach with a single "heap" and general-purpose allocators. Actually, I think the best here, in this discussion, would be to try and forget the *heap* and not even call memory available for allocation a "heap". Or even several of them. That would avoid being biased by what we are used to.

Actually, as I said, using different allocators for different use cases would be the way to go, IMO, and each of those allocators could potentially tap into a different area of available memory. One can also, on top of that, "cascade" allocators. For instance, at the moment, I'm using a linear (or "arena") allocator as the base allocator for the whole external memory (but I may split it further later on), and pool allocators which themselves allocate from memory given to them by the former allocator.

We could add even more layers of allocation if required. The whole thing, apart from selecting the right allocators depending on the kind of data you're manipulating, is once again about controlling the lifetime of objects. Thanks to the base linear allocator with markers, you can precisely define lifetimes (although you obviously have the constraint here that you must arrange lifetimes in "LIFO" order) and release all objects with a given lifetime at once in O(1).

Also as evoked earlier, even with standard allocators on "standard" systems - say Linux or Windows - the "heap" and malloc() are just a local "fantasy".
What happens is that it's all *layers* of memory management and allocators, from your local "heap" to the actual memory reserved on the system level.
Sure, if you're using malloc() on a typical small embedded system such as an MCU with a minimal environment, the "heap" will usually just be a single area of available memory determined at link time, and malloc() in the std lib will be the only allocator behind the scenes, but that's not the case at all for more complex systems.

As to "reallocation", it would be interesting to discuss exact use cases and how we can often replace this with another allocation scheme.
So, for instance:
- Do you typically use reallocation for growing blocks, or for both growing and shrinking? (My own use cases of realloc() are almost always only 'growing'.)
- Is that typically to implement dynamic tables?

[Nominal Animal]

Actually, I think the best here, in this discussion, would be to try and forget the *heap* and not even call memory available for allocation a "heap". Or even several of them. That would avoid being biased by what we are used to.

Right.  In that case, let me rephrase: the pattern where I do use reallocation is very distinct.

- Do you typically use reallocation for growing blocks, or for both growing and shrinking? (My own use cases of realloc() are almost always only 'growing'.)

Typical cases are buffers for things like files that fit in memory.  I do not use the pattern where one examines the file size, and then reads that amount of data, because it is unreliable.  Instead, I read into a dynamically growing buffer, and when complete, (do a whitespace compaction, comment removal pass and then) shrink the allocation to the size used.  The shrinking is useful if additional allocations are done before the file area is freed, for example for key data needed later.

When splitting one into separate chunks, the possibility of a chunk ending in the middle of a multibyte identifier (say, escape sequence, or between CR and LF in a file that contains CR LF newlines) is the detail that makes handling them in chunks annoying.  The simple approaches are "slow", and the fast approach (a true FSM that can be progressed byte by byte) complex or hard to maintain.

In the getline() pattern, the buffer may grow, but isn't shrunk; it will eventually be freed.  I do not want to pre-allocate a buffer that can contain the largest possible line (buffer) I want to support, because that occurs too rarely.  As an example, most C source lines are short (say, under 200 characters), but occasionally you have generated code etc. that can have lines with thousands of characters.

- Is that typically to implement dynamic tables?

No; the common denominator seems to be human readable text or a related format, like config files, JSON, HPGL, G-code, etc., and input of unknown length or complexity.

I often use a binary heap for timeouts, with the heap represented as an array of (time, event_id) pairs.  Each event_id refers to a slot in a separate array, that contains the timeout state and an offset back to the entry in the heap.  Percolation is only a bit more complex than in an ordinary binary heap, since also the reference back to the hash table needs to be updated when an entry moves in the heap.  That makes it cheap to delete any entry using just the event_id.  The slots can be split into fixed-size chunks trivially, but the heap really does need to be contiguous in memory.
However, when the heap array needs to grow, the old one can be freed and a new one allocated from scratch, because the new one can be populated in a single pass over the active slots.  It can be easier to use realloc instead, but I don't think I really need realloc() to implement a timeout heap efficiently.

For hash tables, I use malloc()+copy+free(), not realloc().

Images etc. specify their size before the data is read, unlike text/stream formats, so no realloc() needed there either.

An interesting detail: Current implementations for parsing floating-point numbers are slow.  Even on spinny HDDs, the parser tends to be the bottleneck, not the storage I/O speed.  Daniel Lemire's Number Parsing at a Gigabyte per Second describes the issues and approaches well, but even it gives up and uses the old arbitrary precision approaches for values with more than 19 digits in the significand (decimal part excluding the power of ten exponent).  (Arbitrary/multiprecision support does not need realloc(), because the new size is known when summing or multiplying anyway.)
While this might sound irrelevant to embedded stuff (since HPGL and G-Code limit real parameters to a smaller range and precision anyway), your JSON and configuration data can contain decimal-format floating-point values, and the slowness (and memory needs) when parsing these can be surprising.  Speccing max. 19 decimal digits in the significand, and rejecting the input if more are given (or just using a best guess approximation), can make a big difference in both speed and firmware size.

When I do use realloc(), I almost always have only one "active" region I realloc(); it is extremely rare to need more than one such chunk of memory at the same time.
I often do do "normal" malloc()s at the same time, with varying life times, but these never get realloc()'d.

Perhaps the best description is that on top of my normal malloc()+free() patterns, I sometimes need a separate buffer whose maximum size should depend on the available memory, but should not preclude making normal allocations.  I can even live with this buffer being moved or resized when making those separate allocations; no problem.
This is why I suggested that maybe a separate interface for this, where the user code specifies the size it currently uses and may modify it at any time, but the allocator dictates its maximum size and may move and resize it to satisfy a normal allocation done at the same time.

[brucehoult]

An interesting detail: Current implementations for parsing floating-point numbers are slow.  Even on spinny HDDs, the parser tends to be the bottleneck, not the storage I/O speed.  Daniel Lemire's Number Parsing at a Gigabyte per Second describes the issues and approaches well, but even it gives up and uses the old arbitrary precision approaches for values with more than 19 digits in the significand (decimal part excluding the power of ten exponent).  (Arbitrary/multiprecision support does not need realloc(), because the new size is known when summing or multiplying anyway.)

Interesting to see someone else has done this now. I did the same thing in a proprietary system in 2006 and wanted to publish but was not allowed to. Most literals are far smaller than 19 digits, and if you're printing from a floating point value then you never need to print more than 17 digits to uniquely identity which IEEE double you started with anyway.

Also: you don't need arbitrary precision. Multiple-precision, yes, but not arbitrarily large. There is an upper limit that is if I recall correctly something like 1024+53+53 bits, or 144 bytes if you round to a multiple of 32/64/128 bits, no matter how long the input string of digits is (could be millions of digits).

The key is to use the first 17 digits to find which pair of doubles the input value lies between, then start to convert the mid-point of those two values back to decimal. You can stop as soo as you find an input digit that is greater than or less than the expansion of that mid-point.

[Nominal Animal]

An interesting detail: Current implementations for parsing floating-point numbers are slow.  Even on spinny HDDs, the parser tends to be the bottleneck, not the storage I/O speed.  Daniel Lemire's Number Parsing at a Gigabyte per Second describes the issues and approaches well, but even it gives up and uses the old arbitrary precision approaches for values with more than 19 digits in the significand (decimal part excluding the power of ten exponent).  (Arbitrary/multiprecision support does not need realloc(), because the new size is known when summing or multiplying anyway.)

Interesting to see someone else has done this now. I did the same thing in a proprietary system in 2006 and wanted to publish but was not allowed to. Most literals are far smaller than 19 digits, and if you're printing from a floating point value then you never need to print more than 17 digits to uniquely identity which IEEE double you started with anyway.

That – not getting permission to publish – is really annoying.

A lot of HPC – at least molecular dynamics simulations – still uses text input/output for a number of reasons, and that is artificially slow, because libraries etc. don't want to incorporate the known faster approaches until they've been properly verified in peer-reviewed journals.  Exhaustive brute force testing is not feasible.

Also: you don't need arbitrary precision. Multiple-precision, yes, but not arbitrarily large. There is an upper limit that is if I recall correctly something like 1024+53+53 bits, or 144 bytes if you round to a multiple of 32/64/128 bits, no matter how long the input string of digits is (could be millions of digits).

Of course.  The exponent in IEEE 754 Binary64 'double' has 11 bits and mantissa 53 bits, so it cannot be more than 2048+53+1+1 (the extra bits for exact rounding and overflow detection), or 264 bytes.

I meant that the existing C libraries use either multiprecision or arbitrary precision libraries to implement this.  GNU C for example uses GMP, GNU Multiprecision Library, which is actually an arbitrary precision library.

The key is to use the first 17 digits to find which pair of doubles the input value lies between, then start to convert the mid-point of those two values back to decimal. You can stop as soo as you find an input digit that is greater than or less than the expansion of that mid-point.

In general, obtaining the limiting pairs of doubles that bracket the decimal representation, would be useful in many other ways, too: for example, general interval arithmetic.

Circling back to the topic of memory allocation, when parsing numbers from a stream-like source (say, serial connection), to support exact conversion of all numeric formats, we do have to (temporarily) store the entire token, since we need to know the power of ten exponent (zero, if not specified), before picking the approach.
It is possible to limit that temporary storage requirement to a few dozen bytes by writing your own numeric parser from scratch (handling pathological cases like leading or trailing decimal zero digits), but the code is rather complex and math-intensive.  If you have the entire number as a string in some buffer, even avr-libc provides a nice strtod() you can use to parse it into a double.  (Not to mention that you can do speculative non-destructive parsing, too.)

This is the tradeoff I see in the cases where I use reallocation to dynamically resize the buffer I need: being able to reallocate/grow just one active buffer when needed, I can avoid nasty complexity elsewhere.  For example, when parsing a flat configuration file with just key-value pairs, I typically implement a get-key function, one or more get-value functions, and a next-key function (to skip any unread values to the beginning of the next key).  The get-key function returns the key identifier, using the hash of the key and the key text to look it up.  The get-value functions parse for example a numeric value, a true/yes/1|false/no/0 boolean, or an identifier of some sort, or say a 2D or 3D point.  Depending on the use, I can allow more than one value per key.  The next-key skips to the beginning of the next key, and reports if it skipped anything that might have been considered a value.  This approach also works well to parse HPGL and G-code streams.
The active buffer is mostly like a scratch pad or cache.  For 99% of the time, the default size is fine.  Yet, for ease of use for the end users, I would prefer it to work, even if slower, for that 1% of oddball cases too.

[SiliconWizard]

Just a thought here - I've myself never used reallocation for such use cases, but disclaimer: I may have to see the parsing code, because maybe there's something I'm missing.

Unless you're extremely short on memory - very small targets - and/or you have to concurrently parse a lot of files, allocating a temporary buffer of several tens or even hundreds of bytes to accomodate the largest "token" is usually more than good enough and much better in terms of performance. I don't think I've ever done otherwise, unless of course the "tokens" we may encounter are not bounded in size, which would make the non-reallocating approach fail in some cases. But tokens of arbitrary size in text files, that's pretty rare in practice.

[Marco]

Ultimately the need to accommodate nearly arbitrary allocations of truly random size which need to be linear addressable is restricted to game engines streaming in data from other types of storage and in particular with no or a 32 bit MMU (64 bit won't fragment fast enough to matter). The graphics hardware necessitates the linear addressing, the streaming and large dynamic ranges of object sizes necessitates full dynamism. It's the only application I can think of where defragmenting on the fly makes much sense.

Any time else even if for some reason you need to keep it fully dynamic and for allocations of arbitrary size it's better to just use a language which can elegantly and with an easy to follow programming style use growing/shrinking buffers based on linked lists (ie. not C). The performance impact will be less than defragmenting. Even for a sane GC language (ie. not C+GC) for a no or 32 bit MMU processor it doesn't make much sense to build on arrays (with a 64 bit MMU you can get away with it again).

[DiTBho]

The graphics hardware necessitates the linear addressing

I have recently seen something similar in the Nitro(gen) development system for Nintendo DS.

[SiliconWizard]

To wrap it up a little - even if I think I'm repeating myself here - it's really all about using proper allocation patterns and managing lifetime of objects, rather than about the allocators themselves (which will just be selected as a consequence.)

@DiTBho, I don't think we disagree as much as you may have figured. I still very much think abritrary-size allocations with standard allocators and the standard heap in embedded dev is usually to be avoided at all costs (of course there are always exceptions, and maybe also that's fine if you really really know what you're doing. At all times.)

As I mentioned earlier, what you find a lot more reliable and more comfortable to deal with, is statically allocated memory, that you may still use in a dynamic way in some cases at run time. My point here is that this approach (that we have all used I'm sure) is a form of dynamic allocation, just an ad-hoc one. And for those ad-hoc solutions, I'm thinking of replacing them with well tested allocators that you can reuse instead of writing ad-hoc schemes again and again.

Using various "allocators" instead of ad-hoc code also forces us to take the lifetime of objects much more seriously into account, which I think is a good thing. (No, again not the standard allocators. )

And the benefit is that they can be extended to using memory that may only be "discovered" at run time, instead of being strictly tied to statically allocated memory. Of course in this use case, you must make sure that having a varying amount of usable memory that you can't know in advance is appropriate. Which is why it can't be used exclusively either. A mix of purely statically allocated objects and dynamically allocated ones - in ways I described earlier - would be the way to go.

@Marco: would be interesting to give more precise examples of truly arbitrary size allocations in game engines, because those are precisely most often using the kind of allocators that I'm talking about in this thread, among which pool allocators (fixed size) is one of the most commonly used. Of course, we should not confuse allocating an "arbitrary" number of objects each with a fixed size (typical pool allocation) with arbitrary size allocations. (Possibly obvious, but just saying.)

[Marco]

@Marco: would be interesting to give more precise examples of truly arbitrary size allocations in game engines, because those are precisely most often using the kind of allocators that I'm talking about in this thread, among which pool allocators (fixed size) is one of the most commonly used.

AFAICS the problem with pool allocators with a 32 bit virtual memory space and GB range memory is that you just don't have enough virtual memory space to over-provision the pools. They need to be able to shrink/expand the pools (as the balance of say texture and geometry changes frame by frame depending on what's being streamed in). For that they need to be able to defragment the virtual memory space.

The reason I say game devs use it is because of the blog post from the Chinese blogger I linked earlier.