Lowest open space in memory I am writing a simple compiled programming language. Everything but the bytecode interpreter can run as slow as possible, but I would like the interpreter to fun fast, because that's why I made it compiled. 

Now that much of the language is working, I decided to profile it to see where I could improve the interpreter. And I find out that a particular method, the method that enables the interpreter to use space freed up by previously deleted variables, is the major bottleneck.

The function, find_space, takes in the size of the contiguous memory block to find. A nonlocal variable called used_mem stores all the indices that are being used by other variables. To find_space, one must find an index where the next size items are not in used_mem.

The original implementation (also the fastest):

def find_space(size: int) -&gt; int:
    for i in range(256):  # all possible memory indices
        for offset in range(size):  # for index past the starting index in size
            if i+offset in used_mem:  # check that new index is not in the used memory
                break  # oh well, its used, lets move on
            else:
                return i  # it works! lets use it
    return None


My second implementation (slowest):

def find_space(size: int) -&gt; int:
    return next(i for i in range(256) if all(i+offset not in used_mem for offset in range(size)))


My third implementation (middle):

def find_space(size: int) -&gt; int:
    for i in range(256):
        if used_mem.isdisjoint(range(i, i+size)):
            return i
    return None


However, all these implementations still couldn't get the average total time used on calculating the 46th fibonacci number 10 times below 0.086 sec.

I've tried 3 times, and 3rd time is supposed to be the charm. Therefore, I'm asking all you wonderful, talented people of codereview.stackexchange.com to help me in optimizing this code. 

How can I optimize this code to run as fast as humanely possible in python?
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.