Re: [PATCH] Optimize SSE 4.1 x86_64 memcmp

[Florian Weimer <fweimer at redhat dot com>]

On 02/03/2014 10:30 PM, Carlos O'Donell wrote:

> > Unaligned loads overlapping with data previously compared as equal.
> > This data cannot affect the outcome of the final comparison.  (This
> > trick was already used before, but it's not entirely obvious.)
> >
> > The SETNE/CMOVAE sequence for the branchless sign function.

(It turns out that this part is not actually present anymore.)

> No, that looks good from a commenting perspective.

I have incorporated the comment updates.

I think it still makes sense to apply this for 2.20 because OndÅej's 
changes are much more radical, although his approach seems faster still, 
and it can be combined with the BSWAP trick for the page-crossing case, 
avoiding the timing oracle.

> > In addition, I performed specialized comparisons for varying lengths
> > and shared prefixes, and benchmarked qsort on random data and
> > /usr/share/dict/words.  My test loop uses CPUID, yet it turns out
> > that getting good measurements of individual memcmp calls is really
> > quite tricky.  My benchmark code is available here:
> > <https://github.com/fweimer/memcmp-timing>
>
> Do you think it would be useful to integrate your benchmark as an
> additional test, or even replace the memcmp test we have with yours?

I'll look into deriving a qsort-based test from it.  I did some more 
measurements and the overhead added by qsort is fairly low.  I suppose 
we could use the abilist files as input data, that would look less 
arbitrary than sorting the lines of the manual.

> We do not know what would be a reasonable benchmark or we would
> have it :-)

Hah.  I think the qsort-based benchmark would be a good addition (not a 
replacement).  The existing memcmp microbenchmarks are still helpful as 
long as one is aware of their limitations.

> > One thing I would like to get consensus on eventually is whether
> > future implementations of memcmp must not behave as a timing oracle.
> > (There might be architectures where achieving this has a run-time
> > cost.)  If we are unwilling to make this promise, the oracle-free
> > version would have to be conditional on _FORTIFY_SOURCE.
>
> The present goal of the library is to be a high performance C library.
> Requiring that memcmp not behave as a timing oracle is out of the
> question for a *default* configuration.

If the pipeline has a sufficiently long CPU and you're sorting, I'm 
pretty sure that the oracle-free version will be faster as well because 
it has fewer hard-to-predict branches.

I plan to convert a few more memcmp variants (not just for x86), and 
then we can decide if we need to make this conditional, or if we can 
just provide it by default.

--
Florian Weimer / Red Hat Product Security Team