Benchmarking packingcubes¶

Setup¶

We use the code in benchmarks/performance to run our benchmarks. It's similar in functionality to the timeit module (which it was based on), with further customization.

For each search object, we construct a dataset of size \(n\) with random data and pass it to the creation method. Psuedocode:

dataset = InMemory(positions=random_positions)
for name, creation_method in creation_dict.items():
    search_objects[name], bench[name] = benchmark(
        creation_method,
        dataset.copy()
    )

We then generate a number of random spheres (10 for now) that overlap the dataset (they do not need to be entirely contained). These are our "search balls" and we set their radii such that \(\sim m\) particles are contained:

for i in range(10):
    centers[i] = random_point_in_dataset(dataset)
    radii[i], actual_numbers[i] = smallest_radii_containing_points(dataset, center, m)

Finally, for every search method, we average the time taken to search over all search balls:

for name, (so_name, search_method) in search_dict.items():
    search_results, bench[name] = benchmark(
        search_objects[so_name].search_method, 
        (centers, radii)
    )
    if can_verify(search_method):
        verify_search(search_results, actual_numbers)

For some of the search methods (anywhere a strict search is available), we verify that we return the correct number of particles as well.

We benchmark across the following dataset sizes and search ball sizes:

We benchmark the following functions:

Finally, we show results across 3 different machines:

Results¶

Raw Timing¶

Here we show the raw timing results. For all benchmarks, we do an untimed trial run first, to sort out any precompiling/warmup.

Expected Scaling¶

Here we show the timing for the various tasks divided by the expected growth rate, normalized at \(n=10^6\).

Consider, for example, tree creation, which involves (and is dominated by) a sorting of the data. Sorting is classically an \(O(n\log n)\) process, and, if we normalize and divide out \(n\log n\), we would expect a flat line. We can see this behavior in the first panel for the PackedTree. The KDTree does a little worse than \(n \log n\) (the slight upwards trend); Cubes does slightly better⁶.

VS SciPy¶

Here we normalize to the SciPy results from KDTree.

Latest CI Run¶

In the following images, we show the latest CI run only, highlighting the most up-to-date performance: