From: Rusty Russell <rusty@rustcorp.com.au>
Date: Mon, 8 Nov 2010 03:02:51 +0000 (+1030)
Subject: htable: push capacity limit from 66 to 75%
X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=0473813acdfad62221ec9f2b9b41bc10d1f4586d

htable: push capacity limit from 66 to 75%

With the extra bits, long runs don't hurt our cache very much on search,
so we can pack quite a few in.  Here are the runs at maximal density before
and after:

Before:
$ ./speed 3145000
Initial insert:  248 ns
Details: hash size 4194304, mask bits 9, perfect 63%
Initial lookup (match):  122 ns
Initial lookup (miss):  142 ns
Initial lookup (random):  170 ns
Initial delete all:  134 ns
Details: rehashes 3145000
Initial re-inserting:  149 ns
Deleting first half:  73 ns
Details: rehashes 1572500, delete markers 1572500
Adding (a different) half:  128 ns
Details: delete markers 0, perfect 62%
Lookup after half-change (match):  129 ns
Lookup after half-change (miss):  145 ns
Details: initial churn
Churning second time:  703 ns
Churning third time:  725 ns
Churning fourth time:  717 ns
Churning fifth time:  710 ns
Details: reinserting with spread
Details: delete markers 149261, perfect 57%
Details: worst run 254 (2 deleted)
Lookup after churn & spread (match):  132 ns
Lookup after churn & spread (miss):  159 ns
Lookup after churn & spread (random):  184 ns
Deleting half after churn & spread:  71 ns
Adding (a different) half after churn & spread:  129 ns
Details: delete markers 0, perfect 62%

After:
$ ./speed 3145727
Initial insert:  232 ns
Details: hash size 4194304, mask bits 9, perfect 63%
Initial lookup (match):  122 ns
Initial lookup (miss):  141 ns
Initial lookup (random):  234 ns
Initial delete all:  129 ns
Details: rehashes 3145727
Initial re-inserting:  153 ns
Deleting first half:  80 ns
Details: rehashes 1572864, delete markers 1572864
Adding (a different) half:  137 ns
Details: delete markers 0, perfect 62%
Lookup after half-change (match):  125 ns
Lookup after half-change (miss):  145 ns
Details: initial churn
Churning second time:  702 ns
Churning third time:  719 ns
Churning fourth time:  712 ns
Churning fifth time:  709 ns
Details: reinserting with spread
Details: delete markers 169474, perfect 56%
Details: worst run 248 (12 deleted)
Lookup after churn & spread (match):  129 ns
Lookup after churn & spread (miss):  159 ns
Lookup after churn & spread (random):  242 ns
Deleting half after churn & spread:  70 ns
Adding (a different) half after churn & spread:  133 ns
Details: delete markers 0, perfect 62%
---

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index bbd4fa96..788e7189 100644
--- a/ccan/htable/htable.c
+++ b/ccan/htable/htable.c
@@ -66,8 +66,8 @@ struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv),
 		ht->priv = priv;
 		ht->elems = 0;
 		ht->deleted = 0;
-		ht->max = (1 << ht->bits) * 2 / 3;
-		ht->max_with_deleted = (1 << ht->bits) * 4 / 5;
+		ht->max = ((size_t)1 << ht->bits) * 3 / 4;
+		ht->max_with_deleted = ((size_t)1 << ht->bits) * 9 / 10;
 		/* This guarantees we enter update_common first add. */
 		ht->common_mask = -1;
 		ht->common_bits = 0;
diff --git a/ccan/htable/tools/speed.c b/ccan/htable/tools/speed.c
index 72a08e6b..26231924 100644
--- a/ccan/htable/tools/speed.c
+++ b/ccan/htable/tools/speed.c
@@ -330,7 +330,7 @@ int main(int argc, char *argv[])
 	fflush(stdout);
 	gettimeofday(&start, NULL);
 	for (i = 0; i < num; i++) {
-		unsigned int n = num * 6 + i * 9;
+		unsigned int n = num * (5 + 9) + i * 9;
 		if (htable_obj_get(ht, &n))
 			abort();
 	}