[CompilerDev] Resolving operator overloading
Posted: Thu Apr 28, 2016 5:36 pm
Hello, AltaLang'ers!
I have a problem, that I managed to solve with huge effort, but with 2-2.5x performance degradation. So, I guess, I should take a step back and re-think if I'm solving the right problem.
Currently I have a bunch of built-in operators, which are overloaded: you can use '+' with int's and float's, use can use '&' with int's and bool's, you can assign value of any type into a reference to that type, etc.
I've started with a bunch of if's then refactored that into a table that contains all possible signatures - with the built-in types number of signatures was finite.
That was a temporary solution as I'm planning to implement int's of different capacity as generics. But, for now, I don't have generics, so I just limited it to commonly used capacities - 8, 16, 32 and 64 bits.
But now I'm implementing tuples - first used defined types. There are two operations on tuples - assignment and member access. Member access is handled separately, because it involves member lookup. But assignment feels like a normal infix operation on two expressions.
For tuples there two overloaded versions of assignment operator: normal one assigns entire tuple into reference to tuple; and unpacking version assigns tuple into tuple of references.
So, I've tried to switch from specifying exact types in the operator table, to using type patterns. So, when checking if certain operator can be used here, I need to find a type that matches generic type pattern and is a supertype of the argument types.
I've ended up with patterns that consist of:
Variables - X
Constants - anything handled by the resolver in the opaque way
Lists - zero or more expressions
For-All expressions - lists of unknown size with elements of the same structure
Lists are used to represent arrays and product types (structures) of compiler data structures used to describe types.
For modelling sum types (tagged unions), I'm using 2-element lists where first element is a tag and a second one is a payload.
Type resolver is trying to solve a statement built out of
* Relation - binary relation on two expressions. Resolver has a built-in relation of equality and a table of user-defined relations, subtyping in particular
* And/Or - containers that require either all/any of their elements to be true
* For-All statement - a statement about elements of the For-All expression
With this representation, here are my subtyping rules:
Resolving algorithm:
1. Normalize input statement into DNF and store a list of alternatives
2. While list of alternatives is not empty - take one alternative and try to solve
3. Processing alternative may fail - no solutions for this alternative, get solved and produce a solution, or spawn new alternatives
4. Add newly spawned alternatives to the list and repeat
For each alternative, statements maintained sorted and are processed in the following order:
1. First equality relations
1.1. First equalitiy of constant to constant, list or forall - this fails bad alternatives early
1.2. Equality of variable to something
1.3. Equality of two lists
1.4. Other equality
2. User defined relations
2.1. Relations over expressions with constant prefixes - they have minimum possible alternatives
2.2. Other relations
3. For-All statements - never processed directly, should be expanded when matching corresponding for-all expression
User defined relations are processed by comparing their elements with conclusions of the rules and get replaced with Or of the premises of the matched rules. This is the source of forking of the alternatives.
First implementation of the resolver slowed-down my tests 10x, after several optimizations it is now about 2-2.5x. In particular, for real inputs resolving does not fork alternatives at all, and all rules are matched by O(1) lookup in hashtable indexed by constant prefixes of the related items. Around 70% of resolving time is spent on variable substitution and about 10% - on normalizing statements.
Probably, I could come up with more ideas for optimization and bring the number down to 1.5-2x - but that's still a lot. That means that matching operators takes as much time as parsing and the rest of semantical analysis altogether. That's very frustrating.
Should I just stop worring about this and continue developing new features on top? Or should I proceed with optimizing? Or is there a way to do things in a dramatically simpler way?
I have a problem, that I managed to solve with huge effort, but with 2-2.5x performance degradation. So, I guess, I should take a step back and re-think if I'm solving the right problem.
Currently I have a bunch of built-in operators, which are overloaded: you can use '+' with int's and float's, use can use '&' with int's and bool's, you can assign value of any type into a reference to that type, etc.
I've started with a bunch of if's then refactored that into a table that contains all possible signatures - with the built-in types number of signatures was finite.
That was a temporary solution as I'm planning to implement int's of different capacity as generics. But, for now, I don't have generics, so I just limited it to commonly used capacities - 8, 16, 32 and 64 bits.
But now I'm implementing tuples - first used defined types. There are two operations on tuples - assignment and member access. Member access is handled separately, because it involves member lookup. But assignment feels like a normal infix operation on two expressions.
For tuples there two overloaded versions of assignment operator: normal one assigns entire tuple into reference to tuple; and unpacking version assigns tuple into tuple of references.
So, I've tried to switch from specifying exact types in the operator table, to using type patterns. So, when checking if certain operator can be used here, I need to find a type that matches generic type pattern and is a supertype of the argument types.
I've ended up with patterns that consist of:
Variables - X
Constants - anything handled by the resolver in the opaque way
Lists - zero or more expressions
For-All expressions - lists of unknown size with elements of the same structure
Lists are used to represent arrays and product types (structures) of compiler data structures used to describe types.
For modelling sum types (tagged unions), I'm using 2-element lists where first element is a tag and a second one is a payload.
Type resolver is trying to solve a statement built out of
* Relation - binary relation on two expressions. Resolver has a built-in relation of equality and a table of user-defined relations, subtyping in particular
* And/Or - containers that require either all/any of their elements to be true
* For-All statement - a statement about elements of the For-All expression
With this representation, here are my subtyping rules:
Code: Select all
// Any type is a subtype of itself, for tuples and functions there are distinct rules
T != Tuple, T != Function ⊢ (T, X) <: (T, X)
// This rule enables automatic de-referencing of L-values
T != Ref, (T, X) <: (U, Y) ⊢ (Ref, (T, X)) <: (U, Y)
// Bottom type is a subtype of any type. 'break', 'continue', 'return', 'throw' have bottom type
⊢ (Bottom, ()) <: (T, X)
// Tuple is a subtype of other tuple, if they have identical field names and type of each field in the first tuple is a subtype of the type of the field in the second tuple
[T <: U for N, T, U in c] ⊢ (Tuple, [(N, T) for N, T, U in c]) <: (Tuple, [(N, U) for N, T, U in c])
// Functions result types are covariant, argument types are contravariant
Q <: R, Y <: X ⊢ (Function, (X, R)) <: (Function, (Y, Q))
1. Normalize input statement into DNF and store a list of alternatives
2. While list of alternatives is not empty - take one alternative and try to solve
3. Processing alternative may fail - no solutions for this alternative, get solved and produce a solution, or spawn new alternatives
4. Add newly spawned alternatives to the list and repeat
For each alternative, statements maintained sorted and are processed in the following order:
1. First equality relations
1.1. First equalitiy of constant to constant, list or forall - this fails bad alternatives early
1.2. Equality of variable to something
1.3. Equality of two lists
1.4. Other equality
2. User defined relations
2.1. Relations over expressions with constant prefixes - they have minimum possible alternatives
2.2. Other relations
3. For-All statements - never processed directly, should be expanded when matching corresponding for-all expression
User defined relations are processed by comparing their elements with conclusions of the rules and get replaced with Or of the premises of the matched rules. This is the source of forking of the alternatives.
First implementation of the resolver slowed-down my tests 10x, after several optimizations it is now about 2-2.5x. In particular, for real inputs resolving does not fork alternatives at all, and all rules are matched by O(1) lookup in hashtable indexed by constant prefixes of the related items. Around 70% of resolving time is spent on variable substitution and about 10% - on normalizing statements.
Probably, I could come up with more ideas for optimization and bring the number down to 1.5-2x - but that's still a lot. That means that matching operators takes as much time as parsing and the rest of semantical analysis altogether. That's very frustrating.
Should I just stop worring about this and continue developing new features on top? Or should I proceed with optimizing? Or is there a way to do things in a dramatically simpler way?
