Unnecessary closure in ast.literal_eval

[aaronchall]

BPO	31753
Nosy	@rhettinger, @terryjreedy, @serhiy-storchaka, @aaronchall
Files	variable_access.py

^{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 = None
closed_at = <Date 2019-03-20.20:22:51.939>
created_at = <Date 2017-10-10.22:02:07.728>
labels = ['library', 'performance']
title = 'Unnecessary closure in ast.literal_eval'
updated_at = <Date 2021-05-12.21:14:31.550>
user = 'https://github.com/aaronchall'

bugs.python.org fields:

activity = <Date 2021-05-12.21:14:31.550>
actor = 'terry.reedy'
assignee = 'none'
closed = True
closed_date = <Date 2019-03-20.20:22:51.939>
closer = 'Aaron Hall'
components = ['Library (Lib)']
creation = <Date 2017-10-10.22:02:07.728>
creator = 'Aaron Hall'
dependencies = []
files = ['47225']
hgrepos = []
issue_num = 31753
keywords = []
message_count = 12.0
messages = ['304089', '304092', '304101', '304143', '304215', '304221', '304356', '304520', '304532', '304554', '338510', '393533']
nosy_count = 5.0
nosy_names = ['rhettinger', 'terry.reedy', 'serhiy.storchaka', 'Aaron Hall', 'thierry.excoffier']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue31753'
versions = []

[aaronchall]

Removing the closure seems to make the function about 10% faster.

Original source code at: https://github.com/python/cpython/blob/3.6/Lib/ast.py#L40

Empirical evidence: astle.py

import timeit
from ast import literal_eval as orig_literal_eval
from ast import *

def new_literal_eval(node_or_string):
    """
    Safely evaluate an expression node or a string containing a Python
    expression.  The string or node provided may only consist of the following
    Python literal structures: strings, bytes, numbers, tuples, lists, dicts,
    sets, booleans, and None.
    """
    if isinstance(node_or_string, str):
        node_or_string = parse(node_or_string, mode='eval')
    if isinstance(node_or_string, Expression):
        node_or_string = node_or_string.body
    node = node_or_string
    if isinstance(node, Constant):
        return node.value
    elif isinstance(node, (Str, Bytes)):
        return node.s
    elif isinstance(node, Num):
        return node.n
    elif isinstance(node, Tuple):
        return tuple(map(_convert, node.elts))
    elif isinstance(node, List):
        return list(map(_convert, node.elts))
    elif isinstance(node, Set):
        return set(map(_convert, node.elts))
    elif isinstance(node, Dict):
        return dict((_convert(k), _convert(v)) for k, v
                    in zip(node.keys, node.values))
    elif isinstance(node, NameConstant):
        return node.value
    elif isinstance(node, UnaryOp) and isinstance(node.op, (UAdd, USub)):
        operand = _convert(node.operand)
        if isinstance(operand, _NUM_TYPES):
            if isinstance(node.op, UAdd):
                return + operand
            else:
                return - operand
    elif isinstance(node, BinOp) and isinstance(node.op, (Add, Sub)):
        left = _convert(node.left)
        right = _convert(node.right)
        if isinstance(left, _NUM_TYPES) and isinstance(right, _NUM_TYPES):
            if isinstance(node.op, Add):
                return left + right
            else:
                return left - right
    raise ValueError('malformed node or string: ' + repr(node))



def main():
    print('orig first, then new')
    print("'1.01'")
    print(min(timeit.repeat(lambda: orig_literal_eval('1.01'))))
    print(min(timeit.repeat(lambda: new_literal_eval('1.01'))))
    print("""'"1.01"'""")
    print(min(timeit.repeat(lambda: orig_literal_eval('"1.01"'))))
    print(min(timeit.repeat(lambda: new_literal_eval('"1.01"'))))
    print("'1'")
    print(min(timeit.repeat(lambda: orig_literal_eval('1'))))
    print(min(timeit.repeat(lambda: new_literal_eval('1'))))


if __name__ == '__main__':
    main()

Shell:

$ python -m astle
orig first, then new
'1.01'
3.518230145502848
3.274753015923377
'"1.01"'
3.189016693752965
2.906869704238048
'1'
3.40557457956146
3.157061471625788

[serhiy-storchaka]

Test more complex examples including list and dict displays, binary operators.

[aaronchall]

Rejecting and withdrawing with apologies.

[aaronchall]

So... moving the closure (which may be called recursively) to the global scope actually does improve performance (for small cases, about 10% - larger cases amortize the cost of the closure being built, but in a 100 item dictionary, still about 4% faster to extricate the closure). So I'm reopening. Also suggesting we consider doing this with other functions if they are unnecessarily closures in the module.

fix_missing_locations appears to be another such function with an unnecessary closure.

the closure in dump cannot be removed without some rewriting of the signature, as it uses variables it closes over. Not sure this would be worth it.

[rhettinger]

I prefer the existing code and think this shouldn't be changed.

[serhiy-storchaka]

I prefer the existing code too.

But I'm surprised that this change has a measurable effects at all. I thought that creating a closure is cheaper. Of course it is much faster than creating a class. Maybe it is worth to spend some time for optimizing closure creation.

[terryjreedy]

On win10, installed 3.7.0a1, speedup is 7-8% (It is 'only' 5% on repository debug build that takes 5-6 times longer.)

[aaronchall]

Static analysis:

My mental model currently says the rebuilt function every outer call is an expense with no offsetting benefit. It seems that a function shouldn't build a closure on every call if the closure doesn't close over anything immediately used by the functionality. But I can't explain why the cost doesn't amortize toward zero in my testing.

Usage analysis:

On the other hand, this doesn't seem used very much at all in the std lib.
I'm not sure what the entire global benefit is to moving the closure to be a global instead - but there are about 88000 potential uses of the code on github: https://github.com/search?p=3&q=literal_eval&type=Code&utf8=%E2%9C%93 One use seems to be scanning Python code - so potentially it gets a lot of use?

Alternatively: - to echo Serhiy ("Maybe it is worth to spend some time for optimizing closure creation."), perhaps the matter could be made irrelevant by looking at how we handle closures. I'm not sure why the difference didn't amortize to nearly nothing in my testing - I used Anaconda's Python 3.6.1 distribution on Linux - if that matters.

Potential improvement:

So to be clear, the suggested change would probably be to move _convert to a global, maybe named _literal_eval_convert (this is less half-baked than my first code post, which I somewhat regret. Note that the recursive calls would need to be edited as well as the move and dedent.):

def literal_eval(node_or_string):
    """
    Safely evaluate an expression node or a string containing a Python
    expression.  The string or node provided may only consist of the following
    Python literal structures: strings, bytes, numbers, tuples, lists, dicts,
    sets, booleans, and None.
    """
    if isinstance(node_or_string, str):
        node_or_string = parse(node_or_string, mode='eval')
    if isinstance(node_or_string, Expression):
        node_or_string = node_or_string.body
    return _literal_eval_convert(node_or_string)


def _literal_eval_convert(node):
    if isinstance(node, Constant):
        return node.value
    elif isinstance(node, (Str, Bytes)):
        return node.s
    elif isinstance(node, Num):
        return node.n
    elif isinstance(node, Tuple):
        return tuple(map(_literal_eval_convert, node.elts))
    elif isinstance(node, List):
        return list(map(_literal_eval_convert, node.elts))
    elif isinstance(node, Set):
        return set(map(_literal_eval_convert, node.elts))
    elif isinstance(node, Dict):
        return dict((_literal_eval_convert(k), _literal_eval_convert(v)) for k, v
                    in zip(node.keys, node.values))
    elif isinstance(node, NameConstant):
        return node.value
    elif isinstance(node, UnaryOp) and isinstance(node.op, (UAdd, USub)):
        operand = _literal_eval_convert(node.operand)
        if isinstance(operand, _NUM_TYPES):
            if isinstance(node.op, UAdd):
                return + operand
            else:
                return - operand
    elif isinstance(node, BinOp) and isinstance(node.op, (Add, Sub)):
        left = _literal_eval_convert(node.left)
        right = _literal_eval_convert(node.right)
        if isinstance(left, _NUM_TYPES) and isinstance(right, _NUM_TYPES):
            if isinstance(node.op, Add):
                return left + right
            else:
                return left - right
    raise ValueError('malformed node or string: ' + repr(node))

Note that I am not strongly committed to this issue, and won't feel badly if it is closed. It just seemed to be some low-hanging fruit in the standard library that I happened across.

[aaronchall]

New information: I think I have pinpointed at least a contributor to the difference - closure lookups seem to be currently slightly slower (by a few percent) than global lookups (see https://stackoverflow.com/a/46798876/541136).

And as we can see, an inner function that references itself is a closure on itself (see LOAD_DEREF):

>>> def foo():
...     def bar():
...         return bar
...     return bar
...
>>> bar = foo()
>>> import dis
>>> dis.dis(bar)
  3           0 LOAD_DEREF               0 (bar)
              2 RETURN_VALUE

This, at least to me, explains why the performance difference doesn't completely amortize away.

[rhettinger]

I question those timings. Here's the results from a script I've been using for many years:

$ python3.6 variable_access.py
0.065	read_local
0.068	read_nonlocal
0.179	read_global
0.236	read_builtin
0.267	read_classvar
0.392	read_instancevar
0.291	read_unboundmethod
0.383	read_boundmethod
0.077	write_local
0.069	write_nonlocal
0.240	write_global
1.154	write_classvar
0.540	write_instance

See the attached timing script: variable_access.py

Also, take a look at the underlying code:

        #define GETLOCAL(i)     (fastlocals[i])

        TARGET(LOAD_FAST) {
            PyObject *value = GETLOCAL(oparg);
            if (value == NULL) {
                ...
            }
            Py_INCREF(value);
            PUSH(value);
            FAST_DISPATCH();
        }

        #define PyCell_GET(op) (((PyCellObject *)(op))->ob_ref)

        TARGET(LOAD_DEREF) {
            PyObject *cell = freevars[oparg];
            PyObject *value = PyCell_GET(cell);
            if (value == NULL) {
                ...
            }
            Py_INCREF(value);
            PUSH(value);
            DISPATCH();
        }

You can see that the only difference is that LOAD_DEREF has one extra indirection. That should be very cheap. In contrast, a LOAD_GLOBAL does a lot more work. If this isn't evident in your timings, I suspect there is something wrong with the timings.

[aaronchall]

No need to keep this open, I agree with the core developers this shouldn't be changed.