flaming vs accuracy [was Re: Performance of int/long in Python 3]
Neil Hodgson
nhodgson at iinet.net.au
Thu Mar 28 23:34:27 EDT 2013
Steven D'Aprano:
> Some string operations need to inspect every character, e.g. str.upper().
> Even for them, the increased complexity of a variable-width encoding
> costs. It's not sufficient to walk the string inspecting a fixed 1, 2 or
> 4 bytes per character. You have to walk the string grabbing 1 byte at a
> time, and then decide whether you need another 1, 2 or 3 bytes. Even
> though it's still O(N), the added bit-masking and overhead of variable-
> width encoding adds to the overall cost.
It does add to implementation complexity but should only add a small
amount of time.
To compare costs, I am using the text of the web site
http://www.mofa.go.jp/mofaj/ since it has a reasonable amount (10%) of
multi-byte characters. Since the document fits in the the BMP, Python
would choose a 2-byte wide implementation so I am emulating that choice
with a very simple 16-bit table-based upper-caser. Real Unicode case
conversion code is more concerned with edge cases like Turkic and
Lithuanian locales and Greek combining characters and also allowing for
measurement/reallocation for the cases where the result is
smaller/larger. See, for example, glib's real_toupper in
https://git.gnome.org/browse/glib/tree/glib/guniprop.c
Here is some simplified example code that implements upper-casing
over 16-bit wide (utf16_up) and UTF-8 (utf8_up) buffers:
http://www.scintilla.org/UTF8Up.cxx
Since I didn't want to spend too much time writing code it only
handles the BMP and doesn't have upper-case table entries outside ASCII
for now. If this was going to be worked on further to be made
maintainable, most of the masking and so forth would be in macros
similar to UTF8_COMPUTE/UTF8_GET in glib.
The UTF-8 case ranges from around 5% slower on average in a 32 bit
release build (VC2012 on an i7 870) to averaging a little faster in a
64-bit build. They're both around a billion characters per-second.
C:\u\hg\UpUTF\UpUTF>..\x64\Release\UpUTF.exe
Time taken for UTF8 of 80449=0.006528
Time taken for UTF16 of 71525=0.006610
Relative time taken UTF8/UTF16 0.987581
> Any string method that takes a starting offset requires the method to
> walk the string byte-by-byte. I've even seen languages put responsibility
> for dealing with that onto the programmer: the "start offset" is given in
> *bytes*, not characters. I don't remember what language this was... it
> might have been Haskell? Whatever it was, it horrified me.
It doesn't horrify me - I've been working this way for over 10 years
and it seems completely natural. You can wrap access in iterators that
hide the byte offsets if you like. This then ensures that all operations
on those iterators are safe only allowing the iterator to point at the
start/end of valid characters.
> Sure. And over a different set of samples, it is less compact. If you
> write a lot of Latin-1, Python will use one byte per character, while
> UTF-8 will use two bytes per character.
I think you mean writing a lot of Latin-1 characters outside ASCII.
However, even people writing texts in, say, French will find that only a
small proportion of their text is outside ASCII and so the cost of UTF-8
is correspondingly small.
The counter-problem is that a French document that needs to include
one mathematical symbol (or emoji) outside Latin-1 will double in size
as a Python string.
Neil
More information about the Python-list
mailing list