#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 Difficulty: Unknown
Test Case: Blocked By:
Blocking: Related Tickets:

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 12 months ago.
test case
0002-Maintain-per-generation-lists-of-weak-pointers.patch (16.2 KB) - added by akio 11 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 10 months ago.
Relax an invariant in the garbage collector
0001-Update-GHC.ForeignPtr-to-use-addCFinalizerToWeak.patch (8.1 KB) - added by akio 10 months ago.
Changes to GHC.ForeignPtr?
0001-Update-fptr01.patch (760 bytes) - added by akio 10 months ago.
Patch to the test suite
0002-Maintain-per-generation-lists-of-weak-pointers-7847.patch (15.7 KB) - added by akio 10 months ago.

Download all attachments as: .zip

Change History (19)

Changed 12 months ago by akio

test case

comment:1 Changed 12 months ago by akio

  • Status changed from new to patch

comment:2 Changed 12 months ago by liyang

  • Cc hackage.haskell.org@… added

comment:3 Changed 12 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 12 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 12 months ago by akio

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

comment:6 Changed 12 months ago by akio

Updated comments in the patches.

comment:7 Changed 11 months ago by AndreasVoellmy

  • Cc andreas.voellmy@… added

Changed 11 months ago by akio

Split the weak pointer list

comment:8 Changed 11 months ago by akio

I rebased the patches.

comment:9 follow-up: Changed 11 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 10 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 10 months ago by akio

Relax an invariant in the garbage collector

Changed 10 months ago by akio

Patch to the test suite

comment:11 Changed 10 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 10 months ago by aljee@…

commit fe652a8b56c864167ecf1fac899bb3d99363dfcf

Author: Takano Akio <aljee@hyper.cx>
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 10 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.