Profiling of a Fedora 14 "yum install *" showed it spending 80 seconds out of 274 within its implementation of "str_eq" (24 million calls), so optimizing this seems worthwhile.
One possibility is to hand-optimize this in C, or use Cython.
As a first step, attached are some more selftests for kitchen's [1] implementation of this function, to try to better capture some of the expected behavior.
What's the expected behavior, if any, of passing in objects that aren't str or unicode?
e.g. passing in a float
str_eq(0.1, 0.1)
True
Is it acceptable if, say it, raises a TypeError instead?
Do you need support for objects that are derived from str/unicode as well as those specific classes?
Hope this is helpful Dave
On Tue, Aug 24, 2010 at 06:28:06PM -0400, David Malcolm wrote:
Profiling of a Fedora 14 "yum install *" showed it spending 80 seconds out of 274 within its implementation of "str_eq" (24 million calls), so optimizing this seems worthwhile.
One possibility is to hand-optimize this in C, or use Cython.
As a first step, attached are some more selftests for kitchen's [1] implementation of this function, to try to better capture some of the expected behavior.
I reworked these to use the standard data that's part of that particular test class and reorganized them to put the emphasis on bytes vs unicode instead of ascii vs non-ascii which just confuses things.
Thanks for organizing the matrix of what to test.
What's the expected behavior, if any, of passing in objects that aren't str or unicode?
e.g. passing in a float
str_eq(0.1, 0.1)
True
Is it acceptable if, say it, raises a TypeError instead?
Do you need support for objects that are derived from str/unicode as well as those specific classes?
I'm not sure what the expected behaviour for yum is. For the to_bytes and to_unicode kitchen code, this is configurable with the default being to return the simplerepr (basically, str but without throwing an error if there's a problem).
I'm not sure that's what we want to do here, though -- str_eq is not explicitly a converter between bytes and unicode. It's a test for equality. Two objects could return the same (or different) simplereprs and still be different (or the same). So TypeError seems like a better default. However, throwing a TypeError requires more isinstance calls which may be counter to your goal of speeding this up.
Right now, I'd say the behaviour of passing in non-basestring objects could be documented as undefined.
-Toshio
On Tue, 2010-08-24 at 18:28 -0400, David Malcolm wrote:
btw, that sounds like a really useful project.
Jon.
On Tue, 2010-08-24 at 18:28 -0400, David Malcolm wrote:
Profiling of a Fedora 14 "yum install *" showed it spending 80 seconds out of 274 within its implementation of "str_eq" (24 million calls), so optimizing this seems worthwhile.
(replying to self, sorry)
I added some instrumentation to my copy of yum/i18n.py:
str_eq_calls = {} def str_eq(a, b): """ convert between unicode and not and compare them, w/o warning or being annoying""" typesig = (type(a), type(b)) if typesig in str_eq_calls: str_eq_calls[typesig] += 1 else: str_eq_calls[typesig] = 1 (rest of function follows)
to capture the type signature of all of these calls, adding: from yum.i18n import str_eq_calls from pprint import pprint pprint(str_eq_calls) to yummain.py, to dump the stats on output.
The output indicates that in this case at least [1], all of the calls are for the str vs str case:
{(<type 'str'>, <type 'str'>): 24274562}
So it seems to me to be worth optimizing for this case (24 million calls, taking 29% of user time on a warm cache). I can try to cook something up in .c or Cython, if this would be acceptable to the yum/kitchen maintainers?
[snip]
Dave
[1] Fedora 14 x86_64, yum-3.2.27-19.fc14.noarch python-2.7-7.fc14.x86_64 "yum install *" on a test box inside RH's test lab with various test repositories enabled
On Tue, Aug 24, 2010 at 08:14:11PM -0400, David Malcolm wrote:
On Tue, 2010-08-24 at 18:28 -0400, David Malcolm wrote:
Profiling of a Fedora 14 "yum install *" showed it spending 80 seconds out of 274 within its implementation of "str_eq" (24 million calls), so optimizing this seems worthwhile.
(replying to self, sorry)
I added some instrumentation to my copy of yum/i18n.py:
str_eq_calls = {} def str_eq(a, b): """ convert between unicode and not and compare them, w/o warning or being annoying""" typesig = (type(a), type(b)) if typesig in str_eq_calls: str_eq_calls[typesig] += 1 else: str_eq_calls[typesig] = 1 (rest of function follows)
to capture the type signature of all of these calls, adding: from yum.i18n import str_eq_calls from pprint import pprint pprint(str_eq_calls) to yummain.py, to dump the stats on output.
The output indicates that in this case at least [1], all of the calls are for the str vs str case:
{(<type 'str'>, <type 'str'>): 24274562}
Hah! So there's a few things that we should think about here:
* We're dealing almost exclusively with byte strings here. * This function exists because we must occassionally get unicode strings * I count exactly two places in the yum code where this function is called
There's multiple ways that we could approach this issue. We could track down where we're getting unicode strings from and make sure that it's converted to (or remains a) byte string instead.
We could move the str_eq code back to the two places that it exists and put it there. (Function calls are expensive in python... 24 million function calls can add up).
We could decide that it's okay to issue a UnicodeWarning here (not a UnicodeError -- we'd need to keep a patch for RHEL5/python-2.4.x systems to pass errors) and just use str1 == str2. The two effects of this would be: 1) UnicodeWarning would be issued whenever data that is unicode gets compared to the data that is byte str.
2) When unicode and str is compared and the two are not ASCII subsets, the strings will compare False -- currently if the byte string is utf8 and the converted utf8 is equal to the unicode string, the two will compare true.
So it seems to me to be worth optimizing for this case (24 million calls, taking 29% of user time on a warm cache). I can try to cook something up in .c or Cython, if this would be acceptable to the yum/kitchen maintainers?
We could. But I've sped this up so that 24,274,562 calls on a trivial data set is much quicker for most cases:
yum kitchen no unicode 19.1686849594 9.54083299637 eq high_m 75.4539899826 174.357154846 eq high_b 25.5565230846 10.6922521591 no bytes 26.7292191982 9.38552594185 eq high_u 16.9556469917 11.5864810944 no high_b 28.2855761051 12.2306518555 no mixed 78.3247509003 12.7160179615 no high_m 80.1753909588 191.129307985 eq mixed 75.383769989 17.843116045 no high_u 19.0863358974 11.2000300884 no mixed 2 76.1719119549 12.2282829285 eq unicode 16.7433609962 11.509526968 eq bytes 26.5654168129 11.2505509853
The right hand columns are wall clock seconds for the vanilla yum code and the currently checked in kitchen code. The key to the left hand column is:
eq: The two strings evaluate equal no: The two strings evaluate unequal unicode: Both strings are unicode type bytes: Both strings are byte type mixed: One string is unicode, the other is bytes high: The strings are outside of the ASCII subset high_(u|b|m): strings outside the ASCII subset where the strings are (u)nicode, (bytes), or (m)ixed
As you can see, the two pathological cases for the new code are when dealing with non-ascii characters mixed between unicode and bytes. The common case of <str> == <str> is between 2 and 3 times faster.
If you'd care to try the new code out on the real data, it's here: http://bzr.fedorahosted.org/bzr/kitchen/devel/annotate/head%3A/kitchen/text/...
As another point of interest, here's the timings for running with: def str_eq(str1, str2): try: return str1 == str2 except UnicodeError: pass return False
This basically allows us to emulate the python-2.5+ behaviour of ``<unicode> == <str>`` in older versions of python. As you can see, it has problems with the same cases as the current code but those cases degrade performance by a much smaller margin and overall performance is improved. (the <str> <str> common case is 3 to 4 times faster)
yum kitchen no unicode 19.1630501747 7.34791111946 eq high_m 77.9920949936 116.689537048 eq high_b 24.3305389881 6.65209698677 no bytes 26.4734601974 6.85160303116 eq high_u 17.3166980743 7.12775802612 no high_b 28.1892650127 8.82573199272 no mixed 75.0359661579 10.1168701649 no high_m 77.378319025 119.901776791 eq mixed 74.2815010548 10.0155761242 no high_u 18.7383151054 7.27747106552 no mixed 2 72.941822052 9.82383584976 eq unicode 16.5604941845 7.07374501228 eq bytes 24.1317751408 6.49520802498
* Note that this version prints the following warning to stderr: /home/badger/kitchen/devel/kitchen/text/misc.py:118: UnicodeWarning: Unicode equal comparison failed to convert both arguments to Unicode - interpreting them as being unequal return str1 == str2
I'll attach the script I'm using to generate these timings
-Toshio
On Wed, 2010-08-25 at 01:10 -0400, Toshio Kuratomi wrote:
On Tue, Aug 24, 2010 at 08:14:11PM -0400, David Malcolm wrote:
On Tue, 2010-08-24 at 18:28 -0400, David Malcolm wrote:
Profiling of a Fedora 14 "yum install *" showed it spending 80 seconds out of 274 within its implementation of "str_eq" (24 million calls), so optimizing this seems worthwhile.
(replying to self, sorry)
I added some instrumentation to my copy of yum/i18n.py:
str_eq_calls = {} def str_eq(a, b): """ convert between unicode and not and compare them, w/o warning or being annoying""" typesig = (type(a), type(b)) if typesig in str_eq_calls: str_eq_calls[typesig] += 1 else: str_eq_calls[typesig] = 1 (rest of function follows)
to capture the type signature of all of these calls, adding: from yum.i18n import str_eq_calls from pprint import pprint pprint(str_eq_calls) to yummain.py, to dump the stats on output.
The output indicates that in this case at least [1], all of the calls are for the str vs str case:
{(<type 'str'>, <type 'str'>): 24274562}
Hah! So there's a few things that we should think about here:
- We're dealing almost exclusively with byte strings here.
- This function exists because we must occassionally get unicode strings
- I count exactly two places in the yum code where this function is called
There's multiple ways that we could approach this issue. We could track down where we're getting unicode strings from and make sure that it's converted to (or remains a) byte string instead.
We could move the str_eq code back to the two places that it exists and put it there. (Function calls are expensive in python... 24 million function calls can add up).
We could decide that it's okay to issue a UnicodeWarning here (not a UnicodeError -- we'd need to keep a patch for RHEL5/python-2.4.x systems to pass errors) and just use str1 == str2. The two effects of this would be:
- UnicodeWarning would be issued whenever data that is unicode gets
compared to the data that is byte str.
Of course the giant opt. threads happen when I'm on holiday! Anyway, I don't mind any of this (I'm unlikely to NAK anything reasonable), however I do have a couple of minor concerns:
1. If a bug ever opened saying "yum install '*'" in Fedora was slow, I'd be more likely to CLOSE => DONTCARE than anything else.
2. Following on from #1, I'm intrigued about how much str_eq is called in any kind of common case.
3. Following on from #2, I'm intrigued if we can speed up "install '*'" with a tiny API change and something in the depsolver (assuming it was worth it :).
4. IIRC the main reason str_eq() was introduced was because Fedora _had_ to allow utf-8 provides, and so we got bugs about:
"yum install 'font(花園明朝)'
...and we'll get them again if we start issuing warnings.
5. Following on from #4, IIRC the reason we didn't keep the utf-8 provides as bytes (and thus. not have this bug) was because then install/provides commands on the above argument caused other bugs.
6. Given:
yum provides font* | fgrep 'font(' | \ LANG=C egrep -v 'font([:[:alpha:]]' | nl
...I'm half tempted to suggest someone campaign to outlaw utf-8 in provides, on the grounds it'll speed up yum a lot :).
On Sat, Aug 28, 2010 at 02:29:12PM -0400, James Antill wrote:
On Wed, 2010-08-25 at 01:10 -0400, Toshio Kuratomi wrote:
On Tue, Aug 24, 2010 at 08:14:11PM -0400, David Malcolm wrote:
On Tue, 2010-08-24 at 18:28 -0400, David Malcolm wrote:
Profiling of a Fedora 14 "yum install *" showed it spending 80 seconds out of 274 within its implementation of "str_eq" (24 million calls), so optimizing this seems worthwhile.
(replying to self, sorry)
I added some instrumentation to my copy of yum/i18n.py:
str_eq_calls = {} def str_eq(a, b): """ convert between unicode and not and compare them, w/o warning or being annoying""" typesig = (type(a), type(b)) if typesig in str_eq_calls: str_eq_calls[typesig] += 1 else: str_eq_calls[typesig] = 1 (rest of function follows)
to capture the type signature of all of these calls, adding: from yum.i18n import str_eq_calls from pprint import pprint pprint(str_eq_calls) to yummain.py, to dump the stats on output.
The output indicates that in this case at least [1], all of the calls are for the str vs str case:
{(<type 'str'>, <type 'str'>): 24274562}
Hah! So there's a few things that we should think about here:
- We're dealing almost exclusively with byte strings here.
- This function exists because we must occassionally get unicode strings
- I count exactly two places in the yum code where this function is called
There's multiple ways that we could approach this issue. We could track down where we're getting unicode strings from and make sure that it's converted to (or remains a) byte string instead.
We could move the str_eq code back to the two places that it exists and put it there. (Function calls are expensive in python... 24 million function calls can add up).
We could decide that it's okay to issue a UnicodeWarning here (not a UnicodeError -- we'd need to keep a patch for RHEL5/python-2.4.x systems to pass errors) and just use str1 == str2. The two effects of this would be:
- UnicodeWarning would be issued whenever data that is unicode gets
compared to the data that is byte str.
Of course the giant opt. threads happen when I'm on holiday! Anyway, I don't mind any of this (I'm unlikely to NAK anything reasonable), however I do have a couple of minor concerns:
- If a bug ever opened saying "yum install '*'" in Fedora was slow, I'd
be more likely to CLOSE => DONTCARE than anything else.
- Following on from #1, I'm intrigued about how much str_eq is called
in any kind of common case.
Dmalcolm could instrument this but my testing of time yum install 'l*' 'python-*' --skip-broken resulted in:
2300 packages to install, 22 to update. Everything ran in the range of 50-52s with the known best case (inlining reqn == n in the yum code) not getting consistent times better than the worst case (current code).
- Following on from #2, I'm intrigued if we can speed up "install '*'"
with a tiny API change and something in the depsolver (assuming it was worth it :).
For dmalcolm's pathological transaction he was able to come up with the following timings:
1m44s original code 1m35s cython compiled depsolve.so and misc.so 1m20s my new str_eq 1m17s str_eq that does str1 == str2 (similar to code that would be necessary to not throw an error on old python) 1m16s my new str_eq, cython compiled 1m15s str_eq, str1 == str2, cython compiled 1m13s inlined reqn == n
- IIRC the main reason str_eq() was introduced was because Fedora _had_
to allow utf-8 provides, and so we got bugs about:
"yum install 'font(花園明朝)'
...and we'll get them again if we start issuing warnings.
Yeah, I think so too. I didn't write code to just shut up this warning while we're in str_eq() but I suspect that would be slower than my new str_eq().
- Following on from #4, IIRC the reason we didn't keep the utf-8
provides as bytes (and thus. not have this bug) was because then install/provides commands on the above argument caused other bugs.
Hmm.. something to look into if we ever do a complete review of the way we handle unicode and byte strings.
- Given:
yum provides font* | fgrep 'font(' | \ LANG=C egrep -v 'font([:[:alpha:]]' | nl
...I'm half tempted to suggest someone campaign to outlaw utf-8 in provides, on the grounds it'll speed up yum a lot :).
Heh. You don't even need that. If you could successfully campaign to have a single encoding in rpm you'd be able to get rid of things like this. That encoding doesn't need to be ASCII.
-Toshio
kitchen-devel@lists.fedorahosted.org