High-performance vectorised positional popcount routines for Go

This repository contains implementations of the positional population count functions for Go. Details on the algorithms used will be published in a future research paper.

To use this library, import it as follows:

import "github.com/clausecker/pospop"

You can then count populations using the Count8, Count16, Count32, and Count64 functions:

var counts [8]int
pospop.Count8(&counts, buf)

The positional population count for buf is added to the contents of counts.

Supported Platforms

The kernels works on a block size of 240 or 480 bytes (depending on whether AVX2 is available or not). A buffer size that is a multiple of 480 bytes and at least 10 kB in size is recommended.

Implementations are provided for the following SIMD extensions:

• AVX-512 F/BW (amd64)
• AVX2 (amd64, 386)
• SSE2 (amd64, 386)
• NEON (arm64)
• generic kernel (all architectures)

The three kernels for amd64 correspond to the v4, v3, and v1 values of the upcoming GOAMD64 environment variable.

Due to some required improvements in the assembler, the NEON kernel will only be available on Go 1.16 or newer. When building with earlier versions of the tool chain, only the generic kernel is available.

The library automatically chooses the fastest available kernel for the system it is running on.

Performance

As all functions (Count8, Count16, Count32, Count64) of one set are based on the same kernel with a different accumulation function, they all perform equally well. This does not apply to the generic implementations whose performance is therefore given for every function individually.

The following performance table is grouped by the instruction set used and the architecture it runs on. A buffer size of 100 kB was used to find these results.

	amd64		386		arm64		arm

avx512 82.1 GB/s --- --- --- avx2 34.8 GB/s 31.6 GB/s --- --- sse2 16.0 GB/s 15.6 GB/s --- --- neon --- --- 36.9 GB/s --- generic8 1.02 GB/s 297 MB/s 1.68 GB/s 49.0 MB/s generic16 1.71 GB/s 1.36 GB/s 3.03 GB/s 67.1 MB/s generic32 2.66 GB/s 2.21 GB/s 3.83 GB/s 105 MB/s generic64 3.43 GB/s 1.89 GB/s 6.56 GB/s 82.9 MB/s

The following systems were used for benchmarks, all using Go 1.16:

• amd64, 386: Intel(R) Xeon(R) Gold 6138 CPU @ 2.00GHz
• arm64: Apple M1
• arm: ARM Cortex-A72 r0p3 (Raspberry Pi 4B)

Remaining Work

• provide assembly kernels for arm, ppcle, and others (hardware donations appreciated for further targets)
• provide variants of Count16, Count32, and Count64 working on byte arrays

(c) 2020--2022 Robert Clausecker [email protected]. All Rights Reserved.

This code is published under a 2-clause BSD license. See the file COPYING for details.