DiffArray performance unusable for advertized purpose

[claus]

(cf. this  ghc-users thread)

Data.Array.Diff.DiffArray is unusably slow. Sometimes even Data.Array.Array is faster in single-threaded use, defeating the purpose. The attached code tries to demonstrate the issue, if I got the single-threadedness via $! right (default compilation ghc --make SlowDiffArray.hs gives Array, build with -DUseDiff to get DiffArray).

As I happened to have some older ghcs around, I tried those as well, and it seems the issue got worse around 6.8.3 (SlowDiffArrayA-<version>: Array; SlowDiffArrayDA-<version>: DiffArray?):

$ for i in *.exe ; do  echo $i; time ./$i; done
SlowDiffArrayA-61120081004.exe
9990001

real    0m0.307s
user    0m0.015s
sys     0m0.015s
SlowDiffArrayA-641.exe
9990001

real    0m0.261s
user    0m0.030s
sys     0m0.000s
SlowDiffArrayA-661.exe
9990001

real    0m0.260s
user    0m0.015s
sys     0m0.000s
SlowDiffArrayA-683.exe
9990001

real    0m0.232s
user    0m0.015s
sys     0m0.000s
SlowDiffArrayDA-61120081004.exe
9990001

real    0m12.932s
user    0m0.031s
sys     0m0.000s
SlowDiffArrayDA-641.exe
9990001

real    0m7.114s
user    0m0.015s
sys     0m0.016s
SlowDiffArrayDA-661.exe
9990001

real    0m5.774s
user    0m0.015s
sys     0m0.015s
SlowDiffArrayDA-683.exe
9990001

real    0m12.814s
user    0m0.015s
sys     0m0.000s

(measured on Pentium M 760, 2GHz, Windows XP)

[the majority of the issue probably lies in the DiffArray implementation, hence component libraries, but it seems that compiler and runtime system also play a role]

[claus]

example of DiffArray? slower than Array in single-threaded use

[igloo]

Thanks for the report and testcase!

[igloo]

DiffArray isn't getting much love where it is now; perhaps we should split it off into a separate diffarray package? That way it could have a separate maintainer and become decoupled from GHC's major release schedule. Also, it wouldn't appear to be blessed, which is a good thing if it is "unusably slow".

[duncan]

Splitting it out seems reasonable to me.

[igloo]

Proposal is #3370.

[igloo]

diffarray is now in its own package. Ticket moved to here:  http://trac.haskell.org/diffarray/ticket/2