Good afternoon, and welcome to Using Vectorization Techniques to Maximize Performance. I’m Jeff Kidder, a mathematician in the vector and numerics team. In about five minutes, I’ll be introducing my colleague, Eric Postpischil. Session today has two parts. First, I’ll be giving a quick introduction to the math libraries that ship on OS X. And then Eric has a fantastic primer in store for you on writing fast SIMD code. OK, let’s get started. OS X ships with three math libraries, LibM, which provides C99 standard math functions. VMathLib provides the corresponding functions for SIMD vectors and VForce for arrays.

You get at the libm functions by including math.h, which gives you the float double and long double versions of the functions. If you want the corresponding complex variable versions, you include complex.h. And on the screen, we have the performance of the cycle counts for our five example functions as they were when we shipped Tiger as compared to the corresponding functions for Leopard, our latest release, 10.5.3. We can see the first two functions are single precision, as sine f and x-bef.

The next two functions are double precision, log, and hyperbolic cosine. We actually had a question yesterday in the performance lab about when to use the float functions, when to use the double precision functions. With Leopard especially, you’ll notice the significant performance speedup if you use the float versions of the functions that have the f suffix, as long as you don’t need the additional precision or range that you get from double precision. The fifth example is the complex exponential function, which while significantly more complicated to compute, we also see a nice speedup in Leopard.

Eric will be talking much more about SIMD operations. So let me just say about VMathLib that it does for SIMD vectors what LibM does for scalars. It’s included in the Accelerate framework. As an example, let’s imagine that you have two SIMD vectors, A and B, of four floats. And you want to compute A to the power B in each of those four slots with a single call to vfloatf. You can get all four of the outputs nice and easy.

If instead you have an array of inputs that you want to process, we wouldn’t want you to have to call libm in a loop for every single element of your array. So instead, we have vforce as part of the Accelerate framework. which allows you to get rid of that loop and replace it with a single function call with pointers to the output buffer, the two input buffers, A and B, and a pointer to the length of the array. And in one pass, VForce will calculate the results for the whole array.

Let’s take a quick look at the performance of some vfloat functions. Here I’m showing the corresponding element by element cycle count for libm. These are the timings on Tiger. You’ll see the first two examples, again, are single precision. We see the vfloat is about twice as fast. We hadn’t optimized the double precision functions in Tiger. We’ve now done that in Leopard. So those are also faster than the libm functions.

A few words about accuracy. Most of our libm functions are accurate to about six units in the last place, some significantly more accurate. Of course, the best you could hope for is half a unit in the last place, since ultimately you have to round the result to a floating point type. Because we want to give you the best possible performance in vforce and vmathlib, we actually loosen up the tolerance there to a couple of units in the last place.

Libim provides you fast, accurate, and robust routines for computing the C99 standard functions. Even faster versions are available in Accelerate for vector or arrays. And for more information, you can see the man pages in math or Accelerate with a capital A. Now let me introduce Eric Postpischil, a senior vector and numerics engineer. Take it away.

Thank you, Jeff. So Jeff told you about some of the libraries we have, and there are more. I’m gonna talk to you about what to do when you need to write your own SIMD code because we can’t write everything. So what we’re gonna talk about today, first I’ll talk about what is single instruction multiple data and how to write operations in C, for example, that use SIMD functions. And I’ll talk about some of the advantages and disadvantages of doing that and how to deal with some of the problems that come up when you start using SIMD code.

And we’re going to go through in detail the development of one SIMD routine. If you look at the documents associated with this session, there’s a SIMD primer sample that contains the complete source code for a running example. So any details I leave out during the talk, you can find everything in there ready to go.

So here’s the problem we’re going to study today. We’ve got this code. It’s a fairly simple loop. It’s in a routine that takes a couple of pointers to arrays with input data and one array with space for output data and how many elements. And we just go through the two input arrays, getting eight corresponding elements from each and adding them together and running them to the output. And that’s it, simple loop. But it runs too slowly. That’s the problem we want to fix today. It takes 2.53 CPU cycles per element when I measure it for 1,024 elements on a Xeon processor.

It can go, ideally, four times faster in some cases. And so that’s the goal we want to hit. So SIMD stands for single instruction, multiple data. We can have an object, which in this case, I’ll use floating point elements inside the object. SIMD objects, as we’ll see in a moment, can handle other things inside. But I’m going to talk mostly today about having float objects inside a SIMD object.

So we can have one object with four floating point numbers in it. In this case, I’ve got one, two, three, four, and a vfloat I call a. And I can take another SIMD object, B in this case, with some other numbers in it, and I can do one addition that gets me four answers. So one instruction, single instruction, multiple data.

So the basic SIMD object we work with today is 128 bits. And we can treat that 128 bits as 16 8-bit integers, or 16-bit integers, or four 32-bit integers. And those can be signed or unsigned. Or we can treat it as four single precision floating point numbers. And on Intel, not on PowerPC, we can also treat it as two 64-bit integers or two double precision numbers.

And some terms before I go on. SIMD, vector, and block, for the purposes of today’s talk, are the same thing. I might talk about a SIMD object. I might talk about a vector block. I’m talking about a 16-byte chunk of stuff. When I say scalar, I’m referring to things that aren’t SIMD objects or code. So the usual objects you’re used to seeing in C, int A, float B, or NSNumber from Objective-C, those are scalar objects.

On PowerPC, SIMD is called AltiVec, VMX, or Velocity Engine, and that’s just three different companies and their lawyers’ names for the different names of the same thing. All right. On Intel, SIMD features go by names such as MMX, SSE, SSE2, SSE3, SSSE3, and SSE4.1, and so on. And those are names for incremental extensions of SIMD features.

So SIMD features are found on every G4, G5, and Intel-based Mac. And you’ll notice I’m leaving out G3 in case you have to support the older processors. The ideal performance is we get a speedup proportional to the number of elements in a SIMD object. Ideally, if everything else works well, then SIMD instructions can go twice as fast when you’re working with two doubles or two integers, or four times as fast when you’re working with four things or so on, eight or 16.

But there are limits to that. It’s dependent on the CPU model. Not every CPU executes SIMD instructions as fast as we would like. It’s also only part of your computation. The routine we’re using, SIMD operations, also has other instructions. It’s got instructions to control your loop. It may have some instructions you can’t do with SIMD, so they’re scalar instructions. So you’re not always gonna reach this ideal, but we’re gonna try today.

SIMD is great when you’re working with arrays, when you’re working with matrices, when you’re working with vectors of numbers, especially when you’re doing parallel operations on elements. Like today, we’re looking at this VAD routine where each element, the operation we do with each pair of elements from A and B is completely independent of the other data in the array. They can all be done in parallel. So SIMD is great when you’ve got a situation like that. It’s also helpful with some other operations on arrays, notably the FFT. And these things are typically found and signal processing applications, or image processing, or linear algebra.

So why do you need to learn SIMD methods? The compilers are not delivering SIMD benefits automatically. It’d be nice if you could take that loop we saw at the beginning and tell GCC, well, I’ve got this loop, go vectorize it for me. One problem is the compiler is limited by the formal semantics of the language.

It’s required to do certain things in a certain order and using SIMD instructions might change that order. And so the compiler can’t do it. It doesn’t have permission to do it. It’s also constrained by the layout of data and address alignments and so on. We’ll talk more about what the address limits required by Cindy are, but the way-- Because SIMD requires certain alignments in your objects and your regular declarations, your scalar declarations of floating point arrays might not yield that alignment, the compiler can’t assume it’s going to have the alignment it needs to put in the SIMD instructions.

It’s also difficult for the compiler to transform some of the algorithms that you write in C into algorithms that can use effectively with Cindy instructions. In addition, the languages are not defining SIMD types or operations for you to work with. Standard C doesn’t have a way to refer to a SIMD object, so it’s not easy for you to write it in C. You need extensions of the compiler. And that means it’s also not standard from compiler to compiler.

But in spite of these problems of writing SIMD code, it can produce huge speed improvements. So that’s something you want to use, but the compiler’s not doing it for you. And so we have to write it ourselves. But before you go, write any SIMD routine yourself. Do look in our Accelerate library. We may have written the routine for you. We’ve got a lot of routines in the library.

Some drawbacks when you go write SIMD code, it’s going to cost you increased engineering time. It takes time to use some of the techniques I’m going to show you today. You have to spend a while figuring out what can I do to make this go faster, writing more code and so on. So you have to figure out if it’s worth it to you. Probably only want to use SIMD code where you’re really going to get the most performance gain.

Another drawback of SIMD, it’s sensitive to processor architecture. The SIMD operations that are available differ from PowerPC to Intel, for example. And so you may have to target one architecture and settle for that. Or if you need to support multiple architectures, you’re going to have to spend additional engineering time to handle them separately. There are also some flexibility issues with SIMD. You can’t always use it when you want because you’ve got to meet the address alignment requirements and so on.

I’ve mentioned address alignment several times. SIMD load and store operations when you’re loading something from memory into a register or storing it from registers back into memory generally must be aligned. They must use memory addresses that are multiples of the SIMD size, which is 16 bytes for now. The Intel architecture has unaligned load and store instructions, but the performance is poor for those instructions on the processes we’ve observed so far.

so we don’t want to use those instructions if we can avoid them. So one thing to do is design your code for aligned addresses. Allocate your buffers. When you call malloc, you’ll get an address that’s aligned the way you need it. Use that alignment. Start your buffer at the location malloc gives you, not after a header that’s not a good size for Cindy or something like that. And perform your work at the start of that aligned buffer. Avoid starting in the middle. If you’ve got an algorithm that requires you to start in the middle or where you have to subdivide your buffer for some reason, try to subdivide it in multiples of SIMD objects.

What happens if you can’t get this alignment that you need for SIMD? Well, if you’ve got a choice between moving your data around so that you have either an unaligned load or an unaligned store, you want to prefer the unaligned load. And the reason for that is that unaligned stores perform much worse than unaligned loads, and they’re harder to work around.

If you can’t get aligned addresses, but your misalignments are only occasionally occurring, they’re not the major part of your work, then go ahead and use the unaligned load instructions. They will not perform as well as the aligned instructions or alternatives that I’m going to show you today, but they may be good enough. If your misalignments are rare, take the performance hit. Don’t spend the time writing new code for that.

When you do that, you would want to have two sets of code. You’d want to have one set of code that handles the case where all of your data is aligned, and you can use the fast instructions. And you’d want to branch to another set of code where some of your data is misaligned, and you have to use the misaligned load and store instructions.

If you have to deal with a lot of misalignments, if it’s a fairly common thing, you don’t want to use the unaligned load instructions. They’re not good enough. And you may need to specialize code for each possible case of alignment on an Intel processor. And that’s the bulk of today’s lesson. So onto the code. Start looking at what you need to do for SIMD.

First thing you need to do in the source code is declare an object type, which I’ll call vfloat, per vector float. So you need to declare this object type. And we do it differently on different architectures. On Intel, we use this code. We include this header that Intel has specified called emm_intrn.h.

And that includes for us definitions, declarations of SSE2 intrinsics, which are-- they look like function calls, and they provide you with the SSE2 operations and earlier things, so SSE and some MMX. On PowerPC, we include altavec.h, and we typed vfloat to be a vector float. And if we’re not in either of those two architectures, we can use a GCC extension that will define vfloat to be a vector of size 16 bytes.

Outside of the source code, you have to tell the compiler what you’re doing. On Intel, SSE2 is on by default with our GCC compiler, our version of the GCC compiler. If you want to use something beyond SSE2, you can turn on more switches to tell GCC, I want to generate, I want to work with SSE3, or so on. Or if you’re not doing this at the command line, and you’re using Xcode, you can enable the-- there’s a build setting called enable SSE3 extensions and so on for the other variants of SSE.

On PowerPC, you have a choice. You can either put “-m Altivec on the command line and include altavec.h, or you can use “-f Altivec, and the compiler implicitly includes the functions in the declarations in altavec.h, so you don’t need to. If you’re using Xcode, you just enable the build setting, enable Altivec extensions.

So those are the preliminaries. Now we can start working on the actual code. And this is the code we’d like to have. We’d like to take that simple loop and change the types and change the number of iterations and then just have a loop on the vector objects. And so these first lines, these are just changing the pointers from pointers to float objects into pointers to vfloat objects. They don’t actually change the address involved. They just tell the compiler, “We’re going to work with this new type of object.”

And this next line just divides the number of iterations. Instead of working with n float elements, we just want to loop through n divided by 4 v float elements. And then this loop at the end looks just like the loop at the beginning, except it’s got different variable names, because we’re pointing-- variable names are pointing at v floats now. And we can actually write that code, but it’s got some issues we’ll talk about. Ideally, it would run at four times the best speed of scalar code, but there are some problems getting there and we’ll talk about those.

Some of the problems with this code, it does not work if any address is not vector block aligned. If A, B, or C is not vector block aligned and then we convert it to a pointer to vflow to then use it, we will get an exception. It also doesn’t work if n is not a multiple of 4. We divided n by 4 to calculate vn, and so we just threw the remainder away. We’ve got to do something about that. And it also doesn’t work for any operations except plus minus times and a few others.

So let’s work on some of these problems. We’ll tackle some of the easy ones first, actually. We’ll make C vector block aligned. And this is fairly simple. We just process using scalar code some elements at the beginning of the array. We just process an element, say, is C aligned now, process an element to C aligned now. And we’ll do 0, 1, 2, or 3 elements that way. And then C will be aligned.

And then we’re done. We’ve aligned at least one of our pointers. Why do I choose C and not ARB? And again, that’s because if we have a choice between aligning our loads or aligning our stores, we want to align our stores. And C is the output pointer. We want the stores to memory to be aligned. It’s better that way because the unaligned loads don’t hurt us as bad as the unaligned stores.

Okay, next problem. The code doesn’t work if n is not a multiple of four, so we’ll make it a multiple of four, and we use the sort of same technique, except instead of processing scalar elements at the beginning of the array, we will process scalar elements from the end of the array.

And we’ll just take them off one by one, do the add, store them, until n is a multiple of four. And that leaves us with a clean problem. C is now vector block aligned, and n is a multiple of four. But what we have to deal with now is that A or B might or might not be vector block aligned.

There’s actually a variety of combinations involved. Assuming A and B were at least aligned for float pointers, so there’s 0, 4, 8, or 12 modulus 16 bytes, we’d have 16 combinations. A and B could each be 0, 4, 8, or 12. And we’ll have to deal with that somehow.

And again, we could use move unaligned instructions to handle all cases, but the performance is poor. So we’re going to write multiple solutions for each case of alignment that we want to handle with fast code. And since we’re going to have multiple cases for different alignments, we need somebody to dispatch between the different routines we’re going to use for this.

So at the beginning, I’m looking at the remainders of A and B modulo 16, and I’m just sorting them so that I know A is smaller than B, which I can do in this case because the operation I’m doing addition is commutative, so it doesn’t matter if I swap the two inputs. If you’re working on a non-commutative operation, you can’t do this part.

But once I’ve done that, I just go into a switch statement. I say, first, if A is aligned, then I’m going to switch based on the remainder of B, modulo 16. And I’m going to call one of these four subroutines, VAD B00 or B04, B08, B12, to handle that particular alignment. And then I’m going to go write a different subroutine for each case.

And if that subroutine handles the operation I want to do, then I return, I’m done. In case I didn’t find anything in that switch statement that were written special code will just fall through to the scalar code at the end. It just calls a routine the original code we saw, handles it with slow code, but at least we’ve gotten the job done.

OK, so the rest of what we need to do to finish this routine is write the four subroutines. We’ll look at that one by one. The first one, A and B are both vector block aligned. So this is V add B 0 0. And it’s our favorite code because it’s the simplest.

I said we wanted to convert our pointers and convert our loop count and then just use a loop on vector objects. And in fact, we can do that and it will run in 1.34 CPU cycles per element. So already we’ve doubled our speed, but that’s not enough. We want some more speed. So now we’re going to use another trick.

It’s not particular to SIMD code. It’s just something we do when we want high performance code. We’re going to unroll the loop. And so to unroll the loop, we’re going to take the body of the loop and repeat it multiple times. And so we see here I’ve got four addition statements.

And I’ve got one adjustment to each of the pointers and the loop counter in this. So I’ve reduced the overhead of the loop. I have only one update of these addresses and counter for each four instances of the loop body. Now this sort of change is very sensitive to the compiler, to the version and quality of the compiler. We don’t have complete control over how the compiler generates code. So this is something you have to experiment with. How many times do I need to unroll before I get good code? How fast does it go when I try this or that?

It’s one of the hazards of writing SIMD code or writing high-performance code in general. And another problem with this loop is that it might end with N at 0, 1, 2, or 3. Sorry, I went backwards. Because if you look at the clause that ends the loop here, well, 4 is less than or equal to n, it continues. So when n is 0, 1, 2, or 3, we exit the loop, and we might have a few more iterations to do.

So here’s how we handle the last few iterations. We have an if statement. If n is two or more, we do two more iterations. And if we need another iteration after that, we do that. And then we’ve done all the original iterations. And epilogues like this are very common in SIMD code and high performance code. We’ve got a loop that does the bulk of the work, and it does it in groups. And then we need to finish up something at the end.

That completes one case. That’s all the code we need to handle one case of alignment. And it runs in 0.6 CPU cycles per element. It’s 4.3 times faster than the original code. So that’s what’s making this worthwhile, is we’re getting a big gain by doing this extra work.

Also, in this routine, the code works, when you compile it with GCC, for any architecture. If your target architecture is either PowerPC or Intel, where you do have SIMD code, the compiler will generate SIMD instructions, and the code will execute very quickly. If you’re compiling for another architecture that does not have SIMD code, GCC will emulate those SIMD objects for you.

And that means you’ll get a correct result, but it won’t be fast. But at least it gives you working code, which is great when you want to port or you need to support some architecture that you can’t or someone. So let’s go on to the next case. And I’m going to skip over the 4 mod 16 case. We’re going to go right to the 8 mod 16 case because it’s a little simpler.

So in this case, we’re facing the problem that we must load aligned vector blocks of memory, but the data we want in B isn’t aligned. And so to deal with that, we’re going to load two blocks from B, and we need to get the elements out of those. And to do that, we’re going to use the Intel Chef PD instruction. The Chef PD instruction blends eight bytes from one block with eight bytes from another block, which is just what we need.

When we do this, we’re getting some Intel-specific code. There isn’t any cross-architecture model for SIMD permuting or merging. If you go to write this sort of routine on a PowerPC, you’re going to use a different solution. There is no general agreement on what permutation operations there should be on all processors. Okay.

This Chef PD instruction is supplied by that header we included earlier, emm in trin.h, where it’s given to you as a function called _mm_shuffle_pd. It’s also supplied, if you’re using GCC, as a built-in, a built-in IA32-shuf PD. And here’s how we use it in source. I like to define a macro That makes it a little easier for me to use. It calls the intrinsic, and it casts the result to a vFloat. And there’s a selector argument there.

I also defined a macro to help me use that selector. It’s pretty simple in this case, but when we get to a four-element shuffle, the selector’s a little more complicated. But in this case, the selector is two bits. The E0 parameter is either 0 or 1 to say, I want the first 8 bytes or the second 8 bytes of that V0, the first argument.

and the next bit is either 0 or 1 to say I want the first or second 8 bytes of the other argument. Once I’ve defined those two macros, here’s how I use it in source. I just say, “Shift PD, here’s a block, “here’s a block, here’s my selector,” and I’m done.

If you look at the Intel documentation in the bibliography, it’ll document this instruction and others in more detail. And I want to talk about typecasting. I mentioned that I use this macro to cast the type of the return value of MM_SHUFFLE_PD. And that PD in shuffle PD stands for pack double.

This intrinsic is nominally made for working with vfloat-- or excuse me, with SIMD objects that include pack doubles. But you can use it with other types of object. And it returns to you something that’s a pack double. You might call it a v double. And so I need to cast it back.

In this case, GCC is flexible. Any vector object, a vector object containing vfloats, can be cast to any other vector object, a vector object containing v doubles-- excuse me, containing doubles or containing ints. The compiler will allow you to cast it to any other type of vector object.

And this is different from the scalar casts. In scalar code, if you have a float that has the value 3 in it and you cast it to an int, you’ll get an int with the value 3 in it. The compiler will do the necessary operation to change the bits so that its value in the new interpretation has the same value. When you cast a vector object to another vector object, the compiler says, well, you must know what you’re doing. We’re not going to change the bits. We’re just going to treat it as a different type.

What that means is these casts are useful for permuting data because you can use any shuffle, permute, merge, or shift instruction to rearrange the elements in your SIMD object regardless of the types involved. You can just cast it to the type that’s used in the operation you’re going to do, and do the operation, then cast it back.

This casting is also sometimes useful for changing data. And one thing we do sometimes is we use a bitwise and to clear the sign bit in a SIMD object that has floating point numbers in it, which gives us the absolute value of the values inside the SIMD object. OK, so that aside, let’s go back and take the chuff PD instruction and start the loop.

Before this code I show you here, VB has already been adjusted to be vector block aligned. So we knew it was pointing at something that was 8, modulo 16. That’s two floating point elements. So I’ve already subtracted VB before this code that I’ve got up on the screen now. And we need to get two consecutive blocks from VB. So in one statement before the loop, we’re going to load into pipe 0 the first block from VB.

And then inside the loop, I’m going to load another block from VB. And then I’m going to use shuf PD to take the bytes I need out of the first and the bytes I need out of the second, put them together, and give me the bytes that I actually want.

Once I’ve done that, I’ve used eight bytes from pipe one, but there are eight more bytes in it that I’m gonna want in the next edition I’m gonna do. So I’m gonna use pipe one again. So let’s look at the whole loop now. I’ve got, except for the ellipsis here, I’m not hiding much in the ellipsis. All that’s in the ellipsis, I couldn’t fit everything in the screen, so all that’s there is the decrement of the loop counter and the increments of the pointers. All the actual code that gets the data and adds it is up here on the screen.

And we can look at what we’re doing with pipe 1. We load it from VB, and then we use it twice in different positions to get the bytes out of it. We do a similar thing with pipe 2 and with pipe 3. And then I’m going to look at pipe 0. At the bottom of the loop, we load pipe 0 with a block from VB, and we take 8 bytes out of it.

And then we keep the value in pipe 0 around until the next iteration. At the top of the next iteration, we get the next 8 bytes out of pipe 0. And this sort of wrapping around where you knit iterations together is very common in SIMD code and high performance code.

And I showed you an epilogue from the first subroutine, where we finished up with 0, 1, 2, or 3 operations left. We have to do the same sort of thing here. We have to finish the last few operations similarly to the aligned case. The code looks very similar to what we had before, so I’m not putting it on the screen, but the details are in the session sample code.

So that finishes the second case. We figured out how to take this misaligned pointer and use it effectively. And now we have code that runs in 0.53 CPU cycles per element. And that’s 4.8 times faster than the original code. Now you may have noticed that it’s actually faster than the all-aligned case. And OK, sorry, the compiler does not always generate the code we’d like. If you really want that last few percent, you can use assembly language instead.

And an important difference between this routine and the one I just showed you is this code is now using Intel-specific instructions. It will not work on other architectures. The first routine would compile and run for any architecture. This won’t. And so what you need to do is use the preprocessor conditionals to select the code you’re going to execute, even the code you’re going to compile.

If your target is Intel, we can use the routine I just showed you. If it’s not Intel, you need to have some other code. It can be just scalar code, if you don’t mind, if it runs slowly on other processors. Or if you’re never, ever going to compile it for any other processor, you could leave it out. But I recommend scalar code. And the session sample code shows how to do this. Got an example. It has a fallback routine for everything in here.

And so now we go into the third case, which is a little more complicated. A is aligned and B is for modular 16. And again, as before, we must load aligned vector blocks from memory and we must blend two of them to get the desired elements. But that Chef PD instruction won’t do the job because it only moves blocks of eight bytes at a time. We need to move four around.

So two more instructions we’re going to use. There’s an instruction called moveSS, which moves four bytes from one block into another. It moves the low addressed four bytes from one block into the low addressed four bytes of another block. And there’s a pshfd instruction, which will rearrange the four 4-byte objects inside a SIMD object. And it will rearrange them in any order we want. And it will do any selection we want, where we can take all four and just rearrange them, or we can duplicate some and delete some.

And we’ll look at how we’re going to use these instructions. So say we have two blocks, v0 containing 0, 1, 2, 3, and v1 containing 4, 5, 6, 7. We can do this move ss, and it moves that 4 from v1 over and gives us 4, 1, 2, 3. And then we take that and just shuffle it around and get one, two, three, four. And this is a bit cumbersome, but it’s sort of what you need to do to fix up the alignment in this case.

And so once we figured out how to do that fix up, we can write the bulk of the loop very similarly to what we had before. So I’m not going to study this in detail. It’s very much the same loop as before. It just uses a bit different of a permutation inside.

And that finishes the third case. It runs in 0.7 CPU cycles per element, which is 3.6 times faster than the original code. And you can even squeeze a little more out of it if you really want to, if you write in assembly language. And so one thing we’re seeing here is the Intel architecture requires specific solution for each case. And this is really a nuisance. I mean, I have to go and handle if B is 8, if B is 4, and we’re going to get to B at 12 in a minute. You want to avoid that if you can.

So I want to emphasize, try to arrange your data so you avoid having any aligned cases. If you’re going to have some unaligned cases, at least try to arrange your data so you avoid having many cases. At least try to make one of your buffers aligned, and then only deal with misalignment in the other one.

So we’ve got one more case left and a little bit different from the others. A is aligned, B is 12, modular 16. The C code for this is similar to the four modulus 16 case. The shuffling is a little different. And I’ve tried this. It runs in 0.84 CPU cycles per element, which is three times faster than the original code, and that’s what you’ll find in the sample code associated with the session.

However, if we work in assembly, we can actually achieve 0.65 CPU cycles per element. Now, I can’t say that it’s impossible that by doing something with the C code, you might not have been able to get.65, but I tried a few things and I didn’t get that. And so I’m going to use this as an opportunity to talk about C versus assembly, not just to convince you to use assembly language, which I think is fun, but also to show you some of the performance effects that are hidden from you when you are writing in C. And so we’re going to look at the shuffle and move that we need to do when we’re handling this B is 12 mod 16 case.

So the shuffle we need to do would do this rearrangement. It would move 4, 5, 6, 7 around to put 7 in the low 4 bytes where we can get at it with the moveSS instruction. And then the moveSS would let us bring in a 3 from some earlier iteration and insert it in here. And we’d have 3, 4, 5, 6, which is great. It’s just what we need.

And that 7 we want to use in a later iteration. We’re going to go around the loop, come back, and need to get the next block and merge it with this 7 that we’ve got here in this iteration. And to tell you what the problem is here, I want to look at the move SS in C.

So we’ve got this C statement that calls the intrinsic MM move SS, which is Intel’s name in C for what is actually the move SS instruction. And in C, it takes two inputs, V1, V0, and it gives you back something that has something from V0 and three things from V1. So in C, it appears to be a function that has two inputs and one output.

But if you’re working in assembly language, your view of moveSS is this. You see moveSS, and you have two registers, v0 and v1. And when you execute the move instruction, Did I actually see that? OK, I’m sorry. I didn’t see on my screen this happening. When you actually execute that instruction, it doesn’t give you a different output. It actually modifies one of your input registers.

So the compiler hides that modification from you. When you write the intrinsic in C, the compiler does the work necessary to make it look like a function with two inputs and one output. If it knows from the code it can see later on that you’re going to need one of those inputs, the compiler generates an instruction to copy the register for you. And so that’s obscuring your view of the performance effects. You’re not seeing that in your C source code, but it gets generated in the assembly and it can slow things down a little bit.

So how would I deal with that problem? The move SS is to insert that 3. It’s destroying the 7 that I’m going to need later. And one solution for this is to work backward. I’m going to change the order I process my loop in. I’m going to work from high addresses to low addresses. And what that means is that 7 that I’m going to need, I can move that to the higher addressed work that I’m doing earlier in time.

And since I’m moving it out of that register, It’s not destroying the register that the 7 is in. Later on, I’ll move the 3 in to replace the 7. So I’m going to show you this loop as it would appear in C. Before I start this loop, I’ve adjusted VA, VB, and VC. So they’re now pointing at the end of my array.

And here’s the code to do this. And you’ll notice I’m decrementing my pointers now instead of incrementing them, because I’m going to be working backwards. And then I’ve got these instructions. They just do the shuffle and the move that I need. And then the rest of this loop follows pretty similarly to the 4 mod 16 case.

Okay, so that finishes all four cases that I need to get my VAD routine done with high-performance SIMD code. This last case, again, in C, it runs in 0.84 CPU cycles per element. That’s not as fast as it could be. But that’s the best I was able to get in C without doing something extraordinary.

So that finishes our VAD routine. So our original two-line routine, very simple, is now 200 lines long, including all the code for Intel or fallbacks for scalar code for other processes or other architectures and so on. But it’s four times faster. So you can get a really good performance gain, but it can take some work. And so you have to decide if that’s worth it to you.

So some caveats about using SIMD code. First of all, this is just one example. VAD is not the routine you might want to optimize in your code. I used it to teach because it is relatively simple, and I can go through the cases and show you how to do it.

But it’s load store bound, by which I mean for every one SIMD addition we were doing, I had to do two SIMD loads. I had to load something from A, and I had to load something from B. And then I add them, and then I store them. And the processor is actually spending most of its time, or half its time loading things from memory there.

it could actually do the arithmetic more quickly if it didn’t have to do that many loads per add instruction. So instead of optimizing VAD, you want to look for opportunities in your code to perform more arithmetic per load and optimize those. So you may have some loop where you’re doing multiple operations.

That’s a thing you want to optimize if you can. Or if you’ve got a loop where you’re only doing these adds, you want to look at ways of combining it with other code. In addition, you don’t need to write VAD, because we’ve already done it for you. It’s in accelerate as VDSP_VAD. It’s include our accelerate header, and you can call VAD with some extra parameters here that I haven’t discussed.

Another issue when you’re writing SIMD code is compatibility. Now, future Intel processors might have different feature sets. We’re going to guarantee you that Intel-based Macs will have SSE2. But beyond SSE2, if you want to use some neat instruction that’s in SSE3, you have to check that feature at runtime.

Otherwise, your program might fail on a processor that only has SSE2 and doesn’t have SSE3. And that’s true if next week we release a system with a processor that has SSE3. That doesn’t mean that after that we won’t go back and have some processor that only has SSE2. You might find some really neat processor in a MacBook Pro and something that doesn’t have SSE, whatever is at that point, in a lower end system.

Older power PC processors, the G3s, do not have Altivec. So if you want to write code that will run on a G4 or G3 and it will use the SIMD code on a G4, but will use scalar code on a G3, you need to detect at runtime what processor you’re on. And the Velocity Engine webpage that I list in the bibliography has information on doing that detection.

Writing SIMD code is a new thing, and so new errors may get made. One common error is reading one block too many. You’ll notice in that loop I was reading ahead. I was loading something from pipe zero and using part of it, loading something into pipe zero and using part of it and saving the rest for later. So I’ve read data that I’m not going to use.

Well, that’s okay if you’ve read a block and used part of the data in it because the fact that part of the data you know is there means the rest of the block is there too. However, it’s not okay to read a block that you don’t know is in memory.

If somebody’s given you an array and said do a thousand elements here and you’ve got your loop and you’re trying to read ahead a little bit to gain some time here, and you read a block that’s just beyond the end of the array, you never actually add anything with it, but you’ve got that load in there and then you stop your loop. That load can fail because you don’t know what’s beyond the end of the array. That memory might not be mapped.

That’s a very common error you can make in SIMD or high performance code just because of the way the code is structured. So something to watch out for. In general, errors in these loop prologues or epilogues are common because they’re unusual, they’re different from the rest of the code, they don’t get exercised as much. Another error that gets made in SIMD code is using an instruction that’s not in the processor you’re targeting.

And that’s easy to do. You start becoming more familiar with these instructions and have a favorite and use it in some code. And it runs fine on the system on your desktop because that’s the latest whiz-bang processor. And it’s got everything in it. And then you ship your product and it goes to some customer who doesn’t have that processor and the instruction fails. So test on the processors you support.

SIMD code and more high performance code in general also has problems of increased overhead. In place of that simple loop, we spent some time looking at C, looking at N, looking at A and B, saying what should we do with these. That’s increased overhead to figure out what we’re doing and to dispatch to the routine we’re going to use.

Which means if you have very short vectors, you’re going to lose some time here. You’re going to spend your time dispatching and not doing the arithmetic. So SIMD code is not good for short vectors. You want to use it with very long arrays of things, hundreds of elements, thousands of elements, even more.

I also only showed you how to do addition. If you want to go beyond that, GCC has a few things built in. It knows about plus, minus, times, and divide. It knows about unary negation. It knows about some bitwise logical operators, XOR, OR, AND, and complement. And so you can write those operations as if the sort of normal C code, and GCC will generate the appropriate SIMD instruction for you. If you want other operations, you can look into the Intel SSE instructions.

And there are manuals I refer to in the bibliography that list all of those. You can look through those and see what you need. And in addition, as Jeff mentioned, we provide you with VMathlib. And for VMathlib, think vector libm. It’s the vector version of libm. So in scalar code, you might write sine f and pass it a float.

But with vector code, you might have a vfloat va, and you would pass it to the v sine f routine. It will take the sign of each of the things in that float and give them back to you. And to use it, it’s in our Accelerate framework. You include our header, add the framework to your project and Xcode, and call that.

If you’re interested in SIMD code, you’re probably interested in performance in general. So I’m going to throw in some bonus optimization tips as well. In general, you want to limit this expensive optimization. It’s going to take your time. So you want to limit it to the most valuable places.

So we suggest you examine your application using Shark or other tools to find where you’re spending the CPU time. Don’t go and try to optimize your whole application. Don’t try to optimize the complicated parts, necessarily. Find where the CPU time is actually going. And isolate that code to a small routine or several routines so that you can work on it separately from everything else. and then optimize that small sequence of code.

And because SIMD code can get very complicated, I recommend often having plain old C code that forms that function. This is one reason I want to isolate it. You can have two versions of the routine you’re going to optimize. One that’s simple C code you can use for testing or reference or documentation and say this is what the function is supposed to do and it’s easy to read. And then you can have the other code that’s the 200 lines instead of two lines that does the very high performance work.

Another optimization technique is called chaining. And in this situation, let’s say we have two or more loops that operate on the same data or intersecting data. We have some data, maybe multiple arrays here, which we’ve colored in different colors to talk about them. There may be an initial loop that goes through these orange and green arrays and uses the data in them and does something. And then there’s another loop that goes through the green and blue and works on those. And another final loop that goes through the blue and the purple.

And the issue here is if we look at that green array, the data in it has to be loaded or stored in that first loop and loaded again in the second loop. And that’s a waste. We don’t want to do that. The same thing for the blue. It has to be loaded and stored multiple times. And in situations like this, it can sometimes help to combine multiple loops into a single loop.

This sort of thing is very architecture dependent and also compiler dependent. Are there actually enough registers in a processor that you can hold all the data from your first array, your second array, your third array, and do all the arithmetic operations you need without running out of registers, in which case the compiler has to put something on the stack and it’s not actually saving you any loads and stores. So it can be very compiler dependent, very architecture dependent. But in many cases, it can help you. Because now instead of the processor spending its time doing loads and stores, it’s doing arithmetic. And that could be much faster.

Another situation that can occur, in this case we have two or more loops that operate on more data than fits an L1 cache. So we go into this first loop, and we use data from these first two arrays. And this is so much data, the loop is so long, so many elements here, that by the time we get to the end of this array, the data from the beginning of the array is no longer in L1 cache.

And that means when we go into the second loop, that data, since it’s not in cache, we have to go get it from memory, and that’s a lot longer than reading it from cache. And then when we go to the third loop, we have to do it over again.

And to solve this, one thing we can try is to break the work into segments here, strips. And in this case, I’ve shown three strips. So let’s say all the data from one of these strips fits in cache. And I want to do the loops in this order instead. I want to do in that first strip, I want to do the first loop. And then in the same strip of data, I want to do the second loop and then the third loop.

And when I’ve done this, when I get to that second loop in that first strip, the data is still in cache. So now instead of loading it from memory, I can load it from cache. It’s much faster. And then I go into the second strip and do the same three loops, and then the third strip and do the same three loops. And when I’m in this third strip, all the data from the first strip is no longer in L1 cache. But that’s OK. I don’t need it anymore. I’ve already got my savings from it.

Another optimization technique is assembly language. This will give you the best performance, and I think it’s fun, but for many people, it will increase your engineering time. But it does give you complete control over instructions and registers, and sometimes it’s the only way to solve a performance problem.

If you don’t want to use a lot of assembly language, well, again, I said isolate your routine, isolate the part you want to optimize to a smaller section of code as you can, and just write that in assembly. When you do that, I suggest you always keep working C code.

So you’ll have one version of this routine in C, you’ll have one version in assembly. The C version provides you with a reference implementation. It’s good for testing, it’s good when you’re porting to new architectures, it’s good for documentation. Other people can look at it and say, “Oh, I see what this routine does.” But then you use the assembly version for high-performance.

If you’re getting started with assembly language, one thing you can do is generate assembly code from C. So you can write some C that does something you want. Say, oh, I need some operation. I know how to write it in C, but I don’t know how to do it in assembly.

You can write a little subroutine that gets past the parameters you’re going to need and does the operation and then returns. And then compile that code with GCC with these switches, -s and -f verbose asm. And that would cause GCC to generate an assembly file for you. And you can look at that and see what the compiler was doing. And you can use that for ideas of studying how things get done.

Okay, bibliography, you’re gonna need some reference material when you get started with SIMD programming on your own. For GCC, there are some web pages that describe the vector extensions. And you don’t have to write these down. It’s available on the website for WWDC attendees. And so the first section here lists the pages that are relevant to Vector Extend.

The second section there lists some things about GCC writing assembly in C code. I haven’t talked about that, but it’s something you might want to do every now and then. There’s one instruction that’s really helpful, but you can’t quite get at it with the things available in C. You can use embedded assembly to put that instruction in the generated code.

When you’re working with the Intel architecture, you’ll need some manuals from Intel. The first section here, the Intel 64 and IA32 architecture software developers manual has multiple volumes. Volume one has an overview and it has lists of instructions grouped by extension. So you can look in here and there’s a section for SSE2 and you say, oh, these are all the SSE2 instructions.

I can use those and the things on the previous section in SSE and I know they’ll work in any Intel-based Mac. So that’s a good place to look for ideas about what instruction is going to do the thing I need. And then you can go to volumes 2A and 2B, which list the details of each instruction in alphabetical order.

In addition, there’s an instruction reference built into Shark. So if you’ve got Shark running, you can use its help to look up an instruction and see what it does. That can be a very handy reference. Another good manual from Intel is the Software Vectorization Handbook by Art Bick.

It does take a bit of a theoretical approach to some of its things. You might have to translate that a bit to work it into something into practice, but it’s a good reference. And the architecture manuals I described earlier tell you about instructions. When you’re working in C, you need to know about the intrinsics, which have different names. And so you can look in the Intel C++ compiler documentation, and there’s a specific URL here, and you want to go from there to the chapter that’s called “Intrinsics Reference,” and it lists the intrinsics that you’ll find in the headers.

On PowerPC, we have two manuals for you. There’s the Altivec Technology Programming Interface Manual, and that describes the C extensions that you use to use the Altivec features. And then there’s the Programming Environments Manual, which has the instruction descriptions. And again, Shark has the PowerPC instruction set built in, so you can look things right up while you’re in Shark.

Apple has some web pages you’ll find useful. One on SSE performance programming. And another is called the Altivec SSE Migration Guide. But it’s not just useful for migration. In the course of talking about migration, it talks about the different properties of features and so on, the different features of various instructions and ways to do things. So it’s useful for even just getting started with Intel, not only if you’re migrating. and what we call the Velocity Engine page. Velocity Engine was one of those names for Altivec, but this page actually has Intel information as well.

Okay, here’s one contact if you want more information. And after I put together these slides, another source occurred to me. There’s a mailing list at lists.apple.com. If you look for the perfoptimization-dev mailing list, that’s P-E-R-F optimization hyphen dev. That’s a public mailing list where people post questions and help each other out, and we lurk on those lists and answer from time to time.

So in summary, Synthi offers you great speed. I mean, it’s a lot of work, but that four times speed up is real attractive. And you can do it in C. You don’t need to use assembly, in spite of my promoting it here. It may be a lot of work, but once you get into it, I think you’ll find it can be rewarding and maybe not as scary as it looks at first.