PyPy is faster than C, again: string formatting
morepypy.blogspot.com
morepypy.blogspot.com
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, 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! :)
The printf() family of functions is one of the rare parts of the C standard library that is essentially implementing an interpreter. The format string is a program and the library call runs that program with data that is supplied in the other arguments. So in essence this is comparing an interpreter (sprintf) with a JIT compiler (PyPy generating code for a specific format string at runtime).
I agree it's not a very fair comparison: if this C code was performance critical you would call a specialized function for converting an integer to a string, and this would almost certainly beat PyPy.
And the fact that it only runs twice as long is pretty impressive, actually. Sprintf is doing the parsing 999,999,999 times more than the PyPy interpreter is.
I'm not a GCC expert, but Microsoft C compilers could inline cross-module code since the beginning of time. His example may actually produce different results under msvc with /GL flag and with static linking enabled.
"...Inline a function in a module even when the function is defined in another module..." http://msdn.microsoft.com/en-us/library/0zza0de8%28v=vs.80%2...
Edit: Is this not the case? I am under the impression that it is, and is relatively new at that.
Not being a part of the C language itself is irrelevant. The traditional linker has been a part of the C ecosystem for decades.
Dynamic linking has been around since the 1960s, and is the model that has been used by almost all currently active developers for their entire careers. Arguments based around specialized microcontrollers, hard real-time systems, life-or-death control systems, etc. are off in the woods. Few developers use such systems in the real world, and their code is statistically irrelevant to comparisons between e.g. Python and C.
Consider yourself lucky...
Provided program, -O4: ~5.06s
Provided program, -O4 -march=native: ~5.07s (i.e. no difference)
Provided program, includes sprintf and the vprintf family, -O4 -march=native: ~4.84s
Of course, this is just a silly example (realistic programs don't make things that easy on the JIT). Still, quite impressive; congratulations to the PyPy guys!
yeah, it's almost like those "$something in only $few lines of $programming_language" posts where you get highly obfuscated code to read.
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.001sEdit: This was with GCC 4.1.2, newer versions probably optimize differently, so who knows.
/* temp number */
char tmp[20];
int pos = 0;
int j = i > 0 ? i : -i;
do {
tmp[pos++] = '0' + j % 10;
j /= 10;
} while (j != 0 && pos <= 20);
/* output both numbers simultaneously */
char x[44], *p1 = x, *p2 = x + 1 + pos;
if (i < 0) { *p1++ = '-'; *p2++ = '-'; }
do {
int tpos = --pos;
*p1++ = tmp[tpos]; *p2++ = tmp[tpos];
} while (pos > 0);
*p1 = ' ';
*p2 = '\0';(Obviously this code never has i<0 so that branch is never even taken.)
char x[44];
sprintf(x, "%d %d", i, i);
char * x = malloc(44 * sizeof(char));
sprintf(x, "%d %d", i, i);*
char *x;
asprintf(&x, "%d %d", i, i);
return x;If you're not running pypy in production already, then you probably should be[1].
[1]: Yes, there are some obvious exceptions.
edit: formatting.
> 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.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.
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!
def main():
for i in xrange(10000000):
"%d %d" % (i, i)
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.
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.
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-ad...)
#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.
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.
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.
1. The C code is stack allocating a pointer in every loop iteration.
2. Cleaning up the memory without(potentially) triggering Python's GC.
Is the Python GC getting triggered in this scenario? If not, then this is what's actually happening, with the cleanup happening automatically when the process exits:
char x[10000000];
int i;
for (i = 0; i < 10000000; i++) {
x[i] = malloc(44 * sizeof(char));
sprintf(x, "%d %d", i, i);
}
char x[1000];
int i;
int j=0;
for (i = 0; i < 10000000; i++) {
x[j] = malloc(44 * sizeof(char));
sprintf(x, "%d %d", i, i);
j++;
if(j == 1000) {
for(j = 0; j < 1000; ++j)
free(x[j]);
}
}I know the aim is to show off the string operation in and of itself so why not leave it there, why the need to bring garbage collection into the mix?
Edit: it's the way the garbage collection has been thrown into the mix I'm having difficulty understanding the need for.
You are arguing that they should have compared against a less efficient C example, which honestly boggles my mind.
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.
exp = CompileSprintfFormat("%d %d");
for (i = 0; i < 10000000; i++) {
RunCompiledSprintf(exp, i, i);
}
> 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).
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?
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.
But going from this to "PyPy is faster than C" seems quite a stretch, no?
I was under the impression that any number greater than 3 had no effect?