New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Make f'' strings faster than .format: BUILD_STRING opcode? #71265
Comments
I benchmarked some f'' strings against .format, and surprisingly f'' was slower than .format in about all the simple cases I could think of. I guess this is because f'' strings implicitly use The byte code for f'foo is {foo}' currently is 1 0 LOAD_CONST 1 ('') It was mentioned here https://bugs.python.org/issue24965 but since I came up with the idea when inspecting this, I'd propose again here that a new opcode be added for f'' strings - BUILD_STRING n, with which f'foo is {foo}' could be compiled to
instead. Internally this wouldn't even need to call And that way people doing micro benchmarks would find out that the new Python 3.6 feature would not only look nice but also be a way to write better-performing code. |
I considered doing this, and have some of it implemented. I discussed it with Larry Hastings and Mark Shannon at PyCon Ireland, and we decided to just use ''.format() and the new FORMAT_VALUE opcode, since that was the simplest way to fix the previous implementation's faults. That doesn't mean I've given up on improving it, of course. The speed increase would indeed come from avoiding the LOAD_ATTR lookup, not building list, and not calling a function. I'm curious about your benchmarks. Can you share them? I've found f-strings to be typically faster than .format(). But I can't say my benchmarks are particularly awesome. |
The catalyst for this question was a Stack Overflow question I answered:
Compared the |
I am not an expert on writing new opcodes to CPython (having never done it, don't know where to change the disassembler and such, how to make compiler generate them properly and such), but I'd be glad to help with testing, timing and writing the possible joiner algorithm for it, to help it make into Python 3.6. |
For comparison: $ ./python -m timeit -s "x = 2" -- "f'X is {x}'"
1000000 loops, best of 3: 1.04 usec per loop
$ ./python -m timeit -s "x = 2; j = ''.join" -- "j(['X is ', f'{x}'])"
1000000 loops, best of 3: 0.93 usec per loop
$ ./python -m timeit -s "x = 2" -- "'X is {}'.format(x)"
1000000 loops, best of 3: 0.808 usec per loop
$ ./python -m timeit -s "x = 2; f = 'X is {}'.format" -- "f(x)"
1000000 loops, best of 3: 0.748 usec per loop
$ ./python -m timeit -s "x = 2" -- "'X is %s' % (x,)"
1000000 loops, best of 3: 0.467 usec per loop |
And the expected performance for optimal |
That's not necessarily true. The f-string version still needs to invoke the .format() method on the object, instead of only working for a handful of hard-coded types. I'm not saying there aren't optimization opportunities, but it may be that %-formatting is always faster. |
Ah so it seems. Somehow I thought __format__ was slotted, but that is not the case and it needs to be looked up, and what is worse, of course a tuple needs to be built as well. Oh well, at least it should be quite minimal to make it be faster than |
The simplest perf fix is to first use BUILD_TUPLE instead of BUILD_LIST timeit 'x=1;(x,x,x)' timeit 'x=1;[x,x,x]' Introducing a new opcode BUILD_STRING to inline PyTuple_New + PyUnicode_Join to replace BUILD_TUPLE + CALL_FUNCTION should benchmark against BUILD_TUPLE version, not BUILD_LIST + CALL_FUNCTION |
Benchmarked f'X is {x}' with BUILD_TUPLE change: Before: 6.62 usec per loop f'X is {x} {x+2} {x+3}' Attached patch |
fstrtup2.patch is a bit more of an involved optimization for when we are joining 2 strings. Instead it emits BINARY_ADD. This may be considered too 'niche' since it only triggers when the substitution occurs at the start or end of a string & there is only one substitution However, it reduces the "X is {x}" testcase on my machine to 4.9 usec Interesting thing, to consider ceiling of what we can do, Prefixing ./python -m timeit -s "x=1" So we should not be aiming to compete with %. It may be worthy to convert the code to generate "x is {}".format calls tho |
Yet the test cases just prove what is so expensive there: name lookups (global name However for strings, 'foo'.format() already returns the instance itself, so if you were formatting other strings into strings there are cheap shortcuts available to even overtake a = 'Hello'
b = 'World'
'%s %s' % (a, b) for fast string templates, namely, make FORMAT_VALUE without args return the original if |
I'm not understanding your message. We don't call FORMAT_VALUE on constant strings in f"x is {x}" & FORMAT_VALUE doesn't take an argument. Are you saying in a hypothetical FORMAT_VALUE where BUILD_STRING takes a set of objects & applies formatting to them, thus allowing us to remove FORMAT_VALUE as an opcode? That seems like I'm imposing my own internal thoughts on what you're saying, but when I don't understand what someone's saying I'm prone to raise my own imaginations. Also note that f'{x}' compiles to 'LOAD X, FORMAT_VALUE' so there is no join lookup in the last benchmarks I posted Nitpick about fstrtup2: it assumes compiler_joined_str's len is at least 2. Either an assert should be added or the last if-else should be |
Yet one case for comparison (with msg270095): $ ./python -m timeit -s "x = 2" -- 'f"X is {x!s}"'
1000000 loops, best of 3: 0.625 usec per loop Seems f'{x!s}' is the fastest way to stringify a value. Thus there is an opportunity to speed up default formatting by special casing PyObject_Format() for most popular types (str and int). |
Proposed patch adds the BUILD_STRING opcode and speeds up PyObject_Format() in common cases. It makes f-strings the fastest method for simple formatting. $ ./python -m timeit -s "x = 2" -- 'f"X is {x}"'
1000000 loops, best of 3: 0.347 usec per loop |
It seems Eric has done some special casing for strings already in FORMAT_VALUE. Here are the results from my computer after applying Demur's patch for concatenating *strings*.
But then as more components are added, it starts to slow down rapidly:
Of course there is also the matter of string conversion vs "look up __format__":
For FORMAT_VALUE opcode already has a special case for the latter. However I'd too say that switch/case for the some fastest builtin types in For others the speed-up wouldn't really matter either way: either PyObject_Format would fall back to object.format (for example functions) - no one really cares about efficiency when doing such debug dumps - if you cared, you'd not do them at all; or they'd have complex representations (say, lists, dictionaries) - and their use again would mostly be that of debug dumps; or they'd have |
Thanks Serhiy, I was writing my comment for a long time, and only now noticed that you'd already posted the patch. Indeed, it seems that not only is this the fastest method, it might also be the fastest string concatenation method in the history of Python. I did some comparison with 8-bit strings in Python 2, doing the equivalent of
with domain = 'some_really_long_example.com'
lang = 'en'
path = 'some/really/long/path/' and the results look quite favourable: 0.151 µs with your patch; 0.250ish for the second fastest method in Python 3.6 (''.join(tuple)) And the fastest method in Python 2 is a tie between concatenating with + or ''.join with bound method reference; both of them take 0.203 µs on Python 2.7 with 8-bit strings and about 0.245 - 0.255 µs if everything is Unicode. |
Serhiy suggested this in Rietveld:
I was thinking about this and got an idea on how to do this too, without changes to marshal. Essentially, let TOS be a tuple of
flags would be n bytes for n-part format string; each byte would tell whether:
thus that tuple for
would be
and the opcodes would be
|
Nice idea, Antti. But I tried to implement it, and surprisingly found that this approach is slower than FORMAT_VALUE + BUILD_STRING. At least for this particular example. Perhaps because we can't use a stack and need to allocate a new tuple containing literal strings and formatted values for PyUnicode_Join(). Not mentioning that the code is much more complex. Here is updated previous patch with fixed leak. |
I would very much like to see this in 3.6. Who could review it? |
I intend to review this. As this is not a new feature, it doesn't need to be completed by beta 1. I'm focusing my energies on new features, then I'll look at this. |
Since this introduces a new opcode, this is a new feature. Seems opcodes never were added at beta stage before 3.5b1. |
So does this (new opcode) count as a new feature? It would be great to give f'' strings a flying start, saying that not only they're cool, they're also faster than anything that you've used before. Here some more mini-benchmarks with serhiy's patch2 applied, the times are pretty stable:
and
This is only really achievable with some kind of bytecode support. |
I don't think lack of precedence is a reason to say new opcodes are new features. More that generally new opcodes are created for new features |
I put this in the "new feature" category in the sense that after beta we're trying to stabilize the code base. Introducing a new opcode is a higher risk change that needs to go in the release cycle as early as possible. |
Left a review comment. I'd like to see this in before 3.6 beta 1. |
I tried to post a comment on rietveld, but 500 infernal error... PyUnicode_New(0, 0) will return unicode_empty. If unicode_empty is NULL, then it will also initialize it. It would be cleanest if unicode_empty was statically created. NULL cannot be used as the separator argument to |
Of course. Never mind. LGTM. |
Though it is clean to do like this: let _PyUnicode_JoinArray have if (separator == NULL) {
separator = PyUnicode_FromOrdinal(' ');
/* check omitted */
res = _PyUnicode_JoinArray(separator, items, seqlen);
Py_DECREF(separator);
}
else {
res = _PyUnicode_JoinArray(separator, items, seqlen);
} The NULL argument I guess isn't that common to pass to PyUnicode_Join (Python code especially would always have to pass in ' ' instead), so this shouldn't really affect performance for any case at all. |
New changeset 28e280915508 by Serhiy Storchaka in branch 'default': |
Thank you for your review Eric. I considered passing NULL, but as Antti said, it is already used for space separated concatenation. PyUnicode_New(0, 0) is the obvious way to get an empty string, and I think it is fast enough. If this affects performance we can add additional microoptimization later. |
Now that I've looked at PyUnicode_New, I agree with using PyUnicode_New(0, 0). I can't imagine we could measure the difference with optimizing it in the opcode itself before calling PyUnicode_New. Thanks for adding this, Serhiy. I think it's great stuff, and works well with FORMAT_VALUE. |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: