tdb2: use expansion heuristics from tdb1

This reduces the amount of expansion we do.

Before:
./speed 1000000
Adding 1000000 records:  23210 ns (59193360 bytes)
Finding 1000000 records:  2387 ns (59193360 bytes)
Traversing 1000000 records:  2150 ns (59193360 bytes)
Deleting 1000000 records:  13392 ns (59193360 bytes)
Re-adding 1000000 records:  11546 ns (59193360 bytes)
Appending 1000000 records:  29327 ns (91193360 bytes)
Churning 1000000 records:  33026 ns (91193360 bytes)

After:
$ ./speed 1000000
Adding 1000000 records:  17480 ns (61472904 bytes)
Finding 1000000 records:  2431 ns (61472904 bytes)
Traversing 1000000 records:  2194 ns (61472904 bytes)
Deleting 1000000 records:  10948 ns (61472904 bytes)
Re-adding 1000000 records:  11247 ns (61472904 bytes)
Appending 1000000 records:  21826 ns (96051424 bytes)
Churning 1000000 records:  27242 ns (96051424 bytes)

diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c
index 13db5933911073577e42d1175fcecd5b7da12efb..8ff5d74a3fd7a8a400b243b9dd8a22c1dfe44af6 100644 (file)
--- a/ccan/tdb2/free.c
+++ b/ccan/tdb2/free.c
@@ -566,6 +566,14 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size)
                return -1;
        }
 
                return -1;
        }
 

+       /* always make room for at least 100 more records, and at
+           least 25% more space. */
+       if (size * TDB_EXTENSION_FACTOR > tdb->map_size / 4)
+               wanted = size * TDB_EXTENSION_FACTOR;
+       else
+               wanted = tdb->map_size / 4;
+       wanted = adjust_size(0, wanted);
+

        /* Only one person can expand file at a time. */
        if (tdb_lock_expand(tdb, F_WRLCK) != 0)
                return -1;
        /* Only one person can expand file at a time. */
        if (tdb_lock_expand(tdb, F_WRLCK) != 0)
                return -1;


@@ -578,7 +586,7 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size)
                return 0;
        }
 
                return 0;
        }
 

-       if (tdb->methods->expand_file(tdb, wanted*TDB_EXTENSION_FACTOR) == -1) {
+       if (tdb->methods->expand_file(tdb, wanted) == -1) {

                tdb_unlock_expand(tdb, F_WRLCK);
                return -1;
        }
                tdb_unlock_expand(tdb, F_WRLCK);
                return -1;
        }


@@ -586,7 +594,7 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size)
        /* We need to drop this lock before adding free record. */
        tdb_unlock_expand(tdb, F_WRLCK);
 
        /* We need to drop this lock before adding free record. */
        tdb_unlock_expand(tdb, F_WRLCK);
 

-       return add_free_record(tdb, old_size, wanted * TDB_EXTENSION_FACTOR);
+       return add_free_record(tdb, old_size, wanted);

 }
 
 /* This won't fail: it will expand the database if it has to. */
 }
 
 /* This won't fail: it will expand the database if it has to. */

diff --git a/ccan/tdb2/private.h b/ccan/tdb2/private.h
index a10d1070d29c3d5f84f09107d032fbb0cf0dac1b..6e9936f53b92a91c5993049f7335036405af3455 100644 (file)
--- a/ccan/tdb2/private.h
+++ b/ccan/tdb2/private.h
@@ -92,8 +92,8 @@ typedef uint64_t tdb_off_t;
 /* And 8 entries in each group, ie 8 groups per sublevel. */
 #define TDB_HASH_GROUP_BITS 3
 
 /* And 8 entries in each group, ie 8 groups per sublevel. */
 #define TDB_HASH_GROUP_BITS 3
 

-/* Extend file by least 32 times larger than needed. */
-#define TDB_EXTENSION_FACTOR 32
+/* Extend file by least 100 times larger than needed. */
+#define TDB_EXTENSION_FACTOR 100

 
 /* We steal bits from the offsets to store hash info. */
 #define TDB_OFF_HASH_GROUP_MASK ((1ULL << TDB_HASH_GROUP_BITS) - 1)
 
 /* We steal bits from the offsets to store hash info. */
 #define TDB_OFF_HASH_GROUP_MASK ((1ULL << TDB_HASH_GROUP_BITS) - 1)