8 ms·

Lessons from high-performance / embedded development: If you know the size of your data beforehand, or can at least put a bound on it, it's best to pre-allocate

• pdpi 6y ago
  I think the term you're looking for is cache locality. Cache coherence is about ensuring that caches local to different cores see the same values for any one given chunk of memory.
  • gpderetta 6y ago
    It seems to be a very common mistake. Understandable as they are somewhat related as bad cache locality can cause unneeded coherency protocol traffic. Of course locality is important even on single core cpus with no need for coherency.
• captain_price7 6y ago
  I think for C++ vector, when current underlying array gets filled, the common strategy is allocate a new array double the size of the current one, and copy contents over to that.
  • tester34 6y ago
    same in C# for list
  • rerx 6y ago
    But if you expect an upper bound of the required size of that stay, it may be worthwhile to explicitly set the capacity of the vector to avoid these reallocations.
    • spacechild1 6y ago
      That's exactly the purpose of std::vector's “reserve“ method, btw.
      • twoodfin 6y ago
        I once worked with a C++ text processing library that saw more than a 50% throughput bump just from reserve()’ing std::string and std::vector space in hot code paths.
• simiones 6y ago
  Most GC languages use bump-pointer allocation and/or compacting garbage collection to (try to) ensure that objects are stored in memory in this way regardless of being dynamically allocated. This means that even naive linked list implementations are typically much more cache efficient than you would expect coming from C, at least after a GC pass. It also means though that changes to the dependency graph of your program can have unexpected effects for your cache hit rates, since the compacting heuristics are pretty simple (they typically work by copying "child" objects immediately after the "parent" object, but there is no mechanism to define the "right" parent for an object)
  • hinkley 6y ago
    In most GCs the mark phase also disrupts the cache by doing what looks a lot like a table scan. That’s one of the reasons for generational collectors. Better cache locality.
  • gameswithgo 6y ago
    I've seen a Linked List get allocated very contiguously at times in .NET when it is just a toy program, like just benchmarking linkedlist performance, it sometimes does really well. But in the context of a big running program with other things in the heap it is much less likely to work out so well.
  • pradn 6y ago
    Modern memory allocators like tcmalloc are pretty good with putting structs of the same size in contiguous areas of the heap. For smaller structs (which most real world cases fall under), it's just one lookup to find the next place to put the new object. So, C and Java will have similar performance for allocating a lot of small objects, I think. There's probably a difference on the deallocation side, especially with fragmentation, but I'm not as knowledgeable about that. If someone has a richer explanation, I'd love to hear.
    • scott_s 6y ago
      As someone who worked on memory allocators in a past life: cosign. Size-class based allocation for small objects is how modern memory allocators have worked for a long time now. I'm genuinely baffled by how many people think that the bump-pointer allocation for same-sized objects is unique to garbage collection.
• junippor 6y ago
  In Julia if you have an estimate of the size (not necessarily a hard bound) you can `sizehint!` to reduce the number of allocations.
• mytailorisrich 6y ago
  > it's best to pre-allocate your memory and then hand out bits as needed through a custom allocator working on the pre-allocated set. Yes. For linked lists this would typically mean creating a pool of objects to be allocated from the pool and returned to the pool as needed for operating the linked list.
• kqr 6y ago
  Doesn't even malloc do this under the hood by only occasionally calling sbrk and otherwise handing out blocks from an internally managed contiguous region? What's the point of doing this again, manually? Or am I mistaken in my memory of the common modern malloc implementations?
  • cnity 6y ago
    malloc aligns very conservatively (because it doesn't know the size of the data you're allocating for), so there are some space gains to be had there. AFAIK also malloc will call sbrk quite a lot, at least from my cursory reading of this musl implementation[0]. [0] https://git.musl-libc.org/cgit/musl/tree/src/malloc/malloc.c?id=e5d78fe8df9bd61940abcd98ad07ed69b7da4350#n349 https://git.musl-libc.org/cgit/musl/tree/src/malloc/malloc.c...
    • CyberDildonics 6y ago
      That doesn't contain calls to sbrk at all, it maps memory in with mmap which is typical of every modern memory allocator.
      • cnity 6y ago
        You're right, I misinterpreted the calls to __brk
      • quantumofalpha 6y ago
        It uses both brk/sbrk ("__brk()" in that code) and mmap, the latter for allocating larger bits of memory. GNU libc does the same thing from what I remember from straces.
  • JoeAltmaier 6y ago
    It can be an order of magnitude faster to do it yourself, depending on how balled up the runtime library has gotten. If you can make some simple guarantees like "I'll realloc similar sized blocks mostly" and "I'm single-threaded thru these calls" then you can drop the bulk of the runtime drama.
• ciarcode 6y ago
  I think this is the solution used in FreeRTOS if you use heap1 as allocator.
• matheusmoreira 6y ago
  Why can't we have this as a general interface in standard libraries? For example, we could have a contextual allocation function: // Contiguous array of 1024 objects of type context = contextual_allocation(1024, sizeof type); // obtain pointer to next free object object = allocate(context);
  • latch 6y ago
    I believe this is how Zig works. Specifically the FixedBufferAllocator. It can further be paired with the ArenaAllocator to make management dead simple.
  • vbarrielle 6y ago
    Zig requires the allocator to be specified for each allocation: https://ziglang.org/documentation/0.5.0/#Memory https://ziglang.org/documentation/0.5.0/#Memory This has a huge impact on the API design, so I don't think this can be retrofit in standard libraries of existing languages (because of backwards compatibility).
    • thechao 6y ago
      In the mid 00s, my advisor had me explore the concept of adding default parameters to C++ functions where the default snagged the nearest lexically scoped named object of the right type from the calling environment, i.e., int someFunctionThatAllocates(int A, int B, allocator const& alloc = default); Then in the calling environments: { auto& alloc = james; if (someFunctionThatAllocates(4, 5)) // ok, uses 'alloc' { } } { if (someFunctionThatAllocates(4, 5, james)) // ok, uses 'james' { } } { auto& alloc1 = james; if (someFunctionThatAllocates(4, 5)) // error: no `alloc` in scope { } } It handily solves a number of problems. In particular, we were looking at how we manage heap allocation for large sparse matrix libraries a la MTL4.
      • gpderetta 6y ago
        Interesting. Isn't this this vaguely reminiscent of implicits in Scala?
• BunsanSpace 6y ago
  the SOP with C++ is you overload the new and delete operators and implement your own heap. It can be very handy especially when you add tags to your allocation so you can track the number of allocations from a specific piece of code, great for finding memory leaks.
• dragontamer 6y ago
  On the contrary: small objects mean that fragmentation is NOT a problem: because your small nodes can be "fit anywhere". Furthermore, if you've got 1000x 8-sized allocations, any of those "holes" can be repurposed for other 8-sized allocations. Meaning: linked lists innately make most simple allocators more efficient. Linked lists are a tradeoff between the difficulty of malloc/free (of which arrays are very difficult), and latency (of which linked lists have much higher latency). A ton of 8-sized allocations is better on fragmentation than a 8-sized / 16-sized / 32-sized ... allocation pattern that most arary-allocators use.
  • alexhutcheson 6y ago
    But then your objects are scattered all over the address space, which means that objects you’re accessing in sequence are unlikely to be in the same cache line, so you pay a cache miss on every single access. Having (maybe?) more efficient malloc/free in exchange for dramatically increasing the cost of accessing your data is not a good trade-off for most access patterns. See Chandler Carruth’s talk from CppCon 2014: https://youtu.be/fHNmRkzxHWs?t=2085 https://youtu.be/fHNmRkzxHWs?t=2085
    • dragontamer 6y ago
      But the entire point of linked lists is to insert in the middle in constant time. 1 -> 2 -> 3 -> 4 Can become... 1 -> 2 -> 2.5 -> 3 -> 4 If you do that with arrays, you need a O(n) memcpy and maybe even a realloc. ----------- Furthermore, linked lists don't even need a malloc routine !!!!!! See Knuth's dancing links (DXL) algorithm. The ability to efficiently add and remove nodes from a linked list (even if that list was statically allocated) can sometimes beat the performance of arrays, because memcpy is just asymptotically slower than insert / remove.
      • gameswithgo 6y ago
        Yes, but if you actually measure some scenarios, it is usually overall faster to pay the cost of O(1) copy. This of course depends on how often you insert things into the middle, vs how often you iterate over the collection. But on a modern computer it is surprising how big that ratio needs to be! In Knuths prime this tradeoff didn't really exist, because memory accesses were about at the same speed as executing an instruction, rather than ~200 times slower.
• as-j 6y ago
  > Lessons from embedded development Frequently you're working with hardware, devices, etc of which there's a limited number. I don't need a linked list to hold data for 3 peripherals. Even if the hardware is changed and the number changes and there's 10 peripherals I don't need a linked list. Sometimes an array is just fine.
  • sgtnoodle 6y ago
    I usually end up with a singly linked list when implementing a singleton API that needs to support an arbitrary number of application created objects. Rather than have the singleton pre-allocate the memory, the application has to do it, then pass it into the API to use for the lifetime of the program. The various parts of the application knows how many objects it needs, and can statically allocate just the right amount of memory.
• jedimastert 6y ago
  I remember seeing a sizable astrophysics Fortran program from many decades prior that had one "MEMORY" array declared at the beginning of the program and legit used it for every single byte of memory for the entire program. It was nuts
  • vecter 6y ago
    The same goes for the AMBER computational chemistry FORTRAN program. The array is called X.
    • jedimastert 6y ago
      Actually, that might be what I'm thinking of. For some strange reason (this was in 2013, mind you) I was involved with translating legacy Fortran projects for multiple departments.
  • queuebert 6y ago
    TEKTON, a crater modeling code, had this, but I think it called the array 'a'.
  • svat 6y ago
    This is also how the TeX program works. Of course it has lots of variables (hundreds of "global" variables in fact), but for everything whose size may vary (boxes, lists of characters, lists of tokens for macros, …), it has two giant arrays of fixed size, one called “str” (aka the string pool, used for strings), and one called “mem” (used for everything else). It's this way partly because of the limitations of Pascal at the time.
• brundolf 6y ago
  You're talking about arenas, right? https://en.wikipedia.org/wiki/Region-based_memory_management https://en.wikipedia.org/wiki/Region-based_memory_management