Boost logo

Boost :

From: Bruno Martínez (br1_at_[hidden])
Date: 2005-08-17 12:41:00


I was pondering the other day about the unique built in memoization
capabilities of templates. It ocurred to me that if one could share more
between different instantiations the compilation process would be sped
up. For example, take

drop :: Int -> [a] -> [a]

defined so that

(drop 0 list) is (list)
(drop 1 list) is (tail list)
(drop 2 list) is (tail (tail list))

in Haskell this would be written

drop 0 list = list
drop n list = drop (n-1) (tail list)

So that the last clause exploits last call optimization.

However, another way would be

drop 0 list = list
drop n list = tail (drop (n-1) list)

Now, take

at :: Int -> [a] -> a
at n list = head (drop n list)

If I construct a list in O(n) and then take the last element with at, also
in O(n), then access to every element becomes O(1), because traversing to
the last element precalculated all the other positions.

I made a test with gcc, in which I traverse a list in forward direction
but naively use at to get to the current position. There are four
variants. homemade_slow uses the first drop definition. homemade_fast
uses the second. mpl_vector and mpl_list use those sequence classes. The
times were, in seconds:

homemade_slow 41
homemade_fast 0.7
mpl_vector 4
mpl_list 11

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.


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