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.
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
The original implementation (also the fastest):
def find_space(size: int) -> 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) -> 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) -> 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?