Steven D'Aprano <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
