Objectives

CuckooDictionary aims to expose a very similar API to the Swift standard library's Dictionary but by using an open-addressed hash table and the same cuckoo hashing algorithm as CuckooSet.

Tasks

• [x] Write unit tests
• [x] Implement methods
• [x] Write documentation

Objectives

This pull request improves the per-insert performance of CuckooSet by changing its backing storage from Array to UnsafeMutablePointer.

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 storing capacity and count 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:

Tasks with difference scores larger than 1.05:
  Score   Sum     Improvements Regressions  Name
  1.341   1.341   1.341(#76)   1.000(#0)    CuckooSet<Int> Insert (*)

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.

Issue Description

We don't have a system in place to profile the memory allocated to a hash table. We should have a workflow to reliably detect memory efficiency improvements and regressions measured by load factor.

Proposed Solution

Create a new test case for memory efficiency tests. Instead of relying on XCTest performance tests which do not reliably work on all platforms, we can use standard assertions over the count and capacity of a given collection through a series of insertions.

Parameters

The memory efficiency of the current insertion algorithm depends on two variables:

1. The load factor cap, or the maximum ratio of count / capacity.
2. The bump count cap, or the maximum number of consecutive bucket displacements.

Load Factor Cap

Bumps are caused by collisions, so the likelihood of a bump increases as load factor increases. Keeping the load factor low decreases the complexity of each insert operation, but increases the amount of empty buckets in the table. Not considering the bump count cap, the ideal load factor cap is one where any farther increase in load would trigger a bump chain that takes more time to traverse than would be taken to expand the table.

Bump Count Cap

The primary function of the bump count cap is to avoid bump loops. A bump loop occurs when the same sequence of members are bumped more than once. This is the only case where an insertion might fail in a cuckoo hashing algorithm, so these loops must be detected. The number of consecutive bumps per insertion is also a good secondary indicator of load factor, so keeping the bump count cap low can avoid unnecessary work caused by a high or absent load factor cap.

Current Profile

The current master branch uses two methods to determine when to expand the hash table:

1. A load factor cap of 0.5, meaning the hash table is expanded anytime count becomes greater than capacity / 2. The likelihood of collisions increases exponentially as count approaches capacity, so keeping the table's load factor low avoids doing unnecessary bumps.
2. A bump count cap of 20, meaning if 20 consecutive members are displaced from their buckets to insert a new member, the hash table is expanded. As the number of consecutive bumps increases, the probability the insert operation is in a "bump loop" increases.

According to these conditions, the best case load factor with the current design is 0.5, and the worst case could be as low as 2 / capacity. In the event of a hash flooding attack, the capacity of the table would grow exponentially until the machine runs out of memory.

Optimizing for Memory Efficiency

Since memory efficiency and insert performance are inversely related, the optimal cap is where any farther increase in the cap would cause an increase in the rate of change of time per operation.

Detailed Design

The benchmark should be run as an executable that takes the following arguments:

1. A bump count cap range or a ratio of bump count cap to the number of occupied buckets.
2. A number of consecutive benchmarks to run.
3. A maximum number of insertions to perform (optional, defaults to 1M).

Usage: swift run MemoryBenchmarks <file>
  --cycles <Int>
  --size <Int> (optional)
  --max-load-factor <Double> (optional)
  [--min-bump-count <Int> | --min-scaled-bump-count <Double>] 
  [--max-bump-count <Int> | --max-scaled-bump-count <Double>]

And should write a JSON document to <file> with the following structure:

{   
    "runs": [
        {   
            "bumpCountCap": 0.05,
            "loadFactorCap": 0.7,
            "results": [
                {
                    "count": 2,
                    "capacity": 32,
                },
            ]
        },
    ],
}

This data should allows us to plot a two-dimensional graph with:

1. The bump count cap on the X axis.
2. The load factor on the Y axis.

Interpreting Results

When interpreting this graph:

• A slope of 0 would imply memory efficiency is unaffected by the bump count cap (but may be limited by a load factor cap).
• A positive slope would imply memory efficiency increases as the bump count cap increases.
• A negative slope would imply memory efficiency decreases as the bump count cap increases.

This information should help identify when these limits should be changed as the implementation of the insertion algorithm changes. It can also help detect regressions and improvements as the mean load factor accross runs increases or decreases. This should be used in conjunction with a time performance graph to determine how a change affects performance, and optimize algorithm variables.

Overview

To test the efficiency of the algorithm and implementation, we need to measure the performance of common operations on large collections to determine whether they can claim O(1) performance or just O(log n).

It's also important to compare the performance of each data structure with a counterpart. CuckooSet can be compared to Swift's Set and CuckooDictionary to Swift's Dictionary. It's expected that the Element type and number of elements will influence relative performance, so many should be tested. Eventually we can compare CuckooOrderedSet and CuckooOrderedDictionary to counterparts in the Collections package from the team at Apple.

Implementation

We can use XCTest to measure performance, and change the gitignore file to track the baseline files. To make sure these baselines can accurately reflect regressions and improvements to performance, we will need to pay more attention to hardware and software updates fro GitHub Actions, since they handle the allocation and resources for our virtual machines.

Alternatives

Another option is to move the benchmarking to another repository to avoid adding bloat to the main repository. This can always be done down the line if the bloat gets excessive.

Objectives

This pull request adds the following comparison operations to CuckooSet:

• == (lhs:rhs:)
• isSubset(of:)
• isStrictSubset(of:)
• isSuperset(of:)
• isStrictSuperset(of:)
• isDisjoint(with:)

CuckooSet also unconditionally conforms to FNVHashable.

Tasks

• [x] declare methods
• [x] write unit tests
• [ ] implement methods
• [ ] pass & refine tests
• [ ] write documentation

Objectives

This pull request renames the benchmark tasks to a consistent convention. The history explores the requests in #17 and decided to close #17 without adding new benchmarks.

Note on #17

The benchmark tasks for set algebra operations ended up being highly variable, and no more than a poor reflection of the performance of insert and remove operations. The new tasks were introduced on this branch, but then removed in favor of their component operations.

Naming Convention

Each task is now named collection/method-options. For example:

• set/insert
• dict/lookup
• set/insert-reservingCapacity

Objective

This pull request re-implements the CuckooSet.removeAll() method that was previously removed by accident. This closes #18.

Implementation

This PR takes advantage of the changes in #20 by simply re-allocating the set's storage to a default-sized empty instance.

public func removeAll() {
    buckets = CuckooStorage(capacity: 32)
}

In the event this storage is shared with another set, it should remain unaffected. If this storage is uniquely refenced, ARC will deinitialize it.

Impact on Source Stability

This PR restores a part of the original public API. Compared to the last commit, this is an additive change.

Objectives

• Improve the performance of dictionary insertions and updates by optimizing the storage of the underlying hash table. This closes #19.
• Expose sequences of keys and values exclusively to mirror the Swift Dictionary API.

Implementation

Storage Change

The implementation for the storage change mirrors that of CuckooSet. The buckets internal property is now an instance of the CuckooStorage class where each element is a tuple of a key and its associated value. See #19 for more details.

Keys and Values

The new sequences are initialized from the full dictionary, but only return the key or value respectively for each iteration. This means getting a keys or values sequence is a fairly trivial constant-time operation, and iterating over it has very similar performance to iterating over the entire dictionary.

Benchmarks

The benchmark for the Insert operation outputs the following:

Tasks with difference scores larger than 1.05:
  Score   Sum     Improvements Regressions  Name
  1.192   1.192   1.192(#76)   1.000(#0)    CuckooDictionary<Int, Bool> Insert (*)

The lookup operation had no significant change in performance.

Each insert/update operation is approximately twice as slow as with CuckooSet, which is somewhat unexpected. The bulk of the insertion work should be hashing and assignments, which should take the same amount of time. A new optimization pass on the insert/update algorithm may be required. For now though, this is still an improvement.

Impact on Source Stability

There are two potentially breaking changes in this PR:

• The setter for CuckooDictionary.count is now internal. This change fixes a previous oversight. This is technically a breakage, but the property was never meant to be manually mutated.
• The return type of CuckooDictionary.makeIterator() has changed from IndexingIterator to the new CuckooDictionary.Iterator struct. However the only API exposed by each of those types is the IteratorProtocol API. Only code that features the explicitly declared type is affected.

Issue Description

CuckooDictionary is still stored in an array like the old CuckooSet. Using an array comes with additional bounds checks that slow each insert operation down by about 20%. It also makes accessing keys and values exclusively linear time operations since the entire storage array must be iterated over to separate them.

Suggested Solution

Use CuckooStorage to manage buckets, and use a tuple of keys and values as the Element type.

var buckets: CuckooStorage<(key: Key, value: Value)>

Keys and Values

The keys and values sequences should be custom sequences where the iterator separates the tuple at iteration-time. Each property can now be accessed in constant time without copying anything.

Issue Description

The removeAll() method was removed from the CuckooSet API during the storage change and was never put back. We should add it in a new PR.

Proposed Solution

The new storage system allows us to replace the storage of a set entirely. We can implement this method very easily be replacing it with a smaller empty buffer. This would also change the complexity of the method to O(1) since the post-remove capacity is a fixed value.

Issue Description

We currently have benchmarks for insert and lookup operations on both the set and dictionary. The complexity of SetAlgebra methods is not obvious and needs to be benchmarked before declaring it in documentation. Mutating operations are always expected to be O(1), however improvements to the performance of individual operations can still be made and will require a benchmark to justify.

Proposed Solution

Add benchmark tasks for the following set algebra operations:

• union
• formUnion
• intersection
• formIntersection
• symmetricDifference
• formSymmetricDifference
• subtract
• subtracting
• isSubset
• isStrictSubset
• isSuperset
• isStrictSuperset
• isDisjoint

Add benchmark tasks for the following mutating operations:

• remove
• removeAll
• expand
• bump