Forum Topic: Switches
Talk by Ivan Godard – July 12, 2017, at the
SFBay Association of C/C++ Users
Slides: mill-cpu-switches.04 (.pptx)
This is the eleventh topic publicly presented related to the Mill general-purpose CPU architecture.
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 suffer from poor branch prediction performance. 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 taken the approach of putting the table in instruction space, but that adds expensive shifters and datapaths to the instruction fetch.
This talk shows how the ultra-wide-issue Mill 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 works 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 three instructions and no table. Which isn’t too bad, considering 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.
NOTE: the slides may require genuine Microsoft Windows PowerPoint to view; many clones, and Mac native PowerPoint, are unable to show the animations correctly. If you do not have access to Windows PowerPoint then watch the video, which shows the slides as intended.