Lowest open space in memory
I'll start with the obligatory:

If you're looking to write a fast interpreter, and you've identified a bottleneck in your memory allocator, a smarter algorithm may save you but at the end of the day rewriting in something lower level is probably the way to go if interpreter speed is that crucial.

The problem with your three snippets is they effectively all do the same thing. By this, I don't mean that the return the same (correct) answer. I mean these three snippets effectively perform the same operations. Just some of the operations are disguised in the second two.

Without having profiling, I can take some guesses about your observed performance. The first is likely fastest because everything is just unrolled into two loops. The second is slowest because of the function call all and the contained generator expression. The third is in the middle because of the (worst case) 256 calls to is_disjoint.

Why are these all the same?


Goes through every index i in range(256), and for each offset from 0 to size checks if it's used (exiting early if it is) returning i if none of them are
Creates a generator that yields an index i (trying 0 to 256) if all indexes from i to i+size are not in used_mem, exiting early when one is) and takes the first yielded i
Goes through every index i in range(256), and checks if every number from i to i+size is not in used_mem (exiting early if one is), returning such an i


Note how these are all just rephrasings of the same algorithm. Your performance isn't going to change much because at the end of the day your algorithm is O(n). Actually, it's a little worse than that. It's really O(n*size), because in the worst case you have to do size comparisons for each of your n "slots" in memory.

You could probably get some mileage out of representing your used_mem as a bitfield where bit i indicates whether slot i is taken (this will be more compact and likely faster to lookup than a set), but...

What you really need is a more efficient algorithm. And fortunately, there is a lot of research in the area of memory allocators. Look through the wikipedia page for many examples of different algorithms for different use cases. One is bound to fit your problem.

One way to reduce your allocator's runtime is with the following simple adjustment: keep track of ranges of memory allocated instead of each slot. So, instead of a set marking each slot as used, maintain a linked list of ranges of slots that are allocated:

used_mem: (start=0, end=10) -&gt; (start=20, end=25) -&gt; (start=30, end=50)
                                    current pointer ^


Additionally, keep a pointer to the last place in the list where you allocated memory.

To allocate memory, start from your current pointer, and see if there is enough space between the last thing allocated (above, slot 25) and the next thing allocated (above, slot 30). If we were allocating 3 slots, we could immediately return slot 26 (and insert (start=26, end=28) into the list, moving the current pointer to after it). If instead, we were allocating something larger (say, 10 slots), then we'd see there's no space between 26 and 30, and we'd move the current pointer to the right and try again.

To reclaim memory, just remove the allocation from the linked list.

This approach has the advantage that of not reconsidering things that have already been allocated (the current pointer), so it typically will find an empty hole faster. Additionally, it considers allocations in chunks, so it can skip large allocations in one loop instead of iterating through each slot individually.