Subject: Re: [boost] Interest check: memoization
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-01-24 23:17:07
James Porter wrote:
> There are a number of issues that make this a fairly complicated
> problem, even with the improved generic programming facilities in
> C++0x. Chief among these is copying. With the naive implementation of
> the memoizer, I found that calculating the result of an unmemoized
> value created 3 copies (one for creating a tuple to search a map for,
> and two to insert the tuple into the map), and returning a memoized
> value created 1 copy (to create a tuple to search the map).
> To make a long story short, I set about trying to reduce the number of
> copies to the expected amount: 1 copy for unmemoized values and 0 for
> memoized values. I'm happy to say that this was a success! The trick
> was creating a tuple that holds references to each argument and can be
> upgraded to hold the arguments by value. In this way, we can compare
> by reference and store by value. This is simple on the surface, but
> requires some care when dealing with rvalue references.
You might want to look at Boost.Intrusive, which allows you to avoid
the extra copies without adding indirection.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk