Introduction

When you’re building a game engine, it’s practically guaranteed you’ll need a dedicated linear algebra library at some point. Physics calculations, camera movement, enemy AI - all those features rely on these core mathematical operations. If you’re coding in C++, Rust, or Python, you have plenty of well-known libraries to choose from, like Intel’s MKL, PyTorch, Boost, or more specialized solutions such as the Terathon Math Library. But if you’re working in Ada, the landscape for a custom math library is still fresh ground. That’s why, as part of my AdaDoom3 project, I created Neo.SIMD - a new library I hope will help fill that gap.

Wait, so what exactly is SIMD?

SIMD or “Single Instruction Multiple Data” instructions are a way for processors to perform a single operation on multiple values at once. Given the nature of linear algebra these instructions become all-the-more important when matrices and vectors start getting thrown around since performing operations on them tend to involve highly parallel data and algorithms.

Utilizing these special instructions can dramatically reduce the number of required cycles for such use cases, and, while compilers will automatically generate some SIMD instructions behind the scenes when optimizations are enabled, we want to push things a step further.

The goals of Neo.SIMD

The goals of the library are simple:

• Identify key linear algebra functions to implement that can take advantage of hand-written assembly and are relevant to general-purpose calculations and graphics programming.

• Take advantage of Ada’s ability to interface directly with assembly to write simple, modular, inline assembly functions.

• Leverage any known open-source implementations so that we can be sure that we are working with the latest algorithms.

• Support x86-64 (AVX, SSE, etc) as well as ARM (NEON)

Identifying key functions

I began by studying the code for Eric Lengyel’s wonderful Terathon Math Library. Eric is a mathematician with a long history in the games industry and has written several books on subjects such as game physics and game mathematics, so the Terathon Math Library should provide a perfect insight into which functions should be implemented for my purposes.

Using this library as a model, the needed functionality can be boiled down into several categories:

• Minimum/Maximum or “clamping” of vectors

• Arithmetic (addition, subtraction, division, etc) of vectors

• Rounding

• Trigonometry (cos, sin, tan, etc.)

• Transformation via a “Transform matrix”

• Cross products of vectors

• Determinant calculations for matrices

• Multiplication of matrices

Implementation

Generally, most implementations of SIMD math libraries use what are called “intrinsics” which are loosely wrapped assembly instructions that can be easily integrated with high-level code. However, I decided against this method for a couple of reasons - namely, that I would have to import these intrinsic functions for their use in Ada, but also for what I perceive as improved readability, tunability, and understandably.

So, without further ado, let’s dive in and look at a couple of examples that illustrate the difference between the two approaches.

Below is a set of functions (minus some smallish boilerplate ones) from Terathon that accomplish 4D matrix multiplication. Although on the surface this looks like high-level C++ there are, in fact, intrinsic assembly calls present (see the functions starting with “_mm”). In many ways, this can be seen as more readable since it integrates directly with C++ and has a friendly appearance. However, there is a cost - most notably, a lack of fine-grain control over individual registers and ordering of individual instructions.

Here is the implementation for 4D matrix multiplication in Neo.SIMD. Although it may appear longer or more cumbersome, it achieves a certain simplicity. First, this function has no dependencies - it is fully self-contained (all it requires in the definition of Matrix_4D). It also allows very fine control over the order of instructions and registers - which I view as the primary purpose of writing assembly over high-level solutions in the first place. For example, using prefetch operations and organizing instructions to facilitate pipelining can help save those precious cycles.

Finally, assembly blocks satisfy the WYSIWYG criterion - "what you see is what you get" - while the use of intrinsics can result in wildly different object code based on optimization flags and compilers. Although it is impossible to say for sure, in all of the compiler configurations I tested, the resulting assembly from the Terathon implementation of this function ended up being 30%-60% longer in terms of instruction count.

Benchmarks

Now, for the fun part - let’s check out some unscientific benchmarks! I created three test datasets for comparing various functions within the math libraries which generally have the most amount of associated instructions. The test data set consists of 500k operations and are generated from a Python script and output into a CSV table to ensure the same operations get performed for each implementation's test, and all of them were run on my (now aging) Alienware 13 R3 w/ Intel i7 with 32 GB of RAM in sequence. To give some extra perspective, I added two other implementations: a “naive” Ada approach, which uses normal operations and no SIMD, and PyTorch - although I did not include PyTorch in the graphs since it skewed the scales too much for obvious reasons as you'll see.

Build settings

For Neo.SIMD/Ada Naive: -O3 -march=native -ffast-math
For Terathon: -O3 -march=native -ffast-math

Matrix 4D Multiplication

Matrix 3D Multiplication

Matrix 4D Determinant

Analysis of results

Although this is nowhere near a comprehensive test of the different implementations since we are only looking at a small subset of libraries and functions, there are several things that stand out based on the results - namely that the naive approach (without special assembly instructions) still performs fantastically on many tasks. Of course, this will vary from compiler to compiler and based on compilation options, but none-the-less it demonstrates the power of modern compilers and tools such as GNAT.

The second thing of note is that the approach taken by Neo.SIMD is viable - it does indeed outperform its reference library with a 25% speed up in at least one of the core functions above.

Conclusion - what's next?

Hand-written assembly has certainly fallen out of favor in the current age, after all - it is not easy to beat the compiler! However, considering the immense amount of calculations necessary for maintaining 3D environments or performing AI transformations, I don’t think fine-tuned SIMD assembly is going away anytime soon.

As far as next steps, I plan to continue benchmarking the rest of the functions, expanding the library, and, perhaps, use it to move forward with developing some physics for AdaDoom3 🙂

To view the current state of the project you can view it at my github here: https://github.com/AdaDoom3/Ne...