Saturday, July 18, 2015

Linked Weak Reference Arrays paper --- IWST 2015 prize winner

My paper on Linked Weak Reference Arrays was awarded a prize as the second best paper at IWST 2015.  I would like to thank the IWST 2015 chairs for the opportunity to submit and present my paper, as well as to LAM Research for sponsoring IWST.

In a nutshell, the paper asserts the following.  Whereas regular weak arrays tombstone slots ideally tombstone with the small integer zero, linked weak arrays tombstone with a linked list of small integers.  Each small integer tombstone points to the next tombstoned indexed slot.  The small integer zero indicates the end of the linked list.  The root of the linked list is stored in the linked weak array's first instance variable.  Data races are avoided by adopting the ephemeron finalization convention: when a linked weak array is queued for finalization, the VM turns it into a regular strong array.  When the linked weak array finishes mourning, it makes itself weak again.

This functionality requires a memory manager supporting dynamic slot reference strength.  There are examples of this type of memory manager in the wild.  Most of the complexity appears in the presence of an incremental garbage collector.  Changing weakness (as well as doing a become:, or a oneWayBecome:, or changing classes, etc) can easily invalidate the incremental garbage collector's working assumptions.  A number of years ago, I got HPS to handle this complexity for regular weak arrays and ephemerons.  GemStone/S has been using the improved HPS functionality in production for quite some time.  To date, I know of no problems with the implementation.

The benefit of this different approach to weak array finalization is that the image no longer has to reconstruct information the garbage collector knew.  That is, when a linked weak array mourns, it does not have to perform linear search to find where the garbage collector "hid" the tombstones.  Even better, measurements indicate the linked weak array mourning overhead is lower than that of a regular weak array.  Linked weak array mourning does not have to send the message #size, and does not need a #to:do: loop.  The baseline speed improvement, when every slot is tombstoned, is about 30% (Cuis on Cog r3164).

Regarding the second volume of my Fundamentals book, the next chapter to write is on weak references.  How convenient!

See you next year :).

No comments: