Revised the set() and frozenset() implementaion to use its own internal

data structure instead of using dictionaries.  Reduces memory consumption
by 1/3 and provides modest speed-ups for most set operations.

1 files changed, 45 insertions, 13 deletions

diff --git a/Include/setobject.h b/Include/setobject.h
index cc2d683..8569ed1 100644
--- a/Include/setobject.h
+++ b/Include/setobject.h
@@ -1,4 +1,3 @@
-
 /* Set object interface */
 
 #ifndef Py_SETOBJECT_H
@@ -7,28 +6,61 @@
 extern "C" {
 #endif
 
+
 /*
-This data structure is shared by set and frozenset objects.
+There are three kinds of slots in the table:
+
+1. Unused:  key == NULL
+2. Active:  key != NULL and key != dummy
+3. Dummy:   key == dummy
 */
 
+#define PySet_MINSIZE 8
+
 typedef struct {
+	long hash;      /* cached hash code for the entry key */
+	PyObject *key;
+} setentry;
+
+
+/*
+This data structure is shared by set and frozenset objects.
+*/
+
+typedef struct _setobject PySetObject;
+struct _setobject {
 	PyObject_HEAD
-	PyObject *data;
-	long hash;	/* only used by frozenset objects */
-	PyObject *weakreflist; /* List of weak references */
-
-	/* Invariants:
-	 *     data is a dictionary whose values are all True.
-	 *     data points to the same dict for the whole life of the set.
-	 * For frozensets only:
-	 *     data is immutable.
-	 *     hash is the hash of the frozenset or -1 if not computed yet.
+
+	int fill;  /* # Active + # Dummy */
+	int used;  /* # Active */
+
+	/* The table contains mask + 1 slots, and that's a power of 2.
+	 * We store the mask instead of the size because the mask is more
+	 * frequently needed.
 	 */
-} PySetObject;
+	int mask;
+
+	/* table points to smalltable for small tables, else to
+	 * additional malloc'ed memory.  table is never NULL!  This rule
+	 * saves repeated runtime null-tests in the workhorse getitem and
+	 * setitem calls.
+	 */
+	setentry *table;
+	setentry *(*lookup)(PySetObject *so, PyObject *key, long hash);
+	setentry smalltable[PySet_MINSIZE];
+
+	long hash;		/* only used by frozenset objects */
+	PyObject *weakreflist;	/* List of weak references */
+};
 
 PyAPI_DATA(PyTypeObject) PySet_Type;
 PyAPI_DATA(PyTypeObject) PyFrozenSet_Type;
 
+/* Invariants for frozensets only:
+ *     data is immutable.
+ *     hash is the hash of the frozenset or -1 if not computed yet.
+ */
+
 #define PyFrozenSet_CheckExact(ob) ((ob)->ob_type == &PyFrozenSet_Type)
 #define PyAnySet_Check(ob) \
 	((ob)->ob_type == &PySet_Type || (ob)->ob_type == &PyFrozenSet_Type || \