From: Alex Shinn <alexshinn@gmail.com>
To: Mike Gran <spk121@yahoo.com>
Cc: "Mark H Weaver" <mhw@netris.org>,
"Ludovic Courtès" <ludo@gnu.org>,
"guile-devel@gnu.org" <guile-devel@gnu.org>
Subject: Re: Using libunistring for string comparisons et al
Date: Wed, 16 Mar 2011 09:22:20 +0900 [thread overview]
Message-ID: <AANLkTinGRb4swGvgJLnL-Rij-RVvHv4Dw1nBe2xg4JYt@mail.gmail.com> (raw)
In-Reply-To: <511668.33680.qm@web37902.mail.mud.yahoo.com>
On Wed, Mar 16, 2011 at 5:39 AM, Mike Gran <spk121@yahoo.com> wrote:
>> From:Mark H Weaver <mhw@netris.org>
>>
>> Mike Gran <spk121@yahoo.com> writes:
>> > We do, in a matter of speaking, have a single string representation:
>> > UTF-32. The 'narrow' encoding is UTF-32 with the initial 3 bytes
>> of
>> > zero removed.
>>
>> Despite the similarity of these two representations, they are
>> sufficiently different that they cannot be handled by the same machine
>> code. That means you must either implement multiple inner loops, one
>> for each combination of string parameter representations, or else you
>> must dispatch on the string representation within the inner loop. On
>> modern architectures, wrongly predicted conditional branches are very
>> expensive.
>
> Keep in mind that the UTF-8 forward iterator operation has conditional
> branches. Merely the act of advancing from one character to another
> could take one of four paths, or more if you include the possibility
> of invalid UTF-8 sequences.
No, technically you don't need any branching:
/* first-byte lookup table encoded as an integer */
#define magic 3841982464uL
/* read a utf8 char and advance the pointer */
int read_utf8_char(char **pp) {
char *p = *pp;
int tmp, len, res = (unsigned char)*p++;
tmp = (res>>7);
/* tmp is 0 if len is 1, 1 otherwise */
len = (res>>4)*2;
len = tmp*(((magic&(3<<len))>>len)+1) + (1-tmp);
res = ((res<<len)&255)>>len;
res = (tmp*((res<<6)+(63&*p))) + (1-tmp)*res;
p += tmp;
tmp = (len-1)>>1;
/* tmp is 1 if len is 3,4 0 otherwise */
res = (tmp*((res<<6)+(63&*p))) + (1-tmp)*res;
p += tmp;
tmp = len>>2;
/* tmp is 1 if len is 4, 0 otherwise */
res = (tmp*((res<<6)+(63&*p))) + (1-tmp)*res;
p += tmp;
*pp = p;
return res;
}
It turns out this isn't worth it on x86 architectures.
Branch prediction is very fast. Either way, the
overhead tends to be dwarfed by whatever it is
you're doing _with_ the char.
--
Alex
next prev parent reply other threads:[~2011-03-16 0:22 UTC|newest]
Thread overview: 48+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-03-12 21:28 Using libunistring for string comparisons et al Mike Gran
2011-03-15 17:20 ` Mark H Weaver
2011-03-15 20:39 ` Mike Gran
2011-03-15 22:49 ` Mark H Weaver
2011-03-16 0:01 ` Mike Gran
2011-03-16 1:12 ` Mark H Weaver
2011-03-16 11:26 ` Ludovic Courtès
2011-03-17 15:38 ` Mark H Weaver
2011-03-17 15:56 ` Ludovic Courtès
2011-03-17 17:58 ` Mark H Weaver
2011-03-18 0:10 ` Thien-Thi Nguyen
2011-03-18 1:38 ` Mark H Weaver
2011-03-18 8:46 ` Thien-Thi Nguyen
2011-03-18 12:05 ` Mark H Weaver
2011-03-20 22:12 ` Ludovic Courtès
2011-03-30 10:14 ` Andy Wingo
2011-03-17 21:47 ` Ludovic Courtès
2011-03-19 12:31 ` Andy Wingo
2011-03-19 14:06 ` Mark H Weaver
2011-03-19 14:53 ` Noah Lavine
2011-03-19 15:49 ` Mark H Weaver
2011-03-19 15:08 ` Andy Wingo
2011-03-19 19:43 ` Mark H Weaver
2011-03-19 16:37 ` Mark H Weaver
2011-03-20 21:49 ` Ludovic Courtès
2011-03-30 9:50 ` Andy Wingo
2011-03-29 12:39 ` Peter Brett
2011-03-29 13:35 ` Andy Wingo
2011-03-29 21:15 ` Ludovic Courtès
2011-03-31 14:59 ` Peter Brett
2011-03-31 20:12 ` Ludovic Courtès
2011-03-30 9:33 ` Andy Wingo
2011-03-16 0:22 ` Alex Shinn [this message]
-- strict thread matches above, loose matches on Subject: below --
2011-03-17 18:07 Mike Gran
2011-03-16 15:22 Mike Gran
2011-03-16 16:58 ` Ludovic Courtès
2011-03-16 2:03 Mike Gran
2011-03-16 1:30 Mike Gran
2011-03-11 0:54 uc_tolower (uc_toupper (x)) Mike Gran
2011-03-11 22:33 ` Using libunistring for string comparisons et al Mark H Weaver
2011-03-11 22:36 ` Mark H Weaver
2011-03-11 23:09 ` Mark H Weaver
2011-03-12 13:46 ` Ludovic Courtès
2011-03-12 17:28 ` Mark H Weaver
2011-03-13 21:30 ` Ludovic Courtès
2011-03-30 9:05 ` Andy Wingo
2011-03-30 9:03 ` Andy Wingo
2011-03-31 14:19 ` Ludovic Courtès
2011-03-12 13:36 ` Ludovic Courtès
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
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=AANLkTinGRb4swGvgJLnL-Rij-RVvHv4Dw1nBe2xg4JYt@mail.gmail.com \
--to=alexshinn@gmail.com \
--cc=guile-devel@gnu.org \
--cc=ludo@gnu.org \
--cc=mhw@netris.org \
--cc=spk121@yahoo.com \
/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).