Theta sketch output doesn't match between Java and CPP

I have run a simple theta sketch computation as below in Java and CPP

Union union = Union.builder().buildUnion();
       union.update(1);
       union.update(2);
       CompactSketch compactSketch = union.getResult();
byte[] bytes = union.getResult().toByteArray()

Java output:

02 03 03 00 00 1a cc 93 02 00 00 00 00 00 80 3f
15 f9 7d cb bd 86 a1 05 c3 97 fc 12 81 70 9d 1e

CPP :

updateThetaSketch update_sketch = updateThetaSketch::builder().build();

  update_sketch.update(1);
  update_sketch.update(2);
  auto bytes = update_sketch.compact().serialize();

CPP output:

02 03 03 00 00 1a cc 93 02 00 00 00 00 00 00 00
15 f9 7d cb bd 86 a1 05 c3 97 fc 12 81 70 9d 1e

The output seems to not match, as we see in bold at the end of first line, 4 bytes "80 3f" is missing in CPP.

Can anyone share why this is so?

In this case the last 4 bytes in the first row are not used (padding for alignment) and must be 0. I am not sure why Java does not fill this padding with 0. Are you using the latest code (from main branch or latest release)?

@AlexanderSaydakov

@AlexanderSaydakov Thanks. Yes. We are using Java 5.0.1 version. Latest from main branch on CPP.

Also, if I just do single value update in the sketch like

update_sketch.update(1)

The output from Java and CPP is

Java:

01 03 03 00 00 3a cc 93 15 f9 7d cb bd 86 a1 05

and

Cpp:

01 03 03 00 00 1a cc 93 15 f9 7d cb bd 86 a1 05

The flag byte is 3a in Java and 1a in CPP.

In this case Java sets one more flag "single item", but that can be derived from preamble_longs=1 and !is_empty.

On the one hand, these differences are harmless and should not affect anything except you want to have a very strict test comparing bytes.
On the other hand, we may want to align our implementations and make cross-platform compatibility checks more strict. Currently we test that we can read serialized sketches from other languages and assert basic things such as the same theta and the same hash values. We may want to serialize and compare the resulting bytes instead.

@AlexanderSaydakov

Thank you @AlexanderSaydakov. This info helps.

@nmahadevuni

I ran a differential test between the two implementations to chase this down.

Oracle: Java and C++ are specified to serialize identically, so any disagreement is a bug in one of them. I built datasketches-cpp at c8e4218 (master) and datasketches-java at d5cce9b (main, 9.1.0-SNAPSHOT), generated the same 20 theta cases on both sides (empty, single item, exact, estimation, sampling with p<1, union, intersection, a-not-b, ordered and unordered, plus the v4 compressed format) and compared serialized bytes along with retained count, theta, estimate and both bounds. 11 of 20 are byte identical. The 9 that differ do so in exactly two places, and there is a third finding that is not about bytes at all.

1. The p bytes you originally reported are already fixed. Java commit 8044090 ("Set P to zero for compact sketches", Aug 2025) changed insertP(dstWSeg, (float) 1.0) to (float) 0.0 in CompactOperations, with the comment "0.0 to be consistent with C++". That shipped in datasketches-java 9.0.0; @nmahadevuni was on 5.0.1. On current main the exact 2-item case from the first post now matches byte for byte on both sides:

02 03 03 00 00 1a cc 93 02 00 00 00 00 00 00 00
15 f9 7d cb bd 86 a1 05 c3 97 fc 12 81 70 9d 1e

2. The single item flag is still there, in 3 of my 20 cases. Java sets bit 5, C++ does not. It is slightly more than cosmetic, because Java's own PreambleUtil.preambleToString derives the count from that flag (int curCount = singleItem ? 1 : 0). So Java's preamble dump of a C++ single item sketch reports CurrentCount 0 for a sketch that holds 1 entry:

cpp bytes  01 03 03 00 00 1a cc 93 | 15 f9 7d cb bd 86 a1 05
Java preambleToString -> CurrentCount: 0, SINGLE_ITEM: false   (actual retained: 1)
Java on its own bytes -> CurrentCount: 1, SINGLE_ITEM: true    (actual retained: 1)

Java's real parser gets it right: SingleItemSketch.checkForSingleItem masks bit 5 off and accepts (flags & 0x1F) == 0x1A, with the comment "SingleItem flag may not be set due to a historical bug, so we can't depend on it for now". So Java's diagnostic path contradicts Java's own parser, independent of what C++ does. Whichever way you decide to align the bytes, that preambleToString line looks worth fixing on its own.

3. A third divergence that is not in this issue, and this one actually bites. For every empty compact sketch, Java writes a seed hash of 00 00 and C++ writes computeSeedHash(seed):

cpp : 01 03 03 00 00 1e cc 93
java: 01 03 03 00 00 1e 00 00

That accounts for the other 6 differing cases. Java is deliberate here: EmptyCompactSketch is a singleton constant {1, 3, 3, 0, 0, 0x1E, 0, 0} and the source says "The seedHash is ignored".

C++ mostly agrees that an empty sketch's seed hash is meaningless. deserialize_v3 and deserialize_v4 do if (!is_empty) check_seed_hash(...), theta_union_base::update returns early on sketch.is_empty(), and theta_intersection_base::update does if (!sketch.is_empty() && ...). All three existing seed mismatch tests carry the comment "non-empty should not be ignored".

theta_set_difference_base::compute is the one path that does not, and it throws. Its early return only fires when a.get_num_retained() > 0, so when A is non-empty with zero retained entries the check is reached. Reproducible in C++ alone, no Java needed:

auto b = update_theta_sketch::builder().set_seed(12345).build().compact();  // empty, foreign seed
auto a = update_theta_sketch::builder().set_p(1e-6f).build();               // non-empty, 0 retained
a.update(1); a.update(2); a.update(3);

compact_theta_sketch::deserialize(...)      // ACCEPTED
theta_union(seed=9001).update(b)            // ACCEPTED
theta_intersection(seed=9001).update(b)     // ACCEPTED
theta_a_not_b(seed=9001).compute(a, b)      // THREW -> B seed hash mismatch

Cross language, the same thing happens with an unmodified Java empty sketch as B, in all 6 of my empty cases, because Java's seed hash of 0 never matches. Fix is one line, guarding B's check with !b.is_empty() the way intersection already does. I opened #517 for it: all 17 ctest suites pass and the 6 cross language failures go to 0.

So to answer the original question directly: the p difference was a Java bug and is fixed, the single item flag is still unaligned and exposes a real inconsistency inside Java, and the empty sketch seed hash difference is intentional in Java but exposes a real bug in C++ a-not-b.

Happy to share the 20 case harness if it is useful for the stricter byte comparison @AlexanderSaydakov mentioned above; it is about 100 lines on each side.

I used Claude Code to help run the differential harness and draft this comment. I verified every claim above against actual build and test output.

@jaideeppyne

@jaideeppyne

Sorry this has taken so long, but I am taking a close look at Cross-Language Binary (CLB) testing especially between DS-CPP and DS-Java, especially for the deterministic sketches. So I'd be interested in your 20 case harness you developed above. Would you mind sharing it if you still have it?

I think the 3 issues you identified have been fixed, at least in ds-ccp master and ds-java main.
If you have time, and if it is easy could you verify your test harness again?

@nmahadevuni

Closing this issue: all three findings are now resolved in datasketches-cpp, and the fixes will ship in the upcoming 5.3.0 release.

Thank you @nmahadevuni for the original report, and @jaideeppyne for the detailed differential analysis, which made each discrepancy easy to pin down.

I verified each case against current C++ master by serializing the same sketches described above:

┌──────────────────────────────────────┬─────────────┬──────────────────┬──────────────┐
│               Finding                │    Java     │    C++ master    │   Fixed by   │
├──────────────────────────────────────┼─────────────┼──────────────────┼──────────────┤
│ 1. p bytes (2-item sketch)           │ 00 00 00 00 │ 00 00 00 00      │ Java 9.0.0 ¹ │
├──────────────────────────────────────┼─────────────┼──────────────────┼──────────────┤
│ 2. Single-item flag                  │ 3a          │ 3a               │ #526 ²       │
├──────────────────────────────────────┼─────────────┼──────────────────┼──────────────┤
│ 3. Empty seed hash                   │ 00 00       │ 00 00            │ #518 ³       │
├──────────────────────────────────────┼─────────────┼──────────────────┼──────────────┤
│ 3b. A-not-B, empty B with other seed │ —           │ no longer throws │ #517 ⁴       │
└──────────────────────────────────────┴─────────────┴──────────────────┴──────────────┘

C++ always wrote zero. Java changed to zero in 9.0.0. The bytes now match the original report exactly.
Set for both compact sketches and union results.
Also in the compressed (v4) form.
Also when B is an empty image written by Java.

For example, the 2-item sketch from the original report now serializes on C++ master as:

02 03 03 00 00 1a cc 93 02 00 00 00 00 00 00 00
15 f9 7d cb bd 86 a1 05 c3 97 fc 12 81 70 9d 1e

One remaining item is on the Java side: PreambleUtil.preambleToString() still derives the item count from the single-item flag. Since C++ now sets that flag, newly written C++ sketches display correctly in Java, but older images still show "CurrentCount: 0". That's a small diagnostic fix to track in datasketches-java.

@jaideeppyne, if you'd still like to share your 20-case harness, it would be very welcome for our cross-language binary testing.

Thank you, Lee, for the careful verification and for carrying these fixes through. It is great to see all four behaviors aligned, and the table makes the final state very clear. I also appreciate the acknowledgement of the differential analysis.

About the 20-case harness

I cleaned up the scratch workspace after the investigation, so I no longer have the exact scripts I ran. I do not want to present an unverified reconstruction as the original artifact.

The matrix covered:

Sketch states: empty, single-item, exact, and estimation
Sampling: p < 1
Set operations: union, intersection, and A-not-B
Serialization forms: ordered, unordered, and v4 compressed
Seeds: default and alternate seeds
Compared outputs: serialized bytes, retained count, theta, estimate, and upper/lower bounds

Next step

If a repository-native version would still help the CLB work, I would be happy to reconstruct it against current Java main and C++ master, rerun the full matrix, and contribute it in the test location and format you prefer.

Thanks again for closing the loop and getting these fixes into 5.3.0.

Navigation Menu

Repository navigation

Theta sketch output doesn't match between Java and CPP #460

About the 20-case harness

Next step

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Theta sketch output doesn't match between Java and CPP #460

Description

Activity

AlexanderSaydakov commented on Jul 1, 2025

nmahadevuni commented on Jul 2, 2025

nmahadevuni commented on Jul 2, 2025

AlexanderSaydakov commented on Jul 2, 2025

nmahadevuni commented on Jul 3, 2025

jaideeppyne commented on Aug 30, 2026

leerho commented on Sep 29, 2026

leerho commented on Oct 1, 2026

jaideeppyne commented on Oct 1, 2026

About the 20-case harness

Next step

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions