littlesmalltalk

littlesmalltalk copied to clipboard

The compiler in version 4 takes multiple seconds to compile examples/disasm.st, which is only 215 lines long. I started looking into why, and this issue is just to record what I found for anyone else who might want to dig further.

The obvious guess is that this is the first version where the compiler is itself in Smalltalk instead of C, and Little Smalltalk is just that slow at everything. But that's not the reason: on a simple benchmark it executes millions of method calls per second.

I extended lst4 with call-count profiling -- unfortunately, the results don't really clear it up to me. Here are the methods called in compiling examples/disasm.st, with the count of how many calls for each:

callcount.txt

(Some of the numbers are inflated slightly because it also recorded counts for compiling the code that dumps the counts. But those mixed-in counts are under 4% of the counts for disasm.st, so I'm not going to the work to split them out.)

Clearly it's heavy on the string and array ops, but it's not obvious to me what higher-level code is making them pile up. A fancier profiler that also tracked the callers of the heavily-called methods would help. Or maybe just interrupting execution at random moments and printing the backtrace.

In summary: compiling a 5k-byte source file needs millions of string and array operations -- on the order of a couple thousand for each byte. There are some obviously quadratic algorithms in the compiler, but I couldn't see a likely candidate for which, on casual inspection.

The code for the profiler: https://github.com/darius/littlesmalltalk/tree/call-count-profiler

I came back to this -- first, I made it interrupt itself every half-million instructions and print a crude backtrace. This showed that the biggest offender seemed to be File's methodCommand: where it reads a string line by line and concatenates it quadratically into a big string (if the text of the method to be compiled is big).

If I add a joinStrings method to List, and change the above method to keep the lines in a list until it has them all, then that speeds up compiling disasm.st from 2.1sec to <0.6sec. It could probably get much better still -- the individual line reads are quadratic also, and by eyeballing the tracebacks the next most time-consuming operation appeared to be expandByteCodes which quadratically fills the bytecode arrays.

But I'm not too eager to meddle with Budd's code more, and anyway maybe it's best to leave it alone outside of the forks directory?

The compiler hack's at https://github.com/darius/littlesmalltalk/tree/faster-compiler