x86 max/min asm instructions?

Question

Are there any asm instructions that can speed up computation of min/max of vector of doubles/integers on Core i7 architecture?

Update:

I didn't expect such rich answers, thank you. So I see that max/min is possible to do without branching. I have sub-question:

Is there an efficient way to get the index of the biggest double in array?

Answer 1

SSE4 has PMAXSD or PMAXUD for 32 bit signed/unsigned integers, which might be useful.

SSE2 has MAXPD and MAXSD which compare between and across pairs of doubles, so you follow n/2-1 MAXPDs with one MAXSD to get the max of a vector of n, with the usual interlacing of loads and operations.

There are MIN equivalents of the above.

For the double case, you're probably not going to do better in assembler than a half-decent C++ compiler in SSE mode:

peregrino:$ g++ -O3 src/min_max.cpp -o bin/min_max
peregrino:$ g++ -O3 -msse4 -mfpmath=sse src/min_max.cpp -o bin/min_max_sse
peregrino:$ time bin/min_max
0,40

real    0m0.874s
user    0m0.796s
sys 0m0.004s
peregrino:$ time bin/min_max_sse 
0,40

real    0m0.457s
user    0m0.404s
sys 0m0.000s

where min_max computes min and max of an array of 500 doubles 100,000 times using a naive loop:

bool min_max ( double array[], size_t len, double& min, double& max )
{
    double min_value = array [ 0 ];
    double max_value = array [ 0 ];

    for ( size_t index = 1; index < len; ++index ) {
        if ( array [ index ] < min_value ) min_value = array [ index ];
        if ( array [ index ] > max_value ) max_value = array [ index ];
    }

    min = min_value;
    max = max_value;
}

---

In response to part two, the traditional optimisation to remove branching from a max operation is to compare the values, get the flag as a single bit ( giving 0 or 1 ), subtract one ( giving 0 or 0xffff_ffff) and 'and' it with the xor of the two possible results, so you get the equivalent of ( a > best ? ( current_index ^ best_index ) : 0 ) ^ best_index ). I doubt there's a simple SSE way of doing that, simply because SSE tends to operate on packed values rather than tagged values; there are some horizontal index operations, so you could try finding the max, then subtracting that from all elements in the original vector, then gather the sign bit, and the zero signed one would correspond to the index of the max, but that would probably not be an improvement unless you were using shorts or bytes.

Answer 2

Update: I just realized you said "array", not "vector" in part 2. I'll leave this here anyway in case it's useful.

---

re: part two: find the index of the max/min element in an SSE vector:

• Do a horizontal maximum. For a 128b vector of 2 double elements, that's just one shufpd + maxpd to leave the result broadcast to both elements.

  For other cases, it will of course take more steps. See Fastest way to do horizontal float vector sum on x86 for ideas, replacing addps with maxps or minps. (But note that 16-bit integer is special, because you can use SSE4 phminposuw. For max, subtract from 255)

• Do a packed-compare between the vector original vector and the vector where every element is the max.

  (pcmpeqq integer bit patterns or the usual cmpeqpd would both work for the double case).

• int _mm_movemask_pd (__m128d a) (movmskpd) to get the compare result as an integer bitmap.
• bit-scan (bsf) it for the (first) match: index = _bit_scan_forward(cmpmask). cmpmask = 0 is impossible if you used integer compares (because at least one element will match even if they are NaN).

This should compile to only 6 instructions (including a movapd). Yup, just checked on the Godbolt compiler explorer and it does, with SSE.

#include <immintrin.h>
#include <x86intrin.h>

int maxpos(__m128d v) {
  __m128d swapped = _mm_shuffle_pd(v,v, 1);
  __m128d maxbcast = _mm_max_pd(swapped, v);
  __m128d cmp = _mm_cmpeq_pd(maxbcast, v);
  int cmpmask = _mm_movemask_pd(cmp);
  return _bit_scan_forward(cmpmask);
}

Note that _mm_max_pd is not commutative with NaN inputs. If NaN is possible, and you don't care about performance on Intel Nehalem, you might consider using _mm_cmpeq_epi64 to compare bit-patterns. Bypass-delay from float to vec-int is a problem on Nehalem, though.

NaN != NaN in IEEE floating point, so the _mm_cmpeq_pd result mask could be all-zero in the all-NaN case.

Another thing you can do in the 2-element case to always get a 0 or 1 is to replace the bit-scan with cmpmask >> 1. (bsf is weird with input = all-zero).