Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Weighted Reference Counting Example

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.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.