From: Steve Ellcey <sellcey@mips.com>
To: "Ondřej Bílka" <neleai@seznam.cz>
Cc: <libc-ports@sourceware.org>
Subject: Re: [Patch, mips] Faster strcmp for mips
Date: Fri, 15 Nov 2013 18:21:00 -0000 [thread overview]
Message-ID: <1384539604.2484.102.camel@ubuntu-sellcey> (raw)
In-Reply-To: <20131114231434.GA5331@domone.podge>
On Fri, 2013-11-15 at 00:14 +0100, Ondøej BĂlka wrote:
> Problem is that aligned access could be only third of total calls. Also
> around 90% calls need to check only first 16 bytes. These numbers differ
> by application on x64 they are rule rather than exception. I collected
> data of running gcc+gnuplot here:
> http://kam.mff.cuni.cz/~ondra/benchmark_string/i7_ivy_bridge/strcmp_profile/results_gcc/result.html
Very interesting, you have obviously spent a lot more time then I have
on strcmp.
> > This means it could be loading bytes beyond the end of the strings being
> > compared but it looks like other architecture specific strcmp functions
> > are also doing this optimization and the newlib version of strcmp also does
> > this.
> >
> Also unaligned case can be made faster with bit of extra effort.
> How fast are unaligned loads on MIPS? They should be faster than
> assembling value by shifts from two loads manualy which should be faster
> than byte-by-byte checking.
MIPS doesn't have unaligned loads but it has 'partial' loads where two
loads can give you four (or eight) bytes in two load operations
regardless of alignment. I may need to look at this some more though
that will probably mean going to assembly language instead of C.
> Also here
> > + bx.v = x; by.v = y;
> > + if (bx.b.B0 - by.b.B0 != 0 || bx.b.B0 == 0)
> > + return bx.b.B0 - by.b.B0;
> > + if (bx.b.B1 - by.b.B1 != 0 || bx.b.B1 == 0)
> > + return bx.b.B1 - by.b.B1;
> > + if (bx.b.B2 - by.b.B2 != 0 || bx.b.B2 == 0)
> > + return bx.b.B2 - by.b.B2;
> > + if (bx.b.B3 - by.b.B3 != 0 || bx.b.B3 == 0)
> > + return bx.b.B3 - by.b.B3;
> > + if (bx.b.B4 - by.b.B4 != 0 || bx.b.B4 == 0)
> > + return bx.b.B4 - by.b.B4;
> > + if (bx.b.B5 - by.b.B5 != 0 || bx.b.B5 == 0)
> > + return bx.b.B5 - by.b.B5;
> > + if (bx.b.B6 - by.b.B6 != 0 || bx.b.B6 == 0)
> > + return bx.b.B6 - by.b.B6;
> > + return bx.b.B7 - by.b.B7;
>
> There is alternative way to find answer without branching.
> You need to compute a number that has nonzero i-th byte if i-th bytes of
> x and y differ or they are 0. Then find first nonzero bit which can be
> done quickly by CLZ instruction.
>
> This could be implemented as following
>
> uint64_t bitmask = DETECTNULL8(x) | (x ^ y);
> uint64_t bitfirst = bitmask ^ (bitmask - 1);
> int pos = (ffsl(bitfirst) - 1) / 8;
> return a[pos] - b[pos];
This looks very interesting, I tried just plugging it in but it didn't
work in some cases. I need to stare at this some more to understand
exactly how it should work and what cases are failing for me.
Steve Ellcey
sellcey@mips.com
next prev parent reply other threads:[~2013-11-15 18:21 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-11-14 21:25 Steve Ellcey
2013-11-14 23:14 ` Ondřej Bílka
2013-11-15 18:21 ` Steve Ellcey [this message]
2013-11-15 19:02 ` Ondřej Bílka
2013-11-18 23:50 ` Steve Ellcey
2013-11-19 2:32 ` Ondřej Bílka
2013-11-15 18:48 ` Carlos O'Donell
2013-11-15 18:53 ` Steve Ellcey
2013-11-15 18:59 ` Carlos O'Donell
2015-02-19 7:25 ` Matt Turner
2015-02-19 18:12 ` Steve Ellcey
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1384539604.2484.102.camel@ubuntu-sellcey \
--to=sellcey@mips.com \
--cc=libc-ports@sourceware.org \
--cc=neleai@seznam.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).