adler32-go

Accelerating Adler32 Checksum with Arm NEON Instructions

This project demonstrates how to significantly improve the performance of Adler32 checksum calculations using Arm NEON SIMD (Single Instruction, Multiple Data) instructions. The implementation shows how to integrate optimized C code with Go applications to achieve substantial performance gains over the standard library implementation.

What is Adler32?

Adler32 is a checksum algorithm that was invented by Mark Adler in 1995. It's used in the zlib compression library and is faster than CRC32 but provides less reliable error detection. The algorithm works by calculating two 16-bit sums:

1. s1: A simple sum of all bytes
2. s2: A sum of all s1 values after each byte

The final checksum is (s2 << 16) | s1.

Project Overview

This project includes:

1. A standard Go implementation using the hash/adler32 package
2. A NEON-optimized C implementation that processes multiple bytes in parallel
3. CGO bindings to call the optimized C code from Go
4. Benchmarking code to compare performance between implementations

Implementation Details

Standard Go Implementation

The Go standard library provides an Adler32 implementation in the hash/adler32 package. This serves as our baseline for performance comparison.

NEON-Optimized Implementation

The NEON implementation leverages Arm's SIMD instructions to process 16 bytes at a time, significantly improving throughput. Key optimizations include:

• Processing data in 16-byte chunks using NEON vector instructions
• Handling blocks of 5552 bytes to avoid overflow (as per the Adler32 algorithm requirements)
• Carefully managing the position-dependent nature of the s2 calculation
• Falling back to scalar code for any remaining bytes

Integration with Go

The project uses CGO to call the optimized C code from Go:

// calculateNeonAdler32 calculates Adler32 using the C NEON implementation
func calculateNeonAdler32(data []byte) uint32 {
    cData := (*C.uint8_t)(unsafe.Pointer(&data[0]))
    cLen := C.size_t(len(data))
    return uint32(C.adler32_neon(cData, cLen))
}

Performance Results

Neoverse N1 Performance Results

The following performance results were measured on a system with a Neoverse N1 processor:

Implementation Comparison

The project includes three different implementations of Adler32:

1. Simple: A basic scalar implementation
2. Block: An optimized scalar implementation that processes data in blocks to avoid overflow
3. NEON: A SIMD-optimized implementation using Arm NEON instructions

Here are the performance results for each implementation:

Compiler Comparison for NEON Implementation

The NEON implementation was compiled with both GCC and Clang to compare performance:

Note: Actual performance numbers may vary based on your specific ARM hardware. These results were measured on the Neoverse N1 test system.

Neoverse V2 Performance Results (April 2025)

We also tested the implementations on a Neoverse V2 processor, which showed different performance characteristics:

Simple Implementation (Scalar)

Block Implementation (Optimized Scalar)

NEON Implementation (Clang vs GCC)

Key observations:

• For small data sizes (1 KB), all C implementations are slower than Go due to function call overhead
• The NEON implementation is significantly faster than both scalar implementations for data sizes ≥ 10 KB
• On the original test system, Clang consistently produces faster code than GCC for the NEON implementation, with up to 98% better performance
• On the Neoverse V2 system, GCC produces faster code than Clang for the NEON implementation, with approximately 30% better performance
• The Block implementation is slower than Go on the Neoverse V2 system, unlike the results on the original test system
• The optimized implementations show the greatest advantage at the 10 KB data size

Building and Running

Prerequisites

• Go 1.15 or later
• GCC or Clang compiler (Clang is used by default as it produces faster code)
• Arm processor with NEON support

Build Instructions

1. Clone the repository
2. Build the shared library:

   make compile
   

3. Run the benchmark:

   make run
   

Makefile Targets

The project includes a flexible Makefile that allows you to easily switch between different implementations:

• make compile - Builds the library using the default implementation (adler32_neon.c)
• make run - Runs the benchmark using the compiled library
• make all - Combines compile and run targets

You can specify which implementation to use:

• make simple - Builds using the simple scalar implementation (adler32_simple.c)
• make block - Builds using the block-based implementation (adler32_block.c)
• make neon - Builds using the NEON-optimized implementation (adler32_neon.c)

You can also specify the implementation directly:

make IMPL=adler32_simple.c compile

To build and run with a specific implementation in one command:

make IMPL=adler32_block.c all

or

make simple run

How It Works

The NEON implementation works by:

1. Processing 16 bytes at a time using NEON vector registers
2. Calculating s1 and s2 in parallel for these 16 bytes
3. Handling the position-dependent nature of s2 calculation with vector multiplications
4. Processing data in blocks of 5552 bytes to prevent overflow
5. Combining the results and applying the modulo operation

Conclusion

This project demonstrates how leveraging Arm NEON instructions can significantly improve the performance of checksum calculations. The techniques shown here can be applied to other algorithms that process data sequentially and can benefit from SIMD parallelism.

By using hardware-specific optimizations while maintaining a clean Go API, we can achieve the best of both worlds: the development experience of Go with the performance of optimized C code.

License

This project is released into the public domain under the Unlicense.

This means you can copy, modify, publish, use, compile, sell, or distribute this software, either in source code form or as a compiled binary, for any purpose, commercial or non-commercial, and by any means, without any attribution or restrictions.