Recurring C programmer conundrum: You want to allocate memory up front, but you don't know how much memory will be needed. If anyone have good approaches to this, please share them with me! Here are mine:
1, "Dry run" the algorithm first to see how much it will need (I do this often with file parsing). 2. Set a memory budget and fail if you go over it (possibly with a retry). 3. Guestimate and realloc if you run out. 4. Compare maximum possible memory usage. Ideas?
The problem is not how you allocate memory but how to manage the unknown size. Typically example: i need a buffer to put together a string, but how much memory will i need?
@EskilSteenberg You want to use OS-specific methods of taking advantage of 64-bit address space. So you allocate a range of the space that is actually bigger than you will ever need, but don’t commit it, so it hardly costs memory (just page table space). Then as you need more memory you just
@Jonathan_Blow It doesn't solve the issue. If I start using a section of the range, then i cant expand my section, if something has taken memory after that section, so i still need to know how much large continuous section i need up front.
@EskilSteenberg Virtually allocate 1GB or something. Memory will not be "actually" allocated until you write to it. IANAL
@Hasen_Judi You (and almost everyone in this thread) thinks much bigger than i do, so maybe i should have been clearer; a typical example is constructing a string, its likely to be smaller than a tweet, but there is no clear upper bound.
@EskilSteenberg strongly recommend Memory Allocation Strategies from @TheGingerBill TLDR: For your case, using an arena might work, specially if you are able to deallocate the memory all at once https://www.gingerbill.org/ser...
@ikiguy95 @TheGingerBill No allocator is not the issue. The issue is not knowing how much to allocate.
@EskilSteenberg Mmap/virtual alloc but just reserve fuckton of address space, no commit. Commit pages as needed. Also, i usually have a gather fn that finds the correct amount, then do alloc. But mostly, you just have to figure out a big enough number, and realize you were retarded when you
@simplex_fx If you are calling mmap, in order to construct a string, something has gone very wrong.
@EskilSteenberg Batch stuffs together into one/several “arenas”, then grow the arenas dynamically if needed. Allocating everything up front is often not a hard constraint, nor should be (unless your app is the only thing running on the system, like a console game or something).
@hoangdt_ If you are building something like a text string, you can make it a linked list of text chunks in order to be able to extend it, but the complexity and the error-prone-ness is far worse than, just computing how much you need up front.
@EskilSteenberg thousand answers to this, and it warrants a classic: it depends. And it depends on the usage - for example are "objects" to store going to be same size, are they going to benefit from linear access.. preallocate arena, can you flush it or you need to manage it/defrag?..
@Keyframe “It depends” is the right answer.
@EskilSteenberg use Zig #std.heap.StackFallbackAllocator class="text-blue-500 hover:underline" target="_blank" rel="noopener noreferrer">https://ziglang.org/documentat...
@EskilSteenberg The growth strategy matters if you'd like to use realloc() to dynamically grow the memory. High frequent call of realloc() is not good.