Dilemma: DiffArray non-performance vs STArray non-readability

Simon Marlow marlowsd at gmail.com
Mon Nov 3 07:40:45 EST 2008


Claus Reinke wrote:
> I keep wanting to use DiffArray as the natural functional solution to
> single-threaded array use. But everytime I try, I get smacked over
> the head with the actual performance figures. Sometimes, even plain
> arrays are faster in a loop doing array updates, in spite of all the 
> copying involved. And when copying on update dominates the runtime, 
> using IntMap tends to be faster - the "indirections" are the wrong way
> round, but don't pile up, just that array lookups aren't quite constant
> time.
> 
> But when I really need to avoid the updates, and need constant
> time lookup, I'm stuck: DiffArray tends to slow everything down
> (I vaguely recall locks and threads being at the heart of this, but
> I haven't checked the code recently), so my only option seems to
> be to transform my nice functional code into not-nice sequential code 
> and use STArray.
> 
> Is there any way out of this dilemma? What do other Ghc users use?
> 
> If locks really are the issue, perhaps using STM instead of MVars
> in the DiffArray implementation could help. As long as my array uses are 
> single-threaded, STM optimism might be able to avoid
> waiting/scheduler issues? Or am I on the wrong track?

It needs to be thread-safe, but I imagine that using atomicModifyIORef 
rather than STM or MVars is the way to get good performance here.

> PS Btw, I thought the DiffArray performance issue was ancient,
>        but I can't find a ticket for it, nor does the haddock page for
>        Data.Array.Diff mention this little hickup. Should I add a ticket?

I see there is one now, thanks.

Cheers,
	Simon



More information about the Glasgow-haskell-users mailing list