[Pharo-project] Fastest utf-8 encoder contest
Hi, hardcore hackers. please take a look at the code and tell if it can be improved. The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8 then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values). The idea is to make utf-8 encoding speed close to memory copying speed :) convertUnicode: asm " input: - EAX 32-bit unicode value to convert output: - EAX - utf-8 encoded character (in little-endian byte order) max 4 bytes - EDX - number of encoded bytes " | moreThanOne moreThanTwo moreThanThree end | moreThanOne := asm uniqueLabelName: 'moreThanOne'. moreThanTwo := asm uniqueLabelName: 'moreThanTwo'. moreThanThree := asm uniqueLabelName: 'moreThanThree'. end := asm uniqueLabelName: 'end'. asm cmp: asm EAX with: 16r7F; jg: moreThanOne; "one byte" mov: 1 to: asm EDX; jmp: end; label: moreThanOne; cmp: asm EAX with: 16r7FF; jg: moreThanTwo; "two bytes 80 .. 7FF" " AH AL " "00000aaa aabbbbbb" "110aaaaa 10bbbbbb AL AH (little endian order) " shr: asm EAX with: 2; shl: asm AL with: 2; or: asm AX with: 2r1100000010000000; xchg: asm AL with: asm AH; mov: 2 to: asm EDX; jmp: end; label: moreThanTwo; cmp: asm EAX with: 16rFFFF; jg: moreThanThree; "three bytes 800 ... FFFF" " AH AL " "aaaabbbb bbcccccc" " => 1110aaaa 10bbbbbb 10cccccc" shl: asm EAX with: 4; shr: asm AX with: 2; shr: asm AL with: 2; " EAX = ...aaaa xxbbbbbb xxcccccc " or: asm EAX with: 2r111000001000000010000000; "16rE08080" shl: asm EAX with: 8; bswap: asm EAX; mov: 3 to: asm EDX; jmp: end; "four bytes 1000 ... 10FFFF" " AH AL " "000aaabb bbbbcccc ccdddddd" "=> 11110aaa 10bbbbbb 10cccccc 10dddddd" mov: asm EAX to: asm EDX; shl: asm EAX with: 4; shr: asm AX with: 2; shr: asm AL with: 2; " EAX = 0000000a aabbbbbb xxcccccc xxdddddd " and: asm EAX with: 16r3F3F3F; bswap: asm EAX; shr: asm EDX with: 18; "6*3" or: asm DL with: 16r11110000; mov: asm DL to: asm AL; mov: 4 to: asm EDX; label: end -- Best regards, Igor Stasenko.
Hi Igor, It is very good that someone tries to optimize this, it is a weak point currently, performance wise. I am not a low-level guy, so I can't really help with the assembler code. But utf-8 encoding/decoding is an area that interests me. I can point to the 2 currently available utf-8 encoders/decoders that I know of, as this might be instructive for your quest (provided you did not already know of them): UTF8TextConverter ZnUTF8Encoder In Seaside, there is some optimization code in GRPharoUtf8CodecStream>>#encodeFast: that avoids encoding for runs of Latin1 characters. HTH, Sven On 13 Jun 2012, at 04:44, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
convertUnicode: asm " input: - EAX 32-bit unicode value to convert
output: - EAX - utf-8 encoded character (in little-endian byte order) max 4 bytes - EDX - number of encoded bytes " | moreThanOne moreThanTwo moreThanThree end |
moreThanOne := asm uniqueLabelName: 'moreThanOne'. moreThanTwo := asm uniqueLabelName: 'moreThanTwo'. moreThanThree := asm uniqueLabelName: 'moreThanThree'. end := asm uniqueLabelName: 'end'.
asm cmp: asm EAX with: 16r7F; jg: moreThanOne; "one byte" mov: 1 to: asm EDX; jmp: end; label: moreThanOne; cmp: asm EAX with: 16r7FF; jg: moreThanTwo; "two bytes 80 .. 7FF" " AH AL " "00000aaa aabbbbbb"
"110aaaaa 10bbbbbb AL AH (little endian order) " shr: asm EAX with: 2; shl: asm AL with: 2; or: asm AX with: 2r1100000010000000; xchg: asm AL with: asm AH; mov: 2 to: asm EDX; jmp: end; label: moreThanTwo; cmp: asm EAX with: 16rFFFF; jg: moreThanThree; "three bytes 800 ... FFFF" " AH AL " "aaaabbbb bbcccccc" " => 1110aaaa 10bbbbbb 10cccccc" shl: asm EAX with: 4; shr: asm AX with: 2; shr: asm AL with: 2; " EAX = ...aaaa xxbbbbbb xxcccccc " or: asm EAX with: 2r111000001000000010000000; "16rE08080" shl: asm EAX with: 8; bswap: asm EAX; mov: 3 to: asm EDX; jmp: end; "four bytes 1000 ... 10FFFF" " AH AL " "000aaabb bbbbcccc ccdddddd" "=> 11110aaa 10bbbbbb 10cccccc 10dddddd" mov: asm EAX to: asm EDX; shl: asm EAX with: 4; shr: asm AX with: 2; shr: asm AL with: 2; " EAX = 0000000a aabbbbbb xxcccccc xxdddddd " and: asm EAX with: 16r3F3F3F; bswap: asm EAX; shr: asm EDX with: 18; "6*3" or: asm DL with: 16r11110000; mov: asm DL to: asm AL; mov: 4 to: asm EDX; label: end
-- Best regards, Igor Stasenko.
On Jun 13, 2012, at 10:07 AM, Sven Van Caekenberghe wrote:
Hi Igor,
It is very good that someone tries to optimize this, it is a weak point currently, performance wise.
I am not a low-level guy, so I can't really help with the assembler code. But utf-8 encoding/decoding is an area that interests me.
I can point to the 2 currently available utf-8 encoders/decoders that I know of, as this might be instructive for your quest (provided you did not already know of them):
UTF8TextConverter ZnUTF8Encoder
In Seaside, there is some optimization code in
GRPharoUtf8CodecStream>>#encodeFast:
We shoud standardize on *one* converter... what is the use of everyone doing it again? Marcus -- Marcus Denker -- http://marcusdenker.de
On 13 Jun 2012, at 10:29, Marcus Denker wrote:
We shoud standardize on *one* converter... what is the use of everyone doing it again?
Ultimately, yes, there should be one. However, it does not hurt that multiple people are working on the same subject even if that sometimes means multiple implementations coexist in one image. It is one of the ways that open source software advances. As for my rationale for ZnUTF8Encoder: http://zn.stfx.eu/zn/zinc-http-components-paper.html#characterencoding << ZnCharacterEncoding is an extension and reimplementation of regular TextConverter. It only works on binary input and generated binary output. It adds the ability to compute the encoded length of a source character, a crucial operation for HTTP. It is more correct and will throw proper exceptions when things go wrong. >> Throwing out and replacing fundamental system classes is hard. New designs often are not 100% API compatible or change the semantics, on purpose. Look at the #isBinary test in UTF8TextConverter>>nextFromStream and nextPut:toStream, it is so broken. Can it be fixed ? I don't know. Sven -- Sven Van Caekenberghe http://stfx.eu Smalltalk is the Red Pill
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
In Seaside we use an other trick that Andreas Raab come up with. The assumption is that most of the strings are ASCII [1]. We use a CharSet / bitmap to quickly scan the string for the index of the first non-ASCII character. If we find none we just answer the argument. No copying at all. In Seaside 3.1 we go one step further. Imagine you have a long ByteString and only few non-ASCII characters. We do not want to have to copy the whole string just to utf-8 encode a few characters, so we combine the above approach with #next:putAll:startingAt: so that we only have to encode and copy the non-ASCII characters, everything else is not copied. I have become quite paranoid about allocation in Pharo. If I can remove about two or three #streamContents: I can get about 100 to 200 req/s more. [1] This seems to be true for the rendering code in Seaside since it renders many small snippets. Even if you have several non-ASCII strings on a page since each string is rendered individually all the rest will still be ASCII. Cheers Philippe
On 13.06.2012 10:31, Philippe Marschall wrote:
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
In Seaside 3.1 we go one step further. Imagine you have a long ByteString and only few non-ASCII characters. We do not want to have to copy the whole string just to utf-8 encode a few characters, so we combine the above approach with #next:putAll:startingAt: so that we only have to encode and copy the non-ASCII characters, everything else is not copied.
Cheers Philippe
Both Pharo and Squeak default TextConverters have done something similar for the last 1 1/2 years, see (in Pharo) nextPutByteString:toSteam: What Igor describes seems aimed at encoding WideString -> utf8 though, which is still slow with the default converters. As to the assembly, is leadingChar gone entirely? Otherwise the branching may fail miserably. Cheers, Henry
On 06/13/2012 11:40 AM, Henrik Sperre Johansen wrote:
On 13.06.2012 10:31, Philippe Marschall wrote:
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
In Seaside 3.1 we go one step further. Imagine you have a long ByteString and only few non-ASCII characters. We do not want to have to copy the whole string just to utf-8 encode a few characters, so we combine the above approach with #next:putAll:startingAt: so that we only have to encode and copy the non-ASCII characters, everything else is not copied.
Cheers Philippe
Both Pharo and Squeak default TextConverters have done something similar for the last 1 1/2 years, see (in Pharo) nextPutByteString:toSteam:
Yes, it's the name approach apart from that our converters also support #next:putAll:startingAt:. We use the same approach for quick HTML and URL encoding so these converters feed into the utf-8 converter. Cheers Philippe
On 13 June 2012 11:40, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote:
On 13.06.2012 10:31, Philippe Marschall wrote:
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
In Seaside 3.1 we go one step further. Imagine you have a long ByteString and only few non-ASCII characters. We do not want to have to copy the whole string just to utf-8 encode a few characters, so we combine the above approach with #next:putAll:startingAt: so that we only have to encode and copy the non-ASCII characters, everything else is not copied.
Cheers Philippe
Both Pharo and Squeak default TextConverters have done something similar for the last 1 1/2 years, see (in Pharo) nextPutByteString:toSteam: What Igor describes seems aimed at encoding WideString -> utf8 though, which is still slow with the default converters.
As to the assembly, is leadingChar gone entirely? Otherwise the branching may fail miserably.
yes. In Pharo, leadingchar == 0 is unicode. of course i can add another branch to check if unicode value is greater than 16r10FFFF and just fail primitive if it is.
Cheers, Henry
-- Best regards, Igor Stasenko.
On 13 June 2012 10:31, Philippe Marschall <philippe.marschall@netcetera.ch> wrote:
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
In Seaside we use an other trick that Andreas Raab come up with. The assumption is that most of the strings are ASCII [1]. We use a CharSet / bitmap to quickly scan the string for the index of the first non-ASCII character. If we find none we just answer the argument. No copying at all.
Well, in my case i will need copying because i need to null-terminate it, to represent it as null-terminated string. This is what cairo library expects as input for rendering text. And this also means that i can use a single buffer for conversions to avoid generating garbage, i.e. i take input string, convert it to utf8 in private buffer, then pass that buffer as input to external call, on next call an input can be any other string, but output will be the same private buffer. I will be needing to allocate new buffer if incoming string does not fits into it.
In Seaside 3.1 we go one step further. Imagine you have a long ByteString and only few non-ASCII characters. We do not want to have to copy the whole string just to utf-8 encode a few characters, so we combine the above approach with #next:putAll:startingAt: so that we only have to encode and copy the non-ASCII characters, everything else is not copied.
I have become quite paranoid about allocation in Pharo. If I can remove about two or three #streamContents: I can get about 100 to 200 req/s more.
 [1] This seems to be true for the rendering code in Seaside since it renders many small snippets. Even if you have several non-ASCII strings on a page since each string is rendered individually all the rest will still be ASCII.
Cheers Philippe
-- Best regards, Igor Stasenko.
On 06/13/2012 02:59 PM, Igor Stasenko wrote:
On 13 June 2012 10:31, Philippe Marschall <philippe.marschall@netcetera.ch> wrote:
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
In Seaside we use an other trick that Andreas Raab come up with. The assumption is that most of the strings are ASCII [1]. We use a CharSet / bitmap to quickly scan the string for the index of the first non-ASCII character. If we find none we just answer the argument. No copying at all.
Well, in my case i will need copying because i need to null-terminate it, to represent it as null-terminated string. This is what cairo library expects as input for rendering text. And this also means that i can use a single buffer for conversions to avoid generating garbage, i.e. i take input string, convert it to utf8 in private buffer, then pass that buffer as input to external call, on next call an input can be any other string, but output will be the same private buffer. I will be needing to allocate new buffer if incoming string does not fits into it.
I see, different use case. Cheers Philippe
On 13.06.2012 14:59, Igor Stasenko wrote:
On 13 June 2012 10:31, Philippe Marschall <philippe.marschall@netcetera.ch> wrote:
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :) In Seaside we use an other trick that Andreas Raab come up with. The assumption is that most of the strings are ASCII [1]. We use a CharSet / bitmap to quickly scan the string for the index of the first non-ASCII character. If we find none we just answer the argument. No copying at all.
Well, in my case i will need copying because i need to null-terminate it, to represent it as null-terminated string. This is what cairo library expects as input for rendering text. And this also means that i can use a single buffer for conversions to avoid generating garbage, i.e. i take input string, convert it to utf8 in private buffer, then pass that buffer as input to external call, on next call an input can be any other string, but output will be the same private buffer. I will be needing to allocate new buffer if incoming string does not fits into it. So, is this a one-off for Cairo, or are you planning on introducing a <var: #myStringParameter encoding: #utfXX> pragma or something to NBFFI?
Because, on Windows system calls either expect the local system code page, or utf16 (depending on which version of the API you use), while the in other libraries the expected encoding may be different from the one of the system libraries. Heck, the same lib may expect different encodings, case in point: The expected encoding of the Oracle client lib (and by extension DBXTalk*) depends on either an environment variable, what you told it to expect using an API function, or one of many other fallbacks I can't remember at the moment. Cheers, Henry *<rant> OpenDBX makes an explicity choice to simply pass the data you hand it over to whatever backend you have hooked up raw. Very nice of a library that does a good job of abstracting the actual API of communicating with a database to leave it up to you to decide which encoding to use (which depends on the abstracted away backend...) if you want your data stored correctly... There is a reason those benchmarks are fast! :) </rant>
On 14 June 2012 14:05, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote:
On 13.06.2012 14:59, Igor Stasenko wrote:
On 13 June 2012 10:31, Philippe Marschall <philippe.marschall@netcetera.ch> Â wrote:
On 06/13/2012 04:44 AM, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
In Seaside we use an other trick that Andreas Raab come up with. The assumption is that most of the strings are ASCII [1]. We use a CharSet / bitmap to quickly scan the string for the index of the first non-ASCII character. If we find none we just answer the argument. No copying at all.
Well, in my case i will need copying because i need to null-terminate it, to represent it as null-terminated string. This is what cairo library expects as input for rendering text. And this also means that i can use a single buffer for conversions to avoid generating garbage, i.e. i take input string, convert it to utf8 in private buffer, then pass that buffer as input to external call, on next call an input can be any other string, but output will be the same private buffer. I will be needing to allocate new buffer if incoming string does not fits into it.
So, is this a one-off for Cairo, or are you planning on introducing a <var: #myStringParameter encoding: #utfXX> pragma or something to NBFFI?
Well, there is utf-8 encoder in examples, see NBUTF8StringExample which converts WideString to utf-8 encoded string on stack, and then that string is passed as argument to external function. The drawback of this approach is that results of conversion is not accessible from language side, they are visible only to external function and once call is made, it is gone.
Because, on Windows system calls either expect the local system code page, or utf16 (depending on which version of the API you use), while the in other libraries the expected encoding may be different from the one of the system libraries.
Yes, but those will require many different conversion algorithms.. But i am not interested in making a general-purpose (our world)->all possible encodings converters right now. I just wanna make fast utf-8 encoder for things i am working on :)
Heck, the same lib may expect different encodings, case in point: The expected encoding of the Oracle client lib (and by extension DBXTalk*) depends on either an environment variable, what you told it to expect using an API function, or one of many other fallbacks I can't remember at the moment.
Cheers, Henry
*<rant> OpenDBX makes an explicity choice to simply pass the data you hand it over to whatever backend you have hooked up raw. Very nice of a library that does a good job of abstracting the actual API of communicating with a database to leave it up to you to decide which encoding to use (which depends on the abstracted away backend...) if you want your data stored correctly... There is a reason those benchmarks are fast! :) </rant>
-- Best regards, Igor Stasenko.
Btw, if you want to optimize for shorter-encodings, couldn't you do asm cmp: asm EAX with: 16r80; jl: oneByte; cmp: asm EAX with: 16r800; jl: twoBytes; cmp: asm EAX with:16r1000; jl: threeBytes; label: fourBytes; ... jmp end; label: threeBytes; ... jmp end; label: twoBytes; ... jmp: end; label: oneByte; label: end ie only one cmp/jmp for 1-byte chars (1 less jump than current), and n cmp/2 jmp's for n > 1. Or do the conditional jumps relying on last instruction stall enough that it doesn't really matter? Cheers, Henry On 13.06.2012 04:44, Igor Stasenko wrote:
Hi, hardcore hackers. please take a look at the code and tell if it can be improved.
The AsmJit snippet below transforms an unicode integer value to 1..4-byte sequence of utf-8
then the outer piece of code (which is not yet written) will accumulate the results of this snippet to do a memory-aligned (4byte) writes.. like that, if 4 unicode characters can be encoded into 4 utf-8 bytes (which mostly the case for latin-1 char range), then there will be 4 memory reads (to read four 32-bit unicode values) but only single memory write (to write four 8-bit utf-8 encoded values).
The idea is to make utf-8 encoding speed close to memory copying speed :)
convertUnicode: asm " input: - EAX 32-bit unicode value to convert
output: - EAX - utf-8 encoded character (in little-endian byte order) max 4 bytes - EDX - number of encoded bytes " | moreThanOne moreThanTwo moreThanThree end |
moreThanOne := asm uniqueLabelName: 'moreThanOne'. moreThanTwo := asm uniqueLabelName: 'moreThanTwo'. moreThanThree := asm uniqueLabelName: 'moreThanThree'. end := asm uniqueLabelName: 'end'.
asm cmp: asm EAX with: 16r7F; jg: moreThanOne; "one byte" mov: 1 to: asm EDX; jmp: end; label: moreThanOne; cmp: asm EAX with: 16r7FF; jg: moreThanTwo; "two bytes 80 .. 7FF" " AH AL " "00000aaa aabbbbbb"
"110aaaaa 10bbbbbb AL AH (little endian order) " shr: asm EAX with: 2; shl: asm AL with: 2; or: asm AX with: 2r1100000010000000; xchg: asm AL with: asm AH; mov: 2 to: asm EDX; jmp: end; label: moreThanTwo; cmp: asm EAX with: 16rFFFF; jg: moreThanThree; "three bytes 800 ... FFFF" " AH AL " "aaaabbbb bbcccccc" " => 1110aaaa 10bbbbbb 10cccccc" shl: asm EAX with: 4; shr: asm AX with: 2; shr: asm AL with: 2; " EAX = ...aaaa xxbbbbbb xxcccccc " or: asm EAX with: 2r111000001000000010000000; "16rE08080" shl: asm EAX with: 8; bswap: asm EAX; mov: 3 to: asm EDX; jmp: end; "four bytes 1000 ... 10FFFF" " AH AL " "000aaabb bbbbcccc ccdddddd" "=> 11110aaa 10bbbbbb 10cccccc 10dddddd" mov: asm EAX to: asm EDX; shl: asm EAX with: 4; shr: asm AX with: 2; shr: asm AL with: 2; " EAX = 0000000a aabbbbbb xxcccccc xxdddddd " and: asm EAX with: 16r3F3F3F; bswap: asm EAX; shr: asm EDX with: 18; "6*3" or: asm DL with: 16r11110000; mov: asm DL to: asm AL; mov: 4 to: asm EDX; label: end
On 21 June 2012 16:59, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote:
Btw, if you want to optimize for shorter-encodings, couldn't you do asm   cmp: asm EAX with: 16r80;   jl: oneByte;   cmp: asm EAX with: 16r800;   jl: twoBytes;   cmp: asm EAX with:16r1000;   jl: threeBytes;   label: fourBytes;   ...   jmp end;   label: threeBytes;   ...   jmp end;   label: twoBytes;   ...   jmp: end;   label: oneByte;
  label: end
ie only one cmp/jmp for 1-byte chars (1 less jump than current), and n cmp/2 jmp's for n > 1.
Haha, nice trick.
Or do the conditional jumps relying on last instruction stall enough that it doesn't really matter?
Can't say.. benchmarks should demonstrate that, but guess 1 less jump speedup will be at the level of noise. I'm not even sure that doing 4-byte aligned memory writes will get over noise level :)
Cheers, Henry
-- Best regards, Igor Stasenko.
participants (5)
-
Henrik Sperre Johansen -
Igor Stasenko -
Marcus Denker -
Philippe Marschall -
Sven Van Caekenberghe