San Francisco: Switches — a Mill story

Due to scheduling issues, this meetup will take place at an unusual place for us, in San Francisco. We'll be back at Synopsys in Mountain View next month.

Multi-way branches, known as switches or case clauses in various languages, are a notorious pain for compiler writers and CPU architects. On the critical path in important applications from lexers to byte-code interpreters, switches often predict poorly. Short switches with few cases can use a chain of ifs, but are hampered by the low rate at which branches issue on conventional hardware, and may miss several times while working down the chain. A common alternative is to indirect-branch through a jump table, but that approach is subject to misses in the data cache as well a prediction miss. Some CPU architectures have responded by putting the table in the instruction space, but that adds expensive shifters and datapaths to the instruction fetch.

This talk shows how an ultra-wide-issue architecture responds to the switch challenge. The Mill is a family of wide-issue, statically scheduled, exposed pipeline CPUs. Some family members can issue up to 30 instructions every cycle, including up to five branches — and can retire instructions at the same rate. The talk will work through the compiled code for an example with eight cases spanning 100 values. Spoiler: a mid-range Mill does the whole switch, including the action bodies for each case, in four instructions and no table. Which isn't too bad, except that hand-crafted Mill code can do it in two.

Ivan Godard is CTO and a founder of Mill Computing, Inc., developer of the Mill family of general-purpose CPUs. He has written or led the development team for a dozen compilers, an OS, an OODBMS, and much other software. He has no degrees and has never taken a computing course; such things didn't exist when he started.

Due to scheduling issues, this meetup will take place at an unusual place for us, in San Francisco. We'll be back at Synopsys in Mountain View next month.