I read
For CPython, id(x) is the memory address where x is stored.
And it's a given the id of an object never changes, which means an object always stored at a given memory address in its lifetime. This leads to the question: what about fragmentation of (virtual) memory?
Say an object A is at address 1 (has id 1), takes up 10 bytes, so it takes up addresses 1-10. Object B has id 11 and takes up bytes 11-12, and object C takes up addresses 13-22. Once B goes out of scope and gets GC'd, we'll have fragmentation.
How is this conundrum resolved?
CPython uses its own memory allocator for small objects, the pymalloc-allocator. A quite good description can be found in the code itself.
This allocator is pretty good at avoiding memory fragmentation, because it reuses the freed memory efficiently. However, it is only a heuristic and one could come up with scenarios which lead to memory fragmentation.
Let's play through what happens when we allocate an object with size of 1byte.
CPython has its own so called arena for objects smaller than 512 bytes. Obviously, 1 byte request will be managed by its allocator.
Requested sizes are divided in 64 different classes: 0th-class is for sizes of 1..8 bytes, 1th-class is for sizes or 9..16 bytes and so on - this is due to required alignment of 8 bytes. Every of the above classes has its own more or less independent/dedicated memory. Our request is for the 0th-class.
Let's assume this is the first request for this size-class. A new "pool" will be created or an empty pool reused. A pool is 4KB big, and thus has space for 512 8-byte "blocks". Despite requestion only 1 byte we will be blocking another 7 bytes of the occupied block, so they cannot be used for another objects. All free blocks are kept in a list - in the beginning all 512 blocks are in this list. The allocator deletes the first block from this free-block-list and returns its address as pointer.
The pool itself is marked as "used" and added to a list of used pools for 0th-class.
Now, allocation another object with size <=8 bytes happens as follows. At first we look at the list of used pools for 0th-class and will find a pool which already in use, i.e. has some used and some free blocks. Allocator uses the first free block, deletes it from the list of free blocks and returns its address as pointer.
Deleting first object is easy - we add the occupied block as head of the list of free blocks in the (so far single) used pool.
When a new object of 8 byte is created, so the first block in the free-block-list is used, and this is the block which was used by the first, now deleted, object.
As you can see the memory gets reused, and thus memory fragmentation is vastly reduced. This doesn't mean there cannot be memory fragmentation:
After allocating 512 1-byte-objects, the first pool becomes "full" and a new pool for 0th-class-sizes will be created/used. Once also we add another 512 objects also the second pool becomes "full". And so on.
Now, if the first 511 elements are deleted - there will be still one byte which blocks whole 4KB, which cannot be used for other classes.
Only when the last block is freed, the pool becomes "empty" and thus can be reused for other size-classes.
The empty pools are not returned to the OS, but stay in the arena and are reused. However, the pymalloc manages multiple arenas, and if an arena becomes "unused" it might be freed and occupied memory (i.e. pools) is returned to the OS.