1
\$\begingroup\$

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) -> 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?

\$\endgroup\$
  • 1
    \$\begingroup\$ What is used_mem? A list? A dict? A set? \$\endgroup\$ – AJNeufeld Oct 29 '18 at 4:27
  • \$\begingroup\$ Wouldn't it be easier then to just use some lookup table/hash/dictionary for the numbers instead of calculating them each time? \$\endgroup\$ – t3chb0t Oct 29 '18 at 8:03
3
\$\begingroup\$

Consider searching for 20 free locations, where index 19 is in used_mem.

  • You start at 0, and after finding 19 unused locations, you stumble on index 19 being used.
  • your outer loop restarts the search at 1, and you find 18 unused locations, before (again) finding location 19 is used.
  • you try starting at 2, 3, 4 ... and so on up to 19 ... all futile attempts.
  • finally you advance to starting at 20, which finally has a chance of succeeding.

Clearly you are doing a lot of useless work. Once you find a used location, instead of advancing the outer loop starting location by 1, you should advance the starting location to be 1 more than the used location. After starting at 0, and finding 19 empty locations and discovering location 19 is used, you should immediately start the next iteration at 20.

But we are still testing every index; we can do better.

If locations 5, 10, and 15 are used, using the above strategy, you would start at 0, find index 5 is used, continue from 6, find location 10 is used, continue from 11, find location 15 is used, continue from 16 ...

What if instead, when we start at 0, we jump ahead 19 locations and work backwards? We check 19, 18, 17, 16 ... and find index 15 is used, so we start at 16, jump ahead by 19 to index 35, and work backwards to 16. We haven’t needed to test indexes 0 through 14.

Actually, we only need to work backwards until 20; we’ve already tested 16 through 19 inclusive.

Clearly, for i in range(256) is not going to be useful, because it can’t skip at all. You’ll need while loops and manage your own loop counters. Or use iterators where you can advance it manually using a construct like next(islice(iterator, n, n)).

Implementation left as an exercise for student. Bed is calling.

\$\endgroup\$
3
\$\begingroup\$

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?

  1. 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
  2. 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
  3. 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) -> (start=20, end=25) -> (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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.