Re: hash + LRC better than CRC?

On Sun, Aug 31, 2025 at 08:43:20PM +0700, John Naylor wrote:
> 1) It's trivial to reduce a 64-bit universal hash to a 32 (or
> whatever)-bit universal hash by composing it with another universal
> hash function -- a convenient example is Dietzfelbinger's
> multiplicative hash (see section 2.3 in [1]), which is just a multiply
> and a shift.
>
> 2) An XOR-based longitudinal redundancy check (LRC) [2] also detects
> errors of any odd number of bitflips, and is cheap enough to compute
> along with the hashing loop such that it's likely free on superscalar
> CPUs.
>
> For WAL we could use e.g. a 31-bit hash plus an LRC reduced to a
> single parity bit, or keep 32 bits of hash and steal a WAL header
> padding byte to store a 1-byte LRC (which would additionally detect
> most 2-bit errors and some burst errors (see section 3.1 in [3]) if we
> wanted to keep some weaker CRC-type guarantees).
>
> 128-bit arithmetic has easier portability than CRC instructions (if we
> avoid designs that require carryless multiplication),

Hmm. Okay. If this is more efficient and more reliable, why not.
There's no free cake in this area so my understanding is that it is
usually a trade-off between efficiency and reliability, and that we
cannot have both of them. Of course, this counts for the case of more
efficiency with the same reliability across two different methods, and
vice-versa the efficiency/reliability part.

> and it'd be nice
> to get consistent performance across platforms, possibly with better
> error detection for sector-sized errors. Assuming a suitable function
> (and licence) can be found.

With the amount of platforms that Postgres needs to support, this
feels like potentially like a lot of work in terms of benchmarking.
I am wondering about some actual numbers, in terms of
micro-benchmarking the computations, of course. If this provides for
example a very high performance improvement on Linux and the most
popular BSDs (say as a matter of 2x or 3x), that may be worth
considering to me anyway, even if for example WIN32 shows no
performance difference for reasons I am not aware of, which would
likely come down to the instructions we have through the MSVC
compilers.

Saying that, the argument of reducing 64-bit hash to 32-bit sounds
kind of appealing, still I would worry about the cost of the extra
computation.
--
Michael