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