Dilemma: DiffArray non-performance vs STArray non-readability
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
> 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.
More information about the Glasgow-haskell-users