Looking for info on Python's memory allocation

[Edvard Majakari]

Steven D'Aprano <steve at REMOVEMEcyber.com.au> writes:

> I'm discussing memory allocation techniques with somebody, and I'm trying to
> find a quote from -- I think -- Tim Peters where he discusses the way Python
> allocates memory when you append to lists. In basic terms, he says that every
> time you try to append to a list that is already full, Python doubles the size
> of the list. This wastes no more than 50% of the memory needed for that list,
> but has various advantages -- and I'm damned if I can remember exactly what
> those advantages were.

That method of allocating memory is not used only in Python. The idea is that
if you double the amount of memory always allocated, the interval between
allocations grows exponentially (assuming storage usage grows in linear
manner). 

Memory allocation is often very expensive, because the os works often has to
seek for large enough free block to allocate for application. What is even
more expensive is joining of free blocks which happens every now and then.

I guess you could do the same by tripling memory usage every time you need
more memory. This would reduce number of allocations needed even more. But the
problem is you'd waste even more memory - 2/3 actually. So, doubling the size
of chunks is used, and the technique is quite common.

-- 
# Edvard Majakari		Software Engineer
# PGP PUBLIC KEY available    	Soli Deo Gloria!
You shouldn't verb verbs.