container-growth-ratio.py

# container implementation details: we assume that the growth is exponential
# and that short string buffer handles strings of smaller size
ratio = 1.5
block = 16

# allocator implementation details: we assume that we're using first fit allocator
# that magically stores block metadata externally and has no alignment restrictions
# for simplicity we just keep track of a single live allocation
allocoffset = 0
allocsize = 0

for i in range(20):
    block = int(block * ratio)
    if allocoffset >= block:
        print(f"round {i}: allocated range [{allocoffset}..{allocoffset+allocsize}), allocating {block} from the beginning")
        allocoffset = 0
        allocsize = block
    else:
        print(f"round {i}: allocated range [{allocoffset}..{allocoffset+allocsize}), allocating {block} by advancing range")
        allocoffset += allocsize
        allocsize = block