7 ms·
PyPy is faster than C, again: string formatting
- jperras 15y agoThe pypy guys continue to do amazing work. This project is one of the reasons why I believe the python community is one of the best open source communities out there: Let's work on something incredibly difficult, challenging and something that not long ago was considered to be nearly impossible, and produce incredible results. If you're not running pypy in production already, then you probably should be[1]. [1]: Yes, there are some obvious exceptions. edit: formatting.
- xd 15y agoI'm no python developer but this: def main(): for i in xrange(10000000): "%d %d" % (i, i) main() Does't seem to be copying the result anywhere. Where as the C example is copying the result to memory .. which would explain why it is slower.
- MostAwesomeDude 15y agoInstantiation for side effects happens in Python. Unless PyPy can prove that the string isn't used anywhere (and it can't, really), it has to execute the statement and push the object onto the stack before discarding it.
- wingo 15y agoWhy can't it?
- MostAwesomeDude 15y agoPyPy simply doesn't have such a thing yet, that's all. I don't think there's any technical reason that it couldn't be developed at some point in the future.
- carbonica 15y agoIt's a matter of purity inference. They already trivially know the value isn't used based on the AST, so they need to show that the function being called is pure to elide it. Naturally, in the general case this is undecidable, but there are fast algorithms for very weak purity inference that might do the trick, at least in this case. There may be other Python-specific concerns I'm missing - my work in this area is in Ruby static analysis - but one other thing is that allocating memory is a side-effect itself. The main side-effect visible to Python is that it might raise an exception for being out of memory - this would have to be special-cased as an acceptably ignored side-effect by any purity analyzer.
- kingkilr 15y agoYes, it does seem a little strange that the result is unused, however changing that to be ``x = <stuff>`` would have no effect on the runtime, the compiler isn't quite good enough yet to realize the result is unused.
- xd 15y agoOh and does anyone else think the malloc example in comparison to actual garbage collection is incredibly unfair?
- scott_s 15y ago"Fairness" is not really relevant. As long as they're comparing typical C idioms to typical Python idioms, it's valid.
- xd 15y agoSo why not simply do: #include <stdio.h> #include <stdlib.h> int main() { int i = 0; char *x = malloc(44 * sizeof(char)); for (i = 0; i < 10000000; i++) { sprintf(x, "%d %d", i, i); } free(x); } Their version was intentionally biased, which is a shame.
- scott_s 15y agoProbably because they wanted to simulate calling a function that parsed a string, and such functions will have to allocate and deallocate memory as needed. It's also worth noting that calling malloc and free in a tight loop where you're always requesting the same amount of memory will be pretty fast. Good implementations of malloc - of which glibc certainly is - will consistently return the exact same chunk of memory to you, and you will be on the fast-path of the allocation algorithm.
- xd 15y agoWhy would you assume the need to deallocate in the loop? Reuse of an already allocated memory location is C optimisation 101.
- scott_s 15y agoYou're looking at this from the wrong angle. You're looking at the C code and thinking, "How can I optimize this?" What you need to do in this case is look at it and say, "How can I optimize this and still retain the essence of what I want to test?" Your optimizations remove that essence - if you're calling a function that is a part of an API, it will have to allocate and free its own memory. That the code is in a loop is an artifact of the experiment.
- jckarter 15y agoThe more fundamental mismatch is that they're testing an interpreter (libc's printf implementation) against a compiler (pypy's format string jit). A C++0x or D library that parsed format strings at compile time would likely still beat pypy.
- icebraining 15y agoBut Pypy can optimize dynamic strings, while a static compiler can't. Replace the constant string with argv[1], and run the code: for Pypy, there is no real difference, but the C/C++/D compilers are unable to optimize.
- repsilat 15y agoI think this is still a library problem, not a language problem. "Compiling" a string at runtime for `sprintf` isn't any more difficult than doing it at compile-time, and plenty of regex libraries do very similar things. Compiling of printf strings isn't done, though, because nobody cares about string performance unless they're writing UNIX command-line utils. If you're writing C you're probably only dealing with strings for (infrequent) IO, spending the vast majority of your time crunching away on pointers and integer types (floats in niche cases). In the end, you're probably only printing something out because someone needs to read it, and how fast can humans read, anyway? This goes just as much for the printing of floating point numbers. (http://www.serpentine.com/blog/2011/06/29/here-be-dragons-advances-in-problems-you-didnt-even-know-you-had/ http://www.serpentine.com/blog/2011/06/29/here-be-dragons-ad...)
- old-gregg 15y agoI love PyPy, those guys are amazing. However, every time I see "faster than C" almost always a bit of trickery/wordplay is involved. The examples aren't comparable. The equivalent would be to have Python code invoke an external function which sits in a pre-compiled .so Bulk of the work is happening inside of sprintf(), why handicap C by not letting it to compile the code? The fair comparison would be to place the source of sprinf() nearby and see if C compiler inlines that call or/and unrolls the loop, otherwise it's just about packaging/linking, not really about code generation. Edit: I see this became #1 on HN front page today. I want to take advantage of this and say that http://mailgun.net http://mailgun.net, the programmable email platform, is looking for an engineer who'd find this discussion interesting. See my profile. And we're users of PyPy too! :)
- leon_ 15y ago> However, every time I see "faster than C" almost always a bit of trickery/wordplay is involved. yeah, it's almost like those "$something in only $few lines of $programming_language" posts where you get highly obfuscated code to read.
- scott_s 15y agoBut the whole point of the post was to point out that PyPy can optimize in places that the traditional C model of shared libraries cannot - or, at least, have great difficulty doing so. This is an inherent advantage to optimizing the instructions at runtime.
- burgerbrain 15y agoC the language doesn't have shared libraries. That's something some systems add themselves. Edit: Is this not the case? I am under the impression that it is, and is relatively new at that.
- scott_s 15y agoWhich is why I said "the traditional C model of shared libraries." Shared libraries are not a part of the C language itself, but most real systems make heavy use of shared libraries. Even statically linked C programs have this problem, because optimizing across object files is hard - most compilers don't even try. Not being a part of the C language itself is irrelevant. The traditional linker has been a part of the C ecosystem for decades.
- _delirium 15y agoRe: > GCC is unable to inline or unroll the sprintf call, because it sits inside of libc. If I'm understanding http://gcc.gnu.org/onlinedocs/gcc-4.5.3/gcc/Other-Builtins.html http://gcc.gnu.org/onlinedocs/gcc-4.5.3/gcc/Other-Builtins.h... correctly, sprintf should be handled as a built-in function, rather than linking the libc version, unless you explicitly specify -fno-builtin. In theory that should allow gcc to perform various optimizations; I've seen that happen with printf at least, where e.g. printf-ing a constant string just gets compiled to puts.
- kingkilr 15y agoPerhaps it is recognizing it, but it's not doing anything interesting with that knowledge, on my machine GCC emits a call to "__sprintf_chk"
- pja 15y agoThere's nothing really stopping gcc from doing as well here, since it ought to be able to spot that the format string never changes & roll out a custom sprintf() that doesn't need to parse it every time. However, right now gcc doesn't do that, so it loses to a language implementation that does. The really sad thing is that using an ostringstream in C++ is even worse, despite the fact that C++ has all the types available to it & doesn't need to parse any format strings at all: Not enough template metaprogramming clearly!
- aninteger 15y agoHow did they measure this? How would it compare to C#. I'm assuming they ignore the startup time of course.
- eridius 15y agoSounds like this would be the equivalent of some theoretical exp = CompileSprintfFormat("%d %d"); for (i = 0; i < 10000000; i++) { RunCompiledSprintf(exp, i, i); } All I'm really getting out of this is that PyPy now compiles sprintf formats for you and saves the results, and that there's no equivalent API in libc.
- TylerE 15y agoThat's not really it. This, at least in my understanding, is a fully generic optimization, of operations on constant strings.
- eridius 15y agoFrom the article: > In the case of PyPy, we specialize the assembler if we detect the left hand string of the modulo operator to be constant. So it's very much a targeted optimization at the modulo operator (which is Python's equivalent of sprintf).
- kingkilr 15y agoI wouldn't say it's particularly targeted, let me show you the code that makes this happen: https://bitbucket.org/pypy/pypy/src/unroll-if-alt/pypy/objspace/std/formatting.py#cl-288 https://bitbucket.org/pypy/pypy/src/unroll-if-alt/pypy/objsp...
- pja 15y agoYeah, the point is that by expressing the algorithm in Python, the JIT gets to go hog wild optimising tight loops like this one. Which is great: why do all that work writing some kind of custom sprintf generating function when you can just let the JIT do it for you on the fly?
- greyfade 15y agoIn that case, wouldn't it be more fair to compare it to a C++ re-implementation of sprintf using the new `constexpr` keyword?
- afhof 15y agoThis title is misleading; instead of `C` it should use `CPython`.
- briancurtin 15y agoWhy would it use that title? CPython is a part of some of the numbers, but the comparison is C vs. PyPy.
- pwpwp 15y agoWhat the example shows is that specializing string operations for known inputs can be faster than not doing so. Surprise! But going from this to "PyPy is faster than C" seems quite a stretch, no?
- apaprocki 15y agoSince we're comparing apples to oranges anyway, how fast could it be if you really wanted to format "%d %d" into the stack 10 million times without a function call... Just for fun: int main() { static const char* digits = "0123456789"; int i; for (i = 0; i < 10000000; i++) { char x[44], *p = x, tmp[20]; /* sign */ int j; if (i < 0) { *p++ = '-'; j = -i; } else { j = i; } /* number */ int pos = 0, spos; do { tmp[pos++] = digits[j % 10]; j /= 10; } while (j != 0 && pos <= 20); spos = pos; do { *p++ = tmp[--pos]; } while (pos > 0); /* space, sign, number again */ *p++ = ' '; if (i < 0) *p++ = '-'; do { *p++ = tmp[--spos]; } while (spos > 0); *p++ = '\0'; } } $ gcc -O4 -o s s.c $ time ./s real 0m0.140s user 0m0.138s sys 0m0.001s
- 1amzave 15y agoThat runs in ~0.4s on my system (Xeon E5520, 2.27GHz), but replacing the 'digits' lookup table with simple arithmetic on the ASCII values ('0' + j%10) speeds it up to ~0.23s. Yes, L1 caches are pretty fast, but ALUs are still faster (for integer addition anyway). Edit: This was with GCC 4.1.2, newer versions probably optimize differently, so who knows.
- apaprocki 15y agoInteresting.. I guess I should have mentioned gcc 4.5.2 on a Xeon X5670, 2.93GHz, which is 12M cache. Changing it to ('0' + j % 10) has no change in overall speed for me.
- 1amzave 15y agoOK, I just tested with gcc 4.6.0, and unless I've screwed something up, it looks like (at -O4) it actually optimizes these into the exact same code. As in the generated ELFs are byte-for-byte identical. Impressive.
- 15y ago
- deleted 15y ago[deleted]
- onedognight 15y agochar x[44]; sprintf(x, "%d %d", i, i); This is fine, except you can't even return x from this function, a more fair comparison might be: char * x = malloc(44 * sizeof(char)); sprintf(x, "%d %d", i, i);* There is a standard (C99) way to do this: asprintf(3). char *x; asprintf(&x, "%d %d", i, i); return x;
- tedunangst 15y agoThere is no asprintf function in my copy of the C99 standard.
- onedognight 15y agoSorry, you are correct; I mis-read the man page. It is however in at least glibc and Darwin/FreeBSD's libc.
- supersillyus 15y agoasprintf is a GNU extension, I believe.
- ZoFreX 15y ago> compiled with GCC 4.5.2 at -O4 (other optimization levels were tested, this produced the best performance). I was under the impression that any number greater than 3 had no effect?
- comex 15y agoIf PyPy were really smart, it would notice the unused result and take 0.00s. :)
- malkia 15y agoWhy don't you take an example from Mike Pall's LuaJIT relying on something more computationally expensive like scimark - he has lua version, and also few other benchmarks (from the alioth site). If you really want fast sprintf( %s, "%d %d" ) - then you might aswell craft something specifically for converting text to decimal numbers. sprintf( ) is convenience function, not performance.
- sjs 15y agoI'm sure that's one of the larger goals of PyPy, to make idiomatic code that is convenient to write also perform well. They don't have to be mutually exclusive.
- schiptsov 15y agoWhy be so shy? Faster than Assembly language! Faster than Assembly language with cache size alignment and padding of data structures! ^_^