Re: FOX Development release available!

On Wed, 19 Oct 2022 17:07:20 -0500
Sander Jansen <[email protected]> wrote:

>That's a lot of breaking API changes in FXString, eg compare, comparecase,
>compareversion.
>
>Any reason why FXString::extent was removed? It was quite useful when
>looping through a string:
>
>for (int i=0; i<str.length();i=str.inc(i)) {
>   // do something with length...
>   utf8_length = str.extent(i)
>}

Some new UTF8 and UTF16 processing functions have been housed in a 
new file, fxchar.h.  Most are now inlined, which means if you've
got them in loops, branch-prediction works in your favor making
them almost as cheap as ascii.

The utfBytes[] (used in the old extent() API) array was deleted, in favor of 
inlined API:

	lenUTF8(ch)

this returns #bytes of utf8 sequence whose leading byte is ch. 

Tests show lenUTF8() to be very competitive against the old technique;
its advantage is that no memory accesses are required, and only
a few fast, portable, integer operations are required.  The array
is only small, and would fit into 4 cachelines.  The thing is that
one would have to either hold the base address in a register, and
thus lose it for other work.  The new implementation doesn't suffer
from this, it can be calculated using a single register.

We also added inlines to walk utf8 strings one encoded character
at a time, in BOTH directions:

Ascii:

	c = *ptr++;

or:
	c = *--ptr;

In utf8:

	w = wcnxt(ptr);		// Pointer is incremented up to 4 bytes, left at start of next utf8 character leader

or:

	w = wcprv(ptr);		// Pointer is decremented up to 4 bytes, left at start of previous utf8 character leader


New APIs in FXString:

	w = string.wcnxt(pos);

or:

	w= string.wcprv(pos);


For most efficient way ploughing through utf8 (and presumably
doing something with the wide character...):


	while((w=wcnxt(ptr))!=0){
          do_something(w);
	}

or:


	while(ptr<end){
	  w=wcnxt(ptr);
          do_something(w);
	}


Its all inlined. Processor branch-prediction being what it is, performance will
be almost indistinguishable from ploughing through plain ascii.

There are some tests in "codecs.cpp" which have various methods square off 
against each other.  Now, FYI, which one wins may depend on your processor,
intel or amd, or completely different architectures, like ARMv8, and so on. 

[ascii-chauvinist hat on] Of course, lots of source code and text files are
ascii, or largely ascii [1- or 2-byte utf8].  So we want to "optimize for
the common case" as they say.

So, random unicode (encoded as utf8) up to 1 byte (0...7Fh):

wcnxt: 143,487,276 ticks 99,999,997 chars 1.43 ticks/char
wcprv: 71,569,252 ticks 99,999,997 chars 0.72 ticks/char

for random unicode, up to 2-byte (0...7FFh)

wcinc: 155,236,316 ticks 51,614,426 chars 3.01 ticks/char
wcdec: 142,938,346 ticks 51,614,426 chars 2.77 ticks/char

for random unicode, up to 3-byte (0...FFFFh)

wcnxt: 330,586,624 ticks 33,706,645 chars 9.81 ticks/char
wcprv: 309,453,380 ticks 33,706,645 chars 9.18 ticks/char

And finally, random unicode up to 4-byte (0...1FFFFFh):

wcnxt: 250,880,220 ticks 25,385,543 chars 9.88 ticks/char
wcprv: 233,058,542 ticks 25,385,543 chars 9.18 ticks/char

Finally, random unicode, with equal probability of 1, 2,
3, or 4 byte sequences. Clearly, this is MURDER on the 
processor's branch-predictor. 
It represents more or less worst-case behaviour:

wcnxt: 538,757,812 ticks 40,001,678 chars 13.47 ticks/char
wcprv: 533,908,052 ticks 40,001,678 chars 13.35 ticks/char


Note, the above timings are advancing through the text
while at the same time converting the utf8 to wide character.
[All timings on Ryzen 5950x CPU].

We have timing for plain stepping as well:

1-bytes:
wcinc: 143,809,188 ticks 99,999,997 chars 1.44 ticks/char
wcdec: 122,264,476 ticks 99,999,997 chars 1.22 ticks/char

up to 2-bytes:
wcinc: 153,547,740 ticks 51,611,872 chars 2.98 ticks/char
wcdec: 140,670,342 ticks 51,611,872 chars 2.73 ticks/char

up to 3-bytes:
wcinc: 114,562,626 ticks 33,706,481 chars 3.40 ticks/char
wcdec: 113,721,602 ticks 33,706,481 chars 3.37 ticks/char

up to 4-bytes:
wcinc: 128,525,610 ticks 25,385,131 chars 5.06 ticks/char
wcdec: 103,937,150 ticks 25,385,131 chars 4.09 ticks/char

and worst case equal probability 1,2,3, or 4-byte:
wcinc: 579,145,358 ticks 40,000,467 chars 14.48 ticks/char
wcdec: 585,145,712 ticks 40,000,467 chars 14.63 ticks/char

Clearly, the worst-case suffers from branch-unpredictability.

European languages basically fall into 1- and 2-byte utf8
and thus I believe this code well perform quite well.

NB. the test program has other algorithms; my favorite 
ones:

// Turns out this is the best one (when NO branch predict)
static inline void inc3(const FXchar*& ptr){
  FXival c=(FXuchar)*ptr;
  ptr-=((191-c)>>63)+((223-c)>>63)+((239-c)>>63)-1;
  }


// Turns out this is the best one (when NO branch predict)
static inline void inc4(const FXchar*& ptr){
  FXuchar c=*ptr;
  ptr+=(((0xE5000000>>((c>>4)<<1))&3)+1);
  }


These two perform the best when thrown against worst-case
input [uniformly selected 1,2,3,4 byte sequences].  They
fare less well against pure ascii: they always have the
same performance.

In practice, the convert-and-step methods are very decent,
for when utf8 needs to be processed one utf8 character at
a time, and plain byte-by-byte processing is not an option.



>Is comparenatural functional equivalent to compareversion?

The new comparenatural() sorting function is absolutely superb!


	Cheers,

			-- JVZ



-- 
+----------------------------------------------------------------------------+
| Copyright (C) 18:00 10/19/2022 Jeroen van der Zijp.   All Rights Reserved. |
+----------------------------------------------------------------------------+