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

Ivan Godard
Keymaster
Post count: 627

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 ranges) {