2012-01-31

addm's case instruction

addm/cstr/case/large domain space issues:
[1.8: intro:
. for a classic case stmt, one ensuring that
no more than one exec'path was activated,
the primary purpose of the variables (and arithmetic)
is to dynamically set the guard ranges .]

if case ranges can be variable expressions,
how does that work at the machine level?
. the alternative execution paths are numbered: 0...n,
so the case stmt is an array 0..n of
pointer to subroutine .
. the pointer could be an offset of the program counter,
so they can be word sized or even byte sized .

[1.8: case method depends on domain size:
. typically for each exec'path,
there is either a list of literals,
or else a pair of possibly variable expressions
delimiting a range .
. next there are 2 cases of domain space:

# small:
. the expression being cased is less than a byte,
or certainly not more than a 16bit word .
. in this case there is a direct mapping
from enum to exec'path number .
. we sort the literal cases,
thus allowing for a binary search during run-time .
. for the case ranges, a..b, c..d, ...,
we need the if/else if ... list:
case => a and case <= b ?
  goto ...
else case => c and case <= d ?
  goto ...
else ... .

# huge: ... ]
large domain space issues:
. how do the cases map to 0..n
when not enum literals?
that's when it loses the efficiency
that case stmt's are known for:
. it's eval'ing every exec'path guard expression
as well as the expression being cased,
then it might be reduced to crawling through
a huge {if/else if ...} list;
what it checks first might depend on profiling:
in the past eval's of this case stmt,
what percentage of time was each case chosen?

1.8: hashing intro:
. the expression is larger than small;
in this case, hashing might work?
in a hash the typical problem is
associating a name with an id# .
. when you find the name,
then you need to replace it with the id#;
you could place the string in a sorted container
in which the insertion operation was cheap;
and then do a binary search to find it,
or you could use the hash method:
. if you expect n strings,
then use an algorithm to turn the string into
a number that can range of n values;
eg, if there are less than 2*^16  values,
then your hash function should return 16bit ints .
. if 2 strings result in the same number
then they both go in the same bucket,
so when your search finds a bucket,
it has to crawl as with the binary search .

1.8: back to the casing problem:
. if the expression being cased is a huge number or string,
then with the literals used in the guard
we build a hash table,
and then hash the value being cased .
. when we find the match,
it's associated with the exec'path number we need .

No comments:

Post a Comment