radiance · commit

bitset: Compare common words directly

989569833188992aff7fa977497fe4bc0289166f6d4d7b0424079bcb41787dbf

`eq` selected a word or zero for both operands on every iteration
up to the larger bitset size, adding bounds branches to the common
equal-size case.

Compare the shared prefix directly, then check only unmatched tail
words for zero. The unused `max` helper is removed with the old
loop.

Assisted-by: Codex:gpt-5.6-sol

Alexis Sellier committed 1 month ago 1 parent b9413ac4

lib/std/lang/gen/bitset.rad +13 -13

        return a;
    }
    return b;
}

/// Return the maximum of two 32-bit values.
fn max(a: u32, b: u32) -> u32 {
    if a > b {
        return a;
    }
    return b;
}

/// Calculate the number of 32-bit words needed to store `n` bits.
export fn wordsFor(n: u32) -> u32 {
    return (n + 31) / 32;
}



/// Check if two bitsets are equal.
export fn eq(a: *Bitset, b: *Bitset) -> bool {
    let numWordsA = a.bits.len;
    let numWordsB = b.bits.len;
    let maxWords = max(numWordsA, numWordsB);
    let minWords = min(numWordsA, numWordsB);

    for i in 0..maxWords {
        let wordA = a.bits[i] if i < numWordsA else 0;
        let wordB = b.bits[i] if i < numWordsB else 0;
        if wordA <> wordB {
    for i in 0..minWords {
        if a.bits[i] <> b.bits[i] {
            return false;
        }
    }
    for i in minWords..numWordsA {
        if a.bits[i] <> 0 {
            return false;
        }
    }
    for i in minWords..numWordsB {
        if b.bits[i] <> 0 {
            return false;
        }
    }
    return true;
}

136	128
137	129		/// Check if two bitsets are equal.
138	130		export fn eq(a: Bitset, b: Bitset) -> bool {
139	131		let numWordsA = a.bits.len;
140	132		let numWordsB = b.bits.len;
141		-	let maxWords = max(numWordsA, numWordsB);
	133	+	let minWords = min(numWordsA, numWordsB);
142	134
143		-	for i in 0..maxWords {
144		-	let wordA = a.bits[i] if i < numWordsA else 0;
145		-	let wordB = b.bits[i] if i < numWordsB else 0;
146		-	if wordA <> wordB {
	135	+	for i in 0..minWords {
	136	+	if a.bits[i] <> b.bits[i] {
	137	+	return false;
	138	+	}
	139	+	}
	140	+	for i in minWords..numWordsA {
	141	+	if a.bits[i] <> 0 {
	142	+	return false;
	143	+	}
	144	+	}
	145	+	for i in minWords..numWordsB {
	146	+	if b.bits[i] <> 0 {
147	147		return false;
148	148		}
149	149		}
150	150		return true;
151	151		}

12	12		return a;
13	13		}
14	14		return b;
15	15		}
16	16
17		-	/// Return the maximum of two 32-bit values.
18		-	fn max(a: u32, b: u32) -> u32 {
19		-	if a > b {
20		-	return a;
21		-	}
22		-	return b;
23		-	}
24		-
25	17		/// Calculate the number of 32-bit words needed to store `n` bits.
26	18		export fn wordsFor(n: u32) -> u32 {
27	19		return (n + 31) / 32;
28	20		}
29	21