Solving quadratic equations on ARM NEON.

So two years ago, I've been coding a function that solves quadratic equations, 8 at a time using AVX. Lately, I have been looking into ARM NEON to see what performance can be had on mobile devices. This is what I came up with. The square root implementation is available pmeerw.

/*
 * solve aX^2 + bX + c = 0
 * solves 4 instances at the same time, using NEON SIMD without any branching to avoid stalls.
 * returns two solutions per equation in root0 and root1.
 * returns FLT_UNDF if there is no solution due to discriminant being negative.
 * For sqrtv() see: https://pmeerw.net/blog/programming/neon1.html
 * I've put the reciprocal of (2*a) in the argument list as this one is fixed in my particular problem.
 */

inline void evaluate_quadratic4
(
        float32x4_t a,
        float32x4_t twoa_recip,
        float32x4_t b,
        float32x4_t c,
        float32x4_t* __restrict root0,
        float32x4_t* __restrict root1
)
{
        const float32x4_t four4 = vdupq_n_f32( 4.0f );
        const float32x4_t undf4 = vdupq_n_f32( FLT_UNDF );
        const float32x4_t minb = vnegq_f32( b );                        // -b
        const float32x4_t bb = vmulq_f32( b, b );                       // b*b
        const float32x4_t foura = vmulq_f32( four4, a );                // 4*a
        const float32x4_t fourac = vmulq_f32( foura, c );               // 4*a*c
        const float32x4_t det = vsubq_f32( bb, fourac );                // b*b - 4*a*c
        // We want only positive roots!
        const uint32x4_t  dvalid = vcleq_f32( fourac, bb );
        const float32x4_t sr = sqrtv( det );                            // approximation of sqrt( b*b - 4*a*c )
        float32x4_t r0 = vaddq_f32( minb, sr );                         // -b + sqrt( b*b - 4*a*c )
        float32x4_t r1 = vsubq_f32( minb, sr );                         // -b - sqrt( b*b - 4*a*c )
        r0 = vmulq_f32( r0, twoa_recip );                               // ( -b + sqrt( b*b - 4*a*c ) ) / (2*a)
        r1 = vmulq_f32( r1, twoa_recip );                               // ( -b - sqrt( b*b - 4*a*c ) ) / (2*a)
        // Filter out negative roots.
        *root0 = vbslq_f32( dvalid, r0, undf4 );
        *root1 = vbslq_f32( dvalid, r1, undf4 );
}

I benched this code on Android Galaxy Note4, against a scalar version. The speed-up I measured was 3.7X which I think is pretty good.

So, yeah, writing intrinsics is totally justified. Doubly so, because I tried to have the compiler auto vectorize, but whatever flag I tried, results hardly differed: -fno-vectorize, -ftree-vectorize and -fslp-vectorize-aggressive all showed the same performance.

ARM SIMD

My Pyramid Building Simulator is coming along nicely. Check out the game play video I made for it.

So my Core i5-4570 and nVidia GTX 750Ti run this simulation at an easy 100fps at 1920x1200 pixels. It always leaves me wondering, could it possibly ever be done on mobile, 64 bit iOS or 64 bit Android? If it's possible, it will require some aggressive optimization, as the current code is already AVX SIMD.

But it's an itch I have to scratch: can I do the same on 64 bit ARM NEON? So let's dive into that world: I've never done assembly, intrinsics or SIMD on ARM before, so it's all new to me. I've found a developer that went an interesting route: translate x86 SSE2 to ARM Neon using a translation layer. But I think it pays more to apply ARM Neon intrinsics directly.

So what have I been able to find out so far?

• This ARM intrinsic reference is a great resource.
• An old blog post at hilbert-space.de warns against intrinsics being much slower than hand written assembly. I believe this is currently no longer true, as compilers have matured, and this was mainly an issue with older gcc compilers.
• ARM does have the notion of 16 bit floats, but unfortunately, it seems to be a storage format only, and not suitable for calculations. This is a pity, as it seems to rule out 8-way floating point SIMD on ARM. I may be mistaken, but it looks like you can't do better than 4-way floating point SIMD on ARM, which is a far cry from the x86 world where 8xSIMD (AVX/AVX2) and 16xSIMD (AVX-512) is possible.
• NEON Intrinsics look like vXXXq_FMT where v signifies the vector nature, q means 128 bits, and FMT specifies integer/float and width. So for instance: vmulq_f32() that multiplies 128 bit vectors containing 32 bit floats, so this would be 4xSIMD.
• For conditional moving of values (which in x86 parlance is vblendps or fsel in PowerPC speak) you would use Bitwise Select, vbslq, in the ARM Neon world. In NEON, this intrinsic is actually much more natural than the x86 counterpart, as it has a more logical operand ordering. It follows the same ordering as the ?: operator in C: vbslq( condition, iftrue, iffalse ).
• Writing NEON intrinsics is actually quite enjoyable compared to the x86 world, where MMX, SSE, SSE2, SSE3, SSE4, AVX, AVX2, AVX-512 transitions left the set of intrinsics quite convoluted. The naming scheme in ARM NEON is much cleaner, and requires less use of references as it contains little surprises in naming. The comparison intrinsics are also easier, as there is no third operand as is the case in x86. The type of condition is specified in the name of the intrinsic instead.
• Ugh, NEON doesn't have square root, or reciprocals. Only an estimate for reciprocal, and an estimate for reciprocal of square root. It looks like pmeerw has a solution to this.

I will update this posting as I learn more about ARM SIMD.

Hieroglyphic User Interface.

So, I have embarked on a new game project: A pyramid building simulator. And I decided to go hard-core on authenticity and do all of the UI in hieroglyphics. I've familiarized my self with the script, and the Gardiner classification.

And in Inkscape, I've created a set of words from Ancient Egypt, with the help of this tool among others. Here are the words for: Baker, builder, field, fieldworker, food, grain, granary, house, householdservant, irrigationworker, pyramid, sandstone, water, which are all elements in my new game, and will require UI.

As can be seen from the orientation of the birds and the men, these are reading-right-to-left variants. Stay tuned for some upcoming game play videos that will appear here. If you are press and would like advanced copies of the game, please do no hesitate to contact me.

Approximate functions.

For game development, I often use function from the math library, as there are: sinf(), cosf(), atan2f(), acosf(), logf() and such. And these functions tend to be quite expensive in CPU cycles. However, in game development, low precision math functions will often suffice. Which means we can skip computing a precise answer, and use other functions that approximate the output of the expensive functions.

I've found a few resources for code that approximates expensive math functions with much cheaper approximations. There is SIMD Math prims by jhjourdan e.g. that comes with approximations for expf(), logf(), cosf() and sinf(). As a bonus, these simpler functions are also easier to vectorize.

But my favourite approximation is that of atan2f(), because I use it so often to convert direction vectors to angles. Here are Volkan Salma's approximations for the atan2f() function.

Tile sets

My next game could well be a 2D tile based game. This is mainly, because I want to use my 2D grid based crowd simulation code. So here I will collect some inspiring art work I found with Google. Note: none of the images are mine, they are all copyrighted by their respective authors. I'm just scrap-booking here to see what art work is out there.

An interesting variant of tiles on a 2D grid, is the use of a height-map, so that there are still NxM tiles on a grid, but each tile has a height. The advantage of doing this over free 3D, is that the navigation on a heightmap is still a 2D affair.

Steam

The Little Crane That Could was released on Steam today!

Steaming Ahead - WEEK 09

Yay! The Little Crane That Could -- steam edition is finished! So today, I submitted my game for review, and if it gets through, it will be out on April 27.

I also made this launch trailer:

I'm excited for its release. I've worked very hard for 9 weeks after I got the Steam green-light. And now it is here! I will reward myself with some Scottish Whisky tonight.

At launch you will be able to grab your Win/Mac/Linux copies at 15% discount. And last, let me phrase why this game stands out, and is unique among its peers:

The terrain is the real hero in this game! With never seen before dig-anywhere technology™ you can shape the world. Any changes to the world will persist between levels and game sessions, and there are no restrictions: cliffs, overhangs, caves, tunnels: it is all possible.

The world size is near infinite: you can dig a hole, then drive for an hour in a random direction and backtrack by following your track impressions in the terrain. You will then find your dug hole as you left it: no short-cuts: real terrain simulation!

One disclaimer: I did not solve the problem of 'floating terrain' though... dig away all the dirt below and round an area, and the remaining dirt will float mid-air. I think it has limited effect on enjoyment and playability though, and as it is far from trivial to fix, I will leave it at this."