Opened 9 years ago

Closed 9 years ago

#4278 closed proposal (fixed)

Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

Reported by: tibbe Owned by:
Priority: normal Milestone: Not GHC
Component: libraries (other) Version: 6.12.3
Keywords: Cc: fox@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: #4277 Blocking: #4313
Related Tickets: Differential Rev(s):
Wiki Page:

Description

This proposal depends on #4277.

The current Data.Map API lacks two important functions:

  • A strict left (pre-order) fold -- needed to e.g. sum all the values in a map efficiently.
  • A strict insertLookupWithKey' -- needed to e.g. update an integer counter and retrieve the previous value in a single traversal.

The benchmark we ran indicates that foldlWithKey' is 95% faster than its lazy counter part. insertLookupWithKey' is only 6% faster, but the speedup is highly dependent on how many times each element is update. Each element was only updated once in our benchmark so real speedups should be larger.

The consideration period is 3 weeks.

Note that the attached patch includes the dependent patches in the above linked ticket.

Attachments (4)

add-a-comprehensive-testsuite-for-data_map.dpatch (116.6 KB) - added by tibbe 9 years ago.
strict-foldl-with-key.dpatch (14.3 KB) - added by tibbe 9 years ago.
strict-fold-with-key.dpatch (15.0 KB) - added by tibbe 9 years ago.
strict-fold-with-key2.dpatch (15.2 KB) - added by tibbe 9 years ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 9 years ago by milan

Blocking: 4311 added

comment:2 Changed 9 years ago by milan

Blocking: 4313 added

comment:3 Changed 9 years ago by milan

Blocking: 4311 removed

(In #4311) This patch is no longer blocked by #4278.

comment:4 Changed 9 years ago by igloo

Milestone: Not GHC

Changed 9 years ago by tibbe

comment:5 Changed 9 years ago by tibbe

Status: newpatch

I've attached a patch that adds the foldlWithKey' function. It replaces the earlier patch. Please apply.

N.B. insertLookupWithKey' has already been added in HEAD.

comment:6 Changed 9 years ago by milan

Cc: fox@… added

Changed 9 years ago by tibbe

Attachment: strict-fold-with-key.dpatch added

comment:7 Changed 9 years ago by tibbe

Discussion thread: http://www.mail-archive.com/glasgow-haskell-bugs@haskell.org/msg28268.html

Discussion summary:

  • Also add a strict right fold (included in the patch)
  • Force the traversal evaluation order in addition to the accumulator (not done; we don't get the Core we want for the fold so I rather not mess with it until #4267 is resolved).
  • There are other *WithKey functions that could need strict versions (not done; out of scope for this proposal).

Patch to apply: strict-fold-with-key.dpatch

comment:8 Changed 9 years ago by igloo

Discussion thread is actually here: http://comments.gmane.org/gmane.comp.lang.haskell.libraries/13544

Reformatting tibbe's summary:

  • Also add a strict right fold (included in the patch)
  • Force the traversal evaluation order in addition to the accumulator (not done; we don't get the Core we want for the fold so I rather not mess with it until #4267 is resolved).
  • There are other *WithKey functions that could need strict versions (not done; out of scope for this proposal).

comment:9 Changed 9 years ago by igloo

Re "Force the traversal evaluation order in addition to the accumulator", I thought the conclusion on the thread was that you would make the change? I think without it the semantics are wrong.

Changed 9 years ago by tibbe

comment:10 Changed 9 years ago by tibbe

I've attached a new version that forces the traversal as well.

comment:11 Changed 9 years ago by igloo

Resolution: fixed
Status: patchclosed

Applied, thanks.

Note: See TracTickets for help on using tickets.