[Python-ideas] Ordering keyword dicts

[Nick Coghlan]

(migrating thread from python-dev to python-ideas)

On 10 June 2013 13:13, Alexander Belopolsky
<alexander.belopolsky at gmail.com> wrote:
>
> On Sun, May 19, 2013 at 1:47 AM, Guido van Rossum <guido at python.org> wrote:
>>
>> I'm slow at warming up to the idea. My main concern is speed -- since
>> most code doesn't need it and function calls are already slow (and
>> obviously very common :-) it would be a shame if this slowed down
>> function calls that don't need it noticeably.
>
>
> Here is an idea that will not affect functions that don't need to know the
> order of keywords: a special __kworder__ local variable.  The use of this
> variable inside the function will signal compiler to generate additional
> bytecode to copy keyword names from the stack to a tuple and save it in
> __kworder__.    With that feature, an OrderedDict constructor, for example
> can be written as
>
> def odict(**kwargs):
>       return OrderedDict([(key, kwargs[key]) for key in __kworder__])

The problem is that this is too late to help. To help folks understand
the *technical* (rather than conceptual) limitations that are at issue
in only *sometimes* ordering the keyword arguments here's an overview
of the way the binding of arguments to parameters currently works:

1. In the calling bytecode, the arguments are collected together on
the stack as positional arguments and keyword arguments:

>>> def f():
...     return call(1, 2, *(3, 4), x=1, y=2, **{'z':3})
...
>>> dis(f)
  2           0 LOAD_GLOBAL              0 (call)
              3 LOAD_CONST               1 (1)
              6 LOAD_CONST               2 (2)
              9 LOAD_CONST               3 ('x')
             12 LOAD_CONST               1 (1)
             15 LOAD_CONST               4 ('y')
             18 LOAD_CONST               2 (2)
             21 LOAD_CONST               8 ((3, 4))
             24 BUILD_MAP                1
             27 LOAD_CONST               5 (3)
             30 LOAD_CONST               7 ('z')
             33 STORE_MAP
             34 CALL_FUNCTION_VAR_KW   514 (2 positional, 2 keyword
pair)
             37 RETURN_VALUE

The various "CALL_FUNCTION*" opcodes in CPython almost always end up
passing through a snippet like the following in ceval.c [1,2] (there
are a couple of exceptions related to optimisation of calls that only
involve positional arguments and parameters):

    if (PyCFunction_Check(func)) {
        PyThreadState *tstate = PyThreadState_GET();
        C_TRACE(result, PyCFunction_Call(func, callargs, kwdict));
    }
    else
        result = PyObject_Call(func, callargs, kwdict);

[1] http://hg.python.org/cpython/file/default/Python/ceval.c#l4389
[2] http://hg.python.org/cpython/file/default/Python/ceval.c#l4484

You can see a couple of things here:

* That *any* collection of arguments, regardless of syntax, is reduced
to a positional argument tuple and a keyword argument dictionary
before handing it over to the callable to handle the binding of
arguments to parameters.
* That this applies even to the optimised fast path that lets
functions implemented in C avoid some of the overhead associated with
the method dispatch machinery.

2. In the called object, the supplied arguments are bound
appropriately as parameters. There's a lot more variability in how
this happens. C functions usually use PyArg_ParseTuple or
PyArg_ParseTupleAndKeywords. Python functions handle it as an implicit
part of the frame initialization based on the function metadata.

Guido's speed concern is specifically with any approach which requires
the calling code to *always* check callables to see whether they want
an ordered dictionary or not. Before we proceed to considering more
exotic design ideas that require an "ordered or not" decision at the
call sites, this concern should be validated by someone trying it out
and checking the macro benchmark suite for the consequences.

This can be done without actually making it possible to define
functions that require order preservation - since we're mostly
interested in the performance consequences when such a flag *isn't*
set on the callables, an extra redundant check against
"PyCFunction_GET_FLAGS(func) & 0x8000" (for PyCFunction instances),
falling back to something like "PyObject_GetAttrId(__name__)" (for
everything else), for all code paths in ceval.c that lead to creation
of a kwdict instance should suffice.

It may be that the cost of the flag check is swamped by the cost of
actually creating the keyword dictionary, in which case the runtime
check would be a preferable design choice, since function *invocation*
wouldn't need to change, only function declarations.

Cheers,
Nick.

--
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia