classification
Title: Unnecessary closure in ast.literal_eval
Type: performance Stage: resolved
Components: Library (Lib) Versions:
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: Aaron Hall, rhettinger, serhiy.storchaka, terry.reedy
Priority: normal Keywords:

Created on 2017-10-10 22:02 by Aaron Hall, last changed 2017-10-18 04:09 by rhettinger.

Files
File name Uploaded Description Edit
variable_access.py rhettinger, 2017-10-18 04:09
Messages (10)
msg304089 - (view) Author: Aaron Hall (Aaron Hall) * Date: 2017-10-10 22:02
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
msg304092 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-10-10 22:20
Test more complex examples including list and dict displays, binary operators.
msg304101 - (view) Author: Aaron Hall (Aaron Hall) * Date: 2017-10-11 02:34
Rejecting and withdrawing with apologies.
msg304143 - (view) Author: Aaron Hall (Aaron Hall) * Date: 2017-10-11 14:31
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.
msg304215 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-10-12 07:53
I prefer the existing code and think this shouldn't be changed.
msg304221 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-10-12 08:52
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.
msg304356 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2017-10-13 20:33
On win10, installed 3.7.0a1, speedup is 7-8% (It is 'only' 5% on repository debug build that takes 5-6 times longer.)
msg304520 - (view) Author: Aaron Hall (Aaron Hall) * Date: 2017-10-17 19:48
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.
msg304532 - (view) Author: Aaron Hall (Aaron Hall) * Date: 2017-10-17 21:01
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.
msg304554 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-10-18 04:09
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.
History
Date User Action Args
2017-10-18 04:09:08rhettingersetfiles: + variable_access.py

messages: + msg304554
2017-10-17 21:01:50Aaron Hallsetmessages: + msg304532
2017-10-17 19:48:42Aaron Hallsetmessages: + msg304520
2017-10-13 20:33:07terry.reedysetnosy: + terry.reedy
messages: + msg304356
2017-10-12 08:52:29serhiy.storchakasetmessages: + msg304221
2017-10-12 07:53:59rhettingersetnosy: + rhettinger
messages: + msg304215
2017-10-11 14:31:07Aaron Hallsetstatus: closed -> open
resolution: rejected ->
messages: + msg304143
2017-10-11 02:34:11Aaron Hallsetstatus: open -> closed
resolution: rejected
messages: + msg304101

stage: resolved
2017-10-10 22:20:51serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg304092
2017-10-10 22:02:07Aaron Hallcreate