<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
</head>
<body bgcolor="#ffffff" text="#000000">
<div class="moz-text-flowed"
style="font-family: -moz-fixed; font-size: 12px;" lang="x-western">Let
me refine my earlier posting in this regard. The code below has two
different implementations of convolution, The first implementation
runs marginally faster than a straightforward C implementation using
nested for loops. This is of course a delightful result, especially
given the declarative style of the code.<br>
<br>
The second implementation (my attempt to imitate the nested 'for' loops
of a 'straightforward' convolution) runs 4x slower. Are there any
general principles of Clean programming that would allow me to
understand -- on inspection of the code -- why the second
implementation does not achieve equivalence with the corresponding C
code?
<br>
<br>
Regards,
<br>
David
<br>
----
<br>
module myconvolve
<br>
<br>
import StdEnv
<br>
<br>
// When compiled with clm -fusion, this implementation proves to be
<br>
// marginally faster than gcc -O2 compiled C using nested for loops
<br>
// as in:
<br>
// for(i=0; i<na; i++){
<br>
// for(j=0; j<nb; j++){
<br>
// ab[i+j] += a[i] * b[j];
<br>
// }
<br>
// }
<br>
convolve :: (ar e) (ar e) -> (ar e) | Array ar e & Arith e
<br>
convolve a b = {let start = max 0 (i-m)
<br>
end = min i n
<br>
in
<br>
foldl (+) zero [ a.[i-k] * b.[k] \\ k <-
[start..end] ]
<br>
\\ i <- [0..(m+n)]}
<br>
where
<br>
m = size a - 1
<br>
n = size b - 1
<br>
<br>
<br>
// Why does this implementation (imitating the C code above) run 4x
slower?
<br>
// It used to run 30x slower, but:
<br>
// (1) Adding a type for iconvolve`, including uniqueness for ab
<br>
// and strictness for {i,j,k}, produced a 5x speedup.
<br>
// (2) Adding a and b to the parameter list of iconvolve gave another
2x.
<br>
iconvolve :: !{#Real} !{#Real} -> *{#Real}
<br>
iconvolve a b = iconvolve` ab a b 0 0 0
<br>
where
<br>
na = size a
<br>
nb = size b
<br>
nab = na + nb - 1
<br>
ab :: *{#Real}
<br>
ab = createArray nab 0.0
<br>
iconvolve` :: !*{#Real} !{#Real} !{#Real} !Int !Int !Int ->
*{#Real}
<br>
iconvolve` ab=:{[k]=ab_k} a b i j k // constraint k==i+j is
maintained
<br>
| i >= na = ab
<br>
| j >= nb = iconvolve` ab a b (i+1) 0 (i+1)
<br>
| otherwise = iconvolve` ab` a b i (j+1) (i+j+1)
<br>
where
<br>
ab` = {ab & [k] = ab_k + a.[i] * b.[j]}
<br>
<br>
<br>
Start :: Real
<br>
Start = (iconvolve a b).[m+n-2]
<br>
//Start = (convolve a b).[m+n-2]
<br>
where
<br>
m = 10000
<br>
n = 6000
<br>
a :: {#Real}
<br>
a = {fromInt x \\ x <- [1..m]}
<br>
b :: {#Real}
<br>
b = {fromInt x \\ x <- [1..n]}
<br>
<br>
<br>
</div>
</body>
</html>