lkml.org 
[lkml]   [2010]   [Dec]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Big git diff speedup by avoiding x86 "fast string" memcmp
> static inline int dentry_memcmp_long(const unsigned char *cs,
> const unsigned char *ct, ssize_t count)
> {
> int ret;
> const unsigned long *ls = (const unsigned long *)cs;
> const unsigned long *lt = (const unsigned long *)ct;
>
> while (count > 8) {
> ret = (*cs != *ct);
> if (ret)
> break;
> cs++;
> ct++;
> count-=8;
> }
> if (count) {
> unsigned long t = *ct & ((0xffffffffffffffff >> ((8 - count) * 8))
> ret = (*cs != t)
> }
>
> return ret;
> }

First, let's get the code right, and use correct types, but also, there
are some tricks to reduce the masking cost.

As long as you have to mask one string, *and* don't have to worry about
running off the end of mapped memory, there's no additional cost to
masking both in the loop. Just test (a ^ b) & mask.

#if 1 /* Table lookup */

static unsigned long const dentry_memcmp_mask[8] = {
#if defined(__LITTLE_ENDIAN)
0xff, 0xffff, 0xffffff, 0xffffffff,
#if sizeof (unsigned long) > 4
0xffffffffff, 0xffffffffffff, 0xffffffffffffff, 0xffffffffffffffff
#endif
#elif defined(__BIG_ENDIAN)
#if sizeof (unsigned long) == 4
0xff000000, 0xffff0000, 0xffffff00, 0xffffffff
#else
0xff00000000000000, 0xffff000000000000,
0xffffff0000000000, 0xffffffff00000000,
0xffffffffff000000, 0xffffffffffff0000,
0xffffffffffffff00, 0xffffffffffffffff
#endif
#else
#error undefined endianness
#endif
};

#define dentry_memcmp_mask(count) dentry_memcmp_mask[(count)-1]

#else /* In-line code */

#if defined(__LITTLE_ENDIAN)
#define dentry_memcmp_mask(count) (-1ul >> (sizeof 1ul - (count)) * 8)
#elif defined(__BIG_ENDIAN)
#define dentry_memcmp_mask(count) (-1ul << (sizeof 1ul - (count)) * 8)
#else
#error undefined endianness

#endif

static inline bool dentry_memcmp_long(unsigned char const *cs,
unsigned char const *ct, ssize_t count)
{
unsigned long const *ls = (unsigned long const *)cs;
unsigned long const *lt = (unsigned long const *)ct;

while (count > sizeof *cs) {
if (*cs != *ct)
return true;
cs++;
ct++;
count -= sizeof *cs;
}
/* Last 1..8 bytes */
return ((*ct ^ *cs) & dentry_memcmp_mask(count)) != 0;
}

If your string is at least 8 bytes long, and the processor has fast unaligned
loads, you can skip the mask entirely by redundantly comparing some bytes
(although the code bloat is probably undesirable for inline code):

static inline bool dentry_memcmp_long(const unsigned char *cs,
const unsigned char *ct, ssize_t count)
{
unsigned long const *ls = (unsigned long const *)cs;
unsigned long const *lt = (unsigned long const *)ct;

if (count < sizeof *cs)
return ((*ct ^ *cs) & dentry_memcmp_mask(count)) != 0;

while (count > sizeof *cs) {
if (*cs != *ct)
return true;
cs++;
ct++;
count -= sizeof *cs;
}
cs = (unsigned long const *)((char const *)cs + count - sizeof *cs);
ct = (unsigned long const *)((char const *)ct + count - sizeof *ct);
return *cs != *ct;
}


\
 
 \ /
  Last update: 2010-12-18 23:57    [W:0.110 / U:0.096 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site