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 2019/11/01 02:06:48 UTC
[incubator-datasketches-cpp] branch cpc_template updated (4352eb0
-> 159b375)
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a change to branch cpc_template
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git.
from 4352eb0 header-only version
new eddcdd8 removed unnecessary code
new c3432dd use std::vector and std::sort
new 159b375 statinc inline row_col_from_two_hashes for performance
The 3 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.
Summary of changes:
cpc/include/counter_of_zeros.hpp | 5 +-
cpc/include/cpc_compressor_impl.hpp | 8 +--
cpc/include/cpc_sketch.hpp | 1 -
cpc/include/cpc_sketch_impl.hpp | 34 +++++------
cpc/include/u32_table.hpp | 16 ++---
cpc/include/u32_table_impl.hpp | 115 +++---------------------------------
cpc/test/compression_test.cpp | 3 +-
7 files changed, 35 insertions(+), 147 deletions(-)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 03/03: statinc inline
row_col_from_two_hashes for performance
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch cpc_template
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit 159b375cad5bd5784cc4c61feeac76888e39265a
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Thu Oct 31 19:06:11 2019 -0700
statinc inline row_col_from_two_hashes for performance
---
cpc/include/cpc_sketch.hpp | 1 -
cpc/include/cpc_sketch_impl.hpp | 34 ++++++++++++++++------------------
2 files changed, 16 insertions(+), 19 deletions(-)
diff --git a/cpc/include/cpc_sketch.hpp b/cpc/include/cpc_sketch.hpp
index 29e9785..8502df1 100644
--- a/cpc/include/cpc_sketch.hpp
+++ b/cpc/include/cpc_sketch.hpp
@@ -159,7 +159,6 @@ class cpc_sketch_alloc {
// since this is for internal use, deallocation of the matrix is on the caller
uint64_t* build_bit_matrix() const;
- static uint32_t row_col_from_two_hashes(uint64_t hash1, uint64_t hash2, uint8_t lg_k);
static uint8_t get_preamble_ints(uint32_t num_coupons, bool has_hip, bool has_table, bool has_window);
inline void write_hip(std::ostream& os) const;
inline size_t copy_hip_to_mem(void* dst) const;
diff --git a/cpc/include/cpc_sketch_impl.hpp b/cpc/include/cpc_sketch_impl.hpp
index 9285229..8ac11dc 100644
--- a/cpc/include/cpc_sketch_impl.hpp
+++ b/cpc/include/cpc_sketch_impl.hpp
@@ -160,6 +160,19 @@ void cpc_sketch_alloc<A>::update(float value) {
update(static_cast<double>(value));
}
+static inline uint32_t row_col_from_two_hashes(uint64_t hash0, uint64_t hash1, uint8_t lg_k) {
+ if (lg_k > 26) throw std::logic_error("lg_k > 26");
+ const uint64_t k = 1 << lg_k;
+ uint8_t col = count_leading_zeros_in_u64(hash1); // 0 <= col <= 64
+ if (col > 63) col = 63; // clip so that 0 <= col <= 63
+ const uint32_t row = hash0 & (k - 1);
+ uint32_t row_col = (row << 6) | col;
+ // To avoid the hash table's "empty" value, we change the row of the following pair.
+ // This case is extremely unlikely, but we might as well handle it.
+ if (row_col == UINT32_MAX) row_col ^= 1 << 6;
+ return row_col;
+}
+
template<typename A>
void cpc_sketch_alloc<A>::update(const void* value, int size) {
HashState hashes;
@@ -171,8 +184,8 @@ template<typename A>
void cpc_sketch_alloc<A>::row_col_update(uint32_t row_col) {
const uint8_t col = row_col & 63;
if (col < first_interesting_column) return; // important speed optimization
- const uint64_t k = 1 << lg_k;
- if ((num_coupons << 5) < 3 * k) {
+ // window size is 0 until sketch is promoted from sparse to windowed
+ if (sliding_window.size() == 0) {
update_sparse(row_col);
} else {
update_windowed(row_col);
@@ -181,7 +194,6 @@ void cpc_sketch_alloc<A>::row_col_update(uint32_t row_col) {
template<typename A>
void cpc_sketch_alloc<A>::update_sparse(uint32_t row_col) {
- if (sliding_window.size() > 0) throw std::logic_error("window is not expected in sparse mode");
const uint64_t k = 1 << lg_k;
const uint64_t c32pre = num_coupons << 5;
if (c32pre >= 3 * k) throw std::logic_error("c32pre >= 3 * k"); // C < 3K/32, in other words flavor == SPARSE
@@ -357,26 +369,12 @@ void cpc_sketch_alloc<A>::refresh_kxp(const uint64_t* bit_matrix) {
}
template<typename A>
-uint32_t cpc_sketch_alloc<A>::row_col_from_two_hashes(uint64_t hash0, uint64_t hash1, uint8_t lg_k) {
- if (lg_k > 26) throw std::logic_error("lg_k > 26");
- const uint64_t k = 1 << lg_k;
- uint8_t col = count_leading_zeros_in_u64(hash1); // 0 <= col <= 64
- if (col > 63) col = 63; // clip so that 0 <= col <= 63
- const uint32_t row = hash0 & (k - 1);
- uint32_t row_col = (row << 6) | col;
- // To avoid the hash table's "empty" value, we change the row of the following pair.
- // This case is extremely unlikely, but we might as well handle it.
- if (row_col == UINT32_MAX) row_col ^= 1 << 6;
- return row_col;
-}
-
-template<typename A>
void cpc_sketch_alloc<A>::to_stream(std::ostream& os) const {
os << "### CPC sketch summary:" << std::endl;
os << " lg_k : " << std::to_string(lg_k) << std::endl;
os << " seed hash : " << std::hex << compute_seed_hash(seed) << std::dec << std::endl;
os << " C : " << num_coupons << std::endl;
- os << " flavor : " << determine_flavor(lg_k, num_coupons) << std::endl;
+ os << " flavor : " << determine_flavor() << std::endl;
os << " merged : " << (was_merged ? "true" : "false") << std::endl;
if (!was_merged) {
os << " HIP estimate : " << hip_est_accum << std::endl;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 01/03: removed unnecessary code
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch cpc_template
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit eddcdd80f33d6dd09acc5756fc898bfb2c292f8c
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Thu Oct 31 19:01:00 2019 -0700
removed unnecessary code
---
cpc/include/counter_of_zeros.hpp | 5 ++---
1 file changed, 2 insertions(+), 3 deletions(-)
diff --git a/cpc/include/counter_of_zeros.hpp b/cpc/include/counter_of_zeros.hpp
index b89a6b7..c0a65ba 100644
--- a/cpc/include/counter_of_zeros.hpp
+++ b/cpc/include/counter_of_zeros.hpp
@@ -74,7 +74,7 @@ static const uint64_t FCLZ_MASK_08 = 0x00000000000000ff;
static inline uint8_t count_leading_zeros_in_u64(uint64_t input) {
if (input > FCLZ_MASK_56)
- return 0 + byte_leading_zeros_table[(input >> 56) & FCLZ_MASK_08];
+ return byte_leading_zeros_table[(input >> 56) & FCLZ_MASK_08];
if (input > FCLZ_MASK_48)
return 8 + byte_leading_zeros_table[(input >> 48) & FCLZ_MASK_08];
if (input > FCLZ_MASK_40)
@@ -87,8 +87,7 @@ static inline uint8_t count_leading_zeros_in_u64(uint64_t input) {
return 40 + byte_leading_zeros_table[(input >> 16) & FCLZ_MASK_08];
if (input > FCLZ_MASK_08)
return 48 + byte_leading_zeros_table[(input >> 8) & FCLZ_MASK_08];
- if (1)
- return 56 + byte_leading_zeros_table[(input >> 0) & FCLZ_MASK_08];
+ return 56 + byte_leading_zeros_table[(input ) & FCLZ_MASK_08];
}
static inline uint8_t count_trailing_zeros_in_u64(uint64_t input) {
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-cpp] 02/03: use std::vector and std::sort
Posted by al...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch cpc_template
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
commit c3432ddd28e28c08da635e1c0cbe88dcc9f6e8da
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Thu Oct 31 19:05:21 2019 -0700
use std::vector and std::sort
---
cpc/include/cpc_compressor_impl.hpp | 8 +--
cpc/include/u32_table.hpp | 16 ++---
cpc/include/u32_table_impl.hpp | 115 +++---------------------------------
cpc/test/compression_test.cpp | 3 +-
4 files changed, 17 insertions(+), 125 deletions(-)
diff --git a/cpc/include/cpc_compressor_impl.hpp b/cpc/include/cpc_compressor_impl.hpp
index 996b894..cff9692 100644
--- a/cpc/include/cpc_compressor_impl.hpp
+++ b/cpc/include/cpc_compressor_impl.hpp
@@ -188,7 +188,7 @@ void cpc_compressor<A>::compress_sparse_flavor(const cpc_sketch_alloc<A>& source
if (source.sliding_window.size() > 0) throw std::logic_error("unexpected sliding window");
uint32_t* pairs = source.surprising_value_table.unwrapping_get_items();
const size_t num_pairs = source.surprising_value_table.get_num_items();
- u32_table<A>::introspective_insertion_sort(pairs, 0, num_pairs - 1);
+ std::sort(pairs, &pairs[num_pairs]);
compress_surprising_values(pairs, num_pairs, source.get_lg_k(), result);
AllocU32().deallocate(pairs, num_pairs);
}
@@ -211,7 +211,7 @@ void cpc_compressor<A>::compress_hybrid_flavor(const cpc_sketch_alloc<A>& source
const size_t k = 1 << source.get_lg_k();
uint32_t* pairs_from_table = source.surprising_value_table.unwrapping_get_items();
const size_t num_pairs_from_table = source.surprising_value_table.get_num_items();
- if (num_pairs_from_table > 0) u32_table<A>::introspective_insertion_sort(pairs_from_table, 0, num_pairs_from_table - 1);
+ if (num_pairs_from_table > 0) std::sort(pairs_from_table, &pairs_from_table[num_pairs_from_table]);
const size_t num_pairs_from_window = source.get_num_coupons() - num_pairs_from_table; // because the window offset is zero
uint32_t* all_pairs = tricky_get_pairs_from_window(source.sliding_window.data(), k, num_pairs_from_window, num_pairs_from_table);
@@ -271,7 +271,7 @@ void cpc_compressor<A>::compress_pinned_flavor(const cpc_sketch_alloc<A>& source
pairs[i] -= 8;
}
- u32_table<A>::introspective_insertion_sort(pairs, 0, num_pairs - 1);
+ std::sort(pairs, &pairs[num_pairs]);
compress_surprising_values(pairs, num_pairs, source.get_lg_k(), result);
AllocU32().deallocate(pairs, num_pairs);
}
@@ -323,7 +323,7 @@ void cpc_compressor<A>::compress_sliding_flavor(const cpc_sketch_alloc<A>& sourc
pairs[i] = (row << 6) | col;
}
- u32_table<A>::introspective_insertion_sort(pairs, 0, num_pairs - 1);
+ std::sort(pairs, &pairs[num_pairs]);
compress_surprising_values(pairs, num_pairs, source.get_lg_k(), result);
AllocU32().deallocate(pairs, num_pairs);
}
diff --git a/cpc/include/u32_table.hpp b/cpc/include/u32_table.hpp
index 1034d4e..a7f1093 100644
--- a/cpc/include/u32_table.hpp
+++ b/cpc/include/u32_table.hpp
@@ -39,12 +39,6 @@ public:
u32_table();
u32_table(uint8_t lg_size, uint8_t num_valid_bits);
- u32_table(const u32_table& other);
- u32_table(u32_table&& other) noexcept;
- ~u32_table();
-
- u32_table& operator=(const u32_table& other);
- u32_table& operator=(u32_table&& other) noexcept;
inline size_t get_num_items() const;
inline const uint32_t* get_slots() const;
@@ -60,9 +54,6 @@ public:
uint32_t* unwrapping_get_items() const;
- static void introspective_insertion_sort(uint32_t* a, size_t l, size_t r);
- static void knuth_shell_sort3(uint32_t* a, size_t l, size_t r);
-
static void merge(
const uint32_t* arr_a, size_t start_a, size_t length_a, // input
const uint32_t* arr_b, size_t start_b, size_t length_b, // input
@@ -70,16 +61,17 @@ public:
);
private:
+ typedef typename std::allocator_traits<A>::template rebind_alloc<uint32_t> AllocU32;
+ typedef std::vector<uint32_t, AllocU32> vector_u32;
+
uint8_t lg_size; // log2 of number of slots
uint8_t num_valid_bits;
size_t num_items;
- uint32_t* slots;
+ vector_u32 slots;
inline size_t lookup(uint32_t item) const;
inline void must_insert(uint32_t item);
inline void rebuild(uint8_t new_lg_size);
-
- typedef typename std::allocator_traits<A>::template rebind_alloc<uint32_t> AllocU32;
};
} /* namespace datasketches */
diff --git a/cpc/include/u32_table_impl.hpp b/cpc/include/u32_table_impl.hpp
index e7fb1c5..08316ed 100644
--- a/cpc/include/u32_table_impl.hpp
+++ b/cpc/include/u32_table_impl.hpp
@@ -33,7 +33,7 @@ u32_table<A>::u32_table():
lg_size(0),
num_valid_bits(0),
num_items(0),
-slots(nullptr)
+slots()
{}
template<typename A>
@@ -41,61 +41,10 @@ u32_table<A>::u32_table(uint8_t lg_size, uint8_t num_valid_bits):
lg_size(lg_size),
num_valid_bits(num_valid_bits),
num_items(0),
-slots(nullptr)
+slots(1 << lg_size, UINT32_MAX)
{
if (lg_size < 2) throw std::invalid_argument("lg_size must be >= 2");
if (num_valid_bits < 1 or num_valid_bits > 32) throw std::invalid_argument("num_valid_bits must be between 1 and 32");
- const size_t num_slots = 1 << lg_size;
- slots = AllocU32().allocate(num_slots);
- std::fill(slots, &slots[num_slots], UINT32_MAX);
-}
-
-template<typename A>
-u32_table<A>::u32_table(const u32_table& other):
-lg_size(other.lg_size),
-num_valid_bits(other.num_valid_bits),
-num_items(other.num_items),
-slots(nullptr)
-{
- const size_t num_slots = 1 << lg_size;
- slots = AllocU32().allocate(num_slots);
- std::copy(other.slots, &other.slots[num_slots], slots);
-}
-
-template<typename A>
-u32_table<A>::u32_table(u32_table&& other) noexcept:
-lg_size(other.lg_size),
-num_valid_bits(other.num_valid_bits),
-num_items(other.num_items),
-slots(other.slots)
-{
- other.slots = nullptr;
-}
-
-template<typename A>
-u32_table<A>::~u32_table() {
- if (slots != nullptr) {
- AllocU32().deallocate(slots, 1 << lg_size);
- }
-}
-
-template<typename A>
-u32_table<A>& u32_table<A>::operator=(const u32_table<A>& other) {
- u32_table<A> copy(other);
- std::swap(lg_size, copy.lg_size);
- num_valid_bits = copy.num_valid_bits;
- num_items = copy.num_items;
- std::swap(slots, copy.slots);
- return *this;
-}
-
-template<typename A>
-u32_table<A>& u32_table<A>::operator=(u32_table<A>&& other) noexcept {
- std::swap(lg_size, other.lg_size);
- num_valid_bits = other.num_valid_bits;
- num_items = other.num_items;
- std::swap(slots, other.slots);
- return *this;
}
template<typename A>
@@ -105,7 +54,7 @@ size_t u32_table<A>::get_num_items() const {
template<typename A>
const uint32_t* u32_table<A>::get_slots() const {
- return slots;
+ return slots.data();
}
template<typename A>
@@ -115,7 +64,7 @@ uint8_t u32_table<A>::get_lg_size() const {
template<typename A>
void u32_table<A>::clear() {
- std::fill(slots, &slots[1 << lg_size], UINT32_MAX);
+ std::fill(slots.begin(), slots.end(), UINT32_MAX);
num_items = 0;
}
@@ -202,16 +151,14 @@ void u32_table<A>::rebuild(uint8_t new_lg_size) {
const size_t old_size = 1 << lg_size;
const size_t new_size = 1 << new_lg_size;
if (new_size <= num_items) throw std::logic_error("new_size <= num_items");
- uint32_t* old_slots = slots;
- slots = AllocU32().allocate(new_size);
+ vector_u32 old_slots = std::move(slots);
+ slots = vector_u32(new_size, UINT32_MAX);
lg_size = new_lg_size;
- std::fill(slots, &slots[1 << lg_size], UINT32_MAX);
for (size_t i = 0; i < old_size; i++) {
if (old_slots[i] != UINT32_MAX) {
must_insert(old_slots[i]);
}
}
- AllocU32().deallocate(old_slots, old_size);
}
// While extracting the items from a linear probing hashtable,
@@ -219,6 +166,7 @@ void u32_table<A>::rebuild(uint8_t new_lg_size) {
// isn't too full. Experiments suggest that for sufficiently large tables
// the load factor would have to be over 90 percent before this would fail frequently,
// and even then the subsequent sort would fix things up.
+// The result is nearly sorted, so make sure to use an efficient sort for that case
// This is for internal use, so deallocation is on the caller.
template<typename A>
uint32_t* u32_table<A>::unwrapping_get_items() const {
@@ -246,55 +194,6 @@ uint32_t* u32_table<A>::unwrapping_get_items() const {
return result;
}
-// In applications where the input array is already nearly sorted,
-// insertion sort runs in linear time with a very small constant.
-// This introspective version of insertion sort protects against
-// the quadratic cost of sorting bad input arrays.
-// It keeps track of how much work has been done, and if that exceeds a
-// constant times the array length, it switches to a different sorting algorithm.
-
-template<typename A>
-void u32_table<A>::introspective_insertion_sort(uint32_t* a, size_t l, size_t r) { // r points at the rightmost element
- const size_t length = r - l + 1;
- const size_t cost_limit = 8 * length;
- size_t cost = 0;
- for (size_t i = l + 1; i <= r; i++) {
- size_t j = i;
- uint32_t v = a[i];
- while (j >= l + 1 and v < a[j - 1]) {
- a[j] = a[j - 1];
- j--;
- }
- a[j] = v;
- cost += i - j; // distance moved is a measure of work
- if (cost > cost_limit) {
- knuth_shell_sort3(a, l, r);
- return;
- }
- }
-}
-
-template<typename A>
-void u32_table<A>::knuth_shell_sort3(uint32_t* a, size_t l, size_t r) {
- size_t h;
- for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
- for ( ; h > 0; h /= 3) {
- for (size_t i = l + h; i <= r; i++) {
- size_t j = i;
- const uint32_t v = a[i];
- while (j >= l + h && v < a[j - h]) {
- a[j] = a[j - h]; j -= h;
- }
- a[j] = v;
- }
- }
- size_t bad = 0;
- for (size_t i = l; i < r - 1; i++) {
- if (a[i] > a[i + 1]) bad++;
- };
- if (bad != 0) throw std::logic_error("sorting error");
-}
-
// This merge is safe to use in carefully designed overlapping scenarios.
template<typename A>
void u32_table<A>::merge(
diff --git a/cpc/test/compression_test.cpp b/cpc/test/compression_test.cpp
index 62ee5ca..4a0fb5f 100644
--- a/cpc/test/compression_test.cpp
+++ b/cpc/test/compression_test.cpp
@@ -47,7 +47,8 @@ class compression_test: public CppUnit::TestFixture {
pairArray[i] = rand;
value += golden64;
}
- table::knuth_shell_sort3(pairArray, 0, N - 1); // unsigned numerical sort
+ //table::knuth_shell_sort3(pairArray, 0, N - 1); // unsigned numerical sort
+ std::sort(pairArray, &pairArray[N]);
uint32_t prev = UINT32_MAX;
int nxt = 0;
for (int i = 0; i < N; i++) { // uniquify
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org