Make f'' strings faster than .format: BUILD_STRING opcode?

[ztane]

BPO	27078
Nosy	@rhettinger, @mjpieters, @ericvsmith, @serhiy-storchaka, @ztane, @serprex
Files	fstrtup.patch fstrtup2.patch: BINARY_ADD fstring_build_string.patch fstring_build_string_2.patch

^{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:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2016-09-06.19:23:54.191>
created_at = <Date 2016-05-21.19:18:36.523>
labels = ['interpreter-core', 'performance']
title = "Make f'' strings faster than .format: BUILD_STRING opcode?"
updated_at = <Date 2016-09-06.19:31:16.411>
user = 'https://github.com/ztane'

bugs.python.org fields:

activity = <Date 2016-09-06.19:31:16.411>
actor = 'eric.smith'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2016-09-06.19:23:54.191>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2016-05-21.19:18:36.523>
creator = 'ztane'
dependencies = []
files = ['43701', '43704', '43708', '43735']
hgrepos = []
issue_num = 27078
keywords = ['patch']
message_count = 32.0
messages = ['266016', '266021', '266031', '270083', '270095', '270135', '270136', '270167', '270280', '270281', '270308', '270312', '270319', '270333', '270339', '270344', '270347', '270469', '270505', '271743', '271745', '271747', '273776', '273778', '273816', '274322', '274326', '274327', '274345', '274605', '274608', '274610']
nosy_count = 7.0
nosy_names = ['rhettinger', 'mjpieters', 'eric.smith', 'python-dev', 'serhiy.storchaka', 'ztane', 'Demur Rumed']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue27078'
versions = ['Python 3.6']

[ztane]

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 ''.join([]).

The byte code for f'foo is {foo}' currently is

1 0 LOAD_CONST 1 ('')
3 LOAD_ATTR 0 (join)
6 LOAD_CONST 2 ('foo is ')
9 LOAD_GLOBAL 1 (foo)
12 FORMAT_VALUE 0
15 BUILD_LIST 2
18 CALL_FUNCTION 1 (1 positional, 0 keyword pair)

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

          0 LOAD_CONST               2 ('foo is ')
          3 LOAD_GLOBAL              1 (foo)
          6 FORMAT_VALUE             0
          9 BUILD_STRING             2

instead. Internally this wouldn't even need to call PyUnicode_Join, but instead seplen == 0 case could be refactored into a separate function. Not only with this is it possible to know the length of the string, but also the number of string components are already known, so it'd be possible to build a tuple fast from the values on stack.

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.

[ericvsmith]

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.

[mjpieters]

The catalyst for this question was a Stack Overflow question I answered:

https://stackoverflow.com/questions/37365311/why-are-python-3-6-literal-formatted-strings-so-slow

Compared the str.format() the BUILD_LIST is the bottleneck here; dropping the LOAD_ATTR and CALL_FUNCTION opcodes are nice bonuses.

[ztane]

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.

[serhiy-storchaka]

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

[ztane]

And the expected performance for optimal f'X is {x}' code would be faster than "'X is %s' % (x,)" which still needs to interpret the string at runtime, and build a proper tuple object on stack.

[ericvsmith]

And the expected performance for optimal f'X is {x}' code would
be faster than "'X is %s' % (x,)" which still needs to
interpret the string at runtime, and build a proper tuple object
on stack.

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.

[ztane]

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 f(x) there, which necessarily has one extra bound method call and interpretation of format string as the overhead, so there's minimally at least 30 % performance boost to achieve.

[serprex]

The simplest perf fix is to first use BUILD_TUPLE instead of BUILD_LIST

timeit 'x=1;(x,x,x)'
0.36 usec per loop

timeit 'x=1;[x,x,x]'
0.425 usec per loop

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

[serprex]

Benchmarked f'X is {x}' with BUILD_TUPLE change:

Before: 6.62 usec per loop
After: 6.33 usec per loop

f'X is {x} {x+2} {x+3}'
Before: 15.1 usec per loop
After: 14.7 usec per loop

Attached patch

[serprex]

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"
'%s'%x 1.08 usec
'%s'%(x,) 2.04 usec
str(x) 2.9 usec
f'{x}' 3.65 usec

So we should not be aiming to compete with %. It may be worthy to convert the code to generate "x is {}".format calls tho

[ztane]

Yet the test cases just prove what is so expensive there: name lookups (global name str; looking up join on a string instance); building a tuple (for function arguments) is expensive as well. Of course __format__ will be costly as well as it is not a slot-method, needs to build a new string etc.

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 PyUnicode_CheckExact and no arguments, don't need to build a tuple to join it.