You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by al...@apache.org on 2024/05/08 23:14:24 UTC
(datasketches-cpp) branch get_serialized_size created (now b4ee4b4)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch get_serialized_size
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
at b4ee4b4 fixed warning
This branch includes the following new commits:
new 90a7bba implemented get_serialized_size_bytes()
new b4ee4b4 fixed warning
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
(datasketches-cpp) 02/02: fixed warning
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch get_serialized_size
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit b4ee4b49593712dfb42213da067b03a2f9092872
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Wed May 8 16:14:14 2024 -0700
fixed warning
---
theta/include/theta_helpers.hpp | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/theta/include/theta_helpers.hpp b/theta/include/theta_helpers.hpp
index cbdebb4..8d83d34 100644
--- a/theta/include/theta_helpers.hpp
+++ b/theta/include/theta_helpers.hpp
@@ -57,7 +57,7 @@ public:
// consistent way of initializing theta from p
// avoids multiplication if p == 1 since it might not yield MAX_THETA exactly
static uint64_t starting_theta_from_p(float p) {
- if (p < 1) return static_cast<uint64_t>(theta_constants::MAX_THETA * p);
+ if (p < 1) return static_cast<uint64_t>(static_cast<double>(theta_constants::MAX_THETA) * p);
return theta_constants::MAX_THETA;
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
(datasketches-cpp) 01/02: implemented get_serialized_size_bytes()
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch get_serialized_size
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit 90a7bba5525892800f6c61e617b7c7d22dde9e06
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Wed May 8 16:13:47 2024 -0700
implemented get_serialized_size_bytes()
---
theta/include/theta_sketch.hpp | 13 +++++++-
theta/include/theta_sketch_impl.hpp | 60 ++++++++++++++++++++++++-------------
2 files changed, 51 insertions(+), 22 deletions(-)
diff --git a/theta/include/theta_sketch.hpp b/theta/include/theta_sketch.hpp
index 5fc15f6..081d971 100644
--- a/theta/include/theta_sketch.hpp
+++ b/theta/include/theta_sketch.hpp
@@ -417,6 +417,14 @@ public:
virtual uint32_t get_num_retained() const;
virtual uint16_t get_seed_hash() const;
+ /**
+ * Computes size in bytes required to serialize the current state of the sketch.
+ * Computing compressed size is expensive. It takes iterating over all retained hashes,
+ * and the actual serialization will have to look at them again.
+ * @param compressed if true compressed size is returned (if applicable)
+ */
+ size_t get_serialized_size_bytes(bool compressed = false) const;
+
/**
* This method serializes the sketch into a given stream in a binary form
* @param os output stream
@@ -486,8 +494,11 @@ private:
uint64_t theta_;
std::vector<uint64_t, Allocator> entries_;
+ uint8_t get_preamble_longs(bool compressed) const;
bool is_suitable_for_compression() const;
- uint8_t compute_min_leading_zeros() const;
+ uint8_t compute_entry_bits() const;
+ uint8_t get_num_entries_bytes() const;
+ size_t get_compressed_serialized_size_bytes(uint8_t entry_bits, uint8_t num_entries_bytes) const;
void serialize_version_4(std::ostream& os) const;
vector_bytes serialize_version_4(unsigned header_size_bytes = 0) const;
diff --git a/theta/include/theta_sketch_impl.hpp b/theta/include/theta_sketch_impl.hpp
index e5e5050..2b4318c 100644
--- a/theta/include/theta_sketch_impl.hpp
+++ b/theta/include/theta_sketch_impl.hpp
@@ -24,11 +24,11 @@
#include <vector>
#include <stdexcept>
-#include "serde.hpp"
#include "binomial_bounds.hpp"
#include "theta_helpers.hpp"
#include "count_zeros.hpp"
#include "bit_packing.hpp"
+#include "memory_operations.hpp"
namespace datasketches {
@@ -341,6 +341,34 @@ auto compact_theta_sketch_alloc<A>::end() const -> const_iterator {
template<typename A>
void compact_theta_sketch_alloc<A>::print_specifics(std::ostringstream&) const {}
+template<typename A>
+uint8_t compact_theta_sketch_alloc<A>::get_preamble_longs(bool compressed) const {
+ if (compressed) {
+ return this->is_estimation_mode() ? 2 : 1;
+ }
+ return this->is_estimation_mode() ? 3 : this->is_empty() || entries_.size() == 1 ? 1 : 2;
+}
+
+template<typename A>
+size_t compact_theta_sketch_alloc<A>::get_serialized_size_bytes(bool compressed) const {
+ if (compressed && is_suitable_for_compression()) {
+ return get_compressed_serialized_size_bytes(compute_entry_bits(), get_num_entries_bytes());
+ }
+ return sizeof(uint64_t) * get_preamble_longs(false) + sizeof(uint64_t) * entries_.size();
+}
+
+// store num_entries as whole bytes since whole-byte blocks will follow (most probably)
+template<typename A>
+uint8_t compact_theta_sketch_alloc<A>::get_num_entries_bytes() const {
+ return whole_bytes_to_hold_bits<uint8_t>(32 - count_leading_zeros_in_u32(static_cast<uint32_t>(entries_.size())));
+}
+
+template<typename A>
+size_t compact_theta_sketch_alloc<A>::get_compressed_serialized_size_bytes(uint8_t entry_bits, uint8_t num_entries_bytes) const {
+ const size_t compressed_bits = entry_bits * entries_.size();
+ return sizeof(uint64_t) * get_preamble_longs(true) + num_entries_bytes + whole_bytes_to_hold_bits(compressed_bits);
+}
+
template<typename A>
void compact_theta_sketch_alloc<A>::serialize(std::ostream& os) const {
const uint8_t preamble_longs = this->is_estimation_mode() ? 3 : this->is_empty() || entries_.size() == 1 ? 1 : 2;
@@ -366,12 +394,10 @@ void compact_theta_sketch_alloc<A>::serialize(std::ostream& os) const {
template<typename A>
auto compact_theta_sketch_alloc<A>::serialize(unsigned header_size_bytes) const -> vector_bytes {
- const uint8_t preamble_longs = this->is_estimation_mode() ? 3 : this->is_empty() || entries_.size() == 1 ? 1 : 2;
- const size_t size = header_size_bytes + sizeof(uint64_t) * preamble_longs
- + sizeof(uint64_t) * entries_.size();
+ const size_t size = get_serialized_size_bytes() + header_size_bytes;
vector_bytes bytes(size, 0, entries_.get_allocator());
uint8_t* ptr = bytes.data() + header_size_bytes;
-
+ const uint8_t preamble_longs = get_preamble_longs(false);
*ptr++ = preamble_longs;
*ptr++ = UNCOMPRESSED_SERIAL_VERSION;
*ptr++ = SKETCH_TYPE;
@@ -413,7 +439,7 @@ auto compact_theta_sketch_alloc<A>::serialize_compressed(unsigned header_size_by
}
template<typename A>
-uint8_t compact_theta_sketch_alloc<A>::compute_min_leading_zeros() const {
+uint8_t compact_theta_sketch_alloc<A>::compute_entry_bits() const {
// compression is based on leading zeros in deltas between ordered hash values
// assumes ordered sketch
uint64_t previous = 0;
@@ -423,16 +449,14 @@ uint8_t compact_theta_sketch_alloc<A>::compute_min_leading_zeros() const {
ored |= delta;
previous = entry;
}
- return count_leading_zeros_in_u64(ored);
+ return 64 - count_leading_zeros_in_u64(ored);
}
template<typename A>
void compact_theta_sketch_alloc<A>::serialize_version_4(std::ostream& os) const {
const uint8_t preamble_longs = this->is_estimation_mode() ? 2 : 1;
- const uint8_t entry_bits = 64 - compute_min_leading_zeros();
-
- // store num_entries as whole bytes since whole-byte blocks will follow (most probably)
- const uint8_t num_entries_bytes = whole_bytes_to_hold_bits<uint8_t>(32 - count_leading_zeros_in_u32(static_cast<uint32_t>(entries_.size())));
+ const uint8_t entry_bits = compute_entry_bits();
+ const uint8_t num_entries_bytes = get_num_entries_bytes();
write(os, preamble_longs);
write(os, COMPRESSED_SERIAL_VERSION);
@@ -483,19 +507,13 @@ void compact_theta_sketch_alloc<A>::serialize_version_4(std::ostream& os) const
template<typename A>
auto compact_theta_sketch_alloc<A>::serialize_version_4(unsigned header_size_bytes) const -> vector_bytes {
- const uint8_t preamble_longs = this->is_estimation_mode() ? 2 : 1;
- const uint8_t entry_bits = 64 - compute_min_leading_zeros();
- const size_t compressed_bits = entry_bits * entries_.size();
-
- // store num_entries as whole bytes since whole-byte blocks will follow (most probably)
- const uint8_t num_entries_bytes = whole_bytes_to_hold_bits<uint8_t>(32 - count_leading_zeros_in_u32(static_cast<uint32_t>(entries_.size())));
-
- const size_t size = header_size_bytes + sizeof(uint64_t) * preamble_longs + num_entries_bytes
- + whole_bytes_to_hold_bits(compressed_bits);
+ const uint8_t entry_bits = compute_entry_bits();
+ const uint8_t num_entries_bytes = get_num_entries_bytes();
+ const size_t size = get_compressed_serialized_size_bytes(entry_bits, num_entries_bytes) + header_size_bytes;
vector_bytes bytes(size, 0, entries_.get_allocator());
uint8_t* ptr = bytes.data() + header_size_bytes;
- *ptr++ = preamble_longs;
+ *ptr++ = get_preamble_longs(true);
*ptr++ = COMPRESSED_SERIAL_VERSION;
*ptr++ = SKETCH_TYPE;
*ptr++ = entry_bits;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org