From fd7ed407d79b797e20d0a6fe69e18f9ba9354979 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Tue, 18 Dec 2007 21:24:09 +0000 Subject: Give meaning to the oparg for BUILD_MAP: estimated size of the dictionary. Allows dictionaries to be pre-sized (upto 255 elements) saving time lost to re-sizes with their attendant mallocs and re-insertions. Has zero effect on small dictionaries (5 elements or fewer), a slight benefit for dicts upto 22 elements (because they had to resize once anyway), and more benefit for dicts upto 255 elements (saving multiple resizes during the build-up and reducing the number of collisions on the first insertions). Beyond 255 elements, there is no addional benefit. --- Include/dictobject.h | 1 + Lib/opcode.py | 2 +- Misc/NEWS | 4 ++++ Objects/dictobject.c | 17 +++++++++++++++++ Python/ceval.c | 2 +- Python/compile.c | 6 ++---- 6 files changed, 26 insertions(+), 6 deletions(-) diff --git a/Include/dictobject.h b/Include/dictobject.h index fec6295..c5378cf 100644 --- a/Include/dictobject.h +++ b/Include/dictobject.h @@ -110,6 +110,7 @@ PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp); PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp); PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key); PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, long hash); +PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused); /* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */ PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other); diff --git a/Lib/opcode.py b/Lib/opcode.py index c3457d0..cee5057 100644 --- a/Lib/opcode.py +++ b/Lib/opcode.py @@ -139,7 +139,7 @@ hasconst.append(100) name_op('LOAD_NAME', 101) # Index in name list def_op('BUILD_TUPLE', 102) # Number of tuple items def_op('BUILD_LIST', 103) # Number of list items -def_op('BUILD_MAP', 104) # Always zero for now +def_op('BUILD_MAP', 104) # Number of dict entries (upto 255) name_op('LOAD_ATTR', 105) # Index in name list def_op('COMPARE_OP', 106) # Comparison operator hascompare.append(106) diff --git a/Misc/NEWS b/Misc/NEWS index 1599ade..40e9e6a 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -12,6 +12,10 @@ What's New in Python 2.6 alpha 1? Core and builtins ----------------- +- Compiler now generates simpler and faster code for dictionary literals. + The oparg for BUILD_MAP now indicates an estimated dictionary size. + There is a new opcode, STORE_MAP, for adding entries to the dictionary. + - Issue #1638: %zd configure test fails on Linux - Issue #1620: New property decorator syntax was modifying the decorator diff --git a/Objects/dictobject.c b/Objects/dictobject.c index bfb093b..365aac6 100644 --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -549,6 +549,23 @@ dictresize(PyDictObject *mp, Py_ssize_t minused) return 0; } +/* Create a new dictionary pre-sized to hold an estimated number of elements. + Underestimates are okay because the dictionary will resize as necessary. + Overestimates just mean the dictionary will be more sparse than usual. +*/ + +PyObject * +_PyDict_NewPresized(Py_ssize_t minused) +{ + PyObject *op = PyDict_New(); + + if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) { + Py_DECREF(op); + return NULL; + } + return op; +} + /* Note that, for historical reasons, PyDict_GetItem() suppresses all errors * that may occur (originally dicts supported only string keys, and exceptions * weren't possible). So, while the original intent was that a NULL return diff --git a/Python/ceval.c b/Python/ceval.c index 1af998d..b6501b3 100644 --- a/Python/ceval.c +++ b/Python/ceval.c @@ -1997,7 +1997,7 @@ PyEval_EvalFrameEx(PyFrameObject *f, int throwflag) break; case BUILD_MAP: - x = PyDict_New(); + x = _PyDict_NewPresized((Py_ssize_t)oparg); PUSH(x); if (x != NULL) continue; break; diff --git a/Python/compile.c b/Python/compile.c index 3b0c53f..36ad8a4 100644 --- a/Python/compile.c +++ b/Python/compile.c @@ -2922,11 +2922,9 @@ compiler_visit_expr(struct compiler *c, expr_ty e) case IfExp_kind: return compiler_ifexp(c, e); case Dict_kind: - /* XXX get rid of arg? */ - ADDOP_I(c, BUILD_MAP, 0); n = asdl_seq_LEN(e->v.Dict.values); - /* We must arrange things just right for STORE_SUBSCR. - It wants the stack to look like (value) (dict) (key) */ + ADDOP_I(c, BUILD_MAP, (n>255 ? 255 : n)); + n = asdl_seq_LEN(e->v.Dict.values); for (i = 0; i < n; i++) { VISIT(c, expr, (expr_ty)asdl_seq_GET(e->v.Dict.values, i)); -- cgit v0.12