Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Multi-word monomial hash has exact-collision families: every Bitset with word0 == word1 + 1 hashes to 0

Aperta
  • Qualcosa non va?
#200 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
55/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Tranquilla
Stack tecnologico
cpp
Ambito
performance

Direzione di ricerca

Start with cpp/monoprop/Bitset.h lines 225–247 and inspect how SplitmixHash handles multi-word bitsets; then read the MonomialHash and find_rank call sites to understand effects of changing hashes. Add tests for the stated collision family on 2-word and 8-word bitsets, plus the low-weight distribution check. Run the listed test matrix and benchmark; done means the collisions are addressed and the equivalence suites still pass.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

performance

🤖 AI text below 🤖

What

SplitmixHash combines the words of a multi-word Bitset by XOR-ing per-word mixes with a
position-additive tweak.

cpp/monoprop/Bitset.h:225-247

template <size_t NumBits>
struct SplitmixHash<monoprop::Bitset<NumBits>> {
    static constexpr auto mix(uint64_t x) noexcept -> uint64_t { /* splitmix64 finalizer */ }

    auto operator()(const monoprop::Bitset<NumBits> &bs) const noexcept -> size_t {
        constexpr size_t W = monoprop::Bitset<NumBits>::num_words();
        if constexpr (W == 1) {
            return static_cast<size_t>(mix(bs.word(0)));
        }
        else {
            uint64_t h = 0;
            for (size_t i = 0; i < W; ++i) {
                h ^= mix(bs.word(i) + static_cast<uint64_t>(i));   // <--
            }
            return static_cast<size_t>(h);
        }
    }
};

The single-word case is a clean splitmix64 finalizer and is fine. The multi-word case — i.e. every
NumModes > 32 — is not.

Why this is a problem

XOR is commutative, so the only thing distinguishing word positions is the + i tweak. That makes the
hash invariant under swapping two word positions with a compensating value shift. For two words:

h([a, b])       = mix(a + 0) ^ mix(b + 1)
h([b + 1, a - 1]) = mix(b + 1 + 0) ^ mix(a - 1 + 1) = mix(b + 1) ^ mix(a)     ← identical

The fixed point of that family is worse: whenever word0 == word1 + 1, the two mixes are equal and
cancel, so the hash is exactly 0. That is not a contrived input — it includes ordinary low-weight
monomials. On a 64-mode Majorana system (128 bits, 2 words):

monomial word0 word1 hash
{bit 1, bit 64} (weight 2) 0b10 0b1 0
{bit 2, bits 64,65} (weight 3) 0b100 0b11 0
{bit 5, bits 64..68} (weight 6) 1<<5 (1<<5)-1 0

…and more generally every (v + 1, v) low-weight pair. The same argument generalises to any word
count: ⊕ᵢ mix(wᵢ + i) collides for any position transposition with the matching value adjustment.

Where it hurts:

  • detail::OperatorIndex (cpp/monoprop/detail/operator/OperatorIndex.h) — fold_hash folds the full
    hash to 32 bits, so identical full hashes give identical folds and land in one linear-probe chain.
    A cluster of N such keys costs O(N²) probes plus row_eq_key confirmations on insert and lookup.
  • boost::unordered_flat_map via MonomialHash — MonomialMap, MPOperator::init_op_map.
  • find_rank (cpp/monoprop/detail/mpi/MPIUtils.h:52), which is monomial_hash(mono) % n_ranks.

To be clear about severity: this is a throughput defect, not a wrong-answer defect. Hashes only
need to be consistent, and they are.

Suggested fix

Chain the mixes instead of XOR-ing them, so position is structural rather than an additive tweak:

uint64_t h = 0;
for (size_t i = 0; i < W; ++i) {
    h = mix(h ^ bs.word(i));
}
return static_cast<size_t>(h);

(or a multiply-accumulate with a final avalanche). Either way it is a few lines in one place.

Why this wants its own PR

Changing the hash changes find_rank, and therefore:

  • how terms distribute across MPI ranks and across intra-process partitions;
  • the block order of contract_partially's output — already documented as not positionally stable
    ("not positionally stable across partition counts", MonomialPropagator.h), but it will move.

The equivalence tests should survive: cpp/tests/mpi_utils_tests.cpp only asserts find_rank's range
and determinism, and the MPI/partition equivalence suites compare values and multisets rather than
positions. Still, it deserves a dedicated change with its own full-matrix run rather than riding along
with unrelated work.

Verification

  • A unit test pinning the collision away: assert hash({bit 1, bit 64}) != 0 and that the
    h([a,b]) == h([b+1,a-1]) family no longer collides, for a 2-word and an 8-word Bitset.
  • A distribution smoke test: hash all weight ≤ 4 monomials on a 64-mode system and assert the distinct
    hash count matches the monomial count.
  • Full matrix: just test, just test-mpi "1;2;4", just test-wide.
  • just bench serial — a measurable improvement here would confirm the collisions were costing real
    probe time; no change would mean the colliding family is rare in the benchmarked workloads, which is
    worth recording either way.

Found by a code-reading review of the repository at 29a8050. No build tree was available, so the
collision families above were derived by hand from the source and should be confirmed by the unit test
described above before the fix lands.

Lingua principale
C++
Stelle
52
Fork
2
Merge medio
17h 30m
PR unite (30g)
29

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di Algorithmiq/monoprop

Tutte le issue di Algorithmiq/monoprop

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.