3 ms·

Example: reading a file line-by-line. You don’t, can’t, know how big a line is. Your best option is to allocate some random chunk of memory, like 4 kilobytes, r

Example: reading a file line-by-line. You don’t, can’t, know how big a line is. Your best option is to allocate some random chunk of memory, like 4 kilobytes, read 4 kilobytes from the file into memory, and see if you happened across a newline in there. If you did, shuffle everything around a little / realloc / ringbuffer shenanigans; do your favourite. If you didn’t, make the buffer bigger (by 1.5x? 2x? Log2x?), and try again. This dance is super common with variable length protocols over unframed streams - ie, most things over tcp. So this is an exceptionally common pattern in IO operations. Other common times this pattern happens: finding all items in a list that satisfy a predicate; tracking items a user has added to an interface; cycle detection in graphs; …

dwattttt 2y ago
I don't think this or the sibling would be improved with a function that gave you an arbitrarily sized allocation where you also need to query the size of that allocation though? In all the cases you need to know what the size of the buffer is, even though you don't care whether it's 1kb, 4kb, or 8kb (although I imagine you'd care if you got 16b or 16gb)
- nickelpro 2y ago
  It's not about querying the size, it's about what the allocator has available without having to ask the operating system for new pages. It's got a contiguous block of 6371 bytes? Cool I'll take that, the specific size didn't matter that much.
- nine_k 2y ago
  E.g. "Give me something in the ballpark of 4 KiB; more is OK, but tell me how much". It would allow the allocator to return a chunk it has handy, instead of cutting it to size and fragmenting things, only to be asked to make the chunk larger a few microseconds later. It will save both on housekeeping and fragmentation handling if the caller knows that the chunk will likely need to grow.
  - celrod 2y ago
    C++23 added `allocate_at_least`: https://en.cppreference.com/w/cpp/memory/allocator_traits/allocate_at_least https://en.cppreference.com/w/cpp/memory/allocator_traits/al... I'm not sure if any standard libraries have an implementation that takes advantage of the "at least" yet.

dwattttt 2y ago

I don't think this or the sibling would be improved with a function that gave you an arbitrarily sized allocation where you also need to query the size of that allocation though? In all the cases you need to know what the size of the buffer is, even though you don't care whether it's 1kb, 4kb, or 8kb (although I imagine you'd care if you got 16b or 16gb)

nickelpro 2y ago
It's not about querying the size, it's about what the allocator has available without having to ask the operating system for new pages. It's got a contiguous block of 6371 bytes? Cool I'll take that, the specific size didn't matter that much.
nine_k 2y ago
E.g. "Give me something in the ballpark of 4 KiB; more is OK, but tell me how much". It would allow the allocator to return a chunk it has handy, instead of cutting it to size and fragmenting things, only to be asked to make the chunk larger a few microseconds later. It will save both on housekeeping and fragmentation handling if the caller knows that the chunk will likely need to grow.
- celrod 2y ago
  C++23 added `allocate_at_least`: https://en.cppreference.com/w/cpp/memory/allocator_traits/allocate_at_least https://en.cppreference.com/w/cpp/memory/allocator_traits/al... I'm not sure if any standard libraries have an implementation that takes advantage of the "at least" yet.