From comp.lang.python: chrisperkins99@gmail.com wrote: It seems to me that str.count is awfully slow. Is there some reason for this? Evidence:
######## str.count time test ######## import string import time import array
s = string.printable * int(1e5) # 10**7 character string a = array.array('c', s) u = unicode(s) RIGHT_ANSWER = s.count('a')
def main(): print 'str: ', time_call(s.count, 'a') print 'array: ', time_call(a.count, 'a') print 'unicode:', time_call(u.count, 'a')
def time_call(f, *a): start = time.clock() assert RIGHT_ANSWER == f(*a) return time.clock()-start
if __name__ == '__main__': main()
###### end ########
On my machine, the output is:
str: 0.29365715475 array: 0.448095498171 unicode: 0.0243757237303
If a unicode object can count characters so fast, why should an str object be ten times slower? Just curious, really - it's still fast enough for me (so far).
This is with Python 2.4.1 on WinXP.
Chris Perkins
Your evidence points to some unoptimized code in the underlying C implementation of Python. As such, this should probably go to the python-dev list (http://mail.python.org/mailman/listinfo/python-dev). The problem is that the C library function memcmp is slow, and str.count calls it frequently. See lines 2165+ in stringobject.c (inside function string_count): r = 0; while (i < m) { if (!memcmp(s+i, sub, n)) { r++; i += n; } else { i++; } } This could be optimized as: r = 0; while (i < m) { if (s[i] == *sub && !memcmp(s+i, sub, n)) { r++; i += n; } else { i++; } } This tactic typically avoids most (sometimes all) of the calls to memcmp. Other string search functions, including unicode.count, unicode.index, and str.index, use this tactic, which is why you see unicode.count performing better than str.count. The above might be optimized further for cases such as yours, where a single character appears many times in the string: r = 0; if (n == 1) { /* optimize for a single character */ while (i < m) { if (s[i] == *sub) r++; i++; } } else { while (i < m) { if (s[i] == *sub && !memcmp(s+i, sub, n)) { r++; i += n; } else { i++; } } } Note that there might be some subtle reason why neither of these optimizations are done that I'm unaware of... in which case a comment in the C source would help. :-) --Ben
(manually cross-posting from comp.lang.python) Ben Cartwright wrote:
Your evidence points to some unoptimized code in the underlying C implementation of Python. As such, this should probably go to the python-dev list (http://mail.python.org/mailman/listinfo/python-dev).
This tactic typically avoids most (sometimes all) of the calls to memcmp. Other string search functions, including unicode.count, unicode.index, and str.index, use this tactic, which is why you see unicode.count performing better than str.count.
it's about time that someone sat down and merged the string and unicode implementations into a single "stringlib" code base (see the SRE sources for an efficient way to do this in plain C). [1] moving to (basic) C++ might also be a good idea (in 3.0, perhaps). is any- one still stuck with pure C89 these days ? </F> 1) anyone want me to start working on this ?
Zitat von Fredrik Lundh <fredrik@pythonware.com>:
it's about time that someone sat down and merged the string and unicode implementations into a single "stringlib" code base (see the SRE sources for an efficient way to do this in plain C). [1] [...] 1) anyone want me to start working on this ?
This would be a waste of time: In Python 3, the string type will be gone (or, rather, the unicode type, depending on the point of view). Regards, Martin
martin@v.loewis.de wrote:
it's about time that someone sat down and merged the string and unicode implementations into a single "stringlib" code base (see the SRE sources for an efficient way to do this in plain C). [1] [...] 1) anyone want me to start working on this ?
This would be a waste of time: In Python 3, the string type will be gone (or, rather, the unicode type, depending on the point of view).
no matter what ends up in Python 3, you'll still need to perform operations on both 8-bit buffers and Unicode buffers. (not to mention that a byte type that doesn't support find/split/count etc is pretty useless). </F>
Fredrik Lundh wrote:
moving to (basic) C++ might also be a good idea (in 3.0, perhaps). is any- one still stuck with pure C89 these days ?
Some of us actually *prefer* working with plain C when we have a choice, and don't consider ourselves "stuck" with it. My personal goal in life right now is to stay as far away from C++ as I can get. If CPython becomes C++-based (C++Python?) I will find it quite distressing, because my most favourite language will then be built on top of my least favourite language. Greg
Greg Ewing wrote:
Fredrik Lundh wrote:
moving to (basic) C++ might also be a good idea (in 3.0, perhaps). is any- one still stuck with pure C89 these days ?
Some of us actually *prefer* working with plain C when we have a choice, and don't consider ourselves "stuck" with it.
perhaps, but polymorphic code is a lot easier to write in C++ than in C.
My personal goal in life right now is to stay as far away from C++ as I can get.
so what C compiler are you using ? </F>
Fredrik Lundh wrote:
My personal goal in life right now is to stay as far away from C++ as I can get.
so what C compiler are you using ?
Gcc, mostly. I don't mind if it's capable of compiling C++, as long as I can choose not to write any. -- Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | Carpe post meridiam! | Christchurch, New Zealand | (I'm not a morning person.) | greg.ewing@canterbury.ac.nz +--------------------------------------+
On 2/28/06, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Fredrik Lundh wrote:
My personal goal in life right now is to stay as far away from C++ as I can get.
so what C compiler are you using ?
Gcc, mostly. I don't mind if it's capable of compiling C++, as long as I can choose not to write any.
That's getting harder and harder though. Recent versions of GCC appear to be implementing C98 by default -- at least I didn't get complaints about declarations placed after non-declarations in the same block from any of the buildbot hosts... -- --Guido van Rossum (home page: http://www.python.org/~guido/)
Guido van Rossum wrote:
Fredrik Lundh wrote:
My personal goal in life right now is to stay as far away from C++ as I can get.
so what C compiler are you using ?
Gcc, mostly. I don't mind if it's capable of compiling C++, as long as I can choose not to write any.
That's getting harder and harder though. Recent versions of GCC appear to be implementing C98 by default -- at least I didn't get complaints about declarations placed after non-declarations in the same block from any of the buildbot hosts...
should we perhaps switch to (careful use of) C++ in 3.0 ? </F>
Fredrik Lundh wrote:
should we perhaps switch to (careful use of) C++ in 3.0 ?
I worry that if the Python core becomes dependent on C++, it will force all extensions to be written in C++, too. Not only is this inconvenient for people who don't know C++ or prefer not to use it, but I suspect this would lead to some severe interoperability problems. On most platforms, C code will happily link to just about anything else, but in my experience, C++ code will only interoperate with other C++ code when it's compiled by exactly the same compiler and uses the same runtime system. For another thing, I'm not sure that C++ polymorphism is flexible enough to implement Python's style of polymorphism. Think of all the tricks we play with type objects -- allocating them on the heap, extending them dynamically at runtime, etc. In C++, classes aren't even available as program-accessible entities. So we'd end up implementing our own form of dynamic dispatch anyway, and it would probably look a lot like the current C-based type objects. I don't see that C++ would help much. -- Greg
On Feb 28, 2006, at 6:26 PM, Fredrik Lundh wrote:
should we perhaps switch to (careful use of) C++ in 3.0 ?
I hope not. It would make life more difficult for embedded/extended users like ourselves because it would force us to link our applications as C++ programs. That introduces lots of headaches on certain, shall we say, non-Windows platforms. -Barry
On Feb 28, 2006, at 6:14 PM, Guido van Rossum wrote:
On 2/28/06, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Fredrik Lundh wrote:
My personal goal in life right now is to stay as far away from C++ as I can get.
so what C compiler are you using ?
Gcc, mostly. I don't mind if it's capable of compiling C++, as long as I can choose not to write any.
That's getting harder and harder though. Recent versions of GCC appear to be implementing C98 by default -- at least I didn't get complaints about declarations placed after non-declarations in the same block from any of the buildbot hosts...
I don't know whether you meant "C++98" or "C99" in the above, but the default is (mostly) C99, now. If you like, you can still tell it to compile in C89 mode, with --std=c89. C99 contains some of the superficial C++ syntax changes such as // comments and declarations after non-declarations which have long been implemented as non-standard extensions, anyhow, but it's still nothing like C++. As for the question of whether to switch to C++ in 3.0, I'd say probably not, as it's much harder to interface with C++ from other languages than to C. James
Guido van Rossum wrote:
Recent versions of GCC appear to be implementing C98 by default -- at least I didn't get complaints about declarations placed after non-declarations in the same block from any of the buildbot hosts...
As long as it doesn't complain when I *do* put all my declarations before my non-declarations, I can live with that. :-) -- Greg
Fredrik Lundh schrieb:
should we perhaps switch to (careful use of) C++ in 3.0 ?
I can't see many advantages in moving to C++, but a lot of disadvantages: - Size increase, especially when we start using templates - Performance decrease - Problems with name mangling together with dynamic loading and cross module API's - Everything has to be build with the same compiler, binaries created with different compilers can't interoperate - Possibly all extensions modules have to be (re)written in C++ - Moving to C++ will change Python's well known API substantially --- IMHO, if a Python major version change implies to forget everything that has been established over the years, ignoring backward compaibility, breaking nearly every Python script, than we should definitely find another name for it, or I will stay with Python 2 for the rest of my life. --- Ulli
Hello,
should we perhaps switch to (careful use of) C++ in 3.0 ? I can't see many advantages in moving to C++, but a lot of disadvantages:
- Size increase, especially when we start using templates - Performance decrease - Problems with name mangling together with dynamic loading and cross module API's - Everything has to be build with the same compiler, binaries created with different compilers can't interoperate - Possibly all extensions modules have to be (re)written in C++ - Moving to C++ will change Python's well known API substantially
Same opinion. C++ is evil, please don't use it. You get a lot of new problems and nearly not benefit. Better go to jython or consider the way of pypy. -- bye by Wolfgang
Hello,
should we perhaps switch to (careful use of) C++ in 3.0 ? I can't see many advantages in moving to C++, but a lot of disadvantages:
- Size increase, especially when we start using templates - Performance decrease - Problems with name mangling together with dynamic loading and cross module API's - Everything has to be build with the same compiler, binaries created with different compilers can't interoperate - Possibly all extensions modules have to be (re)written in C++ - Moving to C++ will change Python's well known API substantially
Same opinion. C++ is evil, please don't use it. You get a lot of new problems and nearly not benefit. Better go to jython or consider the way of pypy. -- bye by Wolfgang
Zitat von Ulrich Berning <ulrich.berning@denviso.de>:
I can't see many advantages in moving to C++, but a lot of disadvantages:
There are a few advantages, though, mainly: - increased type-safety, in particular for API that isn't type-checked at all at the moment (e.g. PyArg_ParseTuple) - more reliable reference counting, due to destructors of local variables - "native" exception handling, making exceptions both less error-prone and possible more efficient. Regards, Martin
martin@v.loewis.de wrote:
Zitat von Ulrich Berning <ulrich.berning@denviso.de>:
I can't see many advantages in moving to C++, but a lot of disadvantages:
There are a few advantages, though, mainly: - increased type-safety, in particular for API that isn't type-checked at all at the moment (e.g. PyArg_ParseTuple) - more reliable reference counting, due to destructors of local variables
Indeed, smart pointers should get rid of most reference counting problems.
- "native" exception handling, making exceptions both less error-prone and possible more efficient.
Another advantage might be using inline functions instead of macros with do {foo} while(0). Bye, Walter Dörwald
On 3/1/06, martin@v.loewis.de <martin@v.loewis.de> wrote:
There are a few advantages, though, mainly: - increased type-safety, in particular for API that isn't type-checked at all at the moment (e.g. PyArg_ParseTuple)
How would this be accomplished - by a function with a ton of optional templated arguments? By some sort of TupleParser(tuple) >> var1 >> var2 >> TupleParser::done?
- more reliable reference counting, due to destructors of local variables
Only true when the rules are consistent with what smart pointers or the like do. When there's more than a single rule, this goes out the window because you have to use the correct smart class...
- "native" exception handling, making exceptions both less error-prone and possible more efficient.
...and exceptions make it impossible to not use smart classes. Since there isn't a nested level of C for each function call in Python, I don't see how exceptions in the implementation language would help exceptions in Python. Do I misunderstand your point, or is there some really cool trick I'm missing? (To explain my bias, I'm against the idea of the C++ rewrite as I also fail to see the advantages outweighing the disadvantages, especially in light of the amount of rewriting necessary to see the "advantages" cited so far.) Michael -- Michael Urman http://www.tortall.net/mu/blog
Zitat von Michael Urman <murman@gmail.com>:
On 3/1/06, martin@v.loewis.de <martin@v.loewis.de> wrote: How would this be accomplished - by a function with a ton of optional templated arguments?
That's how I would do it. Actually, I would have PyArg_ParseTuple overloaded with different numbers of arguments, say 0..64. Each of them would be a template.
Only true when the rules are consistent with what smart pointers or the like do. When there's more than a single rule, this goes out the window because you have to use the correct smart class...
Sure. You have to use PyObject* now, so changing to usage of PyObject_ptr wouldn't be that bad. Remember, we are talking about extension modules *to python* here.
...and exceptions make it impossible to not use smart classes. Since there isn't a nested level of C for each function call in Python, I don't see how exceptions in the implementation language would help exceptions in Python. Do I misunderstand your point, or is there some really cool trick I'm missing?
Instead of checking for a NULL return value on all functions, a Python exception could be expressed (on the C++ stack) as a C++ exception. So instead of writing n = PyString_FromString(name); if (n == NULL) return NULL; for (ml = methods; ml->ml_name != NULL; ml++) { if ((ml->ml_flags & METH_CLASS) || (ml->ml_flags & METH_STATIC)) { PyErr_SetString(PyExc_ValueError, "module functions cannot set" " METH_CLASS or METH_STATIC"); Py_DECREF(n); return NULL; } v = PyCFunction_NewEx(ml, passthrough, n); if (v == NULL) { Py_DECREF(n); return NULL; } if (PyDict_SetItemString(d, ml->ml_name, v) != 0) { Py_DECREF(v); Py_DECREF(n); return NULL; } Py_DECREF(v); } Py_DECREF(n); you would write n = PyString_FromString(name); for (ml = methods; ml->ml_name != NULL; ml++) { if ((ml->ml_flags & METH_CLASS) || (ml->ml_flags & METH_STATIC)) raise new PyExc_ValueError(PyExc_ValueError, "module functions cannot set" " METH_CLASS or METH_STATIC"); v = PyCFunction_NewEx(ml, passthrough, n); PyDict_SetItemString(d, ml->ml_name, v); }
(To explain my bias, I'm against the idea of the C++ rewrite as I also fail to see the advantages outweighing the disadvantages, especially in light of the amount of rewriting necessary to see the "advantages" cited so far.)
That's why I'm explaining the advantages to you. I'm not saying Python 3 should be written in C++, I'm only saying that doing so would have not just disadvantages. Regards, Martin
martin@v.loewis.de wrote:
I'm not saying Python 3 should be written in C++, I'm only saying that doing so would have not just disadvantages.
someone also pointed out in private mail (I think; it doesn't seem to have made it to this list) that CPython's extensive use of "inheritance by aggregation" is invalid C. switching to C++ would be one way to address that, of course. </F>
Fredrik Lundh wrote:
someone also pointed out in private mail (I think; it doesn't seem to have made it to this list) that CPython's extensive use of "inheritance by aggregation" is invalid C.
switching to C++ would be one way to address that, of course.
A rather heavyweight solution to a problem that does not seem to have been a problem in practice so far, only in theory. Practicality beats purity once again... -- Greg
Zitat von Greg Ewing <greg.ewing@canterbury.ac.nz>:
A rather heavyweight solution to a problem that does not seem to have been a problem in practice so far, only in theory.
The problem does exist in practice. Python is deliberately build with -fno-strict-aliasing when GCC is used, and might get compiled incorrectly on any other advanced C compiler. The problem with that bug is that it is both very hard to find when it exists, and very hard to dismiss as theoretical, unless an extensive source code review is performed. Have you done this review in the Python source code to know that there is no potential for misinterpretation to make the claim the problem is only theoretical? Regards, Martin
Zitat von Fredrik Lundh <fredrik@pythonware.com>:
I'm not saying Python 3 should be written in C++, I'm only saying that doing so would have not just disadvantages.
someone also pointed out in private mail (I think; it doesn't seem to have made it to this list) that CPython's extensive use of "inheritance by aggregation" is invalid C.
switching to C++ would be one way to address that, of course.
My preferred way of fixing it is to do it the "proper" C way, i.e. make PyObject the first member of each derived type. Regards, Martin
"martin" == martin <martin@v.loewis.de> writes:
martin> There are a few advantages [to C++], though, mainly: martin> - increased type-safety, in particular for API that isn't martin> type-checked at all at the moment (e.g. PyArg_ParseTuple) That's merely an advantage to having a C++ *compiler*. No need to actually use the C++ *language*. :-) XEmacs has had a policy of compiling without warnings under *both* C and C++ for about 5 years now, and it catches a lot of stupidity before it leaves the developer's sandbox. The feature programmers are occasionally annoyed that a pet C idiom gets disallowed, but that's the only downside we've experienced. -- School of Systems and Information Engineering http://turnbull.sk.tsukuba.ac.jp University of Tsukuba Tennodai 1-1-1 Tsukuba 305-8573 JAPAN Ask not how you can "do" free software business; ask what your business can "do for" free software.
Zitat von "Stephen J. Turnbull" <stephen@xemacs.org>:
martin> - increased type-safety, in particular for API that isn't martin> type-checked at all at the moment (e.g. PyArg_ParseTuple)
That's merely an advantage to having a C++ *compiler*. No need to actually use the C++ *language*. :-)
I don't understand. How can you use a C++ compiler, but not the C++ language? Either a program is required to conform to the C++ syntax (in which case it is a C++ program), or it isn't. In the specific example of ParseTuple, I don't see a C++ solution without templates, FWIW.
XEmacs has had a policy of compiling without warnings under *both* C and C++ for about 5 years now, and it catches a lot of stupidity before it leaves the developer's sandbox.
Right. It might be possible to write C++ programs that are also C programs, and it is then possible to release binaries of these through the C compiler. However, in the Python case, I doubt it would gain that much. As the recent const dilemma shows, C99 and C++98 have, unfortunately, different interpretations of "const" (with the C interpretation being more strict). Regards, Martin
"martin" == martin <martin@v.loewis.de> writes:
martin> I don't understand. How can you use a C++ compiler, but martin> not the C++ language? An abbreviation for "those features that aren't in C". martin> As the recent const dilemma shows, C99 and C++98 have, martin> unfortunately, different interpretations of "const" (with martin> the C interpretation being more strict). Yeah, that's really unfortunate. I suppose we'll probably run into it fairly quickly. Nevertheless, the restriction to programs that are both legal C89 and legal C++ of similar vintage has paid off for us, in the sense that we went from GCC 2.95 to GCC 3.4 without having significant problems where the compiler suddenly decided our code was unacceptable. (Similar experience with other vendors' compilers.) Recently we've seen a significant rise in warnings that need to be fixed, and occasional errors, as GCC 4.x has become more common. -- School of Systems and Information Engineering http://turnbull.sk.tsukuba.ac.jp University of Tsukuba Tennodai 1-1-1 Tsukuba 305-8573 JAPAN Ask not how you can "do" free software business; ask what your business can "do for" free software.
It's probably worth mentioning that right now, we don't even come close to compiling with a C++ compiler. A bunch of the bugs are shallow (casting result from malloc, that sort of thing) but a bunch more look a tad uglier. Is this something worth trying to fix? Fixing the shallow bugs at least might be worthwhile... Anthony
"Anthony" == Anthony Baxter <anthony@interlink.com.au> writes:
Anthony> It's probably worth mentioning that right now, we don't Anthony> even come close to compiling with a C++ compiler. A bunch Anthony> of the bugs are shallow (casting result from malloc, that Anthony> sort of thing) but a bunch more look a tad uglier. Is Anthony> this something worth trying to fix? Um ... I really only know the results for XEmacs. C++ warnings and errors do catch a number of "real bugs". But most of the *work* was done before I got really involved in the C code. Martin Buchholz <martin@xemacs.org> probably knows best, although he's been inactive for a couple of years. -- School of Systems and Information Engineering http://turnbull.sk.tsukuba.ac.jp University of Tsukuba Tennodai 1-1-1 Tsukuba 305-8573 JAPAN Ask not how you can "do" free software business; ask what your business can "do for" free software.
Hi Ben, On Mon, Feb 27, 2006 at 06:50:28PM -0500, Ben Cartwright wrote:
It seems to me that str.count is awfully slow. Is there some reason for this?
stringobject.c could do with a good clean-up. It contains very similar algorithms multiple times, in slightly different styles and with different performance characteristics. If I find some motivation I'll try to come up with a patch. A bientot, Armin
participants (16)
-
Anthony Baxter -
Armin Rigo -
Barry Warsaw -
Ben Cartwright -
Bill Janssen -
Fredrik Lundh -
Greg Ewing -
Guido van Rossum -
James Y Knight -
martin＠v.loewis.de -
Michael Urman -
Stephen J. Turnbull -
Ulrich Berning -
Walter Dörwald -
Wolfgang Langner -
Wolfgang Langner