←back to thread

Making a StringBuffer in C, and questioning my sanity

(briandouglas.ie)
42 points coneonthefloor | 3 comments | 15 Jul 25 10:48 UTC | HN request time: 0s | source
Show context
WalterBright ◴[19 Jul 25 00:25 UTC] No.44611357[source]▶

    new_capacity *= 2;
A better value is to increase size by 1.5:

https://stackoverflow.com/questions/1100311/what-is-the-idea...

replies(3): >>44611645 #>>44612459 #>>44613415 #
emmelaich ◴[19 Jul 25 01:15 UTC] No.44611645[source]▶
I remember reading (decades ago) an extensive article in Software Practice and Experience reaching the same conclusion.
replies(1): >>44611788 #
1. manwe150 ◴[19 Jul 25 01:44 UTC] No.44611788[source]▶
Or like Python shows there, 1.25+k which can be better (faster growth and less memory wasted) than both
replies(1): >>44612494 #
2. burnt-resistor ◴[19 Jul 25 04:04 UTC] No.44612494[source]▶
1.25 of what? Do you mean 2.25*k == 9*k/4.
replies(1): >>44613446 #
3. tialaramex ◴[19 Jul 25 07:49 UTC] No.44613446[source]▶
They say 1.25+k, in this context k will be some constant, suppose it's 16 bytes

Thus you might see a curve like 13, 32, 56, 86 - this curve is aggressive to start but then much gentler. Because it's so gentle it gets the re-use upside for medium sized allocations but it incurs a lot more copying, I can imagine in Python that might be a good trade.