some assembly optimization

Have you tried setting the compiler to use SSE and optimize more aggressively? It might be sufficient without needing to try and SIMD the thing -- dunno how far from desired framerate you're running.

I found this in my Intel manuals. Sadly, it's from SSE4.1:


PCMPEQQ: "Compare Packed Qword Data for Equal" operates on 128-bit locations which each contain two 64-bit integers.

The intrinsic listed for the Intel compiler is:

_m128i_mm_cmpeq_epi64(__m128i a, __m128i b);


This seems like a bit of a pain, because the manual says "If a pair of data elements is equal, the corrosponding data element in the destination is set to all 1s; otherwise it is set to all 0s."

It does NOT affect ZF, so you couldn't simply do a Jcc afterwards. Which means you'd have to compare each data element of the result using non-SIMD instructions. Which defeats the entire purpose.

[Edited by - Nypyren on March 20, 2009 9:09:36 PM]

It MIGHT be faster to replace the && with a single & in this case if you expect the first half of the condition to be true most of the time. Or you could put in a branch hint. But I bet the compiler already thought of that.

I vomited out some psuedocode. No promises that it's correct or fast (but please let me know!). I recommend you spice it up with some prefetchnta action, and remember to use intrinsics, not assembly.


[Edited by - Promit on March 20, 2009 10:05:05 PM]

You should always consider algorithmic changes before assembly-level changes.

One of the easiest optimization is to exchange time for space. If xL and yL are limited to a relatively small range, you may be able to use a lookup table rather than a search. Even if your lookup table is several MB in size, looking it up each time would be much faster than the search.

Similarly, if the parameters are frequently reused, consider either a lookup table of that subset or implementing a short LRU or LFU cache.


Linear searches are best when the most likely data is checked first. Is there one section of the data that is more likely to be a match? If so, you should to do that section first.

Running this type of search in parallel yields a superlinear speedup. Are there multiple processors available? If you aren't taking advantage of them already, consider using the OpenMP libraries (which are trivial to use) or other high-performance threading tools.

The fastest function is the one that is never called. What calls isopen4()? Can you call it or its parent less frequently?

frob's right, of course, and I'd suggest applying his suggestions before trying to apply my code. Honestly, I was just bored and wanted to remind myself what was in the SSE instruction sets.

frob: Thanks for your suggestions, but there isn't really much I can change algorithmically. The function is at the bottom of a recursive minimax-type search. I used OpenMP (which is amazingly trivial to use) to parallelize the highest level loop.

Promit: I'm really confused as to how your code works, but I will take a closer look at it tomorrow. Thanks.

Nypyren: PCMPEQQ... looks useful. I'm not averse to using a sse4.1 instruction (I'm on a core i7 right now)

After doing _mm_cmpeq_epi64, you can use _mm_movemask_ps to check the result:

xL2 = { xL, xL }
yL2 = { yL, yL }

zero = _mm_setzero_ps()

for (...; i += 2)
{
fmA = _mm_load_ps(fourMasksA + i)
fmB = _mm_load_ps(fourMasksB + i)
resA = _mm_cmpeq_epi64(zero, _mm_and_ps(xL2, fmA))
resB = _mm_not_ps(_mm_cmpgt_epi64(zero, _mm_and_ps(xL2, fmA)))
res = _mm_movemask_ps(_mm_and_ps(resA, resB))

// res is xxyy, where x is comparison result for i, and y is for i+1;
// if either of them is true, we can return
if (res) return true;

(that's pseudocode of course)

Note that you'll likely benefit from unrolling the loop further, 4 or 8 iterations.
Also note that if you use VS2008 (or any earlier revision), you'll have to write assembly code because there is no intrinsics support beyond SSE2 :(

> cmppd
I'd be very leery of using packed double instructions on arbitrary integers. Obviously you'd run into trouble if the value is a trap representation, but there is also the more insidious Flush-To-Zero flag which calls for replacing denormals with 0.

> I'm not averse to using a sse4.1 instruction (I'm on a core i7 right now)
Nice :) Can't wait to use SSE4.1, it fixes a number of shortcomings in the instruction set.

> After doing _mm_cmpeq_epi64, you can use _mm_movemask_ps to check the result:
Good suggestion, but why are you using floats? Casting between si128 and ps isn't free on some microarchitectures, and there's no need because _mm_movemask_epi8 is also available.

I think we can do better yet.
Let A := xL & fourmasksA, B := _mm_cmpeq_epi64(zero, yL & fourmasksB). Simply "unpack" A,B into a register and then _mm_testz_si128 with a mask of -1. (The implementation of logical NOT for B depends on the layout of the masks, but I bet PTEST will beat any PMOVMSKB-based approach.)

Depending on how the input to the function varies, you could also try this:



This is if you suspect you will be asking "close" questions often enough.

Quote:

Original post by ToohrVyk Depending on how the input to the function varies, you could also try this: *** Source Snippet Removed *** This is if you suspect you will be asking "close" questions often enough.

I don't see what you're accomplishing that way. Doesn't that simply repeat the first loop iteration, when there's an early-out for the loop anyway?

@OP: How often does the table change, versus calls to the function? If the table is fairly settled, you could:

a) As frob suggested, sort the table (keeping entries matched up between fourmasksA and fourmasksB of course) so that more likely matches are first (simple heuristic: bits in fourmasksB - bits in fourmasksA).

b) Add an early-out that I think is what ToohrVyk meant:

unsigned long long logical_and_of_fourmasksA = /* the obvious thing */;unsigned long long logical_or_of_fourmasksB = /* the obvious thing */;bool isopen4(unsigned long long xL, unsigned long long yL) {    if !((yL & logical_or_of_fourmasksB) && (xL & logical_and_of_fourmasksA)) return false; // one of the clauses inside the loop can never be true    for (int i=0;i<1280;i++ ) {        if (  (!(xL & fourmasksA))   &&  (yL & fourmasksB)     ) return true;    }    return false;}

Also, where does the table size of 1280 come from? Is it simply "big enough", in which case you may have filled some of the table with dummy entries that will never match? In that case, sorting and also counting the dummy entries (and thus limiting the loop) should help.

Quote:

Any idea how to assembly-optimize this loop (yes, it is the critical part):

I personally take a very methodical approach to optimization. First things first...

1.) It's good that you've identified your bottleneck in C/C++ code. Now you need to take this a step further. Have you identified what the compiler is generating? If not, I'd suggest setting a breakpoint for this function and viewing the disassembly. Get an idea of what the compiler is doing.

2.) Use a tool to figure out exactly what instruction(s) are causing the problem. If I had to guess, the '&&' operator is likely causing you branch prediction misses. Due to the "early out" capability of this operator, the compiler might be doing branches to avoid the second test. You might be better off evaluating both expressions as integers, bitwise-anding them together, and testing the final result for 0. However, look at the disassembly and use a tool. A tool will tell you exactly what the problem is and will be a far better than my random guess.

3.) Try coercing the compiler to generate the right assembly for you. If this still doesn't fix your problem, then trying to beat the compiler at optimization will most likely not fix your problem. The next step is to try an algorithmic change.

4.) Try an algorithmic change. This does not necessarily mean to do something different in C/C++, but it does mean you need to try a different approach. Going to SSE and handling 4 values at a time *is* an algorithmic change after all. Using fewer loop iterations will likely be a valid approach here. Using a lookup table will likely help you here as well. Note that if you do go into assembly, in my experience, compilers will not optimize it for you.

5.) Finally, use line-level optimizations. Depending on your knowledge of assembly and x86 processors, you can exploit parallism thanks to multiple execution units and the out-of-order cores present in modern processors. This mostly involves re-ordering or using different instructions to exploit parallelism within the chip. To do this effectively, you'll need to learn a lot about the internal architecture of these chips, and Intel's software optimization guides are a good place to start for this kind of information. However, you should hope that you don't need to do this. =)


Also, a simple note on lookup tables: A small lookup table in an inner loop can be a great thing. A larger one with localized access is also a great thing. However, if you have a gigantic lookup table, and the access is scattered, you can actually see a severe performance hit over instructions. Even with the fastest RAM, modern CPUs can generally execute instructions 20x faster than they can access RAM. There is also a penalty for fetching mispredictions. Modern CPUs speculate the results of various calculations and might have to actually undo and redo calculations if the CPU incorrectly guessed a memory fetch. It effectively stalls the pipeline.

Hopefully my post tells you one thing: you generally don't want to mess with assembly level optimizations, but if you need to, good luck. =)

Also, here is something quick to try (this has not been compiled or tested):



As for loop unrolling, I wouldn't be surprised if the compiler does that for you already. You should check the disassembly to verify this, however.

Kevin B

Quote:

Original post by Zahlman I don't see what you're accomplishing that way. Doesn't that simply repeat the first loop iteration, when there's an early-out for the loop anyway?

The i loop index is static, meaning that it will keep the last value that was found, and thus try the last index that worked (though I forgot to reset it when no match is found). This is a statistical optimization that works if most tests return true and there's a high probability that the x and y values for two consecutive tests are very similar.

Quote:

Original post by ToohrVyk Quote: Original post by Zahlman I don't see what you're accomplishing that way. Doesn't that simply repeat the first loop iteration, when there's an early-out for the loop anyway? The i loop index is static, meaning that it will keep the last value that was found, and thus try the last index that worked (though I forgot to reset it when no match is found). This is a statistical optimization that works if most tests return true and there's a high probability that the x and y values for two consecutive tests are very similar.

Interesting technique, but it isn't thread safe so might not be useful here.

[Edited by - Nitage on March 21, 2009 10:15:54 PM]

Quote:

Original post by ToohrVyk Quote: Original post by Zahlman I don't see what you're accomplishing that way. Doesn't that simply repeat the first loop iteration, when there's an early-out for the loop anyway? The i loop index is static, meaning that it will keep the last value that was found, and thus try the last index that worked (though I forgot to reset it when no match is found). This is a statistical optimization that works if most tests return true and there's a high probability that the x and y values for two consecutive tests are very similar.

Ah, I hadn't noticed that it's the same 'i' being reused for the loop. :)

Quote:

Original post by Nitage Interesting technique, but it isn't thread safe so might not be useful here.

That's easy enough to fix by converting the function into a functor and using a member variable to store the value.