From 20defbbcfa088a7574d9897b533d1bc600b2df53 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 22 Nov 2010 11:50:58 +1030 Subject: [PATCH] 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) --- ccan/tdb2/free.c | 12 ++++++++++-- ccan/tdb2/private.h | 4 ++-- 2 files changed, 12 insertions(+), 4 deletions(-) diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index 13db5933..8ff5d74a 100644 --- 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; } + /* 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; @@ -578,7 +586,7 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size) 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; } @@ -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); - 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. */ diff --git a/ccan/tdb2/private.h b/ccan/tdb2/private.h index a10d1070..6e9936f5 100644 --- 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 -/* 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) -- 2.39.2