summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2022-03-09 08:44:18 -0500
committerTavian Barnes <tavianator@tavianator.com>2022-03-09 08:57:56 -0500
commitf1294f1b5ea4c8948433f9c154c59d6f48839572 (patch)
tree4c9b43487690ae6ff876760f5b282f2d128cb451
parent701a55cdd57501ea3309028b80916cb6dcc41d0f (diff)
downloadbfs-f1294f1b5ea4c8948433f9c154c59d6f48839572.tar.xz
bftw: Keep root paths at the head of the LRU list
With a low ulimit -n, this brings performance back in line with the old heap based implementation.
-rw-r--r--bftw.c29
1 files changed, 25 insertions, 4 deletions
diff --git a/bftw.c b/bftw.c
index e159504..dcf270a 100644
--- a/bftw.c
+++ b/bftw.c
@@ -92,6 +92,8 @@ struct bftw_file {
struct bftw_cache {
/** The head of the LRU list. */
struct bftw_file *head;
+ /** The insertion target for the LRU list. */
+ struct bftw_file *target;
/** The tail of the LRU list. */
struct bftw_file *tail;
/** The remaining capacity of the LRU list. */
@@ -101,6 +103,7 @@ struct bftw_cache {
/** Initialize a cache. */
static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
cache->head = NULL;
+ cache->target = NULL;
cache->tail = NULL;
cache->capacity = capacity;
}
@@ -108,6 +111,7 @@ static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
/** Destroy a cache. */
static void bftw_cache_destroy(struct bftw_cache *cache) {
assert(!cache->tail);
+ assert(!cache->target);
assert(!cache->head);
}
@@ -118,15 +122,28 @@ static void bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
assert(!file->lru_prev);
assert(!file->lru_next);
- file->lru_next = cache->head;
- cache->head = file;
+ if (cache->target) {
+ file->lru_prev = cache->target;
+ file->lru_next = cache->target->lru_next;
+ } else {
+ file->lru_next = cache->head;
+ }
+
+ if (file->lru_prev) {
+ file->lru_prev->lru_next = file;
+ } else {
+ cache->head = file;
+ }
if (file->lru_next) {
file->lru_next->lru_prev = file;
+ } else {
+ cache->tail = file;
}
- if (!cache->tail) {
- cache->tail = file;
+ // Prefer to keep the root paths open by keeping them at the head of the list
+ if (file->depth == 0) {
+ cache->target = file;
}
--cache->capacity;
@@ -134,6 +151,10 @@ static void bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
/** Remove a bftw_file from the cache. */
static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
+ if (cache->target == file) {
+ cache->target = file->lru_prev;
+ }
+
if (file->lru_prev) {
assert(cache->head != file);
file->lru_prev->lru_next = file->lru_next;