Wednesday 10 July 2013

Finally, reference types

This morning I coded up another implementation of reference types ("view classes"). And all tests (including codegen) still pass. Yay.

So what has been going on the last two days? Let's first recap the problem statement. In addition to the class fmpzxx, we also want classes fmpzxx_ref and fmpzxx_cref, which we would like to behave essentially like fmpzxx& and const fmpzxx&, except that it should be possible to instantiate them from the underlying C type fmpz*. (NB: you might think that one can use const fmpzxx_ref in place of fmpzxx_cref. But to do so, one has to disable copying of the reference types (i.e. always pass them by reference), and that is not desirable in the applications we have in mind.)

The main problem we have with this is that we do not want to have to write rules for all combinations of argument types (reference, const-reference, non-reference). The natural idea to deal with this is to replace all use of (say) const fmzxx& by fmpzxx_cref, and somehow have the core library deal with this (e.g. using implicit conversion constructors, and translation types, as outlined in my friday email). This takes some work, but is doable, and the result is fairly nice (imho). I have saved the work in my gsoc-views branch.

Unfortunately, this messes with the optimizer. Apparently, the increased number of temporary objects and indirections push the compiler beyond its limits. The result is code like this - which is hilariously bad, and also completely unacceptable. This sort of thing - misestimated register pressure causing the introduction of unnecessary spill slot and then blocking scalar to aggregate optimization - seems to be observable across all versions of gcc, and also clang.

This means two things. Secondly, at some later point in time, I should revisit some of the design decisions of the core library which rely on the optimizer. (I am fairly confident that this will be doable without having to change the concrete classes.) But firstly, I had to abandon Monday's work and start afresh. We need a system in which reference-objects and non-references can be mixed, without converting references to non-reference objects to reference-objects. This can be done (using a kind of duck typing approach), and in fact is what I did this morning. I don't think it's quite as pretty, but still good enough.

2 comments:

  1. Well done on getting view classes working!

    As Fredrik said the other day, this confirms everything we've believed about optimisation of C++ code. But most people will prefer something that works slightly slowly to nothing at all, so this is incredibly valuable work even if it is not able to be sped up as much as one would wish.

    By the way, perhaps srcref would be more consistent with other parts of flint. In fact, cref looks a little like it has something to do with the C language. It's a minor detail, obviously.

    ReplyDelete
  2. I'm not sure what this tells us about optimization of C++ code. I guess its a bit of an arms race. As compiler writers improve the optimizer, users build more layers of indirection, driving the optimizer to its limits, urging the compiler writers to ...

    Regarding srcref: sure, renaming that is no problem at all obviously.

    ReplyDelete