🔒 Locked

Thoughts on a SIMD Library

Started by Tinyn Sep 27, 2005 at 9:52 AM 30 replies 7.1k views

Original Post

Sep 27, 2005 at 9:52 AM

NVec Library code Lately I've been working on a library of general SIMD functions, inspired by Intel's IPP Library. However, this compiles with GCC (needs a version that has instrinsics for SSE3, I know 3.4.3 works, but 3.1.2 doesnt), and will work on AMD. One of the key features of this library is that the user (programmer) doesn't need to worry about if this is being run on a chip that has SSE3 or SSE2 or whatever.


public:
    int DotProduct_Vector4_f32(Vector4_f32 *SrcA, Vector4_f32 *SrcB, f32 *Dest, size_t Len);
private:
    int DotProduct_Vector4_f32_NoVec(Vector4_f32 *SrcA, Vector4_f32 *SrcB, f32 *Dest, size_t Len);
    int DotProduct_Vector4_f32_SSE  (Vector4_f32 *SrcA, Vector4_f32 *SrcB, f32 *Dest, size_t Len);
    int DotProduct_Vector4_f32_SSE2 (Vector4_f32 *SrcA, Vector4_f32 *SrcB, f32 *Dest, size_t Len);
    int DotProduct_Vector4_f32_SSE3 (Vector4_f32 *SrcA, Vector4_f32 *SrcB, f32 *Dest, size_t Len);

The user programmer can only call DotProduct_Vector4_f32() which decides if the chip is capable of using SSE, and then it calls the appropriate specific function. If no vectorized function is available, then it calls the NoVec version, which is written in straight C++, and is as optimized as the compiler makes it, but it wont be processor specific unless you set the compiler flags for GCC to make it specific. Another issue with SSE SIMD is alignment. Most of the SSE instructions that access memory require the memory be aligned on a 16 byte boundry. The default malloc() and new only allocs on a 4 or 8 byte boundry usually. So this class also provides a Malloc() and Free() function. The Malloc will always provide an address that is 32 byte aligned, but it must be deallocated using the provided Free() as well (or _mm_free()). But even if you call the public function with an unaligned bit of memory, no problem. It just uses the NoVec version. (because even though the math would be faster with SSE, the unaligned loads have shown to be too slow to use, you're better off without vectorizing) Below are some benchmarks Ive done with the only two chips available to me. A P4 2ghz and an AMD64 4200. The P4 has SSE2, the AMD has SSE3. Some of the benchmarks in the P4 have a (4) in them, thats the UNSUPPORTED_ERROR that happens if you somehow force a call of a function that your chip doesn't support. But that impossible outside of my test code, cause they are all private. Those are NVec trying to call an SSE3 function on an SSE2 P4. As you can see, some things speed up by alot, some barly at all, but at least they arn't slower. (except my dot product... dunno what Im doing wrong there) Also AMD is clearly superior [grin].


P4, 2ghz, Windows, mingw 3.4.4

                         Copy_Void -    NoVec(0): 0.16644s      SSE1(0): 0.08773s       ratio: 1.89715 
                                                                MemC(0): 0.16209s       ratio: 1.02684 
                          Copy_f32 -    NoVec(0): 0.15348s      SSE1(0): 0.07080s       ratio: 2.16791 

                            Add_s8 -    NoVec(0): 0.06297s      SSE2(0): 0.01501s       ratio: 4.19570 
                           Add_s16 -    NoVec(0): 0.06013s      SSE2(0): 0.02526s       ratio: 2.38015 
                           Add_s32 -    NoVec(0): 0.05942s      SSE2(0): 0.03558s       ratio: 1.66991 
                           Add_s64 -    NoVec(0): 0.23151s      SSE2(0): 0.04226s       ratio: 5.47808 
                           Add_f32 -    NoVec(0): 0.06437s      SSE1(0): 0.02644s       ratio: 2.43460 
                           Add_f64 -    NoVec(0): 0.06274s      SSE2(0): 0.04324s       ratio: 1.45099 

                            Sub_s8 -    NoVec(0): 0.06174s      SSE2(0): 0.01665s       ratio: 3.70858 
                           Sub_s16 -    NoVec(0): 0.05396s      SSE2(0): 0.04232s       ratio: 1.27482 
                           Sub_s32 -    NoVec(0): 0.06556s      SSE2(0): 0.03301s       ratio: 1.98598 
                           Sub_s64 -    NoVec(0): 0.24717s      SSE2(0): 0.04825s       ratio: 5.12274 
                           Sub_f32 -    NoVec(0): 0.06099s      SSE1(0): 0.02866s       ratio: 2.12811 
                           Sub_f64 -    NoVec(0): 0.06350s      SSE2(0): 0.04641s       ratio: 1.36825 

                            Mul_s8 -    NoVec(0): 0.20123s 
                           Mul_s16 -    NoVec(0): 0.21326s      SSE2(0): 0.02868s       ratio: 7.43717 
                           Mul_s32 -    NoVec(0): 0.08393s 
                           Mul_s64 -    NoVec(0): 0.55440s 
                           Mul_f32 -    NoVec(0): 0.07070s      SSE1(0): 0.02631s       ratio: 2.68736 
                           Mul_f64 -    NoVec(0): 0.07513s      SSE2(0): 0.04152s       ratio: 1.80949 

                           Div_f32 -    NoVec(0): 0.71638s      SSE1(0): 0.15914s       ratio: 4.50145 
                                                                SSE2(0): 0.02852s       ratio: 25.11886 
                           Div_f64 -    NoVec(0): 0.71739s      SSE2(0): 0.56716s       ratio: 1.26488 

             Vector_Matrix_Mul_f32 -    NoVec(0): 0.68920s      SSE1(0): 0.23659s       ratio: 2.91303 
                    Matrix_Mul_f32 -    NoVec(0): 0.05337s 
            DotProduct_Vector4_f32 -    NoVec(0): 0.18801s      SSE1(0): 0.45078s       ratio: 0.41707 
                                                                SSE2(0): 0.31374s       ratio: 0.59925 
                                                                SSE3(4): 0.00143s       ratio: 131.39008 
      CrossProduct_Vector4_As3_f32 -    NoVec(0): 0.28419s 

                 Pythag_Point4_f32 -    NoVec(0): 0.78027s      SSE2(0): 0.15287s       ratio: 5.10421 
                                                                SSE3(4): 0.00215s       ratio: 362.16559 
                      DegToRad_f32 -    NoVec(0): 0.06527s      SSE1(0): 0.03107s       ratio: 2.10098 
                      RadToDeg_f32 -    NoVec(0): 0.06727s      SSE1(0): 0.02729s       ratio: 2.46482 
               NormalizeRadian_f32 -    NoVec(0): 1.39405s      SSE2(0): 0.07361s       ratio: 18.93737 
             Normalize_Vector4_f32 -    NoVec(0): 3.52634s      SSE2(0): 0.42094s       ratio: 8.37729 
                                                                SSE3(4): 0.00158s       ratio: 2227.00865 
         Normalize_Vector4_As3_f32 -    NoVec(0): 2.74994s      SSE2(0): 0.41086s       ratio: 6.69320 
                                                                SSE3(4): 0.00159s       ratio: 1734.54167 

                           Sin_f32 -    NoVec(0): 3.19895s      SSE1(0): 0.16969s       ratio: 18.85165 
                           Cos_f32 -    NoVec(0): 3.14094s      SSE1(0): 0.17623s       ratio: 17.82270 
                           Tan_f32 -    NoVec(0): 3.78208s      SSE1(0): 0.16602s       ratio: 22.78061 
			   

AMD 4200x2, Linux gentoo amd64, gcc 3.4.3

                         Copy_Void -    NoVec(0): 0.03698s      SSE1(0): 0.04002s       ratio: 0.92414
                                                                MemC(0): 0.03668s       ratio: 1.00815
                          Copy_f32 -    NoVec(0): 0.16726s      SSE1(0): 0.06289s       ratio: 2.65954

                            Add_s8 -    NoVec(0): 0.04277s      SSE2(0): 0.01932s       ratio: 2.21314
                           Add_s16 -    NoVec(0): 0.04274s      SSE2(0): 0.02595s       ratio: 1.64692
                           Add_s32 -    NoVec(0): 0.04319s      SSE2(0): 0.03743s       ratio: 1.15391
                           Add_s64 -    NoVec(0): 0.04304s      SSE2(0): 0.05437s       ratio: 0.79156
                           Add_f32 -    NoVec(0): 0.04464s      SSE1(0): 0.03387s       ratio: 1.31795
                           Add_f64 -    NoVec(0): 0.04304s      SSE2(0): 0.05444s       ratio: 0.79066

                            Sub_s8 -    NoVec(0): 0.04278s      SSE2(0): 0.03171s       ratio: 1.34933
                           Sub_s16 -    NoVec(0): 0.05569s      SSE2(0): 0.02605s       ratio: 2.13765
                           Sub_s32 -    NoVec(0): 0.04337s      SSE2(0): 0.03763s       ratio: 1.15234
                           Sub_s64 -    NoVec(0): 0.04316s      SSE2(0): 0.05457s       ratio: 0.79078
                           Sub_f32 -    NoVec(0): 0.04353s      SSE1(0): 0.03408s       ratio: 1.27739
                           Sub_f64 -    NoVec(0): 0.04322s      SSE2(0): 0.05468s       ratio: 0.79038

                            Mul_s8 -    NoVec(0): 0.05691s
                           Mul_s16 -    NoVec(0): 0.05353s      SSE2(0): 0.02615s       ratio: 2.04688
                           Mul_s32 -    NoVec(0): 0.06347s
                           Mul_s64 -    NoVec(0): 0.05693s
                           Mul_f32 -    NoVec(0): 0.04352s      SSE1(0): 0.03410s       ratio: 1.27644
                           Mul_f64 -    NoVec(0): 0.04322s      SSE2(0): 0.05466s       ratio: 0.79078

                           Div_f32 -    NoVec(0): 0.18276s      SSE1(0): 0.11666s       ratio: 1.56657
                                                                SSE2(0): 0.03411s       ratio: 5.35777
                           Div_f64 -    NoVec(0): 0.23127s      SSE2(0): 0.21440s       ratio: 1.07869

             Vector_Matrix_Mul_f32 -    NoVec(0): 0.39048s      SSE1(0): 0.29176s       ratio: 1.33836
                    Matrix_Mul_f32 -    NoVec(0): 0.01752s
            DotProduct_Vector4_f32 -    NoVec(0): 0.09569s      SSE1(0): 0.19165s       ratio: 0.49928
                                                                SSE2(0): 0.24406s       ratio: 0.39207
                                                                SSE3(0): 0.13233s       ratio: 0.72311
      CrossProduct_Vector4_As3_f32 -    NoVec(0): 0.12821s

                 Pythag_Point4_f32 -    NoVec(0): 0.27117s      SSE2(0): 0.08501s       ratio: 3.18966
                                                                SSE3(0): 0.07029s       ratio: 3.85759
                      DegToRad_f32 -    NoVec(0): 0.03737s      SSE1(0): 0.01875s       ratio: 1.99312
                      RadToDeg_f32 -    NoVec(0): 0.03724s      SSE1(0): 0.01832s       ratio: 2.03286
               NormalizeRadian_f32 -    NoVec(0): 0.51535s      SSE2(0): 0.05654s       ratio: 9.11448
             Normalize_Vector4_f32 -    NoVec(0): 0.80477s      SSE2(0): 0.26697s       ratio: 3.01448
                                                                SSE3(0): 0.17059s       ratio: 4.71758
         Normalize_Vector4_As3_f32 -    NoVec(0): 0.66702s      SSE2(0): 0.28358s       ratio: 2.35211
                                                                SSE3(0): 0.17074s       ratio: 3.90655

                           Sin_f32 -    NoVec(0): 0.97305s      SSE1(0): 0.12248s       ratio: 7.94434
                           Cos_f32 -    NoVec(0): 1.07045s      SSE1(0): 0.10753s       ratio: 9.95522
                           Tan_f32 -    NoVec(0): 1.51840s      SSE1(0): 0.12262s       ratio: 12.38287

It does use intrinsics, instead of inline asm for the SSE code. But I have written some of the functions as inline asm, and it always comes out to the same speed as intrinsics with -O2 on. Future plans include adding more functionality. Any bit of math that can reasonably by vectorized basically. If anyone has any suggestions for new functionality to add, ideas for how to clean it up, or just use it for your own projects and tell me what breaks, that would be really cool.

Jan Wassenberg

105

Jan Wassenberg

Sep 27, 2005 at 11:21 AM

How are you dealing with the problem that such a lib actually punishes your min-spec system, which is the most in need of improvement?
By saddling it with the run-time choice of codepath *at a very low level*, you are surely adding lots of overhead vs. a simple version that inlines the relevant (non-SSE) code.
BTW such a project is great for learning purposes, but the above issue and dealing with compiler stupidity may turn out to be much more work than expected.
Search for "HorsePower", a similar undertaking.

MaulingMonkey

249

MaulingMonkey

Sep 27, 2005 at 11:50 AM

That was me :3. Repost of code to try and get template args and such to show:

struct mmx_processor {};struct sse_processor {};struct sse2_processor {}; ...struct none_processor {};void somewhere_high_in_the_program() {    if (processor_type == "mmx") do_math< mmx_processor >();    else if (processor_type == "sse") do_math< sse_processor >();    ...    else do_math< none_processor >();}template < typename processor_t >void do_math( void ) {    //...processor "independant" version goes here...    //we provide the template argument to the functions and classes which may    //be able to take advantage of processor optimizations.    proc_specific_vector3d< double , processor_t > vector1, vector2;    add_two_vectors< double , processor_t >( vector1 , vector2 );}template < typename scalar_t , typename processor_t >class proc_specific_vector3d { //generic implementation    typedef scalar_t scalar_type;private:    scalar_type m_x, m_y, m_z;public:    proc_specific_vector3d()        : m_x( 0 ) , m_y( 0 ) , m_z( 0 )    {    }    template < typename other_scalar_t , typename other_processor_t >    proc_specific_vector3d( const proc_specific_vector3d< other_scalar_t , other_procsesor_t > & other )        : m_x( other.x() )        , m_y( other.y() )        , m_z( other.z() )    {    }    ...};template < typename scalar_t >class proc_specific_vector3d< scalar_t , sse2_processor > { //SSE2 implementation    typedef scalar_t scalar_type;private:    __m128 data;public:    ...};

Tinyn

Author

Tinyn

Sep 27, 2005 at 12:11 PM

I tried to deal with that issue, but because of the alignment issues its a bit of a wash really.

If the only issue for determineing SSE or non-SSE what the chip capabilities, my first approch would have worked. It impliemented everything as a bunch of a function pointers. The user is only exposed to one function, but that is actually a pointer and at construction it was pointed at the SSE or NoVec version, based on if that chip could support SSE.

But chip capabilities arn't the only factor. Alignment is just as big. Every time I've tried taking on SSE function, and making it into a unaligned-SSE function by just replacing the movaps with movups instructions, the performance drops to well below the level of the NoVec functions. So theres no point in even having unaligned-SSE versions, and those were all removed a while ago.

The thing is, a check for alignment must be done. No way around it. If you call movaps with an unaligned pointer it will just segfault. I'm not willing to leave the MUST BE ALIGNED OR CRASH issue to the users, so it must be checked at the begining of each call anyway. (edit in:) Its no different then checking for NULL pointers.

That template solution has the same issue. You can decide the CPU at the begining, but if your handed an unaligned array of floats and asked to multiply it, you still have to fall back on unvectorized code. The only way around that is to give users the Align Or Crash option, and I doubt most coders want to deal with that.

So, yes, every exposed function begins with if(HasSSE) and if(AlignCheck(SrcPtr)) or the like. But in practice the those ifs are trivial to the time it takes to do a thousand multiplies or whatever. Its a matter of how you use it. Do not use the matrix vector multiply once for every vector. Line up all your vectors into an aligned array, and call the matrix vector multiple once. The time spent in those first if's disappears.

Is it as good as hand crafted SSE perfect and embedded in your app? Nope! This is supposed to be SIMD for dummies. It might not be as fast a hand crafted asm would be, but if it magically makes your matrix multiplies three times faster for zero effort to the user, all the better.

edit: I can't find a HorsePower library anywhere. Too much other uses for that word...

[Edited by - Tinyn on September 27, 2005 12:11:51 PM]

Jan Wassenberg

105

Jan Wassenberg

Sep 27, 2005 at 1:26 PM

Quote:
It impliemented everything as a bunch of a function pointers.

Be aware that this may actually end up *slower* than well-predicted branches! Reason is that the target address cannot be "predicted"; in fact it must be fetched from mem (which also puts more pressure on the cache *).
* aside: synthetic benchmarks tend to make function pointers and e.g. LUTs look much better than they are, because there is no other activity in the system.

Quote:
The thing is, a check for alignment must be done. No way around it. If you call movaps with an unaligned pointer it will just segfault. I'm not willing to leave the MUST BE ALIGNED OR CRASH issue to the users, so it must be checked at the begining of each call anyway. (edit in:) Its no different then checking for NULL pointers.

Actually NULL pointer checks are a good example. A reasonable policy is to assert() on entry to a function that pointers are not 0, but do not check for that at runtime. The rationale is that this *should never happen* - any source of NULL pointers (failed allocs, user code) catches that and indicates failure without every allowing them to escape. With good testing, you catch all such bugs in debug mode and then run without the overhead of checking for this.
As it should be with alignment - there are no reasonable grounds for passing unaligned data. In fact the compiler even provides support for correctly allocating such variables.
Always checking for NULL/misalign may be safer in that exceptions are never triggered, but it definitely slows down the default case and can hide bugs!

Quote:
Is it as good as hand crafted SSE perfect and embedded in your app? Nope! This is supposed to be SIMD for dummies.

hm.. if that's not your aim, then all is well, I guess.

Quote:
edit: I can't find a HorsePower library anywhere. Too much other uses for that word...

fish or fishing pole.
BTW, also check out liboil.

MaulingMonkey

249

MaulingMonkey

Sep 27, 2005 at 1:34 PM

Quote:
Original post by Tinyn
That template solution has the same issue. You can decide the CPU at the begining, but if your handed an unaligned array of floats and asked to multiply it, you still have to fall back on unvectorized code. The only way around that is to give users the Align Or Crash option, and I doubt most coders want to deal with that.

In my example I specialized the vector class based on processor type as well. For the SSE version it uses the type __m128 (as an example), which is guaranteed to be aligned to a 16 byte boundry for SSE instructions to appropriately operate on it. Basically, instead of allowing the user to pass in a structure which may not be appropriately aligned, I would instead wrap up the data in a class which enforces appropriate alignment as a post-condition to every operation - which may be as simple as assigning the input values to an appropriately aligned type.

So no, the template version does not have the same issue :-). Or it dosn't have to, anyways.

Tinyn

Author

Tinyn

Sep 27, 2005 at 2:54 PM

Quote:
Original post by MaulingMonkey

In my example I specialized the vector class based on processor type as well. For the SSE version it uses the type __m128 (as an example), which is guaranteed to be aligned to a 16 byte boundry for SSE instructions to appropriately operate on it. Basically, instead of allowing the user to pass in a structure which may not be appropriately aligned, I would instead wrap up the data in a class which enforces appropriate alignment as a post-condition to every operation - which may be as simple as assigning the input values to an appropriately aligned type.

So no, the template version does not have the same issue :-). Or it dosn't have to, anyways.

But then you require the user to know about __m128 types. The idea was to create something where any user could see 'float *' or something else they are equally familier with. The function Add(float * SrcA, float *SrcB, float *Dest) is plainly obvious to anyone in CS 101. The function vAdd(__m128 A, __m128 B, __mm128 D) is obvious only to people that know enough SIMD to write their own.

edit:

I went into one of the sets of functions and commented out all of the if's, and let it pass through anyway. After several runs the the average increase in the speedup ratio was 0.01

[Edited by - Tinyn on September 27, 2005 3:54:01 PM]

Jan Wassenberg

105

Jan Wassenberg

Sep 27, 2005 at 5:21 PM

Quote:
The function Add(float * SrcA, float *SrcB, float *Dest) is plainly obvious to anyone in CS 101.

Indeed. But less obvious is that the threat of aliasing just about prevents any meaningful optimization inside this routine (you need to use C99 restrict or MSC __restrict keywords).
Where do you draw the line in your library between ease-of-use and performance?

Quote:
The function vAdd(__m128 A, __m128 B, __mm128 D) is obvious only to people that know enough SIMD to write their own.

.. and it's non-portable to boot. Why not typedef and document it?

Quote:
I went into one of the sets of functions and commented out all of the if's, and let it pass through anyway. After several runs the the average increase in the speedup ratio was 0.01

*sigh* a synthetic benchmark that tells us little. CPU Branch Target Buffers have finite space (2k on Athlon XP); in real-world programs, this and lots of other jumps are vying for space in it. As soon as you aren't only doing one thing, you will get mispredicts that are absolutely devastating when compared to a few SIMD instructions (especially if we're talking about P4, heh).
Curious: how did it look before you did "several runs"? That is much more indicative of real-world performance because it doesn't assume perfect prediction!

Tinyn

Author

Tinyn

Sep 27, 2005 at 5:47 PM

Quote:
Original post by Jan Wassenberg
Indeed. But less obvious is that the threat of aliasing just about prevents any meaningful optimization inside this routine (you need to use C99 restrict or MSC __restrict keywords).

Why use restrict? In the absense of a Mul by Constant, or Add To Itself function, Add(A, A, D) should be a reasonable thing to allow?

Quote:

Where do you draw the line in your library between ease-of-use and performance?

The same place Intel did, cause they probably dumped a ton of research into IPP? And without the actual source code, this matchs that behavior.

Quote:

Quote:
The function vAdd(__m128 A, __m128 B, __mm128 D) is obvious only to people that know enough SIMD to write their own.

.. and it's non-portable to boot. Why not typedef and document it?

What?

Quote:

Quote:
I went into one of the sets of functions and commented out all of the if's, and let it pass through anyway. After several runs the the average increase in the speedup ratio was 0.01

*sigh* a synthetic benchmark that tells us little. CPU Branch Target Buffers have finite space (2k on Athlon XP); in real-world programs, this and lots of other jumps are vying for space in it. As soon as you aren't only doing one thing, you will get mispredicts that are absolutely devastating when compared to a few SIMD instructions (especially if we're talking about P4, heh).
Curious: how did it look before you did "several runs"? That is much more indicative of real-world performance because it doesn't assume perfect prediction!

Some runs with the ifs in place

NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.18697s      SSE1(0): 0.48333s       ratio: 0.38684                                                                 SSE2(0): 0.29575s       ratio: 0.63218 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.18826s      SSE1(0): 0.48484s       ratio: 0.38830                                                                 SSE2(0): 0.29861s       ratio: 0.63046 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.18412s      SSE1(0): 0.48451s       ratio: 0.38001                                                                 SSE2(0): 0.30158s       ratio: 0.61052 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.18027s      SSE1(0): 0.48644s       ratio: 0.37060                                                                 SSE2(0): 0.29645s       ratio: 0.60811 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.18887s      SSE1(0): 0.48761s       ratio: 0.38733                                                                 SSE2(0): 0.29774s       ratio: 0.63434

And a while and a recompile later, with the ifs commented out

NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.17141s      SSE1(0): 0.44908s       ratio: 0.38169                                                                 SSE2(0): 0.26860s       ratio: 0.63816 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.17053s      SSE1(0): 0.44929s       ratio: 0.37955                                                                 SSE2(0): 0.26761s       ratio: 0.63724 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.16808s      SSE1(0): 0.45299s       ratio: 0.37104                                                                 SSE2(0): 0.26318s       ratio: 0.63864 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.17277s      SSE1(0): 0.44691s       ratio: 0.38659                                                                 SSE2(0): 0.26813s       ratio: 0.64434 NBouk@GRAPHICS01 ~/misc/nvec$ nvectest.exe             DotProduct_Vector4_f32 -    NoVec(0): 0.17078s      SSE1(0): 0.46124s       ratio: 0.37027                                                                 SSE2(0): 0.27133s       ratio: 0.62943

Those are all within the same error of margin of each other.

Jan Wassenberg

105

Jan Wassenberg

Sep 27, 2005 at 6:40 PM

Quote:
Why use restrict? In the absense of a Mul by Constant, or Add To Itself function, Add(A, A, D) should be a reasonable thing to allow?

From perspective of your users, yes. Once you understand what aliasing means: no. Short explanation: as soon as you write to *dst, the compiler has to assume all other data has changed. That means software pipelining/unrolling or even basic stuff such as preloading from memory isn't possible, because you always have to reload after each write.

Quote:
Quote:
Where do you draw the line in your library between ease-of-use and performance?

The same place Intel did, cause they probably dumped a ton of research into IPP? And without the actual source code, this matchs that behavior.

Don't get all defensive, dude. I frankly don't care one way or another about the library, just trying to give tips.
This question is important because it is the central design issue; you can't have both.
As it stands, you are leaning heavily towards convenience.

Quote:
Quote:
and it's non-portable to boot. Why not typedef and document it?

What?

__m128 is MSC-specific. Better to replace that with a typedef; when users look at your function and wonder "huh, what's that parameter?", they look up declaration. There you would explain that the compiler takes care of aligning as required. Problem solved.

Quote:
Some runs with the ifs in place

Let me try again. These benchmarks are worthless because you are measuring the absolute best case. After 150K loops of doing nothing else, one would hope the branch predictor gets if() right. In real-world programs, you fill your BTB rather quickly, leading to expensive mispredicts.

Tinyn

Author

Tinyn

Sep 27, 2005 at 11:21 PM

Sorry if I got defensive but after the fish or fishing pole comment it seemed bit insulting. Every other combination of Horsepower and math and SIMD except that one brought up marketing trash from Intel.

Yes, convenience > speed. Because if its not convenient it wont be used. 2x speedup thats used is better then a 4x speedup that is ignored as too complicated or restricting.

I looked back over the template idea. all that really does is it forces the user to bunch their functions call together into one do_math() function or code block, and make them determine which processor it supports, and they have to duplicate their do_math() function for every possibility. Huge inconveniance for something thats supposed to be general purpose. If I split it up so that every function took that template parameter, then the compiler would just convert every function call into the set of if's itself anyway.

I thought about using inheritance. A Base Vec class, and then some number of processor specific. At startup the user would make BaseVec *Vec = PickRightProcVecClass(); And from then on always Vec->Func(). Reasonably convenient, but that would make every single function call a virtual table lookup. Just as bad.

Could make a whole bunch of .a's, one for every chip type. No runtime checks at all. Less of a problem for compiling from source always, but then the user would just have to make a half dozen different exe's if they wanted to distribute binaries. .dll's or .so's, and at startup dynamically decide which to load. Not a problem for the user, but really it works out to just being a bunch of function pointers anyway then.

Jan Wassenberg

105

Jan Wassenberg

Sep 28, 2005 at 4:37 AM

Quote:
Sorry if I got defensive but after the fish or fishing pole comment it seemed bit insulting. Every other combination of Horsepower and math and SIMD except that one brought up marketing trash from Intel.

Not my intent. It's a saying in German: you want just the result, or are you interested in how to duplicate it?
And yes, had to try a few times before the right result popped up.

Quote:
Yes, convenience > speed. Because if its not convenient it wont be used. 2x speedup thats used is better then a 4x speedup that is ignored as too complicated or restricting.

OK. I think differently: time-critical code (as indicated by profiler) should be squeezed till it screams, effort be damned. The rest is irrelevant and should be written for clarity.

Quote:
I thought about using inheritance. A Base Vec class, and then some number of processor specific. At startup the user would make BaseVec *Vec = PickRightProcVecClass(); And from then on always Vec->Func(). Reasonably convenient, but that would make every single function call a virtual table lookup. Just as bad.

Ooh, yeah - baad (even worse than function pointers).

Quote:
Could make a whole bunch of .a's, one for every chip type. No runtime checks at all. Less of a problem for compiling from source always, but then the user would just have to make a half dozen different exe's if they wanted to distribute binaries. .dll's or .so's, and at startup dynamically decide which to load. Not a problem for the user, but really it works out to just being a bunch of function pointers anyway then.

Yes indeed, that's no speed gain. But go one step further: distribute a separate executable for each platform/CPU. A little starter app can check CPU caps and dispatch to the right version (which can protect itself from being started directly via cmdline params).
This will bake in your SIMD stuff without any checks *and inlines them*.

Note: you can get rid of dynamic dispatch overhead by being really clever: expose function calls as a macro that allocates enough room in the code segment (NOPs via inline asm) and then calls a setup function. This VirtualProtects away write protection, writes the appropriate routine into that space and fills the rest with multibyte NOPs (slightly faster to execute than 1-byte 0x90).
This way you even get inlining for almost 0 overhead (if code size is fairly consistent; otherwise you pay like 1 clock for 15 bytes difference). However, I wouldn't swear that future OSes will even allow this, and inline asm macros need to be ported between MSC and GCC. It's probably not worth the trouble.

SlimTimmy

Sep 28, 2005 at 3:41 PM

@Jan Wassenberg:

You repeatedly criticized the way Tinyn benchmarks his library. I agree with you in this point, but do you have suggestions how you could create a benchmark which shows the real benefits of a particular optimization?

evanofsky

527

evanofsky

Sep 28, 2005 at 3:45 PM

I have one suggestion: have the user call a function when his program starts that detects the computer's SSE capabilities. Then when he calls a function, all the root "f32" function has to do is look up what the pre-determined capabilities are.

My 2 cents.

Jan Wassenberg

105

Jan Wassenberg

Sep 28, 2005 at 6:08 PM

SlimTimmy:
The most meaningful benchmark is a real-world application into which you are dropping your routines. The performance of the whole is what you are trying to optimize, so also take it as the goal function :)
Measure the time your routines take - but make sure they are called at reasonable intervals, with typical execution conditions (i.e. not assuming perfect branch prediction / cache contents).

What I have done in similar cases is record a typical test run, and then play it back (assumes your engine is deterministic) once for each version being evaluated.

With some asm + CPU internals under belt, a rough pipeline sim is also a good way to determine performance.

evanofsky:
Unfortunately even branching based on "pre-determined capabilities" is already a problem. I believe Tinyn's code is caching the caps anyway.

Tinyn

Author

Tinyn

Sep 29, 2005 at 12:46 AM

Quote:
Original post by evanofsky
I have one suggestion: have the user call a function when his program starts that detects the computer's SSE capabilities. Then when he calls a function, all the root "f32" function has to do is look up what the pre-determined capabilities are.

My 2 cents.

I am. cpuid is only called during the constructor, and a bool is set for each important flag. HasSSE, HasSSE2, etc. But in every public function there is a check for if(HasSSE) or whichever is appropriate. Any if at all can cause a pipeline stall. The only answer to that is to code without if's, or buy AMD [grin] (shorter pipelines, less waste per stall).

I took some pains to make sure there are no branchs inside the actual math loops (convert any given radian to the same position but inside -pi to +pi range without an if or mod!), but for it to be as easy to use as I want a few ifs at the start of each function are just unavoidable.

Sep 29, 2005 at 5:18 AM

The option I use, which haven't been discussed is to make a new .exe for each CPU.
Then have a small exe, that determines which .exe to use.
That way you get fully inlined code without any branches + you can use the compiler optimization for specific processors.
All cpu dependent features are resolved at compile time via defines.

The intel compiler is for instance very good at generating code that is optimized for the intel processors.
The msvc isn't as good to my knowledge since it targets intel syntax with amd support, different latencies etc isn't considered.

I typically have:

Game.exe // Get caps, currently I've only used "Pentium/FPU", "P3/SSE" and "P4/SSE" builds.GameP.exe // Pentium optimized exe using normal fpuGameP3.exe // Pentium 3 GameP4.exe // Pentium 4

The only thing game.exe does is to execute one of the other three .exe's.
To prevent the user to execute GameP.exe etc, I send a "magic" command line argument. I.e "GameP.exe SuperMagic" is executed from Game.exe.
You could also use .DLL's if you prefer.

I like the .exe version because that let's me test all 3 versions on my p4 by directly executing once of the three .exe's with the magic argument.

To test stuff the way you do it, you'd either have to recompile with some define (overriding the flags). Or read a config from the registry or a file.
You could of course test the code on the different hardware using the same .exe (as you could with the system above).

The cost of using the system above is longer build times.
This is ONLY a problem when debugging your different versions of the processor dependent code, or you release very frequent updates to your end users.
My code's been stable for a few years now so I do all development using p4 code, the other .exe's just work(tm).
I build the other versions really seldom.

Jan Wassenberg

105

Jan Wassenberg

Sep 29, 2005 at 8:08 AM

Quote:
The option I use, which haven't been discussed is to make a new .exe for each CPU.
Then have a small exe, that determines which .exe to use.

I am beginning to wonder why I bother ;p See above ("distribute a separate executable for each platform/CPU").

SlimTimmy

Oct 1, 2005 at 3:16 AM

Quote:
Original post by Jan Wassenberg
SlimTimmy:
The most meaningful benchmark is a real-world application into which you are dropping your routines. The performance of the whole is what you are trying to optimize, so also take it as the goal function :)
Measure the time your routines take - but make sure they are called at reasonable intervals, with typical execution conditions (i.e. not assuming perfect branch prediction / cache contents).

What I have done in similar cases is record a typical test run, and then play it back (assumes your engine is deterministic) once for each version being evaluated.

With some asm + CPU internals under belt, a rough pipeline sim is also a good way to determine performance.

The problem with a real-world application (with graphics, network, game logic etc.) may be that you will hardly see performance gains if you just optimize one single math function (And I would like to be able to do that, even compare a 3DNow optimized version vs. a SSE optimized version)
I thought that there are probably some test cases out that heavily use some of the main math routines.

Another aspect which wasn't dealt with up to now:
It might be interesting how the D3DX library handles these things. They recently put there routines into a .dll which should incur some calling overhead. And they also have to determine the cpu capabilites at runtime, although I do not know whether they use function pointers or some other method to switch between the different implementations.

ajas95

Oct 1, 2005 at 4:53 AM

Several things. Just because you declare something __m128 does NOT mean that it will be 16-byte aligned! On the stack, sure it will be, because the compiler can see to that. Try making a std::vector of these structs. It might work some times but not others... by the time new is allocating memory, it doesn't really care your alignment restrictions. You think there is an argument to malloc that is (int alignment) ?

Also, you should consider that for what you're talking about (dot product, etc), unaligned memory may be no slower! It's fastest to do dot product through just scalar x-component, so movaps/mulps/addps is just a waste of time. And this brings up a more important point: Trying to do this as a math library is a total waste of time because it tries to attack the problem at too abstract a level!

These math problems that are bottlenecks, their data structures and data-flow need to be planned well in advance... the compiler can't magically turn crap into cream. Your conception of SSE is that it can perform miracles and wonders. And, to some extent it can, but only under the exact right circumstances and the compiler will never understand this. In practice, the programmer has to put these circumstances into place explicitly and then exploit SSE with assembly. The compiler is still 2 or 3 years from even being able to generate intrinsics code efficiently (because it deals with register saturation and aliasing so poorly).

[edit] SlimTimmy: I think DX does some crazy thing where it uses function pointers, except that on the first call of the math func it actually calls a routine that determines the proc type, then re-assigns the func ptr based on the result. So there's a little bit of overhead, but the gnarly stuff only happens once [/edit]

Topic Locked

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