aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org>2021-03-20 18:18:50 +0200
committerSergey Poznyakoff <gray@gnu.org>2021-03-20 18:18:50 +0200
commit35d78dd3c6f96904175a8d152828e4616e7fe6c7 (patch)
tree83839e2b77fd5e2c26b819343805554eaef99d4f
parente8070a8ba4ecc539483c06221d31da77ede654c2 (diff)
downloadgdbm-35d78dd3c6f96904175a8d152828e4616e7fe6c7.tar.gz
gdbm-35d78dd3c6f96904175a8d152828e4616e7fe6c7.tar.bz2
More optimizations in cache tree
* src/bucket.c (gdbm_dir_entry_valid_p): Inline (cache_lookup): Keep track of cache hits. (_gdbm_get_bucket): Check the cache_entry first. (gdbm_get_cache_stats): Change signature. Return the per-db number of cache hits as well. * src/cachetree.c: Inline static functions. (_gdbm_cache_tree_lookup): Avoid extra level of indirection (nodeptr) at the expense of one additional comparison. * src/gdbm.h.in (gdbm_get_cache_stats): Change signature. * src/gdbmdefs.h (gdbm_file_info) <cache_hits>: New member.
-rw-r--r--src/bucket.c12
-rw-r--r--src/cachetree.c174
-rw-r--r--src/gdbm.h.in1
-rw-r--r--src/gdbmdefs.h5
4 files changed, 101 insertions, 91 deletions
diff --git a/src/bucket.c b/src/bucket.c
index 675bf32..90734a1 100644
--- a/src/bucket.c
+++ b/src/bucket.c
@@ -48,7 +48,7 @@ _gdbm_new_bucket (GDBM_FILE dbf, hash_bucket *bucket, int bits)
a valid bucket or data block at that offset. All this implies is that
it is safe to use the offset for look up in the bucket cache and to
attempt to read a block at that offset. */
-int
+static inline int
gdbm_dir_entry_valid_p (GDBM_FILE dbf, int dir_index)
{
return dir_index >= 0
@@ -191,6 +191,7 @@ cache_lookup (GDBM_FILE dbf, off_t adr, cache_elem *ref, cache_elem **ret_elem)
case node_found:
elem = node->elem;
elem->ca_hits++;
+ dbf->cache_hits++;
lru_unlink_elem (dbf, elem);
break;
@@ -224,6 +225,9 @@ cache_lookup (GDBM_FILE dbf, off_t adr, cache_elem *ref, cache_elem **ret_elem)
}
}
return node_failure;
+
+ default:
+ abort ();
}
lru_link_elem (dbf, elem, ref);
@@ -258,6 +262,9 @@ _gdbm_get_bucket (GDBM_FILE dbf, int dir_index)
dbf->bucket_dir = dir_index;
bucket_adr = dbf->dir[dir_index];
+ if (dbf->cache_entry && dbf->cache_entry->ca_adr == bucket_adr)
+ return 0;
+
switch (cache_lookup (dbf, bucket_adr, NULL, &elem))
{
case node_found:
@@ -688,12 +695,15 @@ _gdbm_fetch_data (GDBM_FILE dbf, off_t off, size_t size, void *buf)
void
gdbm_get_cache_stats (GDBM_FILE dbf,
size_t *access_count,
+ size_t *cache_hits,
size_t *cache_count,
struct gdbm_cache_stat *bstat,
size_t nstat)
{
if (access_count)
*access_count = dbf->cache_access_count;
+ if (cache_hits)
+ *cache_hits = dbf->cache_hits;
if (cache_count)
*cache_count = dbf->cache_num;
if (bstat)
diff --git a/src/cachetree.c b/src/cachetree.c
index d25739a..de5a5c1 100644
--- a/src/cachetree.c
+++ b/src/cachetree.c
@@ -18,8 +18,6 @@
#include "autoconf.h"
#include "gdbmdefs.h"
-#define NDEBUG
-#include "assert.h"
enum cache_node_color { RED, BLACK };
@@ -111,7 +109,7 @@ node_color (cache_node *n)
/* Replace the OLDN with NEWN.
Does not modify OLDN. */
-static void
+static inline void
replace_node (cache_tree *tree, cache_node *oldn, cache_node *newn)
{
if (oldn->parent == NULL)
@@ -126,7 +124,7 @@ replace_node (cache_tree *tree, cache_node *oldn, cache_node *newn)
}
/* Rotate the TREE left over the node N. */
-static void
+static inline void
rotate_left (cache_tree *tree, cache_node *n)
{
cache_node *right = n->right;
@@ -139,7 +137,7 @@ rotate_left (cache_tree *tree, cache_node *n)
}
/* Rotate the TREE right over the node N. */
-static void
+static inline void
rotate_right (cache_tree *tree, cache_node *n)
{
cache_node *left = n->left;
@@ -152,45 +150,7 @@ rotate_right (cache_tree *tree, cache_node *n)
}
/* Node deletion */
-static void rbt_delete_fixup (cache_tree *tree, cache_node *n);
-
-/* Remove N from the TREE. */
-void
-_gdbm_cache_tree_delete (cache_tree *tree, cache_node *n)
-{
- cache_node *child;
-
- /* If N has both left and right children, reduce the problem to
- the node with only one child. To do so, find the in-order
- predecessor of N, copy its value (elem) to N and then delete
- the predecessor. */
- if (n->left != NULL && n->right != NULL)
- {
- cache_node *p;
- for (p = n->left; p->right; p = p->right)
- ;
- n->adr = p->adr;
- n->elem = p->elem;
- n->elem->ca_node = n;
- n = p;
- }
-
- /* N has only one child. Select it. */
- child = n->left ? n->left : n->right;
- if (node_color (n) == BLACK)
- {
- n->color = node_color (child);
- rbt_delete_fixup (tree, n);
- }
- replace_node (tree, n, child);
- if (n->parent == NULL && child != NULL) /* root should be black */
- child->color = BLACK;
-
- /* Return N to the avail pool */
- rbt_node_dealloc (tree, n);
-}
-
-static void
+static inline void
rbt_delete_fixup (cache_tree *tree, cache_node *n)
{
while (1)
@@ -307,58 +267,45 @@ rbt_delete_fixup (cache_tree *tree, cache_node *n)
break;
}
}
-
-/* Insertion */
-static void rbt_insert_fixup (cache_tree *tree, cache_node *n);
-/* Look up the node with the given ADR.
- If found, put it in *RETVAL and return node_found.
-
- Otherwise, create a new node and insert it at the appropriate place in
- the tree. Store the address of the newly created node in *RETVAL and
- return node_new.
-
- If a new node cannot be created (memory exhausted), return node_failure.
-*/
-int
-_gdbm_cache_tree_lookup (cache_tree *tree, off_t adr, cache_node **retval)
+/* Remove N from the TREE. */
+void
+_gdbm_cache_tree_delete (cache_tree *tree, cache_node *n)
{
- int res;
- cache_node *node, *parent = NULL;
- cache_node **nodeptr;
+ cache_node *child;
- nodeptr = &tree->root;
- while ((node = *nodeptr) != NULL)
- {
- if (adr == node->adr)
- break;
- parent = node;
- if (adr < node->adr)
- nodeptr = &node->left;
- else
- nodeptr = &node->right;
- }
-
- if (node)
+ /* If N has both left and right children, reduce the problem to
+ the node with only one child. To do so, find the in-order
+ predecessor of N, copy its value (elem) to N and then delete
+ the predecessor. */
+ if (n->left != NULL && n->right != NULL)
{
- res = node_found;
+ cache_node *p;
+ for (p = n->left; p->right; p = p->right)
+ ;
+ n->adr = p->adr;
+ n->elem = p->elem;
+ n->elem->ca_node = n;
+ n = p;
}
- else
+
+ /* N has only one child. Select it. */
+ child = n->left ? n->left : n->right;
+ if (node_color (n) == BLACK)
{
- node = rbt_node_alloc (tree);
- if (!node)
- return node_failure;
- *nodeptr = node;
- node->adr = adr;
- node->parent = parent;
- rbt_insert_fixup (tree, node);
- res = node_new;
+ n->color = node_color (child);
+ rbt_delete_fixup (tree, n);
}
- *retval = node;
- return res;
-}
+ replace_node (tree, n, child);
+ if (n->parent == NULL && child != NULL) /* root should be black */
+ child->color = BLACK;
-static void
+ /* Return N to the avail pool */
+ rbt_node_dealloc (tree, n);
+}
+
+/* Insertion */
+static inline void
rbt_insert_fixup (cache_tree *tree, cache_node *n)
{
while (1)
@@ -434,6 +381,57 @@ rbt_insert_fixup (cache_tree *tree, cache_node *n)
break;
}
}
+
+/* Look up the node with the given ADR.
+ If found, put it in *RETVAL and return node_found.
+
+ Otherwise, create a new node and insert it at the appropriate place in
+ the tree. Store the address of the newly created node in *RETVAL and
+ return node_new.
+
+ If a new node cannot be created (memory exhausted), return node_failure.
+*/
+int
+_gdbm_cache_tree_lookup (cache_tree *tree, off_t adr, cache_node **retval)
+{
+ int res;
+ cache_node *node, *parent = NULL;
+
+ node = tree->root;
+ while (node)
+ {
+ if (adr == node->adr)
+ break;
+ parent = node;
+ if (adr < node->adr)
+ node = node->left;
+ else
+ node = node->right;
+ }
+
+ if (node)
+ {
+ res = node_found;
+ }
+ else
+ {
+ node = rbt_node_alloc (tree);
+ if (!node)
+ return node_failure;
+ if (!parent)
+ tree->root = node;
+ else if (adr < parent->adr)
+ parent->left = node;
+ else
+ parent->right = node;
+ node->adr = adr;
+ node->parent = parent;
+ rbt_insert_fixup (tree, node);
+ res = node_new;
+ }
+ *retval = node;
+ return res;
+}
/* Interface functions */
diff --git a/src/gdbm.h.in b/src/gdbm.h.in
index 87f620f..9b2fd95 100644
--- a/src/gdbm.h.in
+++ b/src/gdbm.h.in
@@ -291,6 +291,7 @@ struct gdbm_cache_stat
void gdbm_get_cache_stats (GDBM_FILE dbf,
size_t *access_count,
+ size_t *cache_hits,
size_t *cache_count,
struct gdbm_cache_stat *bstat,
size_t nstat);
diff --git a/src/gdbmdefs.h b/src/gdbmdefs.h
index 3fec82c..e61f36e 100644
--- a/src/gdbmdefs.h
+++ b/src/gdbmdefs.h
@@ -250,8 +250,9 @@ struct gdbm_file_info
/* The directory entry used to get the current hash bucket. */
int bucket_dir;
- /* Number of cache accesses */
- size_t cache_access_count;
+ /* Cache statistics */
+ size_t cache_access_count; /* Number of cache accesses */
+ size_t cache_hits; /* Number of cache hits */
/* Bookkeeping of things that need to be written back at the
end of an update. */

Return to:

Send suggestions and report system problems to the System administrator.