This change replaces the deterministic optimized merge-sort with a highly optimized quick select that performs signficantly faster when publisher count is more than 20. The previous algorithm is very fast running on a normal CPU but doesn't work very well in BPF because all instructions (like load, move, ..) have the same cost as comparisons and are not optimized. Quick select on the other hand, minimized all the operations in the average case due to its minimal reads and writes.
In 32-publisher setup, quick select reduces the CU from 16.5k to 11.5k and in the 64-publisher setup 37k to 17.5k. The numbers are the worst cases running on randomized input.
Worst measured case happens when all elements are equal and is 13k and 24k for 32-publisher and 64-publisher setup respectively.
Unfortunately there is no way to systematically get the the compute usage out of program test. The test_benchmark file has a simple code that helps running benchmarks on various number of publishers.
Quick select algorithm has a quadratic worst case but it is very unlikely to happen and no publisher alone can manipulate the list of prices by themselves.
This change replaces the deterministic optimized merge-sort with a highly optimized quick select that performs signficantly faster when publisher count is more than 20. The previous algorithm is very fast running on a normal CPU but doesn't work very well in BPF because all instructions (like load, move, ..) have the same cost as comparisons and are not optimized. Quick select on the other hand, minimized all the operations in the average case due to its minimal reads and writes.
In 32-publisher setup, quick select reduces the CU from 16.5k to 11.5k and in the 64-publisher setup 37k to 17.5k. The numbers are the worst cases running on randomized input.
Worst measured case happens when all elements are equal and is 13k and 24k for 32-publisher and 64-publisher setup respectively.
Unfortunately there is no way to systematically get the the compute usage out of program test. The
test_benchmarkfile has a simple code that helps running benchmarks on various number of publishers.Quick select algorithm has a quadratic worst case but it is very unlikely to happen and no publisher alone can manipulate the list of prices by themselves.