Opened 11 years ago

Closed 10 years ago

Last modified 10 years ago

#2727 closed bug (invalid)

DiffArray performance unusable for advertized purpose

Reported by: claus Owned by:
Priority: normal Milestone: 6.12.1
Component: libraries (other) Version: 6.11
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

(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]

Attachments (1)

SlowDiffArray.hs (539 bytes) - added by claus 11 years ago.
example of DiffArray slower than Array in single-threaded use

Download all attachments as: .zip

Change History (7)

Changed 11 years ago by claus

Attachment: SlowDiffArray.hs added

example of DiffArray slower than Array in single-threaded use

comment:1 Changed 11 years ago by igloo

difficulty: Unknown
Milestone: 6.12 branch

Thanks for the report and testcase!

comment:2 Changed 10 years ago by igloo

Milestone: 6.12 branch6.12.1

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".

comment:3 Changed 10 years ago by duncan

Splitting it out seems reasonable to me.

comment:4 Changed 10 years ago by igloo

Proposal is #3370.

comment:5 Changed 10 years ago by igloo

Resolution: invalid
Status: newclosed

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

comment:6 Changed 10 years ago by simonmar

Type of failure: Runtime performance bug
Note: See TracTickets for help on using tickets.