On 21.09.2011 18:47, Christophe wrote:
Actually, I don't buy it. I guess the reason it's faster is that it
doesn't check if the codepoint is valid.
Why should it ? The documentation of std.utf.count says the string must
be validly encoded, not that it will enforce that it is.
Checking a string is valid everytime you use it would be very expensive.
Actually, std.range.walkLength does not check the sequence is valid. See
this test:
void main()
{
string text = "aléluyah";
char[] text2 = text.dup;
text2[3] = 'a';
writeln(walkLength(text2)); // outputs: 8
writeln(text2); // outputs: al\303aluyah
}
Ouch, the checking is apparently very loosy.
There is probably a way to check an utf sequence is valid with an
unrollable loop.
In fact you can easily get ridiculous overflowed "negative" lengths.
Maybe we can put it here as unsafe and fast version though.
Unless I am mistaken, the minimum length myCount can return is 0 even
if the string is invalid.
Yeah, a brain malfunction on my part.
Also check std.utf.stride to see if you can get it better, it's the
beast behind narrow string popFront.
stride does not make much checking. It can even return 5 or 6, which is
not possible for a valid utf-8 string !
The equivalent of myCount to stride would be:
size_t myStride(char c)
{
// optional:
// if ( (((c>>7)+1)>>1) - (((c>>6)+1)>>2) + (((c>>3)+1)>>5))
// throw new UtfException("Not the start of the UTF-8 sequence");
return 1 + (((c>>6)+1)>>2) + (((c>>5)+1)>>3) + (((c>>4)+1)>>4);
}
That I compared to:
size_t utfLikeStride(char c)
{
// optional:
// immutable result = UTF8stride[c];
// if (result == 0xFF)
// throw new UtfException("Not the start of the UTF-8 sequence");
// return result;
return UTF8stride[c];
}
One table lookup is replaced by byte some arythmetic in myStride.
I also took only one char as input, since stride only looked at the i-th
character. Actually, if stride signature is kept to uint "stride(char[]
s, int i)", I did not find any change with -O3.
Average times for "a lot" of calls:
(compiled with gcc, tested with -O3 and a homogenous distribution of
"valid" characters from '\x00'..'\x7F' and '\xC2'..'\xF4')
myStride no throws: 1112ms.
utfLikeStride no throws: 1433ms.
utfLikeStride throws: 1868ms. (the current implementation).
myStride throws: 8269ms.
I wonder what impact may have if any changing 0xff to 0x00 in
implementation of utfLikeStride. It should amount to cmp vs test, not
sure if it matters much.
Removing throws from utfLikeStride makes it about 25% faster.
Removing throws from myStride makes it about 7 times faster.
With -O0, myStride gets less 10% slower than utfLikeStride (no throws).
In conclusion, the fastest implementation is myStride without throws,
and it beats the current implementation by about 40%. Changing
std.utf.stride may be desirable. As I said earlier, the throws do
not enforce the validity of the string. Really checking the validity of
the string would cost much more, which may not be desirable, so why
bother checking at all?
The truth is I'd checked this in the past (though I used some bsr black
magic) and if I kept check in place the end result was always slower
then current. But since the check is not very accurate anyway, maybe it
can be replaced. It's problematic if some code happen to depend on it.
(given the doc it should not)
> A more serious benchmark could justify to change
> std.utf.stride. The improvement could be even better in real situation,
> because the lookup table of utfLikeStride may not be always at hand -
> this actually really depends on what the compiler does.
>
Yes and no, I think it would be hard to find app that bottlenecks at
traversing UTF, on decoding - maybe. Generally if you do a lot calls to
stride it's in cache, if not it doesn't matter much(?). Though I'd
prefer non-tabulated version
In any case, this may not improve walkLength by more than a few
percents.
Then specializing walkLength to do your unrollable version seems like
good idea.
--
Dmitry Olshansky
