While scanning my Inbox I read 'fast' and 'array' in the context of functional programming. Well, of course SaC instantly came to my mind (what a surprise ;) ). So I did some measurements myself. I used your programs, except that I increased the array size by a factor of 10. For the C++ version I had to move the array to the heap and fix the order of function applications within the fold. Here are the timings:
<br><br>C++<br>520<br>real&nbsp;&nbsp;&nbsp; 0m0.204s<br>user&nbsp;&nbsp;&nbsp; 0m0.182s<br>sys&nbsp;&nbsp;&nbsp;&nbsp; 0m0.023s<br><br>Haskell IOArray (the extended version with unsafe accesses that was posted shortly after yours)<br>520<br><br>real&nbsp;&nbsp;&nbsp; 0m5.542s<br>user&nbsp;&nbsp;&nbsp; 
0m5.453s<br>sys&nbsp;&nbsp;&nbsp;&nbsp; 0m0.068s<br><br>Haskell Lists (just to be complete)<br>520<br><br>real&nbsp;&nbsp;&nbsp; 0m27.596s<br>user&nbsp;&nbsp;&nbsp; 0m26.650s<br>sys&nbsp;&nbsp;&nbsp;&nbsp; 0m0.870s<br><br>and finally SaC <br>Dimension:&nbsp; 0<br>Shape&nbsp;&nbsp;&nbsp; : &lt; &gt;<br>&nbsp;520<br>
<br>real&nbsp;&nbsp;&nbsp; 0m0.057s<br>user&nbsp;&nbsp;&nbsp; 0m0.048s<br>sys&nbsp;&nbsp;&nbsp;&nbsp; 0m0.000s<br><br>The corresponding SaC program follows. I have compiled it with sac2c -O3. I used the current compiler from the website <a href="http://www.sac-home.org">
http://www.sac-home.org</a>.<br><br>use Structures : all;<br>use StdIO : all;<br><br>inline<br>int sumMod( int a, int b)<br>{<br>&nbsp; return( (a + b) % 911);<br>}<br><br>inline<br>int sumArrayMod( int[*] A)<br>{<br>&nbsp; res = with {
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ( shape(A) * 0 &lt;= iv &lt; shape(A)) : A[iv];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } : fold( sumMod, 0);<br><br>&nbsp; return( res);<br>}<br><br>int main() {<br>&nbsp; testArray = (19*iota(5000001)+23) % 911;<br><br>&nbsp; print( sumArrayMod(<br>
&nbsp;&nbsp;&nbsp; reverse( reverse( reverse( reverse(<br>&nbsp;&nbsp;&nbsp; reverse( reverse( reverse( reverse(<br>&nbsp;&nbsp;&nbsp; reverse( reverse( reverse( reverse(<br>&nbsp;&nbsp;&nbsp; reverse( reverse( reverse( reverse(<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; testArray))))))))))))))))));<br><br>&nbsp; return( 0);
<br>}<br><br><div><span class="gmail_quote">On 5/1/07, <b class="gmail_sendername">Federico Squartini</b> &lt;<a href="mailto:federico.squartini@googlemail.com">federico.squartini@googlemail.com</a>&gt; wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I was reading an old post where Hal Daume III was analyzing Haskell performance for arrays. <br>He proposed a test program which initializes an array, reverse it a number of times, and sums the contents.<br><br>So I wrote a c++ reference program, a naive haskell version using lists and I also tweaked a little bit with the IOArray version, which should be the fastest. Unfortunately there is a&nbsp; huge performance gap. Haskell is slower by a factor of ten, even when using imperative style.
<br><br>C++ <br>time ./arrayC<br>
499<br>
real&nbsp;&nbsp;&nbsp; 0m0.059s<br>
user&nbsp;&nbsp;&nbsp; 0m0.044s<br>
sys&nbsp;&nbsp;&nbsp; 0m0.008s<br>
<br>
HASKELL - IOUArray<br>
time ./IOMutArrayUnboxed<br>
499<br>
real&nbsp;&nbsp;&nbsp; 0m0.720s<br>
user&nbsp;&nbsp;&nbsp; 0m0.571s<br>
sys&nbsp;&nbsp;&nbsp; 0m0.019s<br><br>HASKELL - list<br>

time ./list<br>

499<br>

real&nbsp;&nbsp;&nbsp; 0m1.845s<br>

user&nbsp;&nbsp;&nbsp; 0m1.770s<br>

sys&nbsp;&nbsp;&nbsp; 0m0.064s<br>
<br><br>Can anyone suggest a faster version (using whatever data structure)? I like Haskell very much but I still have to figure out if the slowness of some code is due to my lack of knowledge or to some intrinsic limitation of the language (or libraries).
<br><br>By the way, sorry for the poor quality of the code, I am not a computer scientist.<br><br><br>-------------------------------------------------------------------------------------------------------------------------------
<br>-------------------------------------------------------------------------------------------------------------------------------<br>//compile with <br>//g++ -o arrayC arrayC.cc <br>#include &lt;stdio.h&gt;<br>#include &lt;
math.h&gt;<br><br><br><br>int main()<br>{<br>&nbsp; int array[500001];<br>&nbsp; <br>&nbsp; for (int i=0;i&lt;=500000;i++)<br>&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp; array[i]=(19*i+23)%911;<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp; int tmp=0;<br>&nbsp; for (int cnt=0;cnt&lt;12;cnt++)<br>&nbsp;&nbsp;&nbsp; {<br>


&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int x=0;x&lt;=250000;x++)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp=array[500000-x];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; array[500000-x]=array[x];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; array[x]=tmp;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp; int result=0;<br>&nbsp; for (int i=0;i&lt;=500000;i++)
<br>&nbsp;&nbsp;&nbsp; {<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result=result+(array[i]%911);<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp; result=result % 911;<br>&nbsp; printf(&quot;%d&quot;,result); <br>&nbsp; return 0;<br>}<br><br>---------------------------------------------------------------------------------------------
<br>---------------------------------------------------------------------------------------------<br>-- compile with<br>-- ghc --make -o list list.hs<br>module Main<br>&nbsp;&nbsp;&nbsp; where<br><br>testArray = [ (19*i+23) `mod` 911 |i &lt;- [0..500000]]
<br><br>sumArrayMod =&nbsp; foldl (\x y -&gt; (y+x) `mod` 911) 0<br><br>main = print $ sumArrayMod$<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverse$ reverse$ reverse$ reverse$<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverse$ reverse$ reverse$ reverse$<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverse$ reverse$ reverse$ reverse$
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverse$ reverse$ reverse$ reverse$<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; testArray<br><br><br>---------------------------------------------------------------------------------------------
<br>---------------------------------------------------------------------------------------------<br>-- compile with<br>-- ghc --make -o IOMutArrayUnboxed IOMutArrayUnboxed.hs<br>module Main<br>&nbsp;&nbsp;&nbsp; where<br><br>import Monad
<br>import <a href="http://Data.Array.IO" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">Data.Array.IO</a><br>import Data.Array.MArray<br>import Data.Array.Unboxed<br><br>total, semiTotal ::Int<br>

total= 500000<br>semiTotal=250000<br><br><br>testArray :: IO (IOUArray Int Int)
<br>testArray = newListArray (0,total)&nbsp; [(19*i+23) `mod` 911 |i &lt;- [0..total]]<br><br><br>reverseArray :: IOUArray Int Int -&gt; IO ()<br>reverseArray arr = mapM_&nbsp; (\i -&gt; do oldi &lt;- readArray arr i<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; oldj &lt;- readArray arr (total-i)
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; writeArray arr i oldj<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; writeArray arr (total-i) oldi)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [0..semiTotal]<br><br>sumArrayMod :: IOUArray Int Int -&gt; IO Int
<br>
sumArrayMod arr = foldM (\s i -&gt; do x &lt;- readArray arr i<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return&nbsp;&nbsp; $!(s+x) `mod` 911) 0 [0..total]<br><br><br>main::IO()<br>main = testArray &gt;&gt;= \a -&gt;
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt;
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt; reverseArray a &gt;&gt;
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; sumArrayMod a &gt;&gt;=&nbsp; print<br><br>---------------------------------------------------------------------------------------------------------<br><span class="sg"><br>Federico<br><br><br>
</span><br>_______________________________________________<br>Haskell mailing list<br><a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:Haskell@haskell.org">Haskell@haskell.org</a><br><a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.haskell.org/mailman/listinfo/haskell" target="_blank">
http://www.haskell.org/mailman/listinfo/haskell</a><br><br></blockquote></div><br><br clear="all"><br>-- <br>Stephan Herhut<br>Centre for Computer Science and Informatics Research<br>University of Hertfordshire