`sse2::Group::match_tag` misimplementation?

[smoelius]

Could it be possible that sse2::Group::match_tag is misimplemented?

I have observed discrepancies between rustdoc-types-produced JSON files on MacOS and Linux. I have been trying to determine the root cause.

I noticed that the elements of this hashtable can have different orders on the two platforms, even when elements are inserted in the same order:

    pub(crate) external_paths: FxHashMap<DefId, (Vec<Symbol>, ItemType)>,

Digging further, I noticed that values returned by this call to match_tag can differ on the two platforms:

hashbrown/src/raw/mod.rs

Line 1885 in b5b0655

for bit in group.match_tag(tag_hash) {

From what I can tell, my MacOS platform uses the neon implementation, and my Linux platform uses the sse2 implementation.

Here is a side-by-side comparison withneon on the left and sse2 on the right (please ignore the line numbers):

If I disable the sse2 implementation so that my Linux platform uses the generic one, the returned values still differ, but generated JSON files match.

Disabling the neon implementation on my MacOS platform does not have the same effect (the JSON files still differ).

Am I crazy to point the finger at sse2::Group::match_tag?

[cuviper]

I noticed that values returned by this call to match_tag can differ on the two platforms

I don't know if there's any bug, but at least this part should be expected. Each implementation has a different type BitMaskWord and const BITMASK_ITER_MASK, so they don't really need to be returning the same raw values. In particular, sse2's mask is !0, so it's using all bits, while neon uses 0x8080_8080_8080_8080 -- only the MSB of each byte.

AFAICT, your neon values do look like the same sse2 bits splatted into bytes, like 0x4 = 0b100 -> 0xff0000.

[clarfonthey]

Yeah, I wouldn't exactly consider this a bug; hash tables are so performance-sensitive that it makes sense that they'd perform differently across systems, even if seeded in the same way, due to the way that these platforms handle SIMD differently. If you're looking for determinism, you should be combining the hash tables with a deterministic ordering scheme using something like indexmap instead of relying on the inherent ordering of the hash tables.

[smoelius]

If you're looking for determinism, you should be combining the hash tables with a deterministic ordering scheme using something like indexmap instead of relying on the inherent ordering of the hash tables.

👍

Thank you both for your comments!