Improvements to the caching variable trick

In my last article, I explained how you can use functors to replicate lazy evaluation and caching. Several people mentioned some problems with that trick and I am going to now explain what those are and how to fix them. For review, here is the code from the last article:

template < typename T >
struct cached_value {
  cached_value(function<T()> c) : calculator(c) {}
  void invalidate() { cache_valid = false; }

  T operator() () {
    if (!cache_valid) {
      value = calculator();
      cache_valid = true;
    }
    return value;
  }  

private:
  bool cache_valid;
  T value;
  function<T()> calculator;
};

struct has_cache_value {
  cached_value<int> my_value;

  has_cache_value() 
    : my_value(bind(&has_cache_value::calculate, this))
  {}
private:
  int calculate() { return 5; }
  

The first one is rather glaring and points out that I need to be more careful about what I’m posting sometimes:

template < typename T >
struct cached_value {

  T operator() ();

};

There are some valid reasons why one might want to return a value rather than a reference, and to make my article much easier to read and limit the amount of assumptions made about the type, I decided to go with by value. This assumes though that the cost of copying T outweighs the cost of calculating it with the function attached to this caching functor. Furthermore, if your type is a raw type like a double, an integer, a pointer, etc…then passing by value can be cheaper than by reference. We should also consider making this function a const function.

First thing we need to do is establish what the return type will be. A standard used by many boost metafunctions is for functors to have a “result_of” typedef within them. This makes them easier to use with a variety of constructs including bind. So the first thing that’s going to happen is to calculate that type from the type of the template parameter. To do that we need a test (instructional articles from now on will include unit test code):

#include <boost/type_traits.hpp>
#include "../include/cached.hpp"

struct object
{
};

// Meta-function that returns a bool-type
// representing whether cached<T>::result_of
// is a reference.
template < typename T >
struct reference_check
  : boost::is_reference<typename cached<T>::result_of>
{};

BOOST_AUTO_TEST_CASE(reference_vs_value)
{
	BOOST_CHECK(!reference_check<int>::value);
	BOOST_CHECK(!reference_check<object*>::value);
	BOOST_CHECK(reference_check<object>::value);
}

The code that passes this test uses the boost MPL and type traits modules to decide if a reference should be added to type T for the result of the caching operator:

#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/type_traits.hpp>

template < typename T >
struct cached
{
	typedef typename boost::mpl::eval_if<
	  boost::mpl::or_<
	    boost::is_fundamental<T>
	  , boost::is_pointer<T>
	  >
	, boost::mpl::identity<T>
	, boost::add_reference<typename boost::add_const<T>::type>
	>::type result_of;
};

The second issue is more interesting. Many objects that we might want to cache are not default constructable and this cache class requires they are by holding a default initialized variable of type T. To change this, we’re going to have to use some alignment tricks and placement new/delete.

First though, lets finish the caching interface with the above changes and make unit tests for it:

// new headers in test code...
#include <boost/bind.hpp>

// altered 'object' definition...
struct object
{
	object() {}
	object(int i) : val(i) {}
	int val;
};

// test function...
object fun(int & count) { 
    ++count;
    return object(42); 
}

// test for caching...
BOOST_AUTO_TEST_CASE(non_default_construct)
{
	int count = 0;
	cached<object> cache(boost::bind(fun, boost::ref(count)));

	BOOST_CHECK(cache().val == 42);
	BOOST_CHECK(cache().val == 42);

	BOOST_CHECK(count == 1);

	cache.invalidate();

	BOOST_CHECK(cache().val == 42);
	BOOST_CHECK(count == 2);
	BOOST_CHECK(cache().val == 42);
	BOOST_CHECK(count == 2);
}

And the code that passes it:

template < typename T >
struct cached
{
	typedef typename ... result_of;

	result_of operator()() const {
		if (!valid) {
			valid = true;
			value = fun();
		}
		return value;
	}
	void invalidate() { valid = false; }

	cached(boost::function<T()> const& f)
	  : value()
	  , fun(f)
	  , valid(false)
	{}

private:
	mutable T value;
	boost::function<T()> fun;
	mutable bool valid;
};

Now we know that it works the way it should and can move on by removing the default constructor definition to ‘object':

struct object
{
	object(int i) : val(i) {}
	int val;
};

And we get the failure we expect:

In file included from workspace/cached_variable/test/cacher_test.cpp:8:0:
workspace/cached_variable/test/../include/cached.hpp: In constructor ‘cached::cached(const boost::function&) [with T = object]’:
workspace/cached_variable/test/cacher_test.cpp:36:58: instantiated from here
workspace/cached_variable/test/../include/cached.hpp:33:17: error: no matching function for call to ‘object::object()’

To fix this we need to use placement new and have a storage buffer within which to do so. It is tempting to simply use a byte array for this but you can read Andrei Alexandrescu’s article on discriminated unions to see why this is a problem. To fix that problem we’ll use some boost type traits (that are included in the C++11 standard library) to calculate alignment and provide a correctly aligned buffer for storage of our type:

template < typename T >
struct cached
{
	typedef typename boost::mpl::eval_if<
	  boost::mpl::or_<
	    boost::is_fundamental<T>
	  , boost::is_pointer<T>
	  >
	, boost::mpl::identity<T>
	, boost::add_reference<typename boost::add_const<T>::type >
	>::type result_of;

	result_of operator()() const {
		if (!valid) {
			valid = true;
			new (value) T(fun()); // build from copy in place
		}
		return *value;
	}

	void invalidate() {
		if (valid) value->~T(); // destroy old one
		valid = false;
	}

	cached(boost::function<T()> const& f)
	  : storage()
	  , value(reinterpret_cast<T*>(&storage))
	  , fun(f)
	  , valid(false)
	{}

	~cached() { if (valid) value->~T(); }

private:
	typedef typename boost::aligned_storage<
	  sizeof(T)
	, boost::alignment_of<T>::value
	>::type storage_t;

	mutable storage_t storage;
	T * value;
	boost::function<T()> fun;
	mutable bool valid;
};

Now the only requirement of this object is that the value type it contains is copyable. Since it’s basically useless without this feature this requirement is acceptable. We can now cache any type we might want to and do so efficiently. There’s only one piece of improvement that I can immediately think of that needs to be done to this construct and that is to allow the user the power to override the result_of so that it can return references when it otherwise would not, or visa-versa. This is a relatively simple change to make. First the test:

BOOST_AUTO_TEST_CASE(reference_override)
{
	using namespace boost;
	BOOST_CHECK((is_reference<cached<int,int const&>::result_of>::value));
	BOOST_CHECK((!is_reference<cached<object,object>::result_of>::value));
}

And the production code where we simply move the calculation of result_of to a default template parameter:

template <
  typename T
, typename RESULT_OF = typename boost::mpl::eval_if<
    boost::mpl::or_<
      boost::is_fundamental<T>
    , boost::is_pointer<T>
    >
  , boost::mpl::identity<T>
  , boost::add_reference<typename boost::add_const<T>::type>
  >::type
>
struct cached
{
  typedef RESULT_OF result_of;
  ...
};      

It would also be possible to allow the user to override the storage mechanism but I’m not seeing much utility in that. At any rate, it is left to you, the reader, to perform that task if you need it.

About these ads

One Response to “Improvements to the caching variable trick”

  1. I think using boost::optional (soon to be std::optional) would end up better. If nothing else, you wouldn’t need it to be default constructible.

Leave a Reply

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 26 other followers

%d bloggers like this: