Boost logo

Boost :

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.


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