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 bbd4fa96e587c64a04446756787bd163ad4dc3c8..788e71895b183db45768fd0327572dcf5ccf4fd5 100644 (file)
--- 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->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;
                /* 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 72a08e6b4cd1e253b14436e644d5ab5d5608739f..26231924a1f68b33cfe244b21981d0cb4ca5ebe2 100644 (file)
--- 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++) {
        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();
        }
                if (htable_obj_get(ht, &n))
                        abort();
        }