You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by ti...@apache.org on 2026/07/23 13:46:48 UTC
(datasketches-rust) branch main updated: refactor(common): compute inverse powers inline (#159)
This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 3668658 refactor(common): compute inverse powers inline (#159)
3668658 is described below
commit 3668658f3d0a415f4ee157cf769c8db024364603
Author: Phoenix <Ph...@163.com>
AuthorDate: Thu Jul 23 21:46:42 2026 +0800
refactor(common): compute inverse powers inline (#159)
Closes #157
Signed-off-by: Jiawei Zhao <Ph...@163.com>
Co-authored-by: tison <wa...@gmail.com>
---
datasketches/src/common/{mod.rs => inv_pow2.rs} | 23 ++++--
datasketches/src/common/inv_pow2_table.rs | 103 ------------------------
datasketches/src/common/mod.rs | 2 +-
datasketches/src/cpc/kxp_byte_lookup.rs | 4 +-
datasketches/src/cpc/sketch.rs | 6 +-
datasketches/src/hll/estimator.rs | 10 +--
6 files changed, 27 insertions(+), 121 deletions(-)
diff --git a/datasketches/src/common/mod.rs b/datasketches/src/common/inv_pow2.rs
similarity index 66%
copy from datasketches/src/common/mod.rs
copy to datasketches/src/common/inv_pow2.rs
index d7e0cf5..353faa2 100644
--- a/datasketches/src/common/mod.rs
+++ b/datasketches/src/common/inv_pow2.rs
@@ -15,12 +15,21 @@
// specific language governing permissions and limitations
// under the License.
-//! Data structures and functions that may be used across all the sketch families.
+/// Compute 1 / 2^exp using the same bit construction as DataSketches Java.
+#[inline]
+pub(crate) fn inv_pow2(exp: u8) -> f64 {
+ f64::from_bits((1023 - exp as u64) << 52)
+}
-mod num_std_dev;
-mod resize;
-pub use self::num_std_dev::NumStdDev;
-pub use self::resize::ResizeFactor;
+#[cfg(test)]
+mod tests {
+ use super::*;
-#[cfg(any(feature = "cpc", feature = "hll"))]
-pub(crate) mod inv_pow2_table;
+ #[test]
+ fn assert_inv_pow2() {
+ for i in 0..=255 {
+ let expected = 2f64.powf(-(i as f64));
+ assert_eq!(inv_pow2(i), expected);
+ }
+ }
+}
diff --git a/datasketches/src/common/inv_pow2_table.rs b/datasketches/src/common/inv_pow2_table.rs
deleted file mode 100644
index dd19f1e..0000000
--- a/datasketches/src/common/inv_pow2_table.rs
+++ /dev/null
@@ -1,103 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements. See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership. The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License. You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied. See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-#[rustfmt::skip]
-#[allow(clippy::excessive_precision)]
-pub(crate) static INVERSE_POWERS_OF_2: [f64; 256] = [
- 1.0, 0.5, 0.25, 0.125,
- 0.0625, 0.03125, 0.015625, 0.0078125,
- 0.00390625, 0.001953125, 0.0009765625, 0.00048828125,
- 0.000244140625, 0.0001220703125, 6.103515625e-05, 3.0517578125e-05,
- 1.52587890625e-05, 7.62939453125e-06, 3.814697265625e-06, 1.9073486328125e-06,
- 9.5367431640625e-07, 4.76837158203125e-07, 2.384185791015625e-07, 1.1920928955078125e-07,
- 5.9604644775390625e-08, 2.9802322387695312e-08, 1.4901161193847656e-08, 7.4505805969238281e-09,
- 3.7252902984619141e-09, 1.862645149230957e-09, 9.3132257461547852e-10, 4.6566128730773926e-10,
- 2.3283064365386963e-10, 1.1641532182693481e-10, 5.8207660913467407e-11, 2.9103830456733704e-11,
- 1.4551915228366852e-11, 7.2759576141834259e-12, 3.637978807091713e-12, 1.8189894035458565e-12,
- 9.0949470177292824e-13, 4.5474735088646412e-13, 2.2737367544323206e-13, 1.1368683772161603e-13,
- 5.6843418860808015e-14, 2.8421709430404007e-14, 1.4210854715202004e-14, 7.1054273576010019e-15,
- 3.5527136788005009e-15, 1.7763568394002505e-15, 8.8817841970012523e-16, 4.4408920985006262e-16,
- 2.2204460492503131e-16, 1.1102230246251565e-16, 5.5511151231257827e-17, 2.7755575615628914e-17,
- 1.3877787807814457e-17, 6.9388939039072284e-18, 3.4694469519536142e-18, 1.7347234759768071e-18,
- 8.6736173798840355e-19, 4.3368086899420177e-19, 2.1684043449710089e-19, 1.0842021724855044e-19,
- 5.4210108624275222e-20, 2.7105054312137611e-20, 1.3552527156068805e-20, 6.7762635780344027e-21,
- 3.3881317890172014e-21, 1.6940658945086007e-21, 8.4703294725430034e-22, 4.2351647362715017e-22,
- 2.1175823681357508e-22, 1.0587911840678754e-22, 5.2939559203393771e-23, 2.6469779601696886e-23,
- 1.3234889800848443e-23, 6.6174449004242214e-24, 3.3087224502121107e-24, 1.6543612251060553e-24,
- 8.2718061255302767e-25, 4.1359030627651384e-25, 2.0679515313825692e-25, 1.0339757656912846e-25,
- 5.169878828456423e-26, 2.5849394142282115e-26, 1.2924697071141057e-26, 6.4623485355705287e-27,
- 3.2311742677852644e-27, 1.6155871338926322e-27, 8.0779356694631609e-28, 4.0389678347315804e-28,
- 2.0194839173657902e-28, 1.0097419586828951e-28, 5.0487097934144756e-29, 2.5243548967072378e-29,
- 1.2621774483536189e-29, 6.3108872417680944e-30, 3.1554436208840472e-30, 1.5777218104420236e-30,
- 7.8886090522101181e-31, 3.944304526105059e-31, 1.9721522630525295e-31, 9.8607613152626476e-32,
- 4.9303806576313238e-32, 2.4651903288156619e-32, 1.2325951644078309e-32, 6.1629758220391547e-33,
- 3.0814879110195774e-33, 1.5407439555097887e-33, 7.7037197775489434e-34, 3.8518598887744717e-34,
- 1.9259299443872359e-34, 9.6296497219361793e-35, 4.8148248609680896e-35, 2.4074124304840448e-35,
- 1.2037062152420224e-35, 6.018531076210112e-36, 3.009265538105056e-36, 1.504632769052528e-36,
- 7.5231638452626401e-37, 3.76158192263132e-37, 1.88079096131566e-37, 9.4039548065783001e-38,
- 4.70197740328915e-38, 2.350988701644575e-38, 1.1754943508222875e-38, 5.8774717541114375e-39,
- 2.9387358770557188e-39, 1.4693679385278594e-39, 7.3468396926392969e-40, 3.6734198463196485e-40,
- 1.8367099231598242e-40, 9.1835496157991212e-41, 4.5917748078995606e-41, 2.2958874039497803e-41,
- 1.1479437019748901e-41, 5.7397185098744507e-42, 2.8698592549372254e-42, 1.4349296274686127e-42,
- 7.1746481373430634e-43, 3.5873240686715317e-43, 1.7936620343357659e-43, 8.9683101716788293e-44,
- 4.4841550858394146e-44, 2.2420775429197073e-44, 1.1210387714598537e-44, 5.6051938572992683e-45,
- 2.8025969286496341e-45, 1.4012984643248171e-45, 7.0064923216240854e-46, 3.5032461608120427e-46,
- 1.7516230804060213e-46, 8.7581154020301067e-47, 4.3790577010150533e-47, 2.1895288505075267e-47,
- 1.0947644252537633e-47, 5.4738221262688167e-48, 2.7369110631344083e-48, 1.3684555315672042e-48,
- 6.8422776578360209e-49, 3.4211388289180104e-49, 1.7105694144590052e-49, 8.5528470722950261e-50,
- 4.276423536147513e-50, 2.1382117680737565e-50, 1.0691058840368783e-50, 5.3455294201843913e-51,
- 2.6727647100921956e-51, 1.3363823550460978e-51, 6.6819117752304891e-52, 3.3409558876152446e-52,
- 1.6704779438076223e-52, 8.3523897190381114e-53, 4.1761948595190557e-53, 2.0880974297595278e-53,
- 1.0440487148797639e-53, 5.2202435743988196e-54, 2.6101217871994098e-54, 1.3050608935997049e-54,
- 6.5253044679985245e-55, 3.2626522339992623e-55, 1.6313261169996311e-55, 8.1566305849981557e-56,
- 4.0783152924990778e-56, 2.0391576462495389e-56, 1.0195788231247695e-56, 5.0978941156238473e-57,
- 2.5489470578119236e-57, 1.2744735289059618e-57, 6.3723676445298091e-58, 3.1861838222649046e-58,
- 1.5930919111324523e-58, 7.9654595556622614e-59, 3.9827297778311307e-59, 1.9913648889155653e-59,
- 9.9568244445778267e-60, 4.9784122222889134e-60, 2.4892061111444567e-60, 1.2446030555722283e-60,
- 6.2230152778611417e-61, 3.1115076389305709e-61, 1.5557538194652854e-61, 7.7787690973264271e-62,
- 3.8893845486632136e-62, 1.9446922743316068e-62, 9.7234613716580339e-63, 4.861730685829017e-63,
- 2.4308653429145085e-63, 1.2154326714572542e-63, 6.0771633572862712e-64, 3.0385816786431356e-64,
- 1.5192908393215678e-64, 7.596454196607839e-65, 3.7982270983039195e-65, 1.8991135491519597e-65,
- 9.4955677457597987e-66, 4.7477838728798994e-66, 2.3738919364399497e-66, 1.1869459682199748e-66,
- 5.9347298410998742e-67, 2.9673649205499371e-67, 1.4836824602749686e-67, 7.4184123013748428e-68,
- 3.7092061506874214e-68, 1.8546030753437107e-68, 9.2730153767185535e-69, 4.6365076883592767e-69,
- 2.3182538441796384e-69, 1.1591269220898192e-69, 5.7956346104490959e-70, 2.897817305224548e-70,
- 1.448908652612274e-70, 7.2445432630613699e-71, 3.6222716315306849e-71, 1.8111358157653425e-71,
- 9.0556790788267124e-72, 4.5278395394133562e-72, 2.2639197697066781e-72, 1.131959884853339e-72,
- 5.6597994242666952e-73, 2.8298997121333476e-73, 1.4149498560666738e-73, 7.074749280333369e-74,
- 3.5373746401666845e-74, 1.7686873200833423e-74, 8.8434366004167113e-75, 4.4217183002083556e-75,
- 2.2108591501041778e-75, 1.1054295750520889e-75, 5.5271478752604446e-76, 2.7635739376302223e-76,
- 1.3817869688151111e-76, 6.9089348440755557e-77, 3.4544674220377779e-77, 1.7272337110188889e-77
-];
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- #[test]
- fn assert_inv_pow2_table() {
- for i in 0u8..=255 {
- // expected value
- let expected = INVERSE_POWERS_OF_2[i as usize];
-
- // computed value
- let computed = 2f64.powf(-(i as f64));
-
- assert_eq!(expected, computed);
- }
- }
-}
diff --git a/datasketches/src/common/mod.rs b/datasketches/src/common/mod.rs
index d7e0cf5..6d4c6c6 100644
--- a/datasketches/src/common/mod.rs
+++ b/datasketches/src/common/mod.rs
@@ -23,4 +23,4 @@ pub use self::num_std_dev::NumStdDev;
pub use self::resize::ResizeFactor;
#[cfg(any(feature = "cpc", feature = "hll"))]
-pub(crate) mod inv_pow2_table;
+pub(crate) mod inv_pow2;
diff --git a/datasketches/src/cpc/kxp_byte_lookup.rs b/datasketches/src/cpc/kxp_byte_lookup.rs
index a4118f2..31e2185 100644
--- a/datasketches/src/cpc/kxp_byte_lookup.rs
+++ b/datasketches/src/cpc/kxp_byte_lookup.rs
@@ -52,7 +52,7 @@ pub(super) static KXP_BYTE_TABLE: [f64; 256] = [
#[cfg(test)]
mod tests {
use super::*;
- use crate::common::inv_pow2_table::INVERSE_POWERS_OF_2;
+ use crate::common::inv_pow2::inv_pow2;
#[test]
fn assert_kxp_byte_table() {
@@ -66,7 +66,7 @@ mod tests {
let bit = (byte >> col) & 1;
if bit == 0 {
// note the inverted logic
- computed += INVERSE_POWERS_OF_2[col + 1]; //note the "+1"
+ computed += inv_pow2(col + 1); //note the "+1"
}
}
diff --git a/datasketches/src/cpc/sketch.rs b/datasketches/src/cpc/sketch.rs
index c46a94f..8f8687b 100644
--- a/datasketches/src/cpc/sketch.rs
+++ b/datasketches/src/cpc/sketch.rs
@@ -24,7 +24,7 @@ use crate::codec::assert::ensure_serial_version_is;
use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::common::NumStdDev;
-use crate::common::inv_pow2_table::INVERSE_POWERS_OF_2;
+use crate::common::inv_pow2::inv_pow2;
use crate::cpc::DEFAULT_LG_K;
use crate::cpc::Flavor;
use crate::cpc::MAX_LG_K;
@@ -252,7 +252,7 @@ impl CpcSketch {
let col = (row_col & 63) as usize;
let one_over_p = (k as f64) / self.kxp;
self.hip_est_accum += one_over_p;
- self.kxp -= INVERSE_POWERS_OF_2[col + 1] // notice the "+1"
+ self.kxp -= inv_pow2((col + 1) as u8) // notice the "+1"
}
fn update_sparse(&mut self, row_col: u32) {
@@ -408,7 +408,7 @@ impl CpcSketch {
let mut total = 0.0;
for i in (0..8).rev() {
// the reverse order is important
- let factor = INVERSE_POWERS_OF_2[i * 8]; // pow (256.0, (-1.0 * ((double) j)))
+ let factor = inv_pow2((i * 8) as u8); // pow (256.0, (-1.0 * ((double) j)))
total += factor * byte_sums[i];
}
diff --git a/datasketches/src/hll/estimator.rs b/datasketches/src/hll/estimator.rs
index e094d98..f5b4652 100644
--- a/datasketches/src/hll/estimator.rs
+++ b/datasketches/src/hll/estimator.rs
@@ -23,7 +23,7 @@
//! moderate cardinalities.
use crate::common::NumStdDev;
-use crate::common::inv_pow2_table::INVERSE_POWERS_OF_2;
+use crate::common::inv_pow2::inv_pow2;
use crate::hll::composite_interpolation;
use crate::hll::cubic_interpolation;
use crate::hll::harmonic_numbers;
@@ -91,16 +91,16 @@ impl HipEstimator {
fn update_kxq(&mut self, old_value: u8, new_value: u8) {
// Subtract old value contribution
if old_value < 32 {
- self.kxq0 -= INVERSE_POWERS_OF_2[old_value as usize];
+ self.kxq0 -= inv_pow2(old_value);
} else {
- self.kxq1 -= INVERSE_POWERS_OF_2[old_value as usize];
+ self.kxq1 -= inv_pow2(old_value);
}
// Add new value contribution
if new_value < 32 {
- self.kxq0 += INVERSE_POWERS_OF_2[new_value as usize];
+ self.kxq0 += inv_pow2(new_value);
} else {
- self.kxq1 += INVERSE_POWERS_OF_2[new_value as usize];
+ self.kxq1 += inv_pow2(new_value);
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org