search

AvailLang / Avail

The Avail programming language. Includes the virtual machine, standard library, and standard examples.
BSD 3-Clause "New" or "Revised" License
54 stars 5 forks source link

Avoid redundant type comparisons in LookupTree by navigating to covariant parameters #116

Closed markATavail closed 1 year ago

markATavail commented 8 years ago

After issue #115 we'll have typeTags and metaTags available for many kinds of values and types. That's great for dispatching on top-level arguments, but we often have multimethods that must dispatch on a specific property of an object or type, sometimes even a property of a property of a property.

For example, we have a sorting method that's polymorphic on the number of elements in the tuple being sorted. For performance, it would be useful for the LookupTree to navigate from the argument's type, a tuple type, to its size range, an integer range type. Subsequent tests could examine the integer range type directly, without having to re-examine the tuple type's other properties (the heterogenous and homogenous portions of the element types).

LookupTree can be subclassed with ExtractFeatureLookupTree. The lookup action will maintain an array of "slots", initially populated (on the left) with the arguments. An ExtractFeatureLookupTree indicates what operation (an enum?) to perform, which slot to get the input value from, and which slot to write the extracted feature into. The ExtractFeatureLookupTree has a sole subtree. That subtree's InternalLookupTrees (and the N-way mechanism proposed in #115) will be able to use that newly extracted feature in the exact same way that arguments are already processed individually.

The L2 generated code version of a lookup will likewise introduce a register to hold the extracted feature, and perform a suitable instruction to populate it.

markATavail commented 2 years ago

TypeTag dispatching is complete, including L2. ObjectLayoutVariant dispatching is also complete, including L2. Covariant parameter traversal is essentially implemented (ExtractObjectFieldDecisionStep), but not enabled yet.

markATavail commented 1 year ago

This was completed a couple of years ago. It dispatches based on typeTag, object / object type layout variant, instances of meta- and non-meta enumeration constants, object fields, object type field types, and phrase yield type. The constant-based dispatching can also use a shifted hash value (sometimes producing a perfect-hash lookup) with a shift, mask, and table lookup instruction in the L2 -> JVM.