High-performance vectorised positional popcount routines for Go
===============================================================

This repository contains implementations of the positional population
count functions for Go using an algorithm described in our publication

    Clausecker, Lemire, Schintke: Faster Positional‐Population Counts
    for AVX2, AVX‐512, and ASIMD, Concurrency and Computation: Practice
    and Experience, vo. 37, no. 27--28, Wiley, 2025.

Our publication is open access and can be found on line at

    http://dx.doi.org/10.1002/cpe.70435

To use this library, import it as follows:

    import "github.com/clausecker/pospop"

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

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

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

A C version of this library is provided in the src.c subdirectory.
Refer to the README file in there for details.

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 GOAMD64 environment variable.  However, all kernels are
compiled in regardless of what value GOAMD64 is set to.

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

Performance
-----------

As all functions (Count8, Count16, Count32, Count64, CountString) 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)

Citation
--------

If you use this code in a scientific publication, please cite:

    @article{clausecker2025pospop,
     title={Faster Positional-Population Counts for AVX2, AVX-512, and ASIMD},
     author={Robert Clausecker and Daniel Lemire and Florian Schintke},
     journal={Concurrency and Computation: Practice and Experience},
     volume={37},
     number={27--28},
     year={2025},
     publisher={Wiley Online Library}
    }

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--2024 Robert Clausecker <fuz@fuz.su>.  All Rights Reserved.

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