Re: What is the idiom for cached calculations preserving const-ness?

f.fracassi@gmx.net wrote:


[snip]


I'll admit to not having considered the issues you raise below
initially. Yet, I disagree with the alternative (mutable + locking)
you propose. I may have found some middle ground; see below.


rethrow, I guess. Honestly, I didn't think about it initially, but in
retrospect I'd probably make this an assertion.


`of the changing clients'? Did you mean that, in the hypothetical call
stack:

  funcA(...) in libA
    funcB(const matrix &m) in libB
      const matrix &m2 = m.inverse();

that it's the responsibility of `funcA' to change its code? If so,
then yes, I agree.

I'll note that this isn't usually a concern in my domain. That's an
excuse though, and nobody likes those. It sounds like our main concern
here is that actions waaaaay up the call stack can have ramifications
waaaaay down the call stack, causing nontrivial concerns/fixes if you
happen to be the programmer for the deeply-nested part of the stack.

So I think I've found a solution which ensures compile-time
verification of our requirements. It's basically an application of
CTAssert, with a small twist. Let me know what you think of the
following design:

  ----- matrix.h -----
  #include <algorithm>

  template<bool has_inverse>
  struct matrix {
      matrix() {
        std::fill(this->m, this->m+16, 0);
      }
    public:
      float m[16];
      float inverted[16];
  };

  // matrix<true> is-a matrix<false>.
  template <> struct matrix<true>: public matrix<false> {
    private:
      matrix<true>(); // undefined.
  };

  // I might make a matrix.cpp for this in Real Life (tm).
  inline matrix<true>& invert(matrix<false>& m) {
    // do complicated inversion work...
    return static_cast<matrix<true>&>(m); // or dynamic_cast.
  }

  ----- client.cpp ------
  #include <iostream>
  #include "matrix.h"

  void method(const matrix<true>& m);
  template<bool t> void method2(const matrix<t> &m);

  int main() {
    matrix<false> m;

    method(invert(m)); // OK.
    method(m); // compile error!

    method2(m); // OK
    method2(invert(m)); // OK
    return 0;
  }

  void method(const matrix<true>& m) {
    std::cout << "yay guaranteed zero-cost inverted matrix!" << std::endl;
  }

  template<bool t> void method2(const matrix<t>& m) {
    std::cout << "don't know or care what I get." << std::endl;
  }

I actually didn't think this was possible before trying it. A
template<bool> that derives from .. itself! It works because it's not
really `itself', of course; disregarding my inheritance, matrix<true>
is completely distinct from matrix<false>, typewise.

You might consider defining a `matrix<true>(matrix<false>&)' copy
constructor, or any number of matrix<?> constructors; they have obvious
semantics. Perhaps we could use an enum too, instead of a bool; I like
the readability an enum provides.

I like this design because:

  1. The solution is applied at the right time. The existent cache of
     an inverted matrix is, in principle, known at compile time. Thus
     our solution should be a compile-time solution.

     -> You absolutely cannot mess up and find out your matrix is not
        inverted when you need it to be. If you needed an inverted
        matrix as input, you should declare your argument type as such.
        Then, it's your *caller's* fault if the cache isn't there.

     -> This does leave open the problem of declaring an interface
        `const matrix<T> &' and later realizing it should really
        be `const matrix<true>&'. *shrug*, couldn't be perfect.
        Get your design right the first time ;)

  2. It does not add any additional runtime overhead for the inverse
     operation. I initially toyed with the idea of only defining the
     `float inverted[16]' member in the subclass; I threw that design
     away because of this requirement. I don't want to discourage
     clients from swapping between matrix types at will for some
     perceived performance gains.

     -> for those working on e.g. embedded systems, the additional
        memory requirement may be a showstopper. This is not usually a
        concern in my environment. A policy might help here.

  3. It doesn't use mutable. <g>

I haven't tried, or even given it more than a passing thought, but
there might be a more general idiom here. Perhaps a multi-parameter
template:

  // This template sure has a lot of class.
  template<class <bool> Source, class Cached, class UFunc> class Cache {
    /// contains `Source', `Cached', and uses the unary functor
    /// `UFunc' to save `Cached' from `Source' at appropriate times.
    /// ...
  };


Yes, good point; I had not considered this.


Hrm. Yep, good catch. Still, I think the concern is overblown;
nothing will `explode', but we may get the wrong result from the
inverse. Or, if `c.m_' remained unchanged in both threads, we might
compute the inverse twice when we only needed it once.

It is debatable whether this should be fixed in the `matrix<bool>'
class or not. I can see the case for having a locking policy. I can
also see the simplicity argument in running on the unlocked edge, and
telling your clients that if they share a matrix, then it's their
responsibility to lock it -- just like sharing an int or a float.


In reading your complaint here, I think I implied a different dislike
of mutable then I meant. I dislike mutable because of the additional
complication to program comprehension, particularly in multithreaded
environments. The thing I dislike is that `mutable' and the `const'
attached to a method have no proximity requirements. Thus it is easy
to see one and not the other.

Further, and perhaps my experience is unique here, but I find that
`mutable' is not very common. Putting all of these components
together, it is in too many cases reasonable to assume that a const
method is... well, const. This can make debugging code which uses
mutable `surprising'.

(Thanks for challenging my initial design, btw! I have learned much
 through a deeper analysis of this issue.) Cheers,

-tom

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]