Re: cdbw optimisation in libc

[Alexander Nasonov <alnsn%yandex.ru@localhost>]

Alexander Nasonov wrote:
> The patch of the new implementation is attached. It's faster than
> the original algorithm but for some reason I only get about 20%
> speedup on a Haswell notebook and 10% more by using fast_remainder32(3).

If the algorithm starts with a good seed, the speedup is about 50%.

A significant amount of time can be spent trying to find a good
hypergraph, that is, a hypergraph without identical vertices in
all edges. IIRC, a probability of generating an edge with identical
vertices is around 0.8-0.9.

Alex