This repository has been archived by the owner on Aug 3, 2022. It is now read-only.
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Objectives
This pull request improves the per-insert performance of
CuckooSet
by changing its backing storage fromArray
toUnsafeMutablePointer
.Implementation
When initializing a set, every pointer in the buffer is initialized to
nil
to indicate an empty bucket. This operation still takes linear time as the initializer must iterate through every pointer in the buffer. The buffer's header is empty. Instead of storingcapacity
andcount
in the header, they are stored inline at the class definition. This may change to simplify copy-on-write semantics, but for now should provide meager performance benefits.Performance
Benchmark output on the
CuckooSet<Int> Insert
task outputs the following comparison statistics:The
CuckooSet<Int> Contains
task showed no significant improvement.Most of this improvement is associated with the removed bounds checks associated with unsafe pointers. This significantly reduces memory safety, but our tests guarantee this implementation is safe.