Skip to content

Improve inlining of some key 32-bit functions #755

@lemire

Description

@lemire

In the 64-bit bitmaps, we have functions that are expected to be called often such as roaring64_iterator_advance and roaring64_bitmap_contains. These functions, in turn, call 32-bit functions (container_iterator_next and roaring_bitmap_contains). These functions do not get inlined which almost surely leads to an unfortunate overhead.

We should refactor the code so that the following functions are more often inlined by compilers:

  • container_iterator_next
  • container_iterator_prev
  • roaring_bitmap_contains

And then we should run benchmarks (e.g., ./build/microbenchmarks/bench --benchmark_filter=IterateAll64).

Here are some profiling results...

IterateAll64:

  41.74%  bench    libroaring.so.4.0.0    [.] roaring64_iterator_advance                                                                                                     ◆
  21.24%  bench    libroaring.so.4.0.0    [.] container_iterator_next                                                                                                        ▒
  15.52%  bench    bench                  [.] void BasicBench<iterate_all64>(benchmark::State&)                                                                              ▒
   5.20%  bench    bench                  [.] roaring64_iterator_advance@plt                                                                                                 ▒
   5.14%  bench    libroaring.so.4.0.0    [.] roaring64_iterator_has_value                                                                                                   ▒
   5.14%  bench    libroaring.so.4.0.0    [.] container_iterator_next@plt

RandomAccess64:

  28.90%  bench    libroaring.so.4.0.0   [.] roaring_bitmap_contains
  24.65%  bench    libroaring.so.4.0.0   [.] art_find
  19.24%  bench    libroaring.so.4.0.0   [.] roaring64_bitmap_contains
  14.68%  bench    bench                 [.] void BasicBench<random_access64_cpp>(benchmark::State&)

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions