Dilemma: DiffArray non-performance vs STArray non-readability
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? Claus 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?
claus.reinke:
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.
In my view, DiffArray needs a modern rewrite. There's no need for it to be as slow as it is. We played with some similar structures at work, and got quite good performance, so I think the problem is not fundamental. Time for someone to step up and write a new fast diff array. -- Don
Should I add a ticket?
Sounds good - and if you could attach a small example showing how Array is faster that would be helpful too.
Ok, ticket is http://hackage.haskell.org/trac/ghc/ticket/2727 . Hope I got the example right - the effect is clear, but with "functional" DiffArray, it is way too easy to lose single-threadedness. In addition to the basic slowness issue, it appears there has been a serious regression in the area (handling of $! perhaps?) since 6.4.1. Claus
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
participants (4)
-
Claus Reinke -
Don Stewart -
Ian Lynagh -
Simon Marlow