Boost logo

Boost :

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.


> 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.


>> 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

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at