Re: [boost] Random access and memoization in TMP

From: Bruno Martínez (br1_at_[hidden])
Date: 2005-08-20 14:29:37

> Okay, let's be precise.  *Technically*, at<0, myvec> is O(X) -- where
> X is the number of prior instantiations of at<i,v> -- on most existing
> compilers, but note that v doesn't have to be myvec nor does X have
> any relation to size<myvec>::value.

Yes.

> Okay, that's one way to look at it.  The reasons it is faster are not
> so important for the purposes of this analysis, so I prefer to say
> that it can be very difficult to observe this X because the constant
> is so low compared to the cost of instantiating a single template.

Yes.

>> Metrowerks seems to be bringing the elements accessed to the front af  
>> the list, even.
>
> I think GCC does it too.

Really?  I don't know for sure about Metrowerks, but reordering the list  
would explaint the jumpy behaviour.  In any case the strategies of both  
compilers are different.

>>>> 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.
>
> I guess you're suggesting that instantiating N templates with 1 nested
> typedef might be presumed to be slower than instantiating 1 template
> with N nested typedefs?

No, that's not what I'm trying to say.  Let me put an example, in Haskell  
notation.

blob :: Int -> (Int, Int>
first :: Int -> Int
second :: Int -> Int

In a strict language the fastest implementation is:

first i = func1 (commonfunc i)
second i = func2 (commonfunc i)
blob i = (func1 aux, func2 aux) where aux = commonfunc i

The client does different calls depending on if it needs first i, second i  
or both.

In a lazy language this way is just as fast:

first i = r where (r, _) = blob i
second i = r where (_, r) = blob i
blob i = (func1 aux, func2 aux) where aux = commonfunc i

The client can just call blob and then extract one of the results without  
paying for the other.

With tmp I can go even further:

first i = func1 (commonfunc i)
second i = func2 (commonfunc i)
blob i = (first i, second i)

So blob can disappear without affecting performance.

        
Bruno