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]
