strxfrm output stability

[Zack Weinberg]

On 09/09/2015 03:05 PM, Paul Eggert wrote:
> When I tried a decade ago to use strxfrm in GNU sort to speed it up, I
> ran into two problems.  First, glibc strxfrm generates lengthy output,
> and since I wanted only the first 8 bytes or so I got relatively little
> information out of the prefix and overall it was a performance loss on
> my benchmarks.

That's interesting, because as *I* understand it, that is exactly what
PostgreSQL is doing, with a fallback to strcoll when the 8-byte prefix
collides (and a further fallback to memcmp() when strcoll reports
equality, because they apparently got burnt a time or two by some C
libraries reporting strings as strcoll-identical when they aren't
byte-identical).

I happen to have a pile of strings in a small handful of languages lying
around, and indeed there are a lot of collisions in the first 8 bytes of
strxfrm() output.  It's possible that for large databases this is a win
anyway due to reduced memory access costs (there's some discussion on
that blog post of how it's not so much saving calls to strcoll as saving
pointer dereferences).

> As I understand it the new PostgreSQL code works around
> this problem by doing a collation-preserving compression of the strxfrm
> output.

I didn't see anything about that in the articles I mentioned?

> It would be better, I expect, if GNU libc strxfrm did that
> compression itself rather than require every caller who cares about
> efficiency to do it.

Yeah.  I looked briefly at strxfrm_l.c and was not able to grasp the
algorithm or the encoding, but the output strings sure do look like they
have poor information density.

> The second problem was more of an irritation: I wanted the first (say) 8
> bytes of strxfrm output, but there's no standard way of getting them
> without generating all the strxfrm output bytes and then discarding the
> unwanted trailing bytes, which is slow.

Also an issue for PostgreSQL as I understand it.

It seems like there are two distinct use cases here: 1) grab a short,
fixed-length tag (effectively a collation-preserving hash); collisions
are OK, caller promises to fall back to strcoll()  (PostgreSQL, sort(1).
 2) smuggle a locale-aware comparison into an API that only allows you
to provide a key, not a comparator (Python 3).  Maybe it's time to
invent a new API?

zw