Re: [boost] Random access and memoization in TMP

From: Bruno Martínez (br1_at_[hidden])
Date: 2005-08-19 13:30:39

On Thu, 18 Aug 2005 17:42:26 -0300, David Abrahams  
<dave_at_[hidden]> wrote:

> Bruno Martínez <br1_at_[hidden]> writes:
>
>> 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.
>
> My pointwas that for mpl::vector that's O(1) while for you it's O(N),
> So vector might win in that case.

You're right.

>> 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.
>
> What led you to believe that?

The book.  It has to search for the "memoization record" in a list, even  
if re instantiating the template would have been simple.

>> The difference is that this work is not interpreted.
>
> <blink> Sorry, you lost me.

Nothing new.  The search for the memoization record is faster because it's  
builtin, and it doesn't go through the process of template instantiation.   
Metrowerks seems to be bringing the elements accessed to the front af the  
list, even.

>> 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.
>
> The book says that?

Sorry for putting words in your mouth.

>> It seems to me that there should be several patterns and idioms
>> appropiate for such a system treated in some paper somewhere.
>
> Sounds like a good research topic for... someone like you! ;-)

:D

Bruno