Skip to content
master
Go to file
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
 
 
 
 
 
 
 
 
 
 

README

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)

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		66.3 GB/s	---		---		---
avx2		30.9 GB/s	31.6 GB/s	---		---
sse2		16.0 GB/s	15.6 GB/s	---		---
neon		---		---		3.81 GB/s	---
generic8	1.08 GB/s	297 MB/s	253 MB/s	49.0 MB/s
generic16	1.82 GB/s	1.36 GB/s	445 MB/s	67.1 MB/s
generic32	2.71 GB/s	2.21 GB/s	620 MB/s	105 MB/s
generic64	3.60 GB/s	1.89 GB/s	1.04 GB/s	82.9 MB/s

The following systems were used for benchmarks:

 * amd64, 386: Intel(R) Xeon(R) Gold 6138 CPU @ 2.00 GHz
 * arm64: ARM Cortex-A72 r0p3 (Raspberry Pi 4B)
 * arm: ARM Cortex-A7 r0p5 (Raspberry Pi 2B+)

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

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

About

Positional Population Count for Go

Resources

License

Packages

No packages published
You can’t perform that action at this time.