🔒 Locked

Disappointed by SSE performance

Started by Ysaneya Oct 23, 2007 at 2:20 PM 24 replies 10.3k views

Original Post

Oct 23, 2007 at 2:20 PM

I've been trying to optimize my code by using SSE intrinsic intructions in C++ in order to generate four 3D Perlin noise values at a time. Creating the SSE version was relatively easy, but unfortunately performance is extremely disappointing: the SSE code is 5 to 7 times slower than the standard one. Okay, it does calculate 4 values at a time, but since it's 5-7 times slower, overall there are no performance benefits (quite the contrary), while I was expecting it to be 2 to 3 times faster. The following code uses a few helper functions which I placed in a separate file for reference: http://fl-tw.com/opengl/sselib.h To track the problem, I simplified the code as much as I could to replicate it on as little code as possible. First of all, the C/C++ version:


float test(const SVec3D& xyz)
{
    const int xtr = MFloatToInt(xyz.x - 0.5f);
    const int ytr = MFloatToInt(xyz.y - 0.5f);
    const int ztr = MFloatToInt(xyz.z - 0.5f);

    const float x = xyz.x - xtr;
    const float y = xyz.y - ytr;
    const float z = xyz.z - ztr;

    return x + y + z;
}

Now the SSE version:


SVec4D testSSE(const SVec3D *xyz)
{
    C_SIMD_ALIGN16 float valX[4] = {xyz[0].x, xyz[1].x, xyz[2].x, xyz[3].x};
    C_SIMD_ALIGN16 float valY[4] = {xyz[0].y, xyz[1].y, xyz[2].y, xyz[3].y};
    C_SIMD_ALIGN16 float valZ[4] = {xyz[0].z, xyz[1].z, xyz[2].z, xyz[3].z};

    C_SIMD_ALIGN16 SIMDVec4F xyzX = SIMD_Vec4F_Load(valX);
    C_SIMD_ALIGN16 SIMDVec4F xtrf = SIMD_Vec4F_Sub(xyzX, SIMD_Vec4F_SetScalar(0.5f));
    C_SIMD_ALIGN16 SIMDVec4I xtr = SIMD_Vec4F_To_Vec4I_Round(xtrf);
    xtrf = SIMD_Vec4I_To_Vec4F(xtr);
    C_SIMD_ALIGN16 SIMDVec4F x = SIMD_Vec4F_Sub(xyzX, xtrf);

    xyzX = SIMD_Vec4F_Load(valY);
    xtrf = SIMD_Vec4F_Sub(xyzX, SIMD_Vec4F_SetScalar(0.5f));
    xtr = SIMD_Vec4F_To_Vec4I_Round(xtrf);
    xtrf = SIMD_Vec4I_To_Vec4F(xtr);
    x = SIMD_Vec4F_Add(x, SIMD_Vec4F_Sub(xyzX, xtrf));

    xyzX = SIMD_Vec4F_Load(valZ);
    xtrf = SIMD_Vec4F_Sub(xyzX, SIMD_Vec4F_SetScalar(0.5f));
    xtr = SIMD_Vec4F_To_Vec4I_Round(xtrf);
    xtrf = SIMD_Vec4I_To_Vec4F(xtr);
    x = SIMD_Vec4F_Add(x, SIMD_Vec4F_Sub(xyzX, xtrf));

    C_SIMD_ALIGN16 SVec4D res;
    C_SIMD_Vec4F_Store(&res.x, x);
    return res;
}

I tried a lot of ideas: - making sure all the data is 16-bits aligned, no change - reordering the instructions, groupping them by x/y/z, no change - using explicit temporaries, reusing them for constants, no change Everything I try is, at best, 4 times slower than the standard version, meaning (after taking into account the fact that it calculates 4 values at the same time) that results cancel out, and there's just no performance gain. If anybody has good knowledge about SSE performance, advices/tips/tricks are welcome.. Y.

implicit

Oct 23, 2007 at 2:25 PM

I wouldn't just trust the compiler to do the right thing with intrinsics for a critical innerloop like this. Why don't you post the generated code for both versions so we can get a better idea of what's happening?
I can spot one or two things off hand though, you'll really want to store the input vector in an structure-of-array form if at all possible for one. That initial data shuffling, especially when mixing C and intrinsics like this, is probably one of the main culprits.

edit: I don't know how this is to be used in practice but if the maximum values are fairly small and you're willing to lose a bit of precision you could extract the decimal part by adding a high bias to fix the exponent (essentially converting the float into a fixed point value), mask away the unwanted whole bits with an AND, and finally sum up the components as usual. Without involving any slow float/integer conversions. By choosing clever bias values you can get them to cancel each other out in the finally step and even include the 0.5 factor.
Much the same trick you've probably seen in all of those 'fast' float-to-int converters.

Keep in mind that SSE isn't the fastest unit for all types of problems, 3DNow wins out surprisingly often on AMD machines and the good old x87 is far from useless. It might even be that the your compiler was clever enough to use SSE for your original version and did a better job of implementing it than you, though in my experience that's beyond unlikely..

[Edited by - implicit on October 23, 2007 3:25:23 PM]

strtok

Oct 23, 2007 at 3:10 PM

This may or may not help, but as mentioned, it's probably the data shuffling at the beginning that's hurting the most. If you can live with an unused float in each vector and can modify your function to take 4D vectors, something like this might help:

SVec4D testSSE(const SVec4D *xyzw){    SIMDVec4F c0 = SIMD_Vec4F_Load(xyzw[0]),        c1 = SIMD_Vec4F_Load(xyzw[1]),        c2 = SIMD_Vec4F_Load(xyzw[2]),        c3 = SIMD_Vec4F_Load(xyzw[3]);    _MM_TRANSPOSE4_PS(c0, c1, c2, c3);    ...

Basically treat your 4 incoming vectors as a 4x4 matrix, then use _MM_TRANSPOSE4_PS (SSE transpose macro in xmmintrin.h) to transpose it. This should accomplish the same thing as your initial shuffling, and should (hopefully) be faster. If I'm not mistaken, the compiler should get those 4 vectors into SSE registers from the outset. I haven't tested this though, but it's an idea probably worth trying.

Spoonbender

Oct 23, 2007 at 3:22 PM

Can you post a listing of the ASM output from the compiler?

Also, as already said, you have to be *really* careful with the shuffling data around before and after your SSE code. That can easily take long enough to eliminate the benefits from using SSE in the first place.

Also, what CPU are you testing on? (Newer CPU's are vastly better at SSE, so it should be easier to see a performance improvement there)

Ysaneya

Oct 23, 2007 at 3:31 PM

Here is the assembly output:
http://fl-tw.com/opengl/sse.asm

Release mode, full optimizations, I tried several compilers (MSVC6, MSVC2005) that produced a similar output and performance. Tested on a Q6600 and a Pentium D 830.

Y.

Jan Wassenberg

Oct 23, 2007 at 3:37 PM

It looks like the problem is with swizzling your AoS xyz array to the SoA valX, etc. variables.
As written, it'll copy individual floats to a different memory location and only then load that into a register.

Not sure about your CPU, but I don't think it'll be able to gather the individual 32-bit stores and forward them to a 128-bit load, so the copying probably isn't free.

Can the input data be transformed into SoA format? (i.e. the valX, valY layout, so that it can be loaded directly)
If not, you may be better off with:
- a plain float-to-int cast and
- ICC or VC2005 and
- SSE code generation enabled;
this will provoke use of the scalar SSE instructions. They will only process one item at a time but can be pipelined (your dependency chain doesn't need many registers).

// edit: I type|think too slowly, but hopefully it's still helpful.

implicit

Oct 23, 2007 at 3:41 PM

No wonder it's slow..
You really need to store your input in a pre-shuffled SSE-friendly format and stick the function in a loop, or at least make it's inlined such that whatever uses it can work directly with the SSE results.
Even with the current format switching to a more efficient swizzling variant and returning the result through memory (by a pointer argument) ought to gain you quite a few cycles.

Washu

Oct 23, 2007 at 3:49 PM

Quote:
Original post by implicit
No wonder it's slow..
You really need to store your input in a pre-shuffled SSE-friendly format and stick the function in a loop, or at least make it's inlined such that whatever uses it can work directly with the SSE results.
Even with the current format switching to a more efficient swizzling variant and returning the result through memory (by a pointer argument) ought to gain you quite a few cycles.

Or just using straight out SSE register swizzling to do his manipulations, and keeping 4 output results, it should still be faster.

d00fus

Oct 23, 2007 at 3:57 PM

As the others have said, it is the memory copying and swizzling of the input data that is taking the time. At a minimum, you'll want the incoming data to be 16-byte aligned and in vec4 format. If it can be pre-swizzled great; otherwise it will still be much faster once you can use the 16-byte aligned move instructions into SSE registers to do the swizzling.

d00fus

Oct 23, 2007 at 4:09 PM

Also to comment on the output, if you can output full vec4s to a 16-byte aligned address you will be best off. Using the non-temporal store instruction (movntps) is ideal as you will avoid polluting your memory cache when storing the results. In the past this has made quite a difference for me.

Ysaneya

Oct 23, 2007 at 4:17 PM

Thanks for the comments everybody! I already used your suggestions for 2 optimizations:

1. Inputting 4 4D vectors instead of 4 3D vectors, and swizzling the values.
2. Instead of returning a 4D vector by value, passing a 16-bits aligned address and writing the output there.

Those two modifications ensured that the start/end overhead is minimal. The SSE version is 2.8 times faster.

The ASM output can now be seen here:
http://fl-tw.com/opengl/sse_b.asm

But stay tuned! As I explained initially, I'm trying to optimize my Perlin noise function. What I posted was only a very small test fraction for the beginning. I'll gradually increase the complexity, because I suspect the "good" performance I have now will disappear as soon as I'll touch the lookup tables for the gradiants..

Y.

implicit

Oct 23, 2007 at 4:20 PM

Quote:
Original post by d00fus
Also to comment on the output, if you can output full vec4s to a 16-byte aligned address you will be best off. Using the non-temporal store instruction (movntps) is ideal as you will avoid polluting your memory cache when storing the results. In the past this has made quite a difference for me.

Do not use the cache control instructions lightly. They're greatly dependent on how the other parts of your application perform as well as your processor's cache size and policies, and can just as easily slow things down to a crawl as help you especially in degenerate cases like reading the results back right after writing them.
I'm not saying you shouldn't use them but take care and measure their effectiveness regularly (in context, be wary of micro-benchmarks!).

d00fus

Oct 23, 2007 at 4:33 PM

Quote:
Original post by implicit
Do not use the cache control instructions lightly. They're greatly dependent on how the other parts of your application perform as well as your processor's cache size and policies, and can just as easily slow things down to a crawl as help you especially in degenerate cases like reading the results back right after writing them.
I'm not saying you shouldn't use them but take care and measure their effectiveness regularly (in context, be wary of micro-benchmarks!).

Of course, I should have qualified it with the proviso that this is designed for scenarios where you are not reading the data back for some time afterwards. You should always be profiling continuously while performing optimizations like these, looking especially at things like L1 and L2 cache misses.

implicit

Oct 23, 2007 at 4:49 PM

Quote:
Original post by d00fus
Of course, I should have qualified it with the proviso that this is designed for scenarios where you are not reading the data back for some time afterwards. You should always be profiling continuously while performing optimizations like these, looking especially at things like L1 and L2 cache misses.

The point is that you can't just forget about them after you've optimized your code. Cache behavior is a global problem and affected by just about everything, so you'll end up having to test them continually throughout the development process. And what works great on one machine can be quite inefficient on another so ideally you'll want multiple code paths for machines with different cache sizes. In other words there's a great deal of work involved in using them efficiently, and frankly for the most part you're better off focusing your efforts on trying to make everything fit in the cache in the first place..

Of course there are special cases like say filling up a large array, which just isn't going to fit in any reasonable cache, in a single pass. But all to often I've seen people stick non-temporal writes in "optimized" memcpy implementations because they happened to improve some specific case.

d00fus

Oct 23, 2007 at 5:24 PM

Quote:
Original post by implicit
The point is that you can't just forget about them after you've optimized your code. Cache behavior is a global problem and affected by just about everything, so you'll end up having to test them continually throughout the development process. And what works great on one machine can be quite inefficient on another so ideally you'll want multiple code paths for machines with different cache sizes. In other words there's a great deal of work involved in using them efficiently, and frankly for the most part you're better off focusing your efforts on trying to make everything fit in the cache in the first place..

Of course there are special cases like say filling up a large array, which just isn't going to fit in any reasonable cache, in a single pass. But all to often I've seen people stick non-temporal writes in "optimized" memcpy implementations because they happened to improve some specific case.

This is true to an extent but I think you have overstated the issue somewhat. Using non-temporal stores in an optimized general purpose memcpy is ill-advised as chances are the user will want to use the copied memory immediately afterwards which of course is the worst possible case.

If you are doing this level of optimization you will (should) have a good idea of the implications of cache behaviour, and should be able to identify cases where the nature of the processing is such that it will benefit from the streaming stores, and that processing should be close to its final implementation. There are many examples of stream-style processing where you want to store the results without jeopardising the work you have done in prefetching and priming the cache with the input data which is where the cache misses will hurt you. Using non-temporal stores in these scenerios can often be a win (taking into account different architectures and cache sizes) if done with care. Of course, you may need some differences in the code paths to make best use of the architecture concerned, but nothing I've said precludes this.

Edit: Having re-read this I think I'm preaching to the converted to a degree - I don't mean to say it isn't a significant amount of work or that it should be undertaken lightly :) My original comment was underelaborated, but I did want to emphasise that to get the ultimate performance out of SSE-optimising your code there are a number of non-trivial issues that need to be investigated.

[Edited by - d00fus on October 23, 2007 5:24:47 PM]

implicit

Oct 23, 2007 at 6:00 PM

Quote:
Original post by d00fus
If you are doing this level of optimization you will (should) have a good idea of the implications of cache behaviour, and should be able to identify cases where the nature of the processing is such that it will benefit from the streaming stores, and that processing should be close to its final implementation. There are many examples of stream-style processing where you want to store the results without jeopardising the work you have done in prefetching and priming the cache with the input data which is where the cache misses will hurt you. Using non-temporal stores in these scenerios can often be a win (taking into account different architectures and cache sizes) if done with care.

The point is that the scenarios where it is a clear win are fairly infrequent. You'll almost never want to use them in a library for instance (well.. unless you also provide a temporal alternative).

Few systems in your average game should produce enough data to fill the cache by themselves so whether to use non-temporal stores largely depends on how much data you'll be processing before reaching the consumer (this is not made any easier by multicore/hyperthreaded processors with shared caches). Most of all it's a brittle process, one where reordering a function call or parallelizing the wrong areas can throw off all your careful tuning.

Of course if you're optimizing for a fixed platform or the least common denominator then this is all less of an issue.

Quote:
Original post by d00fus
Of course, you may need some differences in the code paths to make best use of the architecture concerned, but nothing I've said precludes this.

No, I just thought the mentioning that they should be used with care was in order. Claiming that the use of non-temporal stores is ideal is quite a bold statement without knowing more of the specifics, especially as I got the impression that the result was to be used right off the bat for further calculations.

AndyPandyV2

Oct 23, 2007 at 8:20 PM

Not sure if this is helpful cause you might not want to go this route, but I found 3D noise on the GPU to be ~10x faster then in C++. The noise you posted in your dev journal awhile back ported to GLSL runs 13 fps at 1280x1024 with 12 octaves on my 6800.

Ysaneya

Oct 24, 2007 at 4:38 AM

Continuation

I added the code for interpolation parameters (u, v, w used in the final lerps), and that worked fine (performance ratio SSE vs non-SSE: almost x3).

But as I expected, it collapses as soon as I introduce the permutations lookup tables.

To keep it short, I need to implement the following operation:

const int A = ms_impPerm[X] + Y;

Where X and Y are computed from my previous code with:

C_SIMD_ALIGN16 SIMDVec4I X = SIMD_Vec4I_And_Vec4I(xtr, SIMD_Vec4I_SetScalar(255));C_SIMD_ALIGN16 SIMDVec4I Y = SIMD_Vec4I_And_Vec4I(ytr, SIMD_Vec4I_SetScalar(255));

The SSE code is:

C_SIMD_ALIGN16 SIMDVec4I A = SIMD_Vec4I_Set(ms_impPerm[X.m128i_i32[0]], ms_impPerm[X.m128i_i32[1]],ms_impPerm[X.m128i_i32[2]], ms_impPerm[X.m128i_i32[3]]);A = SIMD_Vec4I_Add(A, Y);

The permutation table is an array of 512 32-bits integers.

The assembly output for this table lookup looks like this:

; 297  : 	C_SIMD_ALIGN16 SIMDVec4I A = SIMD_Vec4I_Set(ms_impPerm[X.m128i_i32[0]],; 298  : 		ms_impPerm[X.m128i_i32[1]], ms_impPerm[X.m128i_i32[2]], ms_impPerm[X.m128i_i32[3]]);	mov	ecx, DWORD PTR _X$[esp+60]	mov	eax, DWORD PTR _X$[esp+56]	cvtps2dq xmm0, xmm0	mov	edx, DWORD PTR ?ms_impPerm@@3PAHA[ecx*4]	mov	ecx, DWORD PTR ?ms_impPerm@@3PAHA[eax*4]	mov	DWORD PTR -16+[esp+48], edx	mov	edx, DWORD PTR _X$[esp+52]	mov	DWORD PTR -16+[esp+52], ecx	mov	ecx, DWORD PTR _X$[esp+48]	mov	eax, DWORD PTR ?ms_impPerm@@3PAHA[edx*4]	pand	xmm0, xmm3	mov	edx, DWORD PTR ?ms_impPerm@@3PAHA[ecx*4]	mov	DWORD PTR -16+[esp+56], eax; 299  : 	A = SIMD_Vec4I_Add(A, Y);; 300  : 	SIMD_Vec4F_Store((TFloat *)res, SIMD_Vec4I_To_Vec4F(A));	mov	eax, DWORD PTR _res$[ebp]	mov	DWORD PTR -16+[esp+60], edx	movdqa	xmm1, XMMWORD PTR -16+[esp+48]	paddd	xmm1, xmm0

As soon as I do this operation, my performance goes back to the level of the standard, non-SSE code (and 13 other lookups will be following).

Y.

Skizz

Oct 24, 2007 at 5:34 AM

This is a classic case of piecemeal-micro-optimisation not working too well. I think the only way to get significant optimisation is to look at the whole algorithm. Any chance you can post the whole algorithm - in unoptimised C?

Skizz

d00fus

Oct 24, 2007 at 7:15 AM

The problem looks similar to before - you'll need to 16-byte align the permutation table so you can move the 4 required 32-bit integers into an SSE register in one movdqa instruction. Skizz is also right that generally trying to drop SSE in to selected parts of an existing algorithm will not produce great results; often the entire algorithm needs to be implemented from scratch.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.