Arrays vs Lists and Specialization

[Ketil Z. Malde]

Matthew Donadio <m.p.donadio@ieee.org> writes:

> OK, my question then has to do with the efficiency of lists versus
> arrays.  Do the latest compilers handle handle arrays efficiently, or
> are lists really the way to go?  

I've currently struggled a bit with arrays.  I have a list based
program (calculating suffix arrays, since you ask), and since I
experience a notably lower performance than array based C equivalents,
I thought using arrays would help me out.

Currently, I've been able to use arrays efficiently as read-only data
structures. I've tried to use STArrays to do updates imperatively, but
it's still slow, and uses a lot of memory (that doesn't show up in the
heap profiling).  I'll try to wrap more of the program in the ST
monad, to see if it helps.

> If there is a performace difference, is it generally big enough to
> warrant rewriting algorithms?

I think it is hard to answer that generally.  For some algorithms, the
benefit can be significant; it depends on your application, your data
set, and your resources. 

But remember that correct is better than fast, and readable is better
than correct. :-)

-kzm
-- 
If I haven't seen further, it is by standing in the footprints of giants