> This reminds me of a question I could not solve on my own yet (due to
> lack of an operational profiler for the most part): Is it
> possible that
> ghc knows how to transform Array data structures into destructive
> arrays in some settings?
If you mean does ghc ever implement the (//) operation destructively, the
answer is no. It always copies the array before performing the update.
There's a well-known trick the compiler can play to make (//) work in
constant time: namely instead of copying the array you perform the update
descructively, but ensure that any references to the old array are
indirected through a filter that returns the old values for any updated
slots. In the common case where the array is used single-threadedly, the
filter will be garbage collected. I believe hbc uses this idea.
> I had an algorithm with a terrible time complexity and wrote an
> implementation using purely functional Arrays. Since the runtime was
> still to bad, I tried ST together with MutableArrays instead, but the
> runtime got worse.
There could be a number of reasons for this: perhaps your program wasn't
reliant on O(1) complexity for array update, perhaps the overloading was
expensive (indexing arrays is overloaded), or perhaps the ST combinators
weren't being inlined. In GHC 4.02 the latter two shouldn't be a problem:
if your array is indexed with Int, then you'll get specialised array
operations, and the ST implementation is now much faster than pre-4.00
compilers.
If you still have the program, we'd love to take a look at it and perhaps
add it to our benchmark suite.
Cheers,
Simon
