Skip to content

50% compiler speedup with some hash tables for register lists.

Rika requested to merge runewalsh/source:movehashlist into main

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 objects (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 (so determine_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.

Edited by Rika

Merge request reports