Re: [boost] Random access and memoization in TMP

From: Bruno Martínez (br1_at_[hidden])
Date: 2005-08-18 13:37:51

On Thu, 18 Aug 2005 10:59:51 -0300, David Abrahams  
<dave_at_[hidden]> wrote:

> Memoization has lots of weird effects like this.  If you amortize your
> "fast" access over touching all the elements of the list you clearly
> are beating mpl::vector.  But what happens when you only need to look
> at the last 5 elements of a 100-element sequence?  I wonder how likely
> that is after all.

It should be just as efficient, because there's no 'extra' work involved.   
The same number of elements are touched.

On the other hand, I haven't been able to think how to accelerate  
index_of<>, even if it takes a little speed hit.

>> I've been thinking the past days of other functions like drop that could
>> be improved in a similar way, but they have eluded me.  I didn't find
>> mention of similar techniques in the MPL book, so I wonder if I'm making
>> any sense.
>
> You're making plenty of sense; it's something I've thought about quite
> a bit.  But I never quite realized that you can make it "okay" to use
> O(N) operations as though they were O(1).  Maybe this demands a
> re-think of metaprogram efficiency.  If the MPL algorithms and
> iterators could be reworked to take better advantage of memoization,
> it might be that list becomes the most efficient datastructure
> overall, again.

The patch to mpl::advance seems easy.  I haven't done it locally because I  
don't know which version is the one my compiler actually sees.

> It would also be very interesting to see what happens
> to an algorithm like sort when you take forced memoization into
> account.

Indeed.  I searched for theory on memoization before posting, without  
success.  It would seem the C++ template system is the first language with  
complete memoization.  It probably doesn't make sense to have a language  
like that on a speed basis.  If I don't misunderstand the efficiency  
appendix of your book, even at<0, myvec> is O(N) because of the similar  
instantiations the compiler has to go through.  The difference is that  
this work is not interpreted.

Even without some weird O(N)->O(1) cases, memoization has a sw engineering  
impact.  As it's said in the book, it's easier to avoid blobs, for  
example, because there's no speed hit.  It seems to me that there should  
be several patterns and idioms appropiate for such a system treated in  
some paper somewhere.

Bruno