stojkomilos opened a new pull request, #569:
URL: https://github.com/apache/datasketches-cpp/pull/569

   This PR builds on #558 and is meant to be merged after #558 is merged. Its 
first three commits are #558, and this PR adds the last two.
   
   ## What this adds on top of #558
   
   #558 allocates the items buffer on the first update or merge, but then 
allocates all k items at once, so a sketch with one item still holds 512 KiB at 
k = 65535 with doubles. This PR makes that first allocation room for min(k, 
200) items, and grows a full buffer by 8x up to k: 200, 1600, 12800, then k.
   
   - Compaction still starts only when the buffer holds k items, so the 
compaction points and random bits do not change.
   - While there is one level, the serializers write the levels as offsets into 
a buffer of k items, so the serialized bytes do not change. A deserialized 
sketch still gets the full buffer.
   - After the first compaction nothing changes.
   - No new API: the growth factor is a constant, `kll_constants::RESIZE_FACTOR 
= resize_factor::X8`, the same as the theta default. A `reserve()` as in the 
[dev@ 
proposal](https://lists.apache.org/thread/rv730qo61qqkd99dcy4wnglf3hz1s0fz) 
would allocate k items, and then the buffer never grows.
   
   Bytes held by a `kll_sketch<double>` with k = 65535 (items buffer and 
levels):
   
   | Items | master | #558 | #558 + this PR |
   |---|---|---|---|
   | 0 | 524,288 | 8 | 8 |
   | 1 to 200 | 524,288 | 524,288 | 1,608 |
   | 201 to 1600 | 524,288 | 524,288 | 12,808 |
   | 1601 to 12800 | 524,288 | 524,288 | 102,408 |
   | more | 524,288 | 524,288 | 524,288 |
   
   At the default k = 200 nothing changes, because the first allocation is 
already k items.
   
   The only output that changes is `to_string()`: its "Capacity items" line 
shows the current buffer size of a sketch that is still growing. I can print k 
there instead if you prefer.
   
   ## Tests
   
   New test case `kll sketch: lazy growth of the items buffer`:
   
   - The `test_allocator` bytes follow 200, 1600, 12800, 65535 items, and the 
first merge into an empty sketch allocates 200 items.
   - A growing sketch runs next to a copy with a full buffer (a deserialized 
sketch), with the same `random_utils::random_bit` state, through compactions (k 
= 201, 5000, 20000, up to 10k items), merges in both orders, copies, moves, the 
type-converting constructor and strings. Items, weights, min and max, quantiles 
and ranks at 101 ranks, PMF, CDF and both serializations are identical. 
`override_seed()` seeds only `rand`, and KLL draws from `random_bit`, so the 
test copies that state.
   
   Forcing the serialized level offset to 0 makes this test case fail.
   
   All 17 CTest suites pass with GCC 10.5 and C++11, and `kll_test` also passes 
with ASan and UBSan. A separate harness (not in this PR) wrote 
bitwise-identical serializations with master, #558 and this PR. It covers 
double, float, int64 and string items, 15 values of k, n around every buffer 
size, 4 input orders, 2 seeds, merges by copy and by move, and the 
type-converting constructor.
   
   ## Benchmarks
   
   `benchmarks/benchmark_kll_sketch.cpp` (new) on `kll_sketch<double>`, with 
items from a fixed-seed 64-bit LCG (integers spread uniformly over [0, 2^53)). 
I built the same benchmark against master, #558 and this PR, with GCC 10.5 in 
Release, on an x86_64 VM. The three binaries ran in 5 rounds in random order, 
on one pinned core, with the median of 5 repetitions per round. The times are 
the median over rounds, and the range is the ratio per round.
   
   | Case | k | #558 | this PR | this PR / #558 (range) |
   |---|---|---|---|---|
   | 1000 live sketches, 1 item each | 5000, 20000, 65535 | 1198, 1479, 1618 us 
| 111, 105, 106 us | 0.07 to 0.09 (0.06 to 0.10) |
   | 1000 live sketches, 100 items each | 5000, 20000, 65535 | 1595, 1887, 2907 
us | 339, 342, 337 us | 0.12 to 0.21 (0.11 to 0.22) |
   | 1000 live sketches, 1000 items each | 5000, 20000, 65535 | 5477, 5875, 
6170 us | 2534, 2444, 2453 us | 0.40 to 0.46 (0.37 to 0.47) |
   | 1000 live sketches, 1 to 1000 items | 200, 1000 | | | 0.95 to 1.06 |
   | One sketch filled to k, no compaction | 5000, 20000, 65535 | 10.5, 42.2, 
134.1 us | 11.1, 47.5, 142.0 us | 1.06, 1.12, 1.06 (0.99 to 1.32) |
   | One sketch, 1 or 10 items | 5000, 20000, 65535 | 36 to 56 ns | 48 to 68 ns 
| 1.21 to 1.37 |
   | One sketch, 10^5 or 10^6 items | 1000 to 65535 | | | 1.00 to 1.02 |
   | Merge 100 sketches into a new one | 200, 5000, 65535 | | | 0.97 to 1.03 |
   | Serialize | 200, 5000, 65535 | | | 0.75 to 1.03 |
   
   Filling one sketch up to k copies its items once per growth step (200, 1600 
and 12800 items for k = 65535), which costs 6% to 12% until the first 
compaction. A sketch with 1 or 10 items takes 12 to 14 ns longer at k >= 5000. 
Its time then matches a sketch at the default k = 200 (49 ns on master), which 
makes the same 1.6 KB first allocation.
   
   ## Java
   
   `KllHeapDoublesSketch` also allocates its k items up front. I can make the 
same change there once the dev@ convention is in.
   


-- 
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