50% compiler speedup with some hash tables for register lists.
Clickbaited haha, now look what I mean.
FIRST COMMIT replaces RgObj.TMoveList
with TMoveHashList
.
Currently, TMoveList
is implemented as a list divided into sorted (by id
) and unsorted parts, and is periodically re-sorted. This is referred by a comment as a “disgusting complexity”. I’m inclined to agree, and add it is slow as hell.
Using a HASH TABLE to implement TMoveList
has the following benefits:
-
Client code becomes much cleaner. I also turned move lists into
object
s (without VMTs), as they are only four to five pointers in size anyways. -
Building my application speeds up by 0.1%.
-
Building
webtbs/tw2242
mentioned in the same comment speeds up by >10%:determine_spill_registers()
time decreases from 0.4 to 0.25 seconds (sodetermine_spill_registers()
alone speeds up by >50%), out of ~1.0 second total.
(Not sure if different movelists order can result in different binaries, but even if it can, I tried to reintroduce sorting before traversals and it didn’t affect speed at all.)
SECOND COMMIT replaces CgBase.TSuperRegisterWorkList
with TSuperRegisterWorkHashList
to no effect on my application, but reducing determine_spill_registers()
time on webtbs/tw2242
to nothing: namely, to 0.02 s (20 ms) on the same computer. Stripping 0.35 s of compilation time from ~1.0 s is a 150→100% speedup.