ARM64 popcnt (and hamdist)

[David Sparks]

Highly optimized x86 AVX25/512 and ARM64 NEON popcnt loops can be found
in the RoaringBitmaps project.  Last month, I had an exchange with the
author (Daniel Lemire of blog fame) about tweaking it, and one thing
which came up was the odd slowness of UADALP.  See comment at the end of
https://github.com/RoaringBitmap/roaring/pull/549
where he found it slower than the current pair of UADDW and UADDW2.
(other, less important, tweaks in pull/548).

The actual code is in
https://github.com/RoaringBitmap/roaring/blob/master/popcnt_neon_arm64.s
When reading it, you have to cope with the peculiar syntax of
the Go assembler, which uses src1, src1, dst operand order.

The correponding hamdist code is called _popcntXorSliceNEON.


One thing that could almost certainly be improved in the current
GMP ARM64 code, which is a straightforward port of the ARM32 code,
is the final summation of the sums in v4.8h and v5.8h:

	add	v4.8h, v4.8h, v5.8h
					C we have 8 16-bit counts
L(e0):	uaddlp	v4.4s,  v4.8h		C we have 4 32-bit counts
	uaddlp	v4.2d,  v4.4s		C we have 2 64-bit counts
	mov	x0, v4.d[0]
	mov	x1, v4.d[1]
	add	x0, x0, x1
	ret

I'd think
	add	v4.8h, v4.8h, v5.8h	C reduce to 8 16-bit counts
L(e0):	uaddlv	s4, v4.8h		C reduce to one 32-bit sum
	fmov	x0, s4
	ret

would be shorter and sweeter.  (The V-suffix reduction instructions
are new for ARM64, and have no ARM43 equivalents.)

Using "fmov" rather than "umov" is suggested by
https://github.com/hyf6661669/ARM_documents/blob/main/Apple Silicon CPU Optimization Guide%2C 3.0.pdf?raw=true#page=70


Another, more fundamental, tweak is that ARM64 LD1 can load 4*128
bits in one instruction, twice the 4*64-bit limit of ARM32.  This
would completely change the inner loop.

The inner loop could probably be simplified, as ARM64 cores are OOO,
so software pipelining doesn't have to be nearly as aggressive.


If you're interested in AVX code, I contributed a clever way to
do the equivalent of NEON's cnt instruction using vpshufb to
do a 4-bit popcount, and vpsadbw to sum them.
#define COUNTBLOCK \
	VPAND Ymask, Ydata, Ylo \
	VPSRLW $4, Ydata, Yhi \
	VPAND Ymask, Yhi, Yhi \
	VPSHUFB Ylo, Ylut1, Yc1 \
	VPSHUFB Yhi, Ylut2, Yc2 \
	VPSADBW Yc1, Yc2, Yc1
see
https://github.com/RoaringBitmap/roaring/pull/546

(Lemire came up with using vpsadbw for the reduction; I contributed
using it with a negated Ylut2 to sum Ylo & Yhi at the same time.)

I recognize this is a *much* lower priority code path for GMP than
for RoaringBitmaps.