Re: [boost] Interest check: memoization

Subject: Re: [boost] Interest check: memoization
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-01-24 23:17:07

AMDG

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.
http://www.boost.org/doc/html/intrusive/advanced_lookups_insertions.html

In Christ,
Steven Watanabe