Note
Go to the end to download the full example code.
digit histogram performance benchmarks#
This example benchmarks the digit histogram primitive (the upfront histogram of every radix digit place of a key buffer, as used by the Onesweep radix sort) for the different digit sizes available in Shamrock, on 3 key distributions:
zeros: every key is 0, so every digit place of every key lands in the same bin (worst case for the atomic contention on the histogram bins)shuffled iota: a random permutation of0 .. N-1, the low digit places are uniform while the high ones are concentrated on the few lowest binsrandom: uniformly distributed keys over the full u32 range, every digit place is uniform
17 import time
18
19 import matplotlib.pyplot as plt
20 import numpy as np
21 from shamrock.utils.plot import make_std_bench_plot
22
23 import shamrock
24
25 # If we use the shamrock executable to run this script instead of the python interpreter,
26 # we should not initialize the system as the shamrock executable needs to handle specific MPI logic
27 if not shamrock.sys.is_initialized():
28 shamrock.change_loglevel(1)
29 shamrock.sys.init("0:0")
Use shamrock documentation style for matplotlib
35 shamrock.matplotlib.set_shamrock_mpl_style()
Digit sizes (in bits) supported by the digit histogram
39 radix_bits_list = [1, 2, 4, 8]
Key distributions to benchmark
43 key_cases = ["zeros", "shuffled iota", "random"]
44
45
46 def make_keys(case, N, seed=111):
47 if case == "zeros":
48 keys = shamrock.backends.DeviceBuffer_u32()
49 keys.resize(N)
50 keys.fill(0)
51 return keys
52 elif case == "shuffled iota":
53 rng = np.random.default_rng(seed)
54 keys = shamrock.backends.DeviceBuffer_u32()
55 keys.resize(N)
56 keys.copy_from_stdvec(rng.permutation(N).astype(np.uint32).tolist())
57 return keys
58 elif case == "random":
59 return shamrock.algs.mock_buffer_u32(seed, N, 0, 2**32 - 1)
60 else:
61 raise ValueError(f"unknown key case {case}")
Check the result against numpy
66 def reference_digit_histogram(keys, radix_bits):
67 keys_np = np.array(keys.copy_to_stdvec(), dtype=np.uint64)
68 nbuckets = 2**radix_bits
69 npasses = 32 // radix_bits
70 return np.concatenate(
71 [
72 np.bincount((keys_np >> (p * radix_bits)) & (nbuckets - 1), minlength=nbuckets)
73 for p in range(npasses)
74 ]
75 )
76
77
78 def compute_digit_histogram(keys, radix_bits):
79 N = keys.get_size()
80 return np.array(shamrock.algs.digit_histogram(keys, radix_bits, N).copy_to_stdvec())
81
82
83 for case in key_cases:
84 keys = make_keys(case, 100003)
85 for radix_bits in radix_bits_list:
86 ok = np.array_equal(
87 compute_digit_histogram(keys, radix_bits), reference_digit_histogram(keys, radix_bits)
88 )
89 print(f"{case:>13s}, radix_bits={radix_bits} : result matches numpy = {ok}")
zeros, radix_bits=1 : result matches numpy = True
zeros, radix_bits=2 : result matches numpy = True
zeros, radix_bits=4 : result matches numpy = True
zeros, radix_bits=8 : result matches numpy = True
shuffled iota, radix_bits=1 : result matches numpy = True
shuffled iota, radix_bits=2 : result matches numpy = True
shuffled iota, radix_bits=4 : result matches numpy = True
shuffled iota, radix_bits=8 : result matches numpy = True
random, radix_bits=1 : result matches numpy = True
random, radix_bits=2 : result matches numpy = True
random, radix_bits=4 : result matches numpy = True
random, radix_bits=8 : result matches numpy = True
Main benchmark function
94 def benchmark_u32(keys, radix_bits, nb_repeat=10, max_cumulated_time=2.0):
95 N = keys.get_size()
96
97 times = []
98 cumulated_time = 0.0
99 for _ in range(nb_repeat):
100 t = shamrock.algs.benchmark_digit_histogram(keys, radix_bits, N)
101 times.append(t)
102 cumulated_time += t
103
104 if cumulated_time > max_cumulated_time:
105 break
106 return min(times), max(times), sum(times) / len(times)
Run the performance test for all parameters (the keys of a given case and size are generated once and reused for every digit size)
112 def run_performance_sweep():
113 # logspace as array, deliberately not restricted to powers of 2
114 particle_counts = np.logspace(2, 7, 20).astype(int).tolist()
115
116 results = {case: {radix_bits: [] for radix_bits in radix_bits_list} for case in key_cases}
117
118 print(f"Particle counts: {particle_counts}")
119
120 total_runs = len(particle_counts)
121
122 for current_run, N in enumerate(particle_counts, start=1):
123 for case in key_cases:
124 keys = make_keys(case, N)
125 for radix_bits in radix_bits_list:
126 print(
127 f"[{current_run:2d}/{total_runs}] Running N={N:8d}, {case:>13s}, "
128 f"radix_bits={radix_bits}...",
129 end=" ",
130 )
131
132 start_time = time.time()
133 min_time, max_time, mean_time = benchmark_u32(keys, radix_bits)
134 results[case][radix_bits].append(min_time)
135 elapsed = time.time() - start_time
136
137 print(f"mean={mean_time:.3e}s (took {elapsed:.1f}s)")
138
139 return particle_counts, results
Run the performance benchmarks for all key distributions and digit sizes
145 particle_counts, results = run_performance_sweep()
Particle counts: [100, 183, 335, 615, 1128, 2069, 3792, 6951, 12742, 23357, 42813, 78475, 143844, 263665, 483293, 885866, 1623776, 2976351, 5455594, 10000000]
[ 1/20] Running N= 100, zeros, radix_bits=1... mean=1.035e-04s (took 0.0s)
[ 1/20] Running N= 100, zeros, radix_bits=2... mean=8.054e-05s (took 0.0s)
[ 1/20] Running N= 100, zeros, radix_bits=4... mean=8.142e-05s (took 0.0s)
[ 1/20] Running N= 100, zeros, radix_bits=8... mean=8.446e-05s (took 0.0s)
[ 1/20] Running N= 100, shuffled iota, radix_bits=1... mean=8.398e-05s (took 0.0s)
[ 1/20] Running N= 100, shuffled iota, radix_bits=2... mean=7.665e-05s (took 0.0s)
[ 1/20] Running N= 100, shuffled iota, radix_bits=4... mean=7.385e-05s (took 0.0s)
[ 1/20] Running N= 100, shuffled iota, radix_bits=8... mean=7.459e-05s (took 0.0s)
[ 1/20] Running N= 100, random, radix_bits=1... mean=1.124e-04s (took 0.0s)
[ 1/20] Running N= 100, random, radix_bits=2... mean=1.036e-04s (took 0.0s)
[ 1/20] Running N= 100, random, radix_bits=4... mean=1.648e-04s (took 0.0s)
[ 1/20] Running N= 100, random, radix_bits=8... mean=1.392e-04s (took 0.0s)
[ 2/20] Running N= 183, zeros, radix_bits=1... mean=1.168e-04s (took 0.0s)
[ 2/20] Running N= 183, zeros, radix_bits=2... mean=1.057e-04s (took 0.0s)
[ 2/20] Running N= 183, zeros, radix_bits=4... mean=1.028e-04s (took 0.0s)
[ 2/20] Running N= 183, zeros, radix_bits=8... mean=1.012e-04s (took 0.0s)
[ 2/20] Running N= 183, shuffled iota, radix_bits=1... mean=9.921e-05s (took 0.0s)
[ 2/20] Running N= 183, shuffled iota, radix_bits=2... mean=7.844e-05s (took 0.0s)
[ 2/20] Running N= 183, shuffled iota, radix_bits=4... mean=6.928e-05s (took 0.0s)
[ 2/20] Running N= 183, shuffled iota, radix_bits=8... mean=6.917e-05s (took 0.0s)
[ 2/20] Running N= 183, random, radix_bits=1... mean=9.872e-05s (took 0.0s)
[ 2/20] Running N= 183, random, radix_bits=2... mean=7.214e-05s (took 0.0s)
[ 2/20] Running N= 183, random, radix_bits=4... mean=6.812e-05s (took 0.0s)
[ 2/20] Running N= 183, random, radix_bits=8... mean=7.009e-05s (took 0.0s)
[ 3/20] Running N= 335, zeros, radix_bits=1... mean=9.180e-05s (took 0.0s)
[ 3/20] Running N= 335, zeros, radix_bits=2... mean=7.743e-05s (took 0.0s)
[ 3/20] Running N= 335, zeros, radix_bits=4... mean=7.313e-05s (took 0.0s)
[ 3/20] Running N= 335, zeros, radix_bits=8... mean=6.938e-05s (took 0.0s)
[ 3/20] Running N= 335, shuffled iota, radix_bits=1... mean=9.615e-05s (took 0.0s)
[ 3/20] Running N= 335, shuffled iota, radix_bits=2... mean=8.004e-05s (took 0.0s)
[ 3/20] Running N= 335, shuffled iota, radix_bits=4... mean=6.844e-05s (took 0.0s)
[ 3/20] Running N= 335, shuffled iota, radix_bits=8... mean=7.039e-05s (took 0.0s)
[ 3/20] Running N= 335, random, radix_bits=1... mean=9.862e-05s (took 0.0s)
[ 3/20] Running N= 335, random, radix_bits=2... mean=8.207e-05s (took 0.0s)
[ 3/20] Running N= 335, random, radix_bits=4... mean=7.697e-05s (took 0.0s)
[ 3/20] Running N= 335, random, radix_bits=8... mean=7.266e-05s (took 0.0s)
[ 4/20] Running N= 615, zeros, radix_bits=1... mean=1.172e-04s (took 0.0s)
[ 4/20] Running N= 615, zeros, radix_bits=2... mean=9.222e-05s (took 0.0s)
[ 4/20] Running N= 615, zeros, radix_bits=4... mean=7.982e-05s (took 0.0s)
[ 4/20] Running N= 615, zeros, radix_bits=8... mean=7.127e-05s (took 0.0s)
[ 4/20] Running N= 615, shuffled iota, radix_bits=1... mean=1.192e-04s (took 0.0s)
[ 4/20] Running N= 615, shuffled iota, radix_bits=2... mean=9.028e-05s (took 0.0s)
[ 4/20] Running N= 615, shuffled iota, radix_bits=4... mean=7.720e-05s (took 0.0s)
[ 4/20] Running N= 615, shuffled iota, radix_bits=8... mean=7.247e-05s (took 0.0s)
[ 4/20] Running N= 615, random, radix_bits=1... mean=1.173e-04s (took 0.0s)
[ 4/20] Running N= 615, random, radix_bits=2... mean=9.419e-05s (took 0.0s)
[ 4/20] Running N= 615, random, radix_bits=4... mean=7.846e-05s (took 0.0s)
[ 4/20] Running N= 615, random, radix_bits=8... mean=7.432e-05s (took 0.0s)
[ 5/20] Running N= 1128, zeros, radix_bits=1... mean=1.875e-04s (took 0.0s)
[ 5/20] Running N= 1128, zeros, radix_bits=2... mean=1.200e-04s (took 0.0s)
[ 5/20] Running N= 1128, zeros, radix_bits=4... mean=9.724e-05s (took 0.0s)
[ 5/20] Running N= 1128, zeros, radix_bits=8... mean=8.528e-05s (took 0.0s)
[ 5/20] Running N= 1128, shuffled iota, radix_bits=1... mean=1.664e-04s (took 0.0s)
[ 5/20] Running N= 1128, shuffled iota, radix_bits=2... mean=1.153e-04s (took 0.0s)
[ 5/20] Running N= 1128, shuffled iota, radix_bits=4... mean=9.374e-05s (took 0.0s)
[ 5/20] Running N= 1128, shuffled iota, radix_bits=8... mean=7.986e-05s (took 0.0s)
[ 5/20] Running N= 1128, random, radix_bits=1... mean=1.582e-04s (took 0.0s)
[ 5/20] Running N= 1128, random, radix_bits=2... mean=1.131e-04s (took 0.0s)
[ 5/20] Running N= 1128, random, radix_bits=4... mean=8.550e-05s (took 0.0s)
[ 5/20] Running N= 1128, random, radix_bits=8... mean=7.662e-05s (took 0.0s)
[ 6/20] Running N= 2069, zeros, radix_bits=1... mean=2.374e-04s (took 0.0s)
[ 6/20] Running N= 2069, zeros, radix_bits=2... mean=1.529e-04s (took 0.0s)
[ 6/20] Running N= 2069, zeros, radix_bits=4... mean=1.073e-04s (took 0.0s)
[ 6/20] Running N= 2069, zeros, radix_bits=8... mean=1.084e-04s (took 0.0s)
[ 6/20] Running N= 2069, shuffled iota, radix_bits=1... mean=2.374e-04s (took 0.0s)
[ 6/20] Running N= 2069, shuffled iota, radix_bits=2... mean=1.537e-04s (took 0.0s)
[ 6/20] Running N= 2069, shuffled iota, radix_bits=4... mean=1.068e-04s (took 0.0s)
[ 6/20] Running N= 2069, shuffled iota, radix_bits=8... mean=8.559e-05s (took 0.0s)
[ 6/20] Running N= 2069, random, radix_bits=1... mean=2.496e-04s (took 0.0s)
[ 6/20] Running N= 2069, random, radix_bits=2... mean=1.564e-04s (took 0.0s)
[ 6/20] Running N= 2069, random, radix_bits=4... mean=1.115e-04s (took 0.0s)
[ 6/20] Running N= 2069, random, radix_bits=8... mean=8.760e-05s (took 0.0s)
[ 7/20] Running N= 3792, zeros, radix_bits=1... mean=2.378e-04s (took 0.0s)
[ 7/20] Running N= 3792, zeros, radix_bits=2... mean=1.566e-04s (took 0.0s)
[ 7/20] Running N= 3792, zeros, radix_bits=4... mean=1.075e-04s (took 0.0s)
[ 7/20] Running N= 3792, zeros, radix_bits=8... mean=1.088e-04s (took 0.0s)
[ 7/20] Running N= 3792, shuffled iota, radix_bits=1... mean=2.436e-04s (took 0.0s)
[ 7/20] Running N= 3792, shuffled iota, radix_bits=2... mean=1.538e-04s (took 0.0s)
[ 7/20] Running N= 3792, shuffled iota, radix_bits=4... mean=1.033e-04s (took 0.0s)
[ 7/20] Running N= 3792, shuffled iota, radix_bits=8... mean=8.761e-05s (took 0.0s)
[ 7/20] Running N= 3792, random, radix_bits=1... mean=2.347e-04s (took 0.0s)
[ 7/20] Running N= 3792, random, radix_bits=2... mean=1.544e-04s (took 0.0s)
[ 7/20] Running N= 3792, random, radix_bits=4... mean=1.081e-04s (took 0.0s)
[ 7/20] Running N= 3792, random, radix_bits=8... mean=8.805e-05s (took 0.0s)
[ 8/20] Running N= 6951, zeros, radix_bits=1... mean=2.501e-04s (took 0.0s)
[ 8/20] Running N= 6951, zeros, radix_bits=2... mean=1.603e-04s (took 0.0s)
[ 8/20] Running N= 6951, zeros, radix_bits=4... mean=1.117e-04s (took 0.0s)
[ 8/20] Running N= 6951, zeros, radix_bits=8... mean=1.104e-04s (took 0.0s)
[ 8/20] Running N= 6951, shuffled iota, radix_bits=1... mean=2.496e-04s (took 0.0s)
[ 8/20] Running N= 6951, shuffled iota, radix_bits=2... mean=1.621e-04s (took 0.0s)
[ 8/20] Running N= 6951, shuffled iota, radix_bits=4... mean=1.090e-04s (took 0.0s)
[ 8/20] Running N= 6951, shuffled iota, radix_bits=8... mean=8.683e-05s (took 0.0s)
[ 8/20] Running N= 6951, random, radix_bits=1... mean=2.524e-04s (took 0.0s)
[ 8/20] Running N= 6951, random, radix_bits=2... mean=1.577e-04s (took 0.0s)
[ 8/20] Running N= 6951, random, radix_bits=4... mean=1.099e-04s (took 0.0s)
[ 8/20] Running N= 6951, random, radix_bits=8... mean=1.020e-04s (took 0.0s)
[ 9/20] Running N= 12742, zeros, radix_bits=1... mean=4.485e-04s (took 0.0s)
[ 9/20] Running N= 12742, zeros, radix_bits=2... mean=2.646e-04s (took 0.0s)
[ 9/20] Running N= 12742, zeros, radix_bits=4... mean=1.680e-04s (took 0.0s)
[ 9/20] Running N= 12742, zeros, radix_bits=8... mean=1.623e-04s (took 0.0s)
[ 9/20] Running N= 12742, shuffled iota, radix_bits=1... mean=4.490e-04s (took 0.0s)
[ 9/20] Running N= 12742, shuffled iota, radix_bits=2... mean=2.653e-04s (took 0.0s)
[ 9/20] Running N= 12742, shuffled iota, radix_bits=4... mean=1.576e-04s (took 0.0s)
[ 9/20] Running N= 12742, shuffled iota, radix_bits=8... mean=1.170e-04s (took 0.0s)
[ 9/20] Running N= 12742, random, radix_bits=1... mean=4.746e-04s (took 0.0s)
[ 9/20] Running N= 12742, random, radix_bits=2... mean=2.616e-04s (took 0.0s)
[ 9/20] Running N= 12742, random, radix_bits=4... mean=1.636e-04s (took 0.0s)
[ 9/20] Running N= 12742, random, radix_bits=8... mean=1.311e-04s (took 0.0s)
[10/20] Running N= 23357, zeros, radix_bits=1... mean=6.424e-04s (took 0.0s)
[10/20] Running N= 23357, zeros, radix_bits=2... mean=3.710e-04s (took 0.0s)
[10/20] Running N= 23357, zeros, radix_bits=4... mean=2.196e-04s (took 0.0s)
[10/20] Running N= 23357, zeros, radix_bits=8... mean=2.166e-04s (took 0.0s)
[10/20] Running N= 23357, shuffled iota, radix_bits=1... mean=6.444e-04s (took 0.0s)
[10/20] Running N= 23357, shuffled iota, radix_bits=2... mean=3.727e-04s (took 0.0s)
[10/20] Running N= 23357, shuffled iota, radix_bits=4... mean=2.128e-04s (took 0.0s)
[10/20] Running N= 23357, shuffled iota, radix_bits=8... mean=1.461e-04s (took 0.0s)
[10/20] Running N= 23357, random, radix_bits=1... mean=6.451e-04s (took 0.0s)
[10/20] Running N= 23357, random, radix_bits=2... mean=3.617e-04s (took 0.0s)
[10/20] Running N= 23357, random, radix_bits=4... mean=2.156e-04s (took 0.0s)
[10/20] Running N= 23357, random, radix_bits=8... mean=1.786e-04s (took 0.0s)
[11/20] Running N= 42813, zeros, radix_bits=1... mean=1.210e-03s (took 0.0s)
[11/20] Running N= 42813, zeros, radix_bits=2... mean=6.637e-04s (took 0.0s)
[11/20] Running N= 42813, zeros, radix_bits=4... mean=3.812e-04s (took 0.0s)
[11/20] Running N= 42813, zeros, radix_bits=8... mean=3.777e-04s (took 0.0s)
[11/20] Running N= 42813, shuffled iota, radix_bits=1... mean=1.211e-03s (took 0.0s)
[11/20] Running N= 42813, shuffled iota, radix_bits=2... mean=6.628e-04s (took 0.0s)
[11/20] Running N= 42813, shuffled iota, radix_bits=4... mean=3.657e-04s (took 0.0s)
[11/20] Running N= 42813, shuffled iota, radix_bits=8... mean=2.374e-04s (took 0.0s)
[11/20] Running N= 42813, random, radix_bits=1... mean=1.223e-03s (took 0.0s)
[11/20] Running N= 42813, random, radix_bits=2... mean=6.658e-04s (took 0.0s)
[11/20] Running N= 42813, random, radix_bits=4... mean=3.682e-04s (took 0.0s)
[11/20] Running N= 42813, random, radix_bits=8... mean=2.513e-04s (took 0.0s)
[12/20] Running N= 78475, zeros, radix_bits=1... mean=2.003e-03s (took 0.0s)
[12/20] Running N= 78475, zeros, radix_bits=2... mean=1.148e-03s (took 0.0s)
[12/20] Running N= 78475, zeros, radix_bits=4... mean=6.107e-04s (took 0.0s)
[12/20] Running N= 78475, zeros, radix_bits=8... mean=5.841e-04s (took 0.0s)
[12/20] Running N= 78475, shuffled iota, radix_bits=1... mean=1.998e-03s (took 0.0s)
[12/20] Running N= 78475, shuffled iota, radix_bits=2... mean=1.069e-03s (took 0.0s)
[12/20] Running N= 78475, shuffled iota, radix_bits=4... mean=5.699e-04s (took 0.0s)
[12/20] Running N= 78475, shuffled iota, radix_bits=8... mean=3.537e-04s (took 0.0s)
[12/20] Running N= 78475, random, radix_bits=1... mean=2.000e-03s (took 0.0s)
[12/20] Running N= 78475, random, radix_bits=2... mean=1.095e-03s (took 0.0s)
[12/20] Running N= 78475, random, radix_bits=4... mean=5.745e-04s (took 0.0s)
[12/20] Running N= 78475, random, radix_bits=8... mean=3.940e-04s (took 0.0s)
[13/20] Running N= 143844, zeros, radix_bits=1... mean=3.543e-03s (took 0.1s)
[13/20] Running N= 143844, zeros, radix_bits=2... mean=1.902e-03s (took 0.0s)
[13/20] Running N= 143844, zeros, radix_bits=4... mean=1.038e-03s (took 0.0s)
[13/20] Running N= 143844, zeros, radix_bits=8... mean=1.010e-03s (took 0.0s)
[13/20] Running N= 143844, shuffled iota, radix_bits=1... mean=3.577e-03s (took 0.1s)
[13/20] Running N= 143844, shuffled iota, radix_bits=2... mean=1.877e-03s (took 0.0s)
[13/20] Running N= 143844, shuffled iota, radix_bits=4... mean=9.789e-04s (took 0.0s)
[13/20] Running N= 143844, shuffled iota, radix_bits=8... mean=5.896e-04s (took 0.0s)
[13/20] Running N= 143844, random, radix_bits=1... mean=3.551e-03s (took 0.1s)
[13/20] Running N= 143844, random, radix_bits=2... mean=1.873e-03s (took 0.0s)
[13/20] Running N= 143844, random, radix_bits=4... mean=9.818e-04s (took 0.0s)
[13/20] Running N= 143844, random, radix_bits=8... mean=6.393e-04s (took 0.0s)
[14/20] Running N= 263665, zeros, radix_bits=1... mean=6.434e-03s (took 0.1s)
[14/20] Running N= 263665, zeros, radix_bits=2... mean=3.407e-03s (took 0.1s)
[14/20] Running N= 263665, zeros, radix_bits=4... mean=1.855e-03s (took 0.0s)
[14/20] Running N= 263665, zeros, radix_bits=8... mean=1.795e-03s (took 0.0s)
[14/20] Running N= 263665, shuffled iota, radix_bits=1... mean=6.469e-03s (took 0.1s)
[14/20] Running N= 263665, shuffled iota, radix_bits=2... mean=3.378e-03s (took 0.1s)
[14/20] Running N= 263665, shuffled iota, radix_bits=4... mean=1.751e-03s (took 0.0s)
[14/20] Running N= 263665, shuffled iota, radix_bits=8... mean=1.008e-03s (took 0.0s)
[14/20] Running N= 263665, random, radix_bits=1... mean=6.428e-03s (took 0.1s)
[14/20] Running N= 263665, random, radix_bits=2... mean=3.386e-03s (took 0.1s)
[14/20] Running N= 263665, random, radix_bits=4... mean=1.745e-03s (took 0.0s)
[14/20] Running N= 263665, random, radix_bits=8... mean=1.094e-03s (took 0.0s)
[15/20] Running N= 483293, zeros, radix_bits=1... mean=1.146e-02s (took 0.2s)
[15/20] Running N= 483293, zeros, radix_bits=2... mean=6.033e-03s (took 0.1s)
[15/20] Running N= 483293, zeros, radix_bits=4... mean=3.254e-03s (took 0.1s)
[15/20] Running N= 483293, zeros, radix_bits=8... mean=3.167e-03s (took 0.1s)
[15/20] Running N= 483293, shuffled iota, radix_bits=1... mean=1.148e-02s (took 0.2s)
[15/20] Running N= 483293, shuffled iota, radix_bits=2... mean=5.997e-03s (took 0.1s)
[15/20] Running N= 483293, shuffled iota, radix_bits=4... mean=3.059e-03s (took 0.1s)
[15/20] Running N= 483293, shuffled iota, radix_bits=8... mean=1.733e-03s (took 0.0s)
[15/20] Running N= 483293, random, radix_bits=1... mean=1.148e-02s (took 0.2s)
[15/20] Running N= 483293, random, radix_bits=2... mean=6.006e-03s (took 0.1s)
[15/20] Running N= 483293, random, radix_bits=4... mean=3.063e-03s (took 0.1s)
[15/20] Running N= 483293, random, radix_bits=8... mean=1.886e-03s (took 0.0s)
[16/20] Running N= 885866, zeros, radix_bits=1... mean=2.118e-02s (took 0.4s)
[16/20] Running N= 885866, zeros, radix_bits=2... mean=1.112e-02s (took 0.2s)
[16/20] Running N= 885866, zeros, radix_bits=4... mean=5.956e-03s (took 0.1s)
[16/20] Running N= 885866, zeros, radix_bits=8... mean=5.774e-03s (took 0.1s)
[16/20] Running N= 885866, shuffled iota, radix_bits=1... mean=2.127e-02s (took 0.4s)
[16/20] Running N= 885866, shuffled iota, radix_bits=2... mean=1.105e-02s (took 0.2s)
[16/20] Running N= 885866, shuffled iota, radix_bits=4... mean=5.590e-03s (took 0.1s)
[16/20] Running N= 885866, shuffled iota, radix_bits=8... mean=3.103e-03s (took 0.1s)
[16/20] Running N= 885866, random, radix_bits=1... mean=2.119e-02s (took 0.4s)
[16/20] Running N= 885866, random, radix_bits=2... mean=1.104e-02s (took 0.2s)
[16/20] Running N= 885866, random, radix_bits=4... mean=5.604e-03s (took 0.1s)
[16/20] Running N= 885866, random, radix_bits=8... mean=3.367e-03s (took 0.1s)
[17/20] Running N= 1623776, zeros, radix_bits=1... mean=3.856e-02s (took 0.8s)
[17/20] Running N= 1623776, zeros, radix_bits=2... mean=2.022e-02s (took 0.4s)
[17/20] Running N= 1623776, zeros, radix_bits=4... mean=1.082e-02s (took 0.2s)
[17/20] Running N= 1623776, zeros, radix_bits=8... mean=1.057e-02s (took 0.2s)
[17/20] Running N= 1623776, shuffled iota, radix_bits=1... mean=3.863e-02s (took 0.8s)
[17/20] Running N= 1623776, shuffled iota, radix_bits=2... mean=2.015e-02s (took 0.4s)
[17/20] Running N= 1623776, shuffled iota, radix_bits=4... mean=1.023e-02s (took 0.2s)
[17/20] Running N= 1623776, shuffled iota, radix_bits=8... mean=5.727e-03s (took 0.1s)
[17/20] Running N= 1623776, random, radix_bits=1... mean=3.858e-02s (took 0.8s)
[17/20] Running N= 1623776, random, radix_bits=2... mean=2.023e-02s (took 0.4s)
[17/20] Running N= 1623776, random, radix_bits=4... mean=1.019e-02s (took 0.2s)
[17/20] Running N= 1623776, random, radix_bits=8... mean=6.051e-03s (took 0.1s)
[18/20] Running N= 2976351, zeros, radix_bits=1... mean=9.600e-02s (took 1.9s)
[18/20] Running N= 2976351, zeros, radix_bits=2... mean=5.054e-02s (took 1.0s)
[18/20] Running N= 2976351, zeros, radix_bits=4... mean=2.692e-02s (took 0.5s)
[18/20] Running N= 2976351, zeros, radix_bits=8... mean=2.689e-02s (took 0.5s)
[18/20] Running N= 2976351, shuffled iota, radix_bits=1... mean=9.697e-02s (took 1.9s)
[18/20] Running N= 2976351, shuffled iota, radix_bits=2... mean=5.108e-02s (took 1.0s)
[18/20] Running N= 2976351, shuffled iota, radix_bits=4... mean=2.579e-02s (took 0.5s)
[18/20] Running N= 2976351, shuffled iota, radix_bits=8... mean=1.483e-02s (took 0.3s)
[18/20] Running N= 2976351, random, radix_bits=1... mean=9.596e-02s (took 1.9s)
[18/20] Running N= 2976351, random, radix_bits=2... mean=5.084e-02s (took 1.0s)
[18/20] Running N= 2976351, random, radix_bits=4... mean=2.572e-02s (took 0.5s)
[18/20] Running N= 2976351, random, radix_bits=8... mean=1.547e-02s (took 0.3s)
[19/20] Running N= 5455594, zeros, radix_bits=1... mean=1.485e-01s (took 3.0s)
[19/20] Running N= 5455594, zeros, radix_bits=2... mean=7.924e-02s (took 1.6s)
[19/20] Running N= 5455594, zeros, radix_bits=4... mean=4.284e-02s (took 0.9s)
[19/20] Running N= 5455594, zeros, radix_bits=8... mean=4.057e-02s (took 0.8s)
[19/20] Running N= 5455594, shuffled iota, radix_bits=1... mean=1.514e-01s (took 3.0s)
[19/20] Running N= 5455594, shuffled iota, radix_bits=2... mean=8.107e-02s (took 1.6s)
[19/20] Running N= 5455594, shuffled iota, radix_bits=4... mean=4.303e-02s (took 0.9s)
[19/20] Running N= 5455594, shuffled iota, radix_bits=8... mean=2.180e-02s (took 0.4s)
[19/20] Running N= 5455594, random, radix_bits=1... mean=1.514e-01s (took 3.0s)
[19/20] Running N= 5455594, random, radix_bits=2... mean=8.112e-02s (took 1.6s)
[19/20] Running N= 5455594, random, radix_bits=4... mean=4.297e-02s (took 0.9s)
[19/20] Running N= 5455594, random, radix_bits=8... mean=2.259e-02s (took 0.5s)
[20/20] Running N=10000000, zeros, radix_bits=1... mean=2.583e-01s (took 4.1s)
[20/20] Running N=10000000, zeros, radix_bits=2... mean=1.399e-01s (took 2.8s)
[20/20] Running N=10000000, zeros, radix_bits=4... mean=7.764e-02s (took 1.6s)
[20/20] Running N=10000000, zeros, radix_bits=8... mean=7.201e-02s (took 1.4s)
[20/20] Running N=10000000, shuffled iota, radix_bits=1... mean=2.589e-01s (took 4.2s)
[20/20] Running N=10000000, shuffled iota, radix_bits=2... mean=1.389e-01s (took 2.8s)
[20/20] Running N=10000000, shuffled iota, radix_bits=4... mean=7.481e-02s (took 1.5s)
[20/20] Running N=10000000, shuffled iota, radix_bits=8... mean=4.133e-02s (took 0.8s)
[20/20] Running N=10000000, random, radix_bits=1... mean=2.570e-01s (took 4.1s)
[20/20] Running N=10000000, random, radix_bits=2... mean=1.414e-01s (took 2.8s)
[20/20] Running N=10000000, random, radix_bits=4... mean=7.811e-02s (took 1.6s)
[20/20] Running N=10000000, random, radix_bits=8... mean=4.287e-02s (took 0.9s)
Plot the digit histogram performance benchmarks, one figure per key distribution
151 color_cycle = plt.rcParams["axes.prop_cycle"].by_key()["color"]
152
153
154 def before_plot(ax_plot):
155 Nobj = np.array(particle_counts)
156 Time1G = Nobj / 1e9
157 ax_plot.plot(
158 particle_counts, Time1G, color="grey", linestyle="-", alpha=0.7, label="1G obj/sec"
159 )
160
161
162 for case in key_cases:
163 plot_data = {}
164 for i, radix_bits in enumerate(radix_bits_list):
165 plot_data[f"radix_bits={radix_bits}"] = {
166 "x": particle_counts,
167 "y": results[case][radix_bits],
168 "color": color_cycle[i % len(color_cycle)],
169 "label": f"radix_bits={radix_bits} (u32)",
170 "linestyle": "--",
171 "marker": ".",
172 }
173
174 make_std_bench_plot(
175 plot_data,
176 xlabel="Number of elements",
177 ylabel="Time (s)",
178 title=f"digit histogram performance benchmarks ({case} keys)",
179 end_label_fmt=lambda y: f"{y:.2e} s",
180 before_plot_func=before_plot,
181 )
182 plt.show()
Plot the digit histogram performance benchmarks (bandwidth), one figure per key distribution. The keys are read only once whatever the number of digit places, the histogram itself being negligible in size.
189 for case in key_cases:
190 plot_data = {}
191 for i, radix_bits in enumerate(radix_bits_list):
192 Nobj = np.array(particle_counts)
193 Bytes = 4 * Nobj # 1 u32 key read per element (sizeof = 4)
194 BW = Bytes / np.array(results[case][radix_bits])
195 plot_data[f"radix_bits={radix_bits}"] = {
196 "x": particle_counts,
197 "y": BW,
198 "color": color_cycle[i % len(color_cycle)],
199 "label": f"radix_bits={radix_bits} (u32)",
200 "linestyle": "--",
201 "marker": ".",
202 }
203
204 make_std_bench_plot(
205 plot_data,
206 xlabel="Number of elements",
207 ylabel="Bandwidth (B.s^-1)",
208 title=f"digit histogram performance benchmarks ({case} keys)",
209 end_label_fmt=lambda y: f"{y / 1e9:.2f} GB.s^-1",
210 )
211 plt.show()
Plot the histograms of the 4 digit places of 8 bits for each key distribution
216 N_plot = 1000000
217
218 fig, axs = plt.subplots(1, len(key_cases), figsize=(15, 4), layout="constrained")
219 for ax, case in zip(axs, key_cases):
220 hist = compute_digit_histogram(make_keys(case, N_plot), 8)
221 for p in range(4):
222 ax.plot(hist[p * 256 : (p + 1) * 256], label=f"digit place {p} (bits {8 * p}-{8 * p + 7})")
223 ax.set_xlabel("digit value")
224 ax.set_ylabel("count")
225 ax.set_yscale("symlog")
226 ax.set_title(f"{case} keys")
227 axs[0].legend()
228 fig.suptitle(f"digit histogram (radix_bits=8, {N_plot} u32 keys)")
229 plt.show()
Total running time of the script: (1 minutes 16.335 seconds)
Estimated memory usage: 594 MB