The Properties of Space

This is a rather personal intro on how I stumbled into writing a SIMD module – and I guess the daily life as a software engineer in general. There will be another article solely on the details of SIMD and the current state of SIMDX. If you are interested, I would be more than happy if you check back with this article soon (or with my profile page on Medium or Twitter). It is already in the making and I will add a link once it is available. Arm yourself for the exciting struggles that lie ahead. You will be amused.

Since the public launch of Swift in 2014, I have been programming in Swift Language almost exclusively. Both at work and in personal projects. This led to an excessive amount of Swift source code that ended up in iOS, watchOS, tvOS and macOS applications. Yet also in a lot of source code targeting Server-Side services [^1]. All of these services have been deployed to Linux machines, either natively/virtualised or as Docker containers.

Swift has been a major game changer when it comes to cross-platform compatibility and Server-Side development, comparing it to its predecessor Objective-C. An official Swift Server Work Group promotes the use of Swift for developing and deploying server application. They channel feedback for Swift language features needed by the server development community to the Swift Core Team [^2]. Additionally, having most of its standard library already ported, the Swift Language itself has excellent Linux support.

With all these developments in the language and for the first time ever did I start carrying about cross-platform compatible code and Server-Side applications.

However, Swift is a new and evolving language. The number of existing libraries is rather low. And with every major change to the language, existing libraries need to be updated. So even tough the community is growing and Swift is being more widely adopted, the issue is noticeable. Especially when you start writing cross-platform code, as the issue is mostly a problem to none apple platform targets.

Since launch, Swift allows for interoperability between C and Swift [^3] and additionally Objective-C and Swift on Apple platform. And Apple has a whole lot of libraries|frameworks that are written in (Objective-)C. These have been available on all Apple platforms since then. Effectively eliminating the problem of missing libraries on these targets in the first place.

Why are we talking about this? Is this a rant on Apple?

No, not at all. These frameworks have not been designed for the Swift ecosystem nor have they been developed with Linux in mind. And the rapid evolution of the Swift Language in the past years has made it a lot more elegant and safe in faster iterations than it would have been possible with version compatibility in mind. However it may explain why I was doing what I was doing that I am going to explain now.

So a few years ago I got involved in developing one of the earlier Linux targeting Swift service (to me anyway) and eventually came to a point where I needed to crop, rescale and (de-)saturate images on the Server-Side using Swift. Naturally, I started looking into more mature and battle-tested libraries like ImageMagick and GD and in the end settled with GD as I felt ImageMagick was to much for such simple tasks. Secondly, Paul Hudson had just open-sourced a Swift Library for GD named SwiftGD. It is a Swift Shim above the C functions of GD. This allowed me to not touch C at all and to just write Swift code within that service.

With all the necessary dependencies at hand I started writing an endpoint that would allow clients to send image data or URL along with cropping, scaling or (de-)saturation parameters and in return sends given image manipulated as instructed by these parameters, and – it worked!

I even added a few features to SwiftGD in the process of writing the endpoint. These where later merged into the upstream, making these commits my first ever contribution to someone else’s open source project.

The History of an Idea

Now that the task is done we can move on to the next one, right? Wrong! Well kind of. There are always things to do better and to improve on and while I had to finish the task for the sake of finishing the feature as requested (and not as I thought would be the ultimate solution), I just could not ignore the fact that SwiftGD comes with geometric primitives like Point, Size and Rectangle. And the service is using this primitives when accessing SwiftGD. But these primitives have been written exclusively for SwiftGD. Clients now need to redefine these primitives in order to send cropping or rescaling parameters to the service unless the depend on SwiftGD. So they would have to depend on an image manipulation framework in order to get access to the geometric primitives they need, in order to send cropping or rescaling instructions to a server that does image manipulation. This is not an option. And redefining the primitives on the Client-Side is everything but ideal. Let alone geometric primitives are not a specific feature of a client-server communication. Nor of image manipulation. Geometry may be of use in absolutely different demands like user interfaces, physics simulation, augmented reality, 2D/3D games and much much more. These applications would all have to reimplemented these components and find solutions to problems that may have already be solved by another application – so why not extract these and gather them nicely packed in a reusable 📦 Geometry module? As an Apple platform developer you may now be reminded at the Linux and Apple Framework part at the beginning of the post and why CoreGraphics and its containing CGPoint, CGSize and CGRect are, unfortunately, not a replacement option.

Additionally, SwiftGD defines a struct called Color that represents the red, green, blue and alpha channels of a single image pixel in the range of 0.0 - 1.0. And while this is perfect for SwiftGD, color in other situations may not always be defined by red, green, blue and alpha channels ranging from 0.0 - 1.0. Maybe the RGB color space of the sender differs from RGB color space of the receiver and the color needs to be converted. Maybe the color is not even defined in an RGB color space but in an entirely different color space like CMYK, HSL/HSV, YCbCr/YPbPr. The variations make Color a rather advanced topic in computer science and hard to get right. So why not extract it and make it a standalone 🎨 Color library that is well designed, heavily tested and can be used not only for the single purpose of SwiftGD but for at least most, if not all, applications that need color of some sorts?

Given the complexity of color over geometry, I decided to start with geometry and later build upon the knowledge of writing a geometry library and continue with a color library. So I ventured into the fields of geometry and after some research finalise what I considered a good first architectural layout. At this point the library merely contained two dimensional structs like

Point2 defined by (x: Float, y: Float)
Size2 defined by (width: Float, height: Float)
Rectangle defined by (point: Point2, size: Size2)

and their higher dimensional equivalents, as well as additive and multiplicative arithmetic operations.

But I was not happy with how things turned out. They all where defined by two or three values of the same type but merely any of those structs had anything in common. All of them defined their own set of arithmetic operations and they all had Float aka Float32 as base unit. What if someone needs Double precision aka Float64? So I was back at the drawing board and did some more research and eventually came to the conclusion that all of the geometric primitives, like Point2 and Size2, can be described by a 📐 Vector of certain length. Heck even Color could be described as a Vector of certain length! So I dialled back, scraped the idea of starting with a Geometry library first but rather started with a Vector library.

Don't laugh at me just yet.

The idea was simple. The implementation needs to follow the mathematical definition of an Euclidean vector for as long as possible – and the final definitions ended up quite simple.

A Vector has a magnitude and a direction.
A Vector may be modified using equations defined in Linear algebra – such as additive arithmetics for example.
The cardinality (the number of vector components) is defined by the Euclidean space of the Vector.

Let's move on to Swift. When writing a library it is always a good idea to first look into the standard library and other major frameworks for existing protocols and constructs that align with the library requirements and (re-)use them whenever applicable. It will be easier for other developers to adopt it quicker, knowing the language and some of its concept already. Eventually, I settled with the following definitions:

A Swift Vector is a fixed-length Collection of n-values, where n is a positive integer value.
Each value can be accessed independently of one another, leading to a RandomAccessCollection
Each value can be mutated, making it also a MutableCollection.
A Swift Vector is mostly, but not exclusively, represented by Numeric types. If it is described by a Numeric type it must reflect the purpose of this Numeric (e.g. Allow binary operations, like bit shifting, on a Vector that is described by values of BinaryInteger types)

I came up with more definitions. But ultimately, the 2 core principles of making it Collection based and extend upon Numeric value types shaped the library.

Now show me some code

Writing this library was so much fun. Really! – And I learned a lot, both in the Swift Language and also in Linear Algebra, making the library development an absolut joy.

But while digging deeper I eventually came across SIMD. I will explain SIMD in more detail in the next post (no link yet – read through the end. You are almost there), but for now: SIMD allows for fast CPU optimised vector and matrix operations. And I really did not want to miss out on the performance benefits of SIMD and the optimised vector operations that come with it, when writing an entire library around Vector. But I had no idea how to use SIMD instructions. I just learned it even exists! Yet it was at this Point in Time that a new Swift Evolution Proposal (229) arose and it was dealing with SIMD in Swift. What a lucky coincident, right? I looked through the proposal and learned of a C-module called simd that should be wrapped by a Swift Shim making interaction of SIMD code in Swift less tedious. I started adopting it as early as possible, making it the base of the Vector library. It was amazing. I wrote tests. I integrated Travis builds for macOS and Linux. I pushed those changes and boom... Travis failed on the Linux build. simd.h could not be found. It is an Apple platform only library that was released as part of a bigger Accelerate framework which dates back a few years before Swift was born and there is no drop-in replacement for Linux. I was devastated. How could I have missed that? I was so excited that I have not seen the Apple platform only limitation.

I struggled on the decision on how to advance further with the library. Should I revert the changes? Back to where it was before I learned SIMD exists? Or make it an Apple platform only library? But shouldn’t it be the go to library if you need Vector of some sorts on any Swift supporting platform? And wouldn’t it be cheap to miss out on performance improvements that are available on the target hardware just not in software? Swift is designed to be fast. So fast indeed it wants to be considered a replacement for C/C++. And the library should not strive for anything less. So I decided to venture a bit more into the fields of SIMD and most importantly, to find a C-library that could replace the Apple only simd module. I learned really quickly that SIMD really is a complicated topic and insanely bad documented on the Intel/AMD side of hardware and, while somewhat documented, completely different on Arm architecture. And to make things worse, every library I found to be a worthy replacement of simd was written in C++ which can not be used with Swift, rendering those libraries utterly useless to Vector.

I eventually came to a point where I was wrestling with the idea on porting one of the C++ libraries into plain old C and then use it with Swift – yet decided to not do so, as I merely know SIMD and my C skills are fairly dated. So I ditched the library and decided to wait for someone smarter to finish the work on SIMD, Vector and Geometry (and every other idea connected with it) and way back in when the time is right.

And while I really tried hard to settle with that decision, and to move on, I just could not forgot the fact that there is unfinished work and there is something called SIMD that I barely know but sounds so interesting. After all, not only does SIMD include optimised Vector operations but also 🧮 Matrix operations. These would come in handy when geometry gets extended with transformations, for example. Furthermore, since the dawn of the Vector library, a few things have not stopped itching my brain – and I felt could be improved on. Vectors are displacements in space and not locations, like Points. Points are displaceable by a Vector. But a Vector can not be displaced with another Vector but merely changed in length or direction. But right now, they are the same thing. Also the Equatable operation on Point must return true if two points are located at the same coordinates (x1 == x2 && y1 == y2), while comparing Size for example may yield true if the areas of both sizes are equal (x1 * y1 == x2 * y2). So the idea of everything is a Vector turned out to be not so good after all – at least considering the language I was designing the library for. But having an abstraction layer that is SIMD and that can do any operation at full speed and can be configured as needed, suits perfectly. So a few months later I decided to go deeper and ditch the Vector library for now and to make a platform independent SIMD module first. Going all in with a Swift target that exposes nice generic types but is essentially a wrapper of a C target. This C target wraps all the different vendor specific SIMD instructions and even provides a fallback for none-SIMD hardware. The include/exclude of certain header files is achieved using module maps. And everything must be inlineable by the compiler in order to maximise the performance gain. If the library development fails, I would at least have learned a whole lot more.

Now you can laugh. Moving on.

As mentioned in the beginning, there will be another article solely on the details of SIMD and the current state of SIMDX. If you are interested, I would be more than happy if you check back with this article soon (or with my profile page on Medium or Twitter). It is already in the making and I will add a link once it is available.

Legal

Apple, iOS, macOS, tvOS, watchOS and Swift are trademarks of Apple Inc., registered in the U.S. and other countries.

Arm and Neon are registered trademarks or trademarks of Arm Limited (or its subsidiaries) in the US and/or elsewhere.

Docker and the Docker logo are trademarks or registered trademarks of Docker, Inc. in the United States and/or other countries. Docker, Inc. and other parties may also have trademark rights in other terms used herein.