This branch explores the performance implications of relacing the novem_ak_preserve_experiments

dynamic array data structure underlying Tcl_Preserve/Release with a
Tcl_HashTable, i.e a change from nominally O(n) to nominally O(1).  In
this initial work the Reference data structures are individually
allocated and freed. A continuation may add a free-list of structures
for quicker re-use without going through the memory manager.

Other things we can explore here: Does it make sense to use TSD (i.e.
Thread-Specific Data), to get rid of the mutex currently used in this
subsystem ? Or even better, can we assume that preserved data is
always tied to some interpreter, allowing us to tie the data
structures here in the same manner ?

Passes testsuite.

Note: I have no specific benchmark here, only tclbench. Which makes it difficult to discern how much loss or gain we have. Looking over the table it seems to be roughly +/-0. Tools making the comparison of two tclbench results easier would be appreciated.

1 files changed, 102 insertions, 76 deletions

diff --git a/generic/tclPreserve.c b/generic/tclPreserve.c
index 0bd8f93..6950dd7 100644
--- a/generic/tclPreserve.c
+++ b/generic/tclPreserve.c
@@ -10,6 +10,18 @@
  *
  * See the file "license.terms" for information on usage and redistribution of
  * this file, and for a DISCLAIMER OF ALL WARRANTIES.
+ *
+ *
+ * === NOVEM EXPERIMENT ===
+ *   Replace the dynamic var-sized array of References with a
+ *   hashtable. Faster lookup, no linear search.
+ *
+ *   Current disadvantage - Possible higher memory churn as individual
+ *   Reference structures get allocated and freed.
+ *
+ *   Could be fixable by using a list-based stack of free/reusable Reference
+ *   structures.
+ * === NOVEM EXPERIMENT ===
  */
 
 #include "tclInt.h"
@@ -36,14 +48,9 @@ typedef struct {
  * These variables are protected by "preserveMutex".
  */
 
-static Reference *refArray = NULL;	/* First in array of references. */
-static int spaceAvl = 0;	/* Total number of structures available at
-				 * *firstRefPtr. */
-static int inUse = 0;		/* Count of structures currently in use in
-				 * refArray. */
-TCL_DECLARE_MUTEX(preserveMutex)/* To protect the above statics */
+static Tcl_HashTable* refTable;
 
-#define INITIAL_SIZE	2	/* Initial number of reference slots to make */
+TCL_DECLARE_MUTEX(preserveMutex)/* To protect the above statics */
 
 /*
  * The following data structure is used to keep track of whether an arbitrary
@@ -88,11 +95,19 @@ void
 TclFinalizePreserve(void)
 {
     Tcl_MutexLock(&preserveMutex);
-    if (spaceAvl != 0) {
-	ckfree(refArray);
-	refArray = NULL;
-	inUse = 0;
-	spaceAvl = 0;
+    if (refTable) {
+	for (;;) {
+	    Reference* refPtr;
+	    Tcl_HashSearch s;
+	    Tcl_HashEntry* hEntry;
+	    hEntry = Tcl_FirstHashEntry (refTable, &s);
+	    if (!hEntry) break;
+	    refPtr = Tcl_GetHashValue (hEntry);
+	    Tcl_DeleteHashEntry (hEntry);
+	    ckfree (refPtr);
+	}
+	Tcl_DeleteHashTable (refTable);
+	refTable = 0;
     }
     Tcl_MutexUnlock(&preserveMutex);
 }
@@ -121,7 +136,8 @@ Tcl_Preserve(
     ClientData clientData)	/* Pointer to malloc'ed block of memory. */
 {
     Reference *refPtr;
-    int i;
+    int isnew;
+    Tcl_HashEntry* hEntry;
 
     /*
      * See if there is already a reference for this pointer. If so, just
@@ -129,34 +145,34 @@ Tcl_Preserve(
      */
 
     Tcl_MutexLock(&preserveMutex);
-    for (i=0, refPtr=refArray ; i<inUse ; i++, refPtr++) {
-	if (refPtr->clientData == clientData) {
-	    refPtr->refCount++;
-	    Tcl_MutexUnlock(&preserveMutex);
-	    return;
-	}
+
+    if (!refTable) {
+	refTable = ckalloc (sizeof (Tcl_HashTable));
+	Tcl_InitHashTable (refTable, TCL_ONE_WORD_KEYS);
     }
 
-    /*
-     * Make a reference array if it doesn't already exist, or make it bigger
-     * if it is full.
-     */
+    hEntry = Tcl_FindHashEntry (refTable, clientData);
+    if (hEntry) {
+	refPtr = Tcl_GetHashValue (hEntry);
+	refPtr->refCount++;
 
-    if (inUse == spaceAvl) {
-	spaceAvl = spaceAvl ? 2*spaceAvl : INITIAL_SIZE;
-	refArray = ckrealloc(refArray, spaceAvl * sizeof(Reference));
+	Tcl_MutexUnlock(&preserveMutex);
+	return;
     }
 
     /*
      * Make a new entry for the new reference.
      */
 
-    refPtr = &refArray[inUse];
+    refPtr = ckalloc (sizeof (Reference));
     refPtr->clientData = clientData;
     refPtr->refCount = 1;
     refPtr->mustFree = 0;
     refPtr->freeProc = TCL_STATIC;
-    inUse += 1;
+
+    hEntry = Tcl_CreateHashEntry (refTable, clientData, &isnew);
+    Tcl_SetHashValue (hEntry, refPtr);
+
     Tcl_MutexUnlock(&preserveMutex);
 }
 
@@ -184,60 +200,64 @@ Tcl_Release(
     ClientData clientData)	/* Pointer to malloc'ed block of memory. */
 {
     Reference *refPtr;
-    int i;
+    Tcl_HashEntry* hEntry;
+    int mustFree;
+    Tcl_FreeProc *freeProc;
 
     Tcl_MutexLock(&preserveMutex);
-    for (i=0, refPtr=refArray ; i<inUse ; i++, refPtr++) {
-	int mustFree;
-	Tcl_FreeProc *freeProc;
 
-	if (refPtr->clientData != clientData) {
-	    continue;
-	}
+    if (!refTable) {
+	refTable = ckalloc (sizeof (Tcl_HashTable));
+	Tcl_InitHashTable (refTable, TCL_ONE_WORD_KEYS);
+    }
 
-	if (--refPtr->refCount != 0) {
-	    Tcl_MutexUnlock(&preserveMutex);
-	    return;
-	}
+    hEntry = Tcl_FindHashEntry (refTable, clientData);
+    if (!hEntry) {
+	Tcl_MutexUnlock(&preserveMutex);
 
 	/*
-	 * Must remove information from the slot before calling freeProc to
-	 * avoid reentrancy problems if the freeProc calls Tcl_Preserve on the
-	 * same clientData. Copy down the last reference in the array to
-	 * overwrite the current slot.
+	 * Reference not found. This is a bug in the caller.
 	 */
 
-	freeProc = refPtr->freeProc;
-	mustFree = refPtr->mustFree;
-	inUse--;
-	if (i < inUse) {
-	    refArray[i] = refArray[inUse];
-	}
+	Tcl_Panic("Tcl_Release couldn't find reference for %p", clientData);
+    }
 
-	/*
-	 * Now committed to disposing the data. But first, we've patched up
-	 * all the global data structures so we should release the mutex now.
-	 * Only then should we dabble around with potentially-slow memory
-	 * managers...
-	 */
+    refPtr = Tcl_GetHashValue (hEntry);
 
+    if (--refPtr->refCount != 0) {
 	Tcl_MutexUnlock(&preserveMutex);
-	if (mustFree) {
-	    if (freeProc == TCL_DYNAMIC) {
-		ckfree(clientData);
-	    } else {
-		freeProc(clientData);
-	    }
-	}
 	return;
     }
-    Tcl_MutexUnlock(&preserveMutex);
 
     /*
-     * Reference not found. This is a bug in the caller.
+     * Must remove information from the slot before calling freeProc to
+     * avoid reentrancy problems if the freeProc calls Tcl_Preserve on the
+     * same clientData.
      */
 
-    Tcl_Panic("Tcl_Release couldn't find reference for %p", clientData);
+    freeProc = refPtr->freeProc;
+    mustFree = refPtr->mustFree;
+
+    Tcl_DeleteHashEntry (hEntry);
+    ckfree (refPtr);
+
+    /*
+     * Now committed to disposing the data. But first, we've patched up
+     * all the global data structures so we should release the mutex now.
+     * Only then should we dabble around with potentially-slow memory
+     * managers...
+     */
+
+    Tcl_MutexUnlock(&preserveMutex);
+
+    if (mustFree) {
+	if (freeProc == TCL_DYNAMIC) {
+	    ckfree(clientData);
+	} else {
+	    freeProc(clientData);
+	}
+    }
+    return;
 }
 
 /*
@@ -264,7 +284,6 @@ Tcl_EventuallyFree(
     Tcl_FreeProc *freeProc)	/* Function to actually do free. */
 {
     Reference *refPtr;
-    int i;
 
     /*
      * See if there is a reference for this pointer. If so, set its "mustFree"
@@ -272,18 +291,25 @@ Tcl_EventuallyFree(
      */
 
     Tcl_MutexLock(&preserveMutex);
-    for (i = 0, refPtr = refArray; i < inUse; i++, refPtr++) {
-	if (refPtr->clientData != clientData) {
-	    continue;
-	}
-	if (refPtr->mustFree) {
-	    Tcl_Panic("Tcl_EventuallyFree called twice for %p", clientData);
+
+    if (refTable) {
+	Tcl_HashEntry* hEntry;
+
+	hEntry = Tcl_FindHashEntry (refTable, clientData);
+	if (hEntry) {
+	    refPtr = Tcl_GetHashValue (hEntry);
+
+	    if (refPtr->mustFree) {
+		Tcl_Panic("Tcl_EventuallyFree called twice for %p", clientData);
+	    }
+	    refPtr->mustFree = 1;
+	    refPtr->freeProc = freeProc;
+
+	    Tcl_MutexUnlock(&preserveMutex);
+	    return;
 	}
-	refPtr->mustFree = 1;
-	refPtr->freeProc = freeProc;
-	Tcl_MutexUnlock(&preserveMutex);
-	return;
     }
+
     Tcl_MutexUnlock(&preserveMutex);
 
     /*