On Thu, 18 Aug 2005 10:59:51 -0300, David Abrahams <dave@boost-consulting.com> 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