Hi all, I've been experimenting in ghc with mfix (I noticed on the cvs logs that mdo is going to be supported shortly :P), so I decided to see how it would work for me. My simple task is to normalize an array. That is, given an array, replace each value with a new value such that the array sums to one and that the ratios between values before and after normalization are the same. There is of course a two pass solutions, using a fold and a map. This is implementing using IOArrays, so this looks like: norm a = do t <- foldM (\t i -> (t+) `liftM` readArray a i) 0 [1..sz] mapM_ (\i -> readArray a i >>= writeArray a i . (/t)) [1..sz] where (_,sz) = Data.Array.IO.bounds a There is a one pass solution using mfix. This looks like: mfix (\ ~s -> ioaA a 1 s) where ioaA is defined as: ioaA a i s | i > sz = return 0 | otherwise = do s' <- ioaA a (i+1) s v <- readArray a i writeArray a i (v/s) return (s' + v) where (_,sz) = Data.Array.IO.bounds a Now, in practice, the two-pass solution is about twice as fast as the one-pass solution. I've looked a bit at the core generated, but without knowing what's going on internally, it's hard to say where the inefficiencies come from. I'm hoping someone can shed some light on this. Some timing results based on different array sizes: 50000 elements, 32m heap fix: 0.79u 0.04s 0:00.89 93.2% 0.77u 0.07s 0:00.89 94.3% 0.75u 0.10s 0:00.94 90.4% normal: 0.58u 0.01s 0:00.60 98.3% 0.53u 0.03s 0:00.66 84.8% 0.53u 0.05s 0:00.61 95.0% 100000 elements, 32m heap fix: 2.40u 0.10s 0:02.73 91.5% 2.38u 0.10s 0:02.54 97.6% 2.37u 0.13s 0:02.70 92.5% normal: 1.50u 0.03s 0:01.55 98.7% 1.49u 0.05s 0:01.57 98.0% 1.52u 0.03s 0:01.59 97.4% 200000 elements, 32m heap fix: 7.90u 0.16s 0:08.09 99.6% 7.99u 0.17s 0:08.38 97.3% 7.96u 0.21s 0:08.40 97.2% normal: 4.43u 0.06s 0:04.69 95.7% 4.38u 0.14s 0:04.75 95.1% 4.49u 0.07s 0:04.79 95.1% 400000 elements, 32m heap fix: 29.09u 0.34s 0:30.95 95.0% normal: 14.51u 0.16s 0:15.02 97.6% Using unboxed arrays is not possible in the fixed point version (loop). On the normal version, it just about triples the speed across the board. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
On Friday 27 September 2002 05:19 pm, Hal Daume III wrote:
There is a one pass solution using mfix. This looks like:
mfix (\ ~s -> ioaA a 1 s)
where ioaA is defined as:
ioaA a i s
| i > sz = return 0 | otherwise =
do s' <- ioaA a (i+1) s v <- readArray a i writeArray a i (v/s) return (s' + v) where (_,sz) = Data.Array.IO.bounds a
Using unboxed arrays is not possible in the fixed point version (loop). On the normal version, it just about triples the speed across the board.
Hi, I'm not sure if it's mfix we should blame here. Can you please experiment with the following version of normalize and report on running times? norm a = mdo s <- ioaA 1 s id return () where (_, sz) = bounds a ioaA i s acc | i > sz = return (acc 0) | True = do v <- readArray a i writeArray a i (v/s) ioaA (i+1) s (\x -> v + acc x) It'd be interesting to see the results especially for very large inputs (i.e. >= half a million elements.) -Levent.
Hi again, all. So I rewrote some of the versions, so there are now six versions of the array normalization code. They are: normal: combination of foldM and mapM_ loop: a two-pass loop mimicking foldM and mapM_ unboxed-normal: normal on unboxed arrays unboxed-loop: loop on unboxed arrays fix: using fixIO and a look with Double accumulator cpsfix: using fixIO and a CPS accumulator I ran each of these on arrays of size 100,000, 250,000, 500,000 and 1,000,000 elements. The results are: | FIXIO | TWO LOOPS | fix cpsfix | map/fold loop unboxed-m/f unboxed-loop --------+--------------------+-------------------------------------------------- 100000 | 0.71 1.37 | 1.60 1.61 0.90 0.42 250000 | 6.51 5.74 | 7.48 7.24 2.90 1.22 500000 | 23.88 21.32 | 25.35 26.38 7.51 2.27 1000000 | 92.72 79.16 | 97.83 105.73 21.78 4.54 (sorry if that wraps on your screen -- see the attached file) So, looking at the FIXIO methods, for large arrays, cpsfix seems to dominate. There's a small overhead for small arrays, but this is passed once we get to 250,000 elements (probably much before). I'm (pleasantly) surprised that both fix and cps fix consistently beat the two boxed implementations on the right. I'm shocked that the handwritten loop version does worse than the map/fold version and cannot explain this. Yet, when looking at the unboxed arrays, the map/fold version does *much* worse than the loop version. I'm guessing this has to do with the fact that in the loop version the compiler is unboxing the index variable for the whole loop, rather than unboxing each element in the list for map/fold one-by-one. While I'm happy that the fix versions outperform the 2-pass versions for boxed arrays, the discrepency between 79.16 seconds for one million elements and 4.54 sectons on the same data is alarming. Can anyone suggest a way to reconcile this? - Hal p.s., I've attached the code and results (as comments in the code). -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Sat, 28 Sep 2002, Levent Erkok wrote:
On Friday 27 September 2002 05:19 pm, Hal Daume III wrote:
There is a one pass solution using mfix. This looks like:
mfix (\ ~s -> ioaA a 1 s)
where ioaA is defined as:
ioaA a i s
| i > sz = return 0 | otherwise =
do s' <- ioaA a (i+1) s v <- readArray a i writeArray a i (v/s) return (s' + v) where (_,sz) = Data.Array.IO.bounds a
Using unboxed arrays is not possible in the fixed point version (loop). On the normal version, it just about triples the speed across the board.
Hi,
I'm not sure if it's mfix we should blame here. Can you please experiment with the following version of normalize and report on running times?
norm a = mdo s <- ioaA 1 s id return () where (_, sz) = bounds a ioaA i s acc | i > sz = return (acc 0) | True = do v <- readArray a i writeArray a i (v/s) ioaA (i+1) s (\x -> v + acc x)
It'd be interesting to see the results especially for very large inputs (i.e. >= half a million elements.)
-Levent.
On Monday 14 October 2002 09:25 am, you wrote:
While I'm happy that the fix versions outperform the 2-pass versions for boxed arrays, the discrepency between 79.16 seconds for one million elements and 4.54 sectons on the same data is alarming. Can anyone suggest a way to reconcile this?
As you've remarked before, the mfix version crucially depends on boxing: it wouldn't work with unboxed arrays since the sum is only available after the whole array is traversed. So, the question boils down to the efficiency of boxed vs. unboxed data access, and I don't think there's much we can do there. Of course, I'd love to be proven wrong on this one.. -Levent.
participants (2)
-
Hal Daume III -
Levent Erkok