[boost] Random access and memoization in TMP

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

Hi.

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.

Regards,
Bruno