#7847 closed feature request (fixed)

Maintain per-generation lists of weak pointers

Reported by: akio Owned by:
Priority: normal Milestone:
Component: Runtime System Version: 7.7
Keywords: Cc: hackage.haskell.org@…, andreas.voellmy@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

Currently the runtime system keeps a list of all live weak pointers, and traverses it once every (major or minor) GC. This is very slow if the program keeps many weak pointers alive. Some comments in the rts source suggest that it should be using one weak pointer list per generation, so these patches implement that.

The attached test program tries to imitate the memory behavior of code that uses a particular FRP library. The patches make the program 3x faster on my machine.

One problem I can see with the patches is that it creates a race condition between finalizeForeignPtr and addForeignPtrFinalizer. I'm not even sure what the correct behavior is when addForeignPtrFinalizer is called after finalizerForeinPtr.

Attachments (6)

weak.hs (2.2 KB) - added by akio 23 months ago.
test case
0002-Maintain-per-generation-lists-of-weak-pointers.patch (16.2 KB) - added by akio 22 months ago.
Split the weak pointer list
0001-Allow-multiple-C-finalizers-to-be-attached-to-a-Weak.patch (15.2 KB) - added by akio 21 months ago.
Relax an invariant in the garbage collector
0001-Update-GHC.ForeignPtr-to-use-addCFinalizerToWeak.patch (8.1 KB) - added by akio 21 months ago.
Changes to GHC.ForeignPtr
0001-Update-fptr01.patch (760 bytes) - added by akio 21 months ago.
Patch to the test suite
0002-Maintain-per-generation-lists-of-weak-pointers-7847.patch (15.7 KB) - added by akio 21 months ago.

Download all attachments as: .zip

Change History (19)

Changed 23 months ago by akio

test case

comment:1 Changed 23 months ago by akio

  • Status changed from new to patch

comment:2 Changed 23 months ago by liyang

  • Cc hackage.haskell.org@… added

comment:3 Changed 23 months ago by akio

I updated and re-validated the patches, following the suggestions given by Edward Yang on ghc-devs. I believe now the code doesn't have the addCFianlizerToWeak# / finalizeWeak# race condition. It also fixes a finalizeWeak# / finalizeWeak# race condition that existed before my changes.

comment:4 Changed 23 months ago by akio

I updated the patches again, thanks to more comments by Edward Yang. Now addCFinalizerToWeak# and finalizeWeak# use lockClosure() rather than cas() for synchronization. I believe the first patch is much simpler now.

comment:5 Changed 22 months ago by akio

Updated and rebased the patches. A remaining race condition between finalizeForeignPtr and addForeignPtrFinalizer has been fixed.

comment:6 Changed 22 months ago by akio

Updated comments in the patches.

comment:7 Changed 22 months ago by AndreasVoellmy

  • Cc andreas.voellmy@… added

Changed 22 months ago by akio

Split the weak pointer list

comment:8 Changed 22 months ago by akio

I rebased the patches.

comment:9 follow-up: Changed 21 months ago by simonmar

  • difficulty set to Unknown
  • Status changed from patch to infoneeded

patch 0001 looks good to me.

On patch 0002:

  • Why do we have dead_weak_ptr_list_tail rather than just consing new items on the front of the list?

If you haven't already, I recommend testing these patches with libraries/base/tests/memo001.hs and libraries/base/tests/memo002.hs. Those are pretty good stress tests of the weak pointer implementation.

comment:10 in reply to: ↑ 9 Changed 21 months ago by akio

Thank you for review.

Replying to simonmar:

patch 0001 looks good to me.

On patch 0002:

  • Why do we have dead_weak_ptr_list_tail rather than just consing new items on the front of the list?

This is a trace of an earlier design that survived by accident. I'll clean it up in a few days.

If you haven't already, I recommend testing these patches with libraries/base/tests/memo001.hs and libraries/base/tests/memo002.hs. Those are pretty good stress tests of the weak pointer implementation.

Yes, the patches passed these tests (and the rest of validation).

Changed 21 months ago by akio

Relax an invariant in the garbage collector

Changed 21 months ago by akio

Changes to GHC.ForeignPtr

Changed 21 months ago by akio

Patch to the test suite

comment:11 Changed 21 months ago by akio

  • Status changed from infoneeded to patch

I cleaned up the code and removed weak_ptr_list_tail and dead_weak_ptr_list_tail. Rebased and validated. This change caused one of the test output to change, so I also attached a patch to the test suite.

comment:12 Changed 21 months ago by aljee@…

commit fe652a8b56c864167ecf1fac899bb3d99363dfcf

Author: Takano Akio <[email protected]>
Date:   Mon Mar 11 18:51:05 2013 +0900

    Maintain per-generation lists of weak pointers (#7847)

 includes/rts/storage/GC.h                |    3 +
 includes/stg/MiscClosures.h              |    1 -
 rts/PrimOps.cmm                          |    4 +-
 rts/RetainerProfile.c                    |    8 +-
 rts/RtsStartup.c                         |    6 +-
 rts/Weak.c                               |    2 -
 rts/Weak.h                               |    2 +-
 rts/sm/Compact.c                         |   10 +-
 rts/sm/GC.c                              |    2 +-
 rts/sm/MarkWeak.c                        |  229 ++++++++++++++++++------------
 rts/sm/Storage.c                         |    3 +-
 utils/deriveConstants/DeriveConstants.hs |    1 +
 12 files changed, 161 insertions(+), 110 deletions(-)

comment:13 Changed 21 months ago by igloo

  • Resolution set to fixed
  • Status changed from patch to closed

All applied, thanks

Note: See TracTickets for help on using tickets.