You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "tisonkun (via GitHub)" <gi...@apache.org> on 2026/01/20 13:46:09 UTC
[I] CpcSketch PairTable's constructor should check lgSizeInts < numValidBits? (datasketches-java)
tisonkun opened a new issue, #717:
URL: https://github.com/apache/datasketches-java/issues/717
The C++ impl checks:
```cpp
if (lg_size < 2) throw std::invalid_argument("lg_size must be >= 2");
if (num_valid_bits < 1 || num_valid_bits > 32) throw std::invalid_argument("num_valid_bits must be between 1 and 32");
```
The Java impl checks:
https://github.com/apache/datasketches-java/blob/23072ed1d7bcb16d38583f01e643a5a67510c07d/src/main/java/org/apache/datasketches/cpc/PairTable.java#L49
While we also have:
https://github.com/apache/datasketches-java/blob/23072ed1d7bcb16d38583f01e643a5a67510c07d/src/main/java/org/apache/datasketches/cpc/PairTable.java#L139-L140
So I think we may align all these checks, and we actually have an assertion that `lgSizeInts < numValidBits` which holds for all the construction calls.
BTW, IIUC the `PairTable` is:
```rust
/// A highly specialized hash table used for sparse data.
///
/// This table stores `(row, col)` pairs and uses linear probing for collision resolution. It is
/// optimized for scenarios where the cardinality of entries is low.
```
--
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: dev-unsubscribe@datasketches.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [I] CpcSketch PairTable's constructor should check lgSizeInts < numValidBits? (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #717:
URL: https://github.com/apache/datasketches-java/issues/717#issuecomment-3801300420
@tisonkun,
I have't seen any response on this issue, is there something else I could help you understand?
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [I] CpcSketch PairTable's constructor should check lgSizeInts < numValidBits? (datasketches-java)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on issue #717:
URL: https://github.com/apache/datasketches-java/issues/717#issuecomment-3772977351
For reference, I'm writing the following check in the Rust impl:
```rust
pub fn new(lg_size: u8, num_valid_bits: u8) -> Self {
assert!(
(2..=26).contains(&lg_size),
"lg_size must be in [2, 26], got {lg_size}"
);
assert!(
((lg_size + 1)..=32).contains(&num_valid_bits),
"num_valid_bits must be in [lg_size + 1, 32], got {num_valid_bits} where lg_size = {lg_size}"
);
Self {
lg_size,
num_valid_bits,
num_items: 0,
slots: vec![u32::MAX; 1 << lg_size],
}
}
```
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [I] CpcSketch PairTable's constructor should check lgSizeInts < numValidBits? (datasketches-java)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on issue #717:
URL: https://github.com/apache/datasketches-java/issues/717#issuecomment-3802618191
Thanks for your feedback. Since either check is loose, I'd close this issue as won't do and keep the current code.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [I] CpcSketch PairTable's constructor should check lgSizeInts < numValidBits? (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #717:
URL: https://github.com/apache/datasketches-java/issues/717#issuecomment-3775913023
The whole idea of the PairTable is to hold low cardinality rowCol pairs (sparse mode) before the sketch transistions into one of the "dense" modes. As the cardinality goes into higher modes (hybrid, pinned, and sliding), the PairTable is used for "novel" pairs that lie below or above the 8 bit wide window, which are rare. Nonetheless, the PairTable will never reach a size of 2^26.
So checking the PT 2 <= LgSize <= 26 is OK but loose. (I could figure out what the actual max size is, but it isn't worth the trouble right now.)
Likewise, the number of valid bits should never be less than 10 = 6+4, with a max of 32. Checking the range to be [(lg_size +1)..=32 is OK but loose.
The Java PairTable "final int shift = table.validBits - lgSizeInts; " is a trick to improve probe efficiency of the hash table. The assert that it is > 0 is OK but loose.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [I] CpcSketch PairTable's constructor should check lgSizeInts < numValidBits? (datasketches-java)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun closed issue #717: CpcSketch PairTable's constructor should check lgSizeInts < numValidBits?
URL: https://github.com/apache/datasketches-java/issues/717
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org