Optimizing Codegeneration from Ast

Question

I have been writing a compiler. While profiling the compiler, one method takes 5 seconds to compile 2k lines of code, my profiler tells me that this is the bottleneck.

   def toLLVMHelp(self, tree= None, isGlobal= True):
    if tree == None:
        tree = self.tree #tree is the Ast

    for i in tree: #iterate through the top node
        g = not type(i) is Tree.FuncStart and not type(i) is Tree.FuncBraceOpen and not type(i) is Tree.FuncBody and isGlobal 
        #for code that is not inside a function, it must be put somewhere else, g is a boolean for checking if outside a function 
        if g:
            if i.isEnd(): #is the end node
                self.main += i.compile(self)
            else:
                self.toLLVMHelp(i, g) #recurse for further nodes
                self.main += i.compile(self) #compile turns the node into 'llvm-ir'
        else:
            if i.isEnd():
                self.out += i.compile(self)
            else:
                self.toLLVMHelp(i, g)
                self.out += i.compile(self)

I am guessing, that it is slow because of object dispatch. Any suggestion, would be greatly appreciated.

Answer 1

Ideally, you'd profile it on a line-based manner, seeing where the cost is.

But, I might have some suggestions.

The following if-statement gets run every time the function is called:

    if tree == None:
        tree = self.tree #tree is the Ast

In most cases, it would miss, so maybe separate the rest of the code out to another function? (Also, try tree is None instead of tree == None first).

Now, the following line can also be optimised:

        g = not type(i) is Tree.FuncStart and not type(i) is Tree.FuncBraceOpen and not type(i) is Tree.FuncBody and isGlobal 
        #for code that is not inside a function, it must be put somewhere else, g is a boolean for checking if outside a function 

I think it might as well be written

        g = isGlobal and type(i) not in (Tree.FuncStart, Tree.FuncBraceOpen, Tree.FuncBody)

The reason for this re-arrangement is the following: checking isGlobal is a simple boolean check: really fast. Also, computing type(i) is a function call. Not that expensive, but not cheap either. Better to do that just once. On the other hand, looking up Tree.* is also expensive. There are tricks to make that cheaper as well. I'll get back to that.

        if g:
            if i.isEnd(): #is the end node
                self.main += i.compile(self)
            else:
                self.toLLVMHelp(i, g) #recurse for further nodes
                self.main += i.compile(self) #compile turns the node into 'llvm-ir'
        else:
            if i.isEnd():
                self.out += i.compile(self)
            else:
                self.toLLVMHelp(i, g)
                self.out += i.compile(self)

Not sure if the following will be faster, but I'd like to hope so. That is: profile! I see that in the nested if/else, they share code.

if g:
    if not i.isEnd():
        self.main += self.toLLVMHelp(i, g)
    self.main += i.compile(self)
else:
    if not i.isEnd():
        self.out += self.toLLVMHelp(i, g)
    self.out += i.compile(self)

Again: profile! But I think it will either make it faster, or not be slower, so you should be good. Adding to self.main or self.out is done, but I don't see any nice way to make that better without losing performance.

---

After thinking about it some more, I see you doing string-appends. Depending on the situation, this can be very expensive, as it must do a full copy.

Maybe replace that logic with

self.main_parts.append(self.toLLVMHelp(i, g))
self.main_parts.append(i.compile(self))

and in the end, replace

self.main

with

''.join(self.main_parts)