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.

1 files changed, 17 insertions, 0 deletions

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