26
Oct
12

Mutable and Data Caching

This blog post is going to be about the c++ keyword mutable, it is also going to go into using mutable for data caching. To motivate this I am going to give an example from python. If I have a class with a property which is expensive to compute I want to cache it and only recalculate it when necessary.

#==============================================================================
class DataClass(object):
    
    def __init__(self):
        self.__data = None

    @property
    def data(self):
        if (self.__data is None):
            # work out self.__data
        return self.__data

In the preceding example I have used the dynamic typing of python to essentially combine data and a boolean. So if it is None it will be calculated and if not the cached value will be returned.

Now my goal is to replicate this in c++.

The full code to this post (and more!) is available from my bit bucket at mutable.

C++ is a statically typed language so we cannot use the exact same approach here. So what I have done is make a class to encapsulate this idea. As the type of data is irrelevant to this class I have made it a template class. Here is the public API of the class I have called Validated.

//=============================================================================
template <typename T>
class Validated {
public:

  Validated();
  // invalid constructor

  Validated(const T& data);
  // valid constructor

  bool valid() const;
  // is this valid or not?

  void invalidate();
  // makes the class invalid again, so call in a function which will change the
  // cached value.

  void set_data(const T& data);
  // set the data, makes the instance valid.

  operator T();
  operator T() const;
  // implicit conversions to the template type.

This dictates the behaviour of the class so if it has a data value then it is valid and if one has not been set then it is invalid. It also (unusually) contains an implicit type converter to the data type. This is so it can be naturally treated as the data it is validating. This is normally done using an explicit function, for example the c_str() function on a standard string (also see item 5 in More Effective C++), however I feel that the Validated class is just a wrapper around the data so it should natively handle it’s operations.

The code behind this is quite straight forwards and can be seen here.

This approach can also be accomplished by privately inheriting (implementation inheritance) from a Validated base class. I think that this is a very generic concept and so should be a template

Now for the use of this class and the keyword mutable. My example is going to be a triangle and calculating it’s area. So here is the API for my Triangle class, and a Point struct to hold the coordinates.

//=============================================================================
struct Point {
  Point(double new_x, double new_y) {
    x = new_x;
    y = new_y;
  }

  double x;
  double y;
};

//=============================================================================
class Triangle {
public:

  Triangle(const Point& point_1, const Point& point_2, const Point& point_3);
  // Constructor, points should be entered anti-clockwise.

  void set_first_point(const Point& point);
  // Sets the first point

  double area() const;
  // Returns the area

This is a quite straight forward class but it is the implementation which is interesting here. Here are the private members of Triangle.

private:

  Point m_point_1;
  Point m_point_2;
  Point m_point_3;
  
  mutable Validated<double> m_area;
  // this is mutable as it is used as a cache in area() which is a logically
  // const method

This is where the point of this post comes in, the mutable Validated double. Here is a possible implementation of the area() function.

//=============================================================================
double Triangle::area() const
//
//D Returns the area
//
{
  // work out the area using 1/2 ab sin(C)
    
  // a is the length between point 1 and point 2
  double a = sqrt(
    (m_point_2.x - m_point_1.x) * (m_point_2.x - m_point_1.x) +
    (m_point_2.y - m_point_1.y) * (m_point_2.y - m_point_1.y)
  );
  // b is the length between point 2 and point 3
  double b = sqrt(
    (m_point_3.x - m_point_2.x) * (m_point_3.x - m_point_2.x) +
    (m_point_3.y - m_point_2.y) * (m_point_3.y - m_point_2.y)
  );
  // c is the length between point 3 and point 1
  double c = sqrt(
    (m_point_1.x - m_point_3.x) * (m_point_1.x - m_point_3.x) +
    (m_point_1.y - m_point_3.y) * (m_point_1.y - m_point_3.y)
  );
  // use the cosine rule cos(C) = (a^2 + b^2 - c^2) / 2ab
  double cos_C = (a*a + b*b - c*c) / (2 * a * b);
  return 0.5 * a * b * sin(acos(cos_C);
}

This is not that computationally expensive a function but suppose we are calling it a lot, so we decide to cache the result in a member variable m_area. We have two choices here as we are going to be setting a member variable we could change the method to not be const. This works fine but working out the area is logically not going to change the triangle in any way so we call it logically const. The fact that you are caching the area is an implementation detail that should not be reflected in the public API of the class. So this is why the keyword mutable is used. It means you can change that variable in a const method. This is why I declared the m_area variable as mutable. Combining this with the Validated class the function becomes this.

//=============================================================================
double Triangle::area() const
//
//D Returns the area, first time it works it out it caches the result.
//
{
  if (!m_area.valid()) {
    // work out the area using 1/2 ab sin(C)
    
    // a is the length between point 1 and point 2
    double a = sqrt(
      (m_point_2.x - m_point_1.x) * (m_point_2.x - m_point_1.x) +
      (m_point_2.y - m_point_1.y) * (m_point_2.y - m_point_1.y)
    );

    // b is the length between point 2 and point 3
    double b = sqrt(
      (m_point_3.x - m_point_2.x) * (m_point_3.x - m_point_2.x) +
      (m_point_3.y - m_point_2.y) * (m_point_3.y - m_point_2.y)
    );

    // c is the length between point 3 and point 1
    double c = sqrt(
      (m_point_1.x - m_point_3.x) * (m_point_1.x - m_point_3.x) +
      (m_point_1.y - m_point_3.y) * (m_point_1.y - m_point_3.y)
    );

    // use the cosine rule cos(C) = (a^2 + b^2 - c^2) / 2ab
    double cos_C = (a*a + b*b - c*c) / (2 * a * b);
    m_area.set_data(0.5 * a * b * sin(acos(cos_C)));
  }
  return m_area;
}

So the Validated class wrapper is used to cache the value and the member is mutable so that the method can be const.

In the BitBucket repository there is an executable which shows that the cached value is being used. It also shows the Validated::invalidate() method being used in a non-const method on the Triangle class.

If you want to know more about how to NOT use mutable this is a very good article on it which shows some common but incorrect examples of use.

Thanks for reading and putting up with the sporadic and long posts.

About these ads

3 Responses to “Mutable and Data Caching”


  1. October 26, 2012 at 8:16 pm

    Nice bit of C++ code there Dave! What WordPress plugin do you use to display your code?


What did you think?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Follow

Get every new post delivered to your Inbox.

Join 151 other followers

%d bloggers like this: