[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Using libunistring for string comparisons et al
From: |
Alex Shinn |
Subject: |
Re: Using libunistring for string comparisons et al |
Date: |
Wed, 16 Mar 2011 09:22:20 +0900 |
On Wed, Mar 16, 2011 at 5:39 AM, Mike Gran <address@hidden> wrote:
>> From:Mark H Weaver <address@hidden>
>>
>> Mike Gran <address@hidden> 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
- Re: Using libunistring for string comparisons et al, (continued)
- Re: Using libunistring for string comparisons et al, Mark H Weaver, 2011/03/19
- Re: Using libunistring for string comparisons et al, Mark H Weaver, 2011/03/19
- Re: Using libunistring for string comparisons et al, Ludovic Courtès, 2011/03/20
- Re: Using libunistring for string comparisons et al, Andy Wingo, 2011/03/30
- Re: Using libunistring for string comparisons et al, Peter Brett, 2011/03/29
- Re: Using libunistring for string comparisons et al, Andy Wingo, 2011/03/29
- Re: Using libunistring for string comparisons et al, Ludovic Courtès, 2011/03/29
- Re: Using libunistring for string comparisons et al, Peter Brett, 2011/03/31
- Re: Using libunistring for string comparisons et al, Ludovic Courtès, 2011/03/31
- Re: Using libunistring for string comparisons et al, Andy Wingo, 2011/03/30
- Re: Using libunistring for string comparisons et al,
Alex Shinn <=
Re: Using libunistring for string comparisons et al, Mike Gran, 2011/03/15
Re: Using libunistring for string comparisons et al, Mike Gran, 2011/03/15
Re: Using libunistring for string comparisons et al, Mike Gran, 2011/03/16
Re: Using libunistring for string comparisons et al, Mike Gran, 2011/03/17