I researched this for some Java I wrote. Try to avoid shuffling physical memory - you'll write a lot less code and it will be faster, too.
Use an "allocated" list and an "available" list. Keep them in address order. Inserting (moving list elements from insertion point to end) and deleting (vice-versa) are near-zero cost operations on Intel boxes. ( Two millis to move a million ints at 1GHz 5 years ago when I wrote http://www.martinrinehart.com/articles/repz.html - probably half that today.) The worst choice is the "best fit" allocation algorithm. (Grabbing most of a free bit leaves a probably useless small bit. Grab from the first big piece you find.) Circular first-fit is probably best. (Testing was for compiler-type applications.) When space is freed, insert link in ordered chain of free space blocks. Then combine with prev/next blocks if they are free. And when you find the function in Python that matches Java's System.arraycopy(), please tell me what it's called. I'm sure there must be one. -- http://mail.python.org/mailman/listinfo/python-list
