ChrisJefferson
commented
4 years ago Hi,
So my feeling on enums (which I might regret later / be proved wrong on) is that permutation algorithms tend to spend a lot of time doing perm.apply(integer), and you really want that operation to be as close to an array lookup as possible -- so we probably want to use at least the option to do static trait dispatching on the most important algorithms (of course we can benchmark against dynamic trait dispatching).
Just as an example, I think schreiervector should probably be struct schreiervector<P: Permutation>. Now, I might regret that later, and we don't have to it straight away.
In the lazy implementation, this kind of model would possible require only making Vecs of one type of permutation (although that isn't fatal, the most common way you end up with a Vec of permutations is you are multiplying things together in a schriervector.
Of course, all this staticness will make things take longer to compile. In my constraint solver (https://www.github.com/minion/minion) you can choose at compile time if you want to compile with static or dynamic dispatch (which is possible in C++ with some hackery, don't know about rust). It takes about 8 times longer to compile and runs about twice as fast.
So, this is as far as I can tell the safest way to use the trait approach. This introduces the following things:
Permutation Trait. A trait that encapsulates what being a permutation is. Has support for (lazy) composition, exponentiation, division. It also has non lazy inverses and conversion to the full permutation representation. Also, it allows for application, that automatically unfolds the "computation" and as such can be more efficient than naively multiplying all the levels.
Join and Pow. Two wrapper structs that allow for the lazy approach to exists. Join exists in fixed size (2-arity) and variable, and can be used to efficiently evaluate the composition of many permutations. Pow instead can be used for any kind of exponentiation (in the case of positive exponent application is very efficient, while with negative the inverse needs to be computed and as such can be more complex)
Full Permutation. This is the OG permutation type. It survives mostly untouched, except from the addition of the inverse caching, and from some functionality being moved to the Permutation trait.
As always, there are some tradeoffs to make.
We deviate from the use of ^, * for permutations. Since I have limited experience with GAP and this notation in particular, this change is not one I feel very strongly about, but it might be a big one for some one else. The usage of permutations in code is more verbose, often needing to call the
collapsemethod after the computation. Unfortunately, the orphan rule of Rust does not allow to implement traits for traits, so if we want to maintain the two things the only solution is a wrapper struct.Non fixed size handling is annoying. In the case of MultiJoin, the obvious solution would be to use a
Vec<Box<dyn Permutation>>in order to allow for MultiJoin to act lazyily. However, since the Permutation trait requires Sized, this does not compile. At the moment, I made it so the MultiJoin unfolds the computation tree on creation, which could be a performance hit in case the components are very deep and application is needed.In order to allow for the inverses to be cached, and to comply with the Permutation API I needed to allow for interior mutability and "fight the borrow checker". I have done this via a RefCell. This is all nice and good (and in fact the standard way to do this), but it might come to hurt us down the line when we add multithreading (as while Rc has an Arc counterpart, RefCell needs to be Mutexed to be safe, which might hurt perfomance?)
Benchmarking & Tests. I have not setup testing and benchmarking yet. I have rewritten the existing tests to make use of the new API, but I will need to add more tests and some benches. I am not sure if it would be worth benchmarking against the old implementation or if just for some of the choices (the first that comes to mind is that at the moment we compute (a b)^-1 as is, while an alternative way would be to compute b^-1 a^-1. Naively, the one chosen looks better, but is it?)
Functions naming. To be honest, I kind of winged those ones. Not sure if
and_thenis the best name for composing permutations. Alsocollapseandapply. Also, some names might be better if shorter, in order to make it less ugly to look at.Finally, I have taken the liberty to think about a couple of alternative ways, which can solve some of the issues above:
An enum based approach. While I love traits, it seems that they have a lot of caveats when dealing with these kinds of computation trees (see the Sized issues in 2. and the orphan rules in 1.) An alternative that I have used with some success in cs4201 and have seen used in Rust-analyzer is that of enums instead of traits. Since we a fixed number of permutations that we want to support (and I don't think we will be wanting other crates to extend our permutation trait) this can be a good solution to allow more flexible trees. Some issues with this are that we will pay a dynamic dispatch cost on each call and we will need to allocate a lot more (for example instead of a
Join<A,B>we will need to haveJoin(Box<Join<A,B>>)as an enum variant, with one allocation for each level of the tree.Mixed approach. Trying to combine the two, so add a new enum that implements Permutation, but takes care mostly of what is in JoinMulti. This could give us some flexibility and possibly solve that akwardness. On the negative, I am not 100% sure it would work.
Let me know what you think!