Opcode for creating dict with constant keys

[serhiy-storchaka]

BPO	27140
Nosy	@brettcannon, @birkenfeld, @ncoghlan, @vstinner, @benjaminp, @markshannon, @serhiy-storchaka, @1st1, @serprex
Files	BUILD_MAP_EX.patch BUILD_CONST_KEY_MAP.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 = None
closed_at = <Date 2016-06-16.09:35:19.279>
created_at = <Date 2016-05-27.20:40:40.794>
labels = ['interpreter-core', 'type-feature']
title = 'Opcode for creating dict with constant keys'
updated_at = <Date 2016-06-16.10:56:04.316>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2016-06-16.10:56:04.316>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2016-06-16.09:35:19.279>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2016-05-27.20:40:40.794>
creator = 'serhiy.storchaka'
dependencies = []
files = ['43055', '43057']
hgrepos = []
issue_num = 27140
keywords = ['patch', 'needs review']
message_count = 13.0
messages = ['266511', '266685', '266689', '266694', '267177', '268021', '268096', '268099', '268103', '268273', '268281', '268282', '268655']
nosy_count = 10.0
nosy_names = ['brett.cannon', 'georg.brandl', 'ncoghlan', 'vstinner', 'benjamin.peterson', 'Mark.Shannon', 'python-dev', 'serhiy.storchaka', 'yselivanov', 'Demur Rumed']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue27140'
versions = ['Python 3.6']

[serhiy-storchaka]

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 (bpo-27095) and new CALL_FUNCTION (issue yet not opened) could have a benefit.

[serhiy-storchaka]

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 (bpo-27095) and maybe for new CALL_FUNCTION* opcodes.

The benefit of BUILD_MAP_EX is less LOAD_CONST instructions and less stack consuming.

[serprex]

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

[serhiy-storchaka]

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.

[serprex]

When is this intended to be merged? I've been waiting on this before updating the patch @ bpo-27095 with fixes to other code review comments

[serhiy-storchaka]

Could anyone please make a review?

[benjaminp]

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...

[serhiy-storchaka]

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.

[serhiy-storchaka]

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

[benjaminp]

Okay, I think it's fine then. However, you have a for loop in compiler_subkwargs which only executes once.

[python-dev]

New changeset 27b0dbaf0ea8 by Serhiy Storchaka in branch 'default':
Issue bpo-27140: Added BUILD_CONST_KEY_MAP opcode.
https://hg.python.org/cpython/rev/27b0dbaf0ea8

[serhiy-storchaka]

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.