stojkomilos opened a new pull request, #572:
URL: https://github.com/apache/datasketches-cpp/pull/572
`quantiles_sorted_view::add()` gets two one-line changes. The view that it
builds does not change.
```diff
void quantiles_sorted_view<T, C, A>::add(Iterator first, Iterator last,
uint64_t weight) {
+ if (first == last) return;
const size_t size_before = entries_.size();
- for (auto it = first; it != last; ++it)
entries_.push_back(Entry(ref_helper(*it), weight));
+ for (auto it = first; it != last; ++it)
entries_.emplace_back(ref_helper(*it), weight);
if (size_before > 0) {
```
## Return early for an empty range
On master, if the range is empty and the view already has entries, `add()`
still allocates a new vector, merges all entries into it, and frees the old
buffer.
`kll_sketch::get_sorted_view()` calls `add()` for every level. A compaction
leaves the compacted level empty when the level held an even number of items,
and the level stays empty until the level below it is compacted. I built a KLL
sketch from uniform random floats and looked at its levels after every update,
for n from 1 to 10M:
- In estimation mode, 85% of the view builds at k = 200 and at k = 1000 have
an empty level after a non-empty one, 1.5 per build on average.
- The copies for these empty levels add up to 22% (k = 200) and 31% (k =
1000) of the entries in the view.
`quantiles_sketch` already skips empty levels, and `req_sketch` had no empty
compactors in the sizes I tried.
## Build the entries in place
`push_back(Entry(...))` builds a temporary pair and then copies it into the
vector:
- GCC 10 writes the item and the weight into the temporary with two stores,
then reads them back with one 16-byte load. The CPU cannot forward two stores
into one wider load, so every item waits.
- clang 22 reloads the end and capacity pointers of the vector from memory
after every item.
With `emplace_back()`, GCC 10 and clang write the two fields straight into
the vector and keep the pointers in registers. GCC 9 already wrote the fields
straight into the vector with `push_back()`, so it gains little.
## Benchmarks
Time of `get_sorted_view()`, this PR against master built by the same
compiler. 30 cases: KLL float with k = 8 to 10000 and n = 0 to 1M, KLL double
and string, `get_quantile()` after `update()`, quantiles k = 1024, and REQ.
Intel Xeon Platinum 8375C (Ice Lake), `-std=c++11 -O3 -DNDEBUG`, median of 4
rounds. Each case was also built with `-falign-functions=64` and
`-falign-functions=32`, so each cell covers 3 code layouts.
| compiler | KLL, n = 1M | KLL, 2 <= n <= 100K | quantiles and REQ, n = 1M |
|---|---|---|---|
| GCC 10.5 | 20% to 54% faster (median 35%) | 15% to 78% faster (median 53%)
| 18% to 32% faster |
| clang 22 | 3% to 35% faster (median 16%) | 3% to 52% faster (median 23%) |
0% to 9% faster |
| GCC 9.4 | 4% slower to 21% faster (median 6% faster) | 9% slower to 12%
faster (median 4% faster) | 0% to 4% slower |
Examples in the default layout:
- KLL k = 1000, n = 1M: from 34.2 us to 16.2 us with GCC 10, and from 21.2
us to 13.9 us with clang.
- KLL k = 200, n = 200 (one level): from 1,327 ns to 315 ns with GCC 10.
- At n = 1, the extra comparison costs at most 1 ns (17 to 21 ns per build).
## Tests
All 17 CTest suites pass with GCC 10.5, in Release and in Debug with ASan
and UBSan. The sorted views of 234 seeded KLL, quantiles and REQ sketches are
the same as on master.
This pull request and its description were written by Isaac.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]