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]

Reply via email to