Assume that I have a linear allocator and I want to "build" a string on it. That is, I will be pushing the bytes to the allocation and change the allocation size dynamically. Now, there is a problem, what if during that process of string building someone else allocates? I see two solutions
1. Copy the string from before and continue pushing bytes.
2. Treating this situation as an error in the code. No other allocations can be made during string building.
The first solution is pretty obvious, but If there are two interleaved string builders running the waste of space can be enourmous.
The second solution is better in that it doesn't waste memory, but it forces a certain structure in the code, sometimes can be tricky to think about memory. The way to check for the error in such case would be to store some variable current_token in the allocator. Whenever a normal allocation is done it checks whether no string builder or other allocation is done (current_token == 0).
For string builder allocations, on the builder start, the allocator returns a unique token. After the string building has started only token allocations are allowed and the token must be equal to the one the string builder has given you. Then (a) no other string builder allocation can start and (b) every normal allocation will fail.
In such case it is wise to use assert to check the correctness of the token, because it is an assumption about the structure of our code. But we're coupling asserts with checking procedures that depend on runtime and in release they will execute but have no effect.
The question is whether using assert like this is a good idea (and why!) and if no what alternatives would I have
1. Copy the string from before and continue pushing bytes.
2. Treating this situation as an error in the code. No other allocations can be made during string building.
The first solution is pretty obvious, but If there are two interleaved string builders running the waste of space can be enourmous.
The second solution is better in that it doesn't waste memory, but it forces a certain structure in the code, sometimes can be tricky to think about memory. The way to check for the error in such case would be to store some variable current_token in the allocator. Whenever a normal allocation is done it checks whether no string builder or other allocation is done (current_token == 0).
For string builder allocations, on the builder start, the allocator returns a unique token. After the string building has started only token allocations are allowed and the token must be equal to the one the string builder has given you. Then (a) no other string builder allocation can start and (b) every normal allocation will fail.
In such case it is wise to use assert to check the correctness of the token, because it is an assumption about the structure of our code. But we're coupling asserts with checking procedures that depend on runtime and in release they will execute but have no effect.
The question is whether using assert like this is a good idea (and why!) and if no what alternatives would I have
Edited by bumbread
on
Other options:
3. Reserve space in your linear allocator for max string length, and just fill it in what you have when you do your string "building". Anything else that allocates, will happily take memory from end of max string.
4. First run dummy string "build" that only calculates length of string, but to does not write output. Then you know exactly how much to allocate for running your real string "build" code.
5. Use different arena for string building
Assert is fine to your for your situation if that checks situation that happens because of error in your code (wrong assumptions). Assert is not ok as runtime check for handling errors because of user input. That's error checking, not asserts.
3. Reserve space in your linear allocator for max string length, and just fill it in what you have when you do your string "building". Anything else that allocates, will happily take memory from end of max string.
4. First run dummy string "build" that only calculates length of string, but to does not write output. Then you know exactly how much to allocate for running your real string "build" code.
5. Use different arena for string building
Assert is fine to your for your situation if that checks situation that happens because of error in your code (wrong assumptions). Assert is not ok as runtime check for handling errors because of user input. That's error checking, not asserts.
Edited by Mārtiņš Možeiko
on
I think it's worth pointing out that with exponentially growing buffers on a linear allocator, the amount of memory waste can be large, but it's at least strictly bounded. For example, with a growth factor of 2x, you're guaranteed to waste less than 3 bytes for every 1 byte used (<75% waste), and if I've done my math right, the average waste with worst-case allocation patterns (never able to realloc-in-place) is ~65% waste, or around 1.9 bytes wasted per byte used. Depending on how scarce memory is, you might or might not be okay with that.
Edited by Miles
on