posts/project-panama-and-population-count

[utterances-bot]

Project Panama and Population Count | Richard Startin’s Blog

Project Panama introduces a new interface Vector, where the specialisation for long looks like a promising substrate for an explicitly vectorised bit set. Bit sets are useful for representing composable predicates over data sets. One obvious omission on this interface, required for an adequate implementation of a bit set, is a bit count, otherwise known as population count. Perhaps this is because the vector API aims to generalise across primitive types, whereas population count is only meaningful for integral types. Even so, if Vector can be interpreted as a wider integer, then it would be consistent to add this to the interface. If the method existed, what possible implementation could it have?

https://richardstartin.github.io/posts/project-panama-and-population-count

[zhuker]

    private static final ByteVector lookup256 = ByteVector.fromArray(ByteVector.SPECIES_256, new byte[]{
            0, 1, 1, 2, 1, 2, 2, 3,
            1, 2, 2, 3, 2, 3, 3, 4,
            0, 1, 1, 2, 1, 2, 2, 3,
            1, 2, 2, 3, 2, 3, 3, 4
    }, 0);

    static int bitCount256(ByteVector v) {
        var low_mask = ByteVector.broadcast(ByteVector.SPECIES_256, 0x0f);
        var lo = v.and(low_mask);
        var hi = v.lanewise(LSHR, 4).and(low_mask);
        var popcnt1 = lookup256.rearrange(lo.toShuffle());
        var popcnt2 = lookup256.rearrange(hi.toShuffle());
        var total = popcnt1.add(popcnt2);
        var shortVector = total.castShape(ShortVector.SPECIES_256, 0);
        var shortVector1 = total.castShape(ShortVector.SPECIES_256, 1);
        return (int) (shortVector.reduceLanesToLong(ADD) + shortVector1.reduceLanesToLong(ADD));
    }

[zhuker]

full test case here
https://gist.github.com/zhuker/22e53cc939da2b7eb18ac4a0c2ea64e2