Mill Computing, Inc. › Forums › The Mill › Architecture › switches › Reply To: switches

p.s. For greater detail, here’s the comment from the specializer function that does this.

/*

Each of the ranges can be isolated by a “less than”

comparison, so the maximal number of branches is the size

of the ranges vector. A less-than compare requires one

branch per range, while an equality compare requires one

branch per non-default value. Consequently equality takes

one branch for two ranges when a non-default range of extent

one is adjacent to a default range wheres less-than would

take two branches; a non-default range of extent greater

than one takes one branch using less-than and a number of

branches equal to the extent using equality; and a

non-default branch of extent one adjacent to a non-default

of any size takes one branch in both less-than and

equality.

The worst case is a run of extent-one ranges. If there are

N ranges, then sequential equality needs N branches and

will execute N/2 of them. With less-than you need one

branch to split N to 2*(N/2), 2 to split 2*(N/2) into

4*(N/4) and so on. That is 2N-1 total to the bottom level,

and log2(N) levels. So less-than will always need more

branches than equality, because the bottom level of a

less-than is the same as an equality and there are all the

upper levels on top of that.

As for latency, the dividing point is when is log2(N)

smaller than N/2; the break-even is 8. So we less-than

down until the number of cases is eight or less, and do

sequential equality after that.

The job of this function is to partition

the ranges by adding tests on pred that branch to interior nodes

of the tree until the test is trivial and we can go to the leaf

ebbs given by the switch statement.

“home” is the original ebb that ended with the switch dispatch.

“node” is the root ebb that ends with the switch, or recursively

an inner node in the tree of ebbs that results from splitting

the case space with lss operations.

“pred” is the switch expression that is being tested; it will

be one argument to all the comparisons in the tree.

“ranges” is all the value ranges that must be resolved leafward

of home in the splitting tree; each has a leaf ebb and a

contiguous range of cases that go to that ebb.

*/

void switchPartition(ebbId home, ebbId node, dropId pred,

row