freenode/#sicl - IRC Chatlog
Search
9:52:33
scymtym
beach: thanks. yes, i think it should be as shallow as possible to minimize the expected number of tests. however, perfect balance is not always possible since tests may depend on each other (e.g. layout-of only after lowtag = 3), intervals may overlap, etc. the generator tries to maximize the information gain in each decision node subject to the dependency constraints and logical implications
11:35:49
scymtym
shka__: i don't understand what being optimal for a single concrete call means for a decision tree. for a single concrete call, you don't need a decision tree - the outcome is clear
11:37:05
shka__
but what if in one instance i have drasticly different proportions of types then in the other?
11:40:45
jackdaniel
if you want to optimize it at runtime like that you want tracing jit compilation
11:46:25
scymtym
shka__: that's why i said expected number of tests, i.e. sum of test count for each path multiplied by the probably of the outcome
11:47:06
scymtym
of course, as jackdaniel points out, to get a grasp on the probabilities, some form of profiling is needed
11:48:26
scymtym
and your are right: if the distribution is very non-uniform, a balanced tree may not be optimal
11:48:27
jackdaniel
I think what shka__ is after is optimizing the dispatch at runtime (as opposed to providing optimal one for some kind of "average" workload)
11:59:09
scymtym
it should help a lot in some cases since it cuts down on redundant tests and memory accesses. initial experiments support this. the hard problem will be keep compile time under control
12:00:00
scymtym
but if it works out, it will help with gf dispatch, TYPECASE-like things and pattern matching
12:19:44
scymtym
shka__: i have been wanting to do this for years. now i feel like i'm getting pretty close. but we will see