Boundary function is too slow

[tabcat]

prollipop/src/boundary.ts

Lines 31 to 43 in 9e3c385

	export const createIsBoundary: CreateIsBoundary = (
	average: number,
	level: number,
	): IsBoundary => {
	const limit = Number(MAX_UINT32 / BigInt(average));
	return ({ seq, key }: Tuple) => {
	const digest = sha256(encode([level, seq, key]));
	return (
	new DataView(digest.buffer, digest.byteOffset, 4).getUint32(0) < limit
	);
	};
	};

The boundary function currently encodes each entry [level, seq, key] into CBOR to be hashed by sha256. The boundary function is called on any entry that is encoded or decoded so it's called constantly.

I'm going to try just converting the level and seq to bytes and then concatenating with the entry key, then hashing with sha256. Another option that might work is not using a hash function at all since the boundary test doesn't need to be secure.

[tabcat]

Using the sha256 hash without cbor encoding first is ~2x faster. May be worth looking at non-cryptographic hash functions. I don't see a problem with using one of these for boundary calculation.

[tabcat]

Using xxhash-wasm a boundary check speedup of ~8x can be achieved but cost adding a large (11.4kb) dependency. At this point the 2x speedup is preferable.

Also need to look at how to quickly convert seq > 2^32-1 to bytes quickly. Currently converting the seq to a 32bit uint, but it can be up to 64bit.