Re: [PATCH] last-modified: implement faster algorithm

From: Toon Claes <toon@iotcl.com>
Date: Oct 21, 2025, 09:04 UTC
Message-ID: <87cy6gtym2.fsf@iotcl.com>
In-Reply-To: <87jz0tu3yh.fsf@iotcl.com>

> Taylor Blau <me@ttaylorr.com> writes:

Show 11 quoted lines

>> Nice, I am glad to see that we are using a bitmap here rather than the
>> hacky 'char *' that we had originally written. I seem to remember that
>> there was a tiny slow-down when using bitmaps, but can't find the
>> discussion anymore. (It wasn't in the internal PR that I originally
>> opened, and I no longer can read messages that far back in history.)
>>
>> It might be worth benchmarking here to see if using a 'char *' is
>> faster. Of course, that's 8x worse in terms of memory usage, but not a
>> huge deal given both the magnitude and typical number of directory
>> elements (you'd need 1024^2 entries in a single tree to occupy even a
>> single MiB of heap).

Using ewah bitmaps is slightly faster, although the difference is almost neglible.

    Benchmark 1: bitmap-ewah
      Time (mean ± σ):     793.1 ms ±   6.2 ms    [User: 755.1 ms, System: 35.2 ms]
      Range (min … max):   784.7 ms … 804.8 ms    10 runs

    Benchmark 2: bitmap-chars
      Time (mean ± σ):     808.9 ms ±  11.2 ms    [User: 770.8 ms, System: 35.4 ms]
      Range (min … max):   800.2 ms … 830.5 ms    10 runs

    Summary
      bitmap-ewah ran
        1.02 ± 0.02 times faster than bitmap-chars

And ewah bitmap being more memory efficient, it makes more sense to keep using those.

Show 7 quoted lines

>> Likewise, I wonder if we should have elemtype here be just 'struct
>> bitmap'. Unfortunately I don't think the EWAH code has a function like:
>>
>>     void bitmap_init(struct bitmap *);
>>
>> and only has ones that allocate for us. So we may consider adding one,
>> or creating a dummy bitmap and copying its contents, or otherwise.

I've done some testing, and to do so I've made bitmap_grow() public.

    Benchmark 1: bitmap-as-pointers
      Time (mean ± σ):     783.7 ms ±   8.9 ms    [User: 744.1 ms, System: 37.5 ms]
      Range (min … max):   774.4 ms … 803.4 ms    10 runs

    Benchmark 2: bitmap-as-values
      Time (mean ± σ):     856.7 ms ±  10.5 ms    [User: 816.0 ms, System: 38.1 ms]
      Range (min … max):   845.7 ms … 872.5 ms    10 runs

    Summary
      bitmap-as-pointers ran
        1.09 ± 0.02 times faster than bitmap-as-values

It seems using ewah bitmaps as pointers is faster than using bitmaps as values. I must admit I'm surprised as well, but in case you want to double check, here's the patch:

------------------------ >8 ------------------------

diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index c1316e1019..f607c47506 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -47,7 +47,7 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,
  * Hold a bitmap for each commit we're working with. Each bit represents a path
  * in `lm->all_paths`. Active bit means the path still needs to be dealt with.
  */
-define_commit_slab(commit_bitmaps, struct bitmap *);
+define_commit_slab(commit_bitmaps, struct bitmap);

 struct last_modified {
        struct hashmap paths;
@@ -65,11 +65,12 @@ struct last_modified {

 static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)
 {
-       struct bitmap **bitmap = commit_bitmaps_at(&lm->commit_bitmaps, c);
-       if (!*bitmap)
-               *bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);
+       struct bitmap *bm = commit_bitmaps_at(&lm->commit_bitmaps, c);
+       if (!bm->word_alloc) {
+               bitmap_grow(bm, lm->all_paths_nr);
+       }

-       return *bitmap;
+       return bm;
 }

 static void last_modified_release(struct last_modified *lm)
@@ -442,7 +443,8 @@ static int last_modified_run(struct last_modified *lm)
                }

 cleanup:
-               bitmap_free(active_c);
+               free(active_c->words);
+               active_c->word_alloc = 0;
        }

        if (hashmap_get_size(&lm->paths))
diff --git a/ewah/bitmap.c b/ewah/bitmap.c
index 55928dada8..2500e3a0d7 100644
--- a/ewah/bitmap.c
+++ b/ewah/bitmap.c
@@ -42,7 +42,7 @@ struct bitmap *bitmap_dup(const struct bitmap *src)
        return dst;
 }

-static void bitmap_grow(struct bitmap *self, size_t word_alloc)
+void bitmap_grow(struct bitmap *self, size_t word_alloc)
 {
        size_t old_size = self->word_alloc;
        ALLOC_GROW(self->words, word_alloc, self->word_alloc);
diff --git a/ewah/ewok.h b/ewah/ewok.h
index c29d354236..3316807572 100644
--- a/ewah/ewok.h
+++ b/ewah/ewok.h
@@ -188,6 +188,7 @@ struct bitmap *bitmap_word_alloc(size_t word_alloc);
 struct bitmap *bitmap_dup(const struct bitmap *src);
 void bitmap_set(struct bitmap *self, size_t pos);
 void bitmap_unset(struct bitmap *self, size_t pos);
+void bitmap_grow(struct bitmap *self, size_t word_alloc);
 int bitmap_get(struct bitmap *self, size_t pos);
 void bitmap_free(struct bitmap *self);
 int bitmap_equals(struct bitmap *self, struct bitmap *other);

-- 
Cheers,
Toon