Weighted Reference Counting Example

weighted_reference_counting.md

Weighted Reference Couting

Weighted reference counting is more efficient than traditional reference counting because you don't have to update the reference counted object every time a reference is taken (potentially meaning updating the object on the heap and blowing the processor cache). Weighted reference counting only updates the referenced object when a reference is dropped or when weight is exhausted. Weight Reference Counting is also really good for concurrent systems because the number of synchronisations needed is much lower than normal reference counting.

Algorithm overview:

Allocate a new reference counted object with a default weight (a tunable power of two - usually around 1 << 16 for a real implementation). An initial reference is allocated which points to the object and the weight value is copied into it. Every time the reference is cloned, the weight is split in two (shifting one bit to the right is the same as dividing by two) and one half allocated to the existing reference and one half allocated to the new reference. If the a reference needs to be cloned and it's weight is only 1, then more weight is allocated on the referred to object and a new reference allocated and the whole splitting-and-copying behaviour starts over. Whenever a reference is dropped it's weight is subtracted from the weight of the referred to object. When the object's weight drops to zero it is freed.

Caveats:

Weight reference counting (indeed all reference counting) stops working in the presence of circular references. Either a tracing garbage collector or a "weak" reference should be used to break cycles.

Example:

This example is implemented in Ruby, not because you'd ever need to do such a thing in Ruby, but because it's nice and easy to illustrate the concepts without a lot of boilerplate getting in the way. Also, I like Ruby.

Running the example code below outputs:

Created ReferenceCountedObject with weight 8
Created reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=8>, weight: 8
Dropping my weight from 8 to 4
Created reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=8>, weight: 4
Dropping my weight from 4 to 2
Created reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=8>, weight: 2
Dropping my weight from 2 to 1
Created reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=8>, weight: 1
Allocating more weight
Created reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=16>, weight: 8
Dropping reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=16>
Dropping reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=8>
Dropping reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=4>
Dropping reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=3>
Dropping reference to #<ReferenceCountedObject:0x007fd12489e278 @weight=1>
Weight is 0, drop.

weighted_reference_counting.rb

class ReferenceCountedObject
  # Should be much higher, but is low to make the example exhibit the full range of behaviours.
  DEFAULT_WEIGHT = 1 << 3

  attr_reader :weight

  def initialize
    @weight = DEFAULT_WEIGHT
    puts "Created ReferenceCountedObject with weight #{@weight}"
  end

  def drop_weight(weight)
    @weight -= weight
    puts "Weight is 0, drop." if @weight <= 0
  end

  def add_weight
    puts "Allocating more weight"
    amount_added = DEFAULT_WEIGHT
    @weight += amount_added
    amount_added
  end
end

class Reference
  attr_reader :object, :weight

  def initialize(object, weight)
    puts "Created reference to #{object.inspect}, weight: #{weight}"
    @object = object
    @weight = weight
  end

  def self.create(object)
    new(object, object.weight)
  end

  def clone
    return split_and_clone if weight > 1
    allocate_and_clone
  end

  def drop
    puts "Dropping reference to #{object.inspect}"
    object.drop_weight(weight)
  end

  private

  def split_and_clone
    new_weight = weight >> 1
    puts "Dropping my weight from #{@weight} to #{new_weight}"
    @weight = new_weight
    self.class.new(object, new_weight)
  end

  def allocate_and_clone
    delta = object.add_weight
    self.class.new(object, delta)
  end
end

obj  = ReferenceCountedObject.new
ref0 = Reference.create(obj)
ref1 = ref0.clone
ref2 = ref1.clone
ref3 = ref2.clone
ref4 = ref3.clone
ref4.drop
ref0.drop
ref3.drop
ref1.drop
ref2.drop