https://v2.ocaml.org/api/Stdlib.Buffer.html add_string guarantted to double buffer size when needed?

Learning
1

Imagine we have a buffer that arts with size 1, and we do n add_strings of length 1.

If the buffer size doubles on every overflow, it ends up doing O(log n) resizes, with copying of 1 + 2 + 4 + 8 + … = O(n).

On the other hand, if, on every overflow, it only extends by a constant k, we end up doing O(n/k) resizes with copying of 1 + k + 2k + 3k + … = O(n^2)

Question: on hitting end of buffer, does add_string always double buffer size? If not is there a way to force it (or some other lib that has this property)? Thanks!

2

Related to this: what is the right container for serialization routines? I need some “container” over u8’s that is growable, and I can throw u8’s into and then convert into a Uint8Array.

3

The buffer doubles its size every time it needs to grow: https://github.com/ocaml/ocaml/blob/trunk/stdlib/buffer.ml#L90

2 Likes