classification
Title: Opcode for creating dict with constant keys
Type: enhancement Stage: resolved
Components: Interpreter Core Versions: Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Demur Rumed, Mark.Shannon, benjamin.peterson, brett.cannon, georg.brandl, haypo, ncoghlan, python-dev, serhiy.storchaka, yselivanov
Priority: normal Keywords: needs review, patch

Created on 2016-05-27 20:40 by serhiy.storchaka, last changed 2016-06-16 10:56 by haypo. This issue is now closed.

Files
File name Uploaded Description Edit
BUILD_MAP_EX.patch serhiy.storchaka, 2016-05-30 09:31 review
BUILD_CONST_KEY_MAP.patch serhiy.storchaka, 2016-05-30 14:02 review
Messages (13)
msg266511 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-05-27 20:40
BUILD_MAP, BUILD_MAP_UNPACK and BUILD_MAP_UNPACK_WITH_CALL need pushing key-value pairs on the stack. If keys and values are not constant, this is correct order of evaluating them. But if keys are constant (very common case), the order of pushing them doesn't affect semantic. We can pack them in constant tuple and push on the stack by one instruction.

I think there would be a benefit from adding new opcodes that take a sequence of values and a tuple of keys instead of a sequence of key-value pairs.

New MAKE_FUNCTION (issue27095) and new CALL_FUNCTION (issue yet not opened) could have a benefit.
msg266685 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-05-30 09:31
Proposed patch adds the BUILD_MAP_EX opcode (maybe somebody propose better name?). It takes values from the stack and keys from the tuple on the top of the stack. Currently it affects only creating a dict with const keys and calling a function with keywords after the var-keyword argument.

$ echo "{'a': 1, 'b': 2, 'c': 3}" | ./python -m dis

Unpatched:

  1           0 LOAD_CONST               0 ('a')
              2 LOAD_CONST               1 (1)
              4 LOAD_CONST               2 ('b')
              6 LOAD_CONST               3 (2)
              8 LOAD_CONST               4 ('c')
             10 LOAD_CONST               5 (3)
             12 BUILD_MAP                3
             14 POP_TOP
             16 LOAD_CONST               6 (None)
             18 RETURN_VALUE

Patched:

  1           0 LOAD_CONST               0 (1)
              2 LOAD_CONST               1 (2)
              4 LOAD_CONST               2 (3)
              6 LOAD_CONST               7 (('a', 'b', 'c'))
              8 BUILD_MAP_EX             3
             10 POP_TOP
             12 LOAD_CONST               6 (None)
             14 RETURN_VALUE

$ echo "f(**kw, a=1, b=2, c=3)" | ./python -m dis

Unpatched:

  1           0 LOAD_NAME                0 (f)
              2 LOAD_NAME                1 (kw)
              4 LOAD_CONST               0 ('a')
              6 LOAD_CONST               1 (1)
              8 LOAD_CONST               2 ('b')
             10 LOAD_CONST               3 (2)
             12 LOAD_CONST               4 ('c')
             14 LOAD_CONST               5 (3)
             16 BUILD_MAP                3
             18 EXTENDED_ARG             1
             20 BUILD_MAP_UNPACK_WITH_CALL   258
             22 CALL_FUNCTION_KW         0 (0 positional, 0 keyword pair)
             24 POP_TOP
             26 LOAD_CONST               6 (None)
             28 RETURN_VALUE

Patched:

  1           0 LOAD_NAME                0 (f)
              2 LOAD_NAME                1 (kw)
              4 LOAD_CONST               0 (1)
              6 LOAD_CONST               1 (2)
              8 LOAD_CONST               2 (3)
             10 LOAD_CONST               7 (('a', 'b', 'c'))
             12 BUILD_MAP_EX             3
             14 EXTENDED_ARG             1
             16 BUILD_MAP_UNPACK_WITH_CALL   258
             18 CALL_FUNCTION_KW         0 (0 positional, 0 keyword pair)
             20 POP_TOP
             22 LOAD_CONST               6 (None)
             24 RETURN_VALUE

It could be more useful for new MAKE_FUNCTION opcode (issue27095) and maybe for new CALL_FUNCTION* opcodes.

The benefit of BUILD_MAP_EX is less LOAD_CONST instructions and less stack consuming.
msg266689 - (view) Author: Demur Rumed (Demur Rumed) * Date: 2016-05-30 12:14
Perhaps BUILD_CONST_KEY_MAP?

Ideally the opcode could ellide the LOAD_CONST for the tuple. ie have LOAD_CONST 2 (1, 2, 3), BUILD_CONST_KEY_MAP 3 be BUILD_CONST_KEY_MAP 2 (1, 2, 3). However that'd require stack_effect to somehow lookup the const tuple

Thinking to in the context of MAKE_FUNCTION, I'd like to create a function for ceval which takes stack_pointer & returns stack_pointer at new offset with dict at top of stack. Then use this both for this opcode & have MAKE_FUNCTION call it directly (ie, don't have to emit BUILD_MAP_EX). This too makes for a need to do some backtracking to figure out stack effect

Relying on the peepholer seems unideal; it does more work than generating the tuple the first time & doing it eagerly will produce a more compact stack depth & co_consts
msg266694 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-05-30 14:02
> Perhaps BUILD_CONST_KEY_MAP?

LGTM.

> Ideally the opcode could ellide the LOAD_CONST for the tuple. ie have LOAD_CONST 2 (1, 2, 3), BUILD_CONST_KEY_MAP 3 be BUILD_CONST_KEY_MAP 2 (1, 2, 3). However that'd require stack_effect to somehow lookup the const tuple

I like this idea. But PyCompile_OpcodeStackEffect() doesn't have an access to the consts dict.

> Relying on the peepholer seems unideal; it does more work than generating the tuple the first time & doing it eagerly will produce a more compact stack depth & co_consts

I thought that this would be not easy. But thanks to your encouraging I have tried to do this and the result is pretty simple.

In updated patch the opcode name was changed to BUILD_CONST_KEY_MAP, and the compiler no longer depends on the peephole optimizer for generating constant keys tuple. Thank you Demur.
msg267177 - (view) Author: Demur Rumed (Demur Rumed) * Date: 2016-06-03 22:14
When is this intended to be merged? I've been waiting on this before updating the patch @ #27095 with fixes to other code review comments
msg268021 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-09 12:16
Could anyone please make a review?
msg268096 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2016-06-10 06:46
Does this change break this function?
def subtle():
    one = {-0. : 'a', -1: 'b'}
    two = {0. : 'a', -1: 'b'}
    assert all(math.copysign(1, x) < 0 for x in one)
    assert any(math.copysign(1, x) > 0 for x in two)
Perhaps you should restrict yourself to strings...
msg268099 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-10 07:16
I didn't test, but I'm sure this change doesn't break this function. Otherwise functions containing (0.0, 1) and (-0.0, -1) would be broken. Actually they were broken until recently Victor fixed this bug.
msg268103 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-10 07:48
I have just tested. BUILD_CONST_KEY_MAP doesn't used in it, because at this time -0. still is not a constant, but an expression (negation of 0.). With -0 it doesn't work too.

$ ./python -m dis
{0: 1, 2: 3}
  1           0 LOAD_CONST               0 (1)
              2 LOAD_CONST               1 (3)
              4 LOAD_CONST               2 ((0, 2))
              6 BUILD_CONST_KEY_MAP      2
              8 POP_TOP
             10 LOAD_CONST               3 (None)
             12 RETURN_VALUE
$ ./python -m dis
{-0: 1, 2: 3}    
  1           0 LOAD_CONST               5 (0)
              2 LOAD_CONST               1 (1)
              4 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              8 BUILD_MAP                2
             10 POP_TOP
             12 LOAD_CONST               4 (None)
             14 RETURN_VALUE
msg268273 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2016-06-11 21:09
Okay, I think it's fine then. However, you have a for loop in compiler_subkwargs which only executes once.
msg268281 - (view) Author: Roundup Robot (python-dev) Date: 2016-06-11 21:40
New changeset 27b0dbaf0ea8 by Serhiy Storchaka in branch 'default':
Issue #27140: Added BUILD_CONST_KEY_MAP opcode.
https://hg.python.org/cpython/rev/27b0dbaf0ea8
msg268282 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-11 21:43
Yes, I left it for symmetry and for easier modifying if we will add more restrictions on using BUILD_CONST_KEY_MAP. Thank you for your reviews Demur and Benjamin.
msg268655 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2016-06-16 10:56
Nice enhancement.
History
Date User Action Args
2016-06-16 10:56:04hayposetmessages: + msg268655
2016-06-16 09:35:19serhiy.storchakasetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2016-06-11 21:43:52serhiy.storchakasetmessages: + msg268282
2016-06-11 21:40:36python-devsetnosy: + python-dev
messages: + msg268281
2016-06-11 21:09:30benjamin.petersonsetmessages: + msg268273
2016-06-10 07:48:39serhiy.storchakasetmessages: + msg268103
2016-06-10 07:16:58serhiy.storchakasetmessages: + msg268099
2016-06-10 06:46:34benjamin.petersonsetmessages: + msg268096
2016-06-09 12:16:12serhiy.storchakasetkeywords: + needs review

messages: + msg268021
2016-06-04 21:05:43serhiy.storchakasetnosy: + Mark.Shannon
2016-06-04 07:46:00serhiy.storchakalinkissue27213 dependencies
2016-06-03 22:14:59Demur Rumedsetmessages: + msg267177
2016-05-30 14:02:41serhiy.storchakasetfiles: + BUILD_CONST_KEY_MAP.patch

messages: + msg266694
2016-05-30 12:14:52Demur Rumedsetmessages: + msg266689
2016-05-30 09:31:19serhiy.storchakasetfiles: + BUILD_MAP_EX.patch

nosy: + brett.cannon, georg.brandl, ncoghlan, benjamin.peterson, yselivanov
messages: + msg266685

keywords: + patch
stage: needs patch -> patch review
2016-05-27 20:41:57hayposetnosy: + haypo
2016-05-27 20:40:40serhiy.storchakacreate