jitmap: Jitted bitmaps
jitmap is a small library providing an execution engine for logical binary expressions on bitmaps. Some examples where this is relevant:
-
In search engines, posting lists (sorted sequences of integers) are encoded with bitmaps. Evaluating a search query (logical expression on keywords) can be implemented with logical expression on bitmaps.
-
In columnar databases, selection vectors (index masks) are encoded with bitmaps, the results of predicate on column expressions. The bitmaps are then combined in a final bitmap.
-
In stream processing systems with rule engines, e.g. adtech bid requests filtering with campaign rules, bitmaps are used as a first-pass optimization to lower the number of (costly) rules to evaluate on each incoming event.
jitmap compiles logical expressions into native functions with signature
void fn(const char**, char*). The functions are optimized to minimize memory
transfers and uses the fastest vector instruction set provided by the host.
The following snippet shows an example of what jitmap achieves:
typedef void (*dense_eval_fn)(const char**, char*);
// a, b, c, and output are pointers to bitmap
char* a, b, c, output;
// Note that for now, jitmap only supports static sized bitmaps.
const char** inputs[3] = {a, b, c};
// Compile an expression returned as a function pointer. The function can be
// called from any thread in the same address space and has a global lifetime.
// The generated symbol will be exposed to gdb and linux's perf utility.
const char* symbol_name = "a_and_b_and_c";
dense_eval_fn a_and_b_and_c = jitmap_compile(symbol_name, "a & b & c");
// The result of `a & b & c` will be stored in `output`, applied vertically
// using vectorized instruction available on the host.
a_and_b_and_c(inputs, output);Logical expression language
jitmap offers a small DSL language to evaluate bitwise operations on bitmaps.
The language supports variables (named bitmap), empty/full literals, and basic
operators: not !, and &, or !, xor ^.
A query takes an expression and a list of bitmaps and execute the expression on the bitmaps resulting in a new bitmap.
Supported expressions
- Empty bitmap literal:
$0 - Full bitmap literal:
$1 - Variables (named bitmap):
[A-Za-z0-9_]+, e.g.country,color_red - Not:
!e - And:
e_1 & e_2 - Or:
e_1 | e_2 - Xor:
e_1 ^ e_2
Examples
# NOT(a)
!a
# a AND b
a & b
# 1 AND (a OR b) XOR c
($1 & (a | b) ^ c)
Developing/Debugging
jitmap-ir tool
The jitmap-ir command line utility takes an expression as first input argument and dumps the generated LLVM' IR to stdout. It is useful to debug and peek at the generated code. Using LLVM command line utilies, we can also look at the expected generated assembly for any platform.
# tools/jitmap-ir "(a & b) | (c & c) | (c ^ d) | (c & b) | (d ^ a)"
; ModuleID = 'jitmap_ir'
source_filename = "jitmap_ir"
target triple = "x86_64-pc-linux-gnu"
; Function Attrs: argmemonly
define void @query(i32** nocapture readonly %inputs, i32* nocapture %output) #0 {
entry:
%bitmap_gep_0 = getelementptr inbounds i32*, i32** %inputs, i64 0
%bitmap_0 = load i32*, i32** %bitmap_gep_0
%bitmap_gep_1 = getelementptr inbounds i32*, i32** %inputs, i64 1
%bitmap_1 = load i32*, i32** %bitmap_gep_1
%bitmap_gep_2 = getelementptr inbounds i32*, i32** %inputs, i64 2
%bitmap_2 = load i32*, i32** %bitmap_gep_2
%bitmap_gep_3 = getelementptr inbounds i32*, i32** %inputs, i64 3
%bitmap_3 = load i32*, i32** %bitmap_gep_3
br label %loop
loop: ; preds = %loop, %entry
%i = phi i64 [ 0, %entry ], [ %next_i, %loop ]
%gep_0 = getelementptr inbounds i32, i32* %bitmap_0, i64 %i
%load_0 = load i32, i32* %gep_0
%gep_1 = getelementptr inbounds i32, i32* %bitmap_1, i64 %i
%load_1 = load i32, i32* %gep_1
%gep_2 = getelementptr inbounds i32, i32* %bitmap_2, i64 %i
%load_2 = load i32, i32* %gep_2
%gep_3 = getelementptr inbounds i32, i32* %bitmap_3, i64 %i
%load_3 = load i32, i32* %gep_3
%0 = and i32 %load_0, %load_1
%1 = and i32 %load_2, %load_2
%2 = or i32 %0, %1
%3 = xor i32 %load_2, %load_3
%4 = or i32 %2, %3
%5 = and i32 %load_2, %load_1
%6 = or i32 %4, %5
%7 = xor i32 %load_3, %load_0
%8 = or i32 %6, %7
%gep_output = getelementptr inbounds i32, i32* %output, i64 %i
store i32 %8, i32* %gep_output
%next_i = add i64 %i, 1
%exit_cond = icmp eq i64 %next_i, 2048
br i1 %exit_cond, label %after_loop, label %loop
after_loop: ; preds = %loop
ret void
}
attributes #0 = { argmemonly }We can then use LLVM's opt and llc to transform the IR into native assembly.
# tools/jitmap-ir "(a & b) | (c & c) | (c ^ d) | (c & b) | (d ^ a)" | llc -O3
.text
.file "jitmap_ir"
.globl query # -- Begin function query
.p2align 4, 0x90
.type query,@function
query: # @query
.cfi_startproc
# %bb.0: # %entry
pushq %rbp
.cfi_def_cfa_offset 16
pushq %rbx
.cfi_def_cfa_offset 24
.cfi_offset %rbx, -24
.cfi_offset %rbp, -16
movq (%rdi), %r8
movq 8(%rdi), %r9
movq 16(%rdi), %r10
movq 24(%rdi), %r11
movq $-8192, %rax # imm = 0xE000
.p2align 4, 0x90
.LBB0_1: # %loop
# =>This Inner Loop Header: Depth=1
movl 8192(%r8,%rax), %ecx
movl 8192(%r9,%rax), %edx
movl 8192(%r10,%rax), %edi
movl 8192(%r11,%rax), %ebx
movl %edi, %ebp
xorl %ebx, %ebp
xorl %ecx, %ebx
andl %edx, %ecx
orl %edi, %ebp
andl %edx, %edi
orl %ebp, %edi
orl %edi, %ebx
orl %ecx, %ebx
movl %ebx, 8192(%rsi,%rax)
addq $4, %rax
jne .LBB0_1
# %bb.2: # %after_loop
popq %rbx
.cfi_def_cfa_offset 16
popq %rbp
.cfi_def_cfa_offset 8
retq
.Lfunc_end0:
.size query, .Lfunc_end0-query
.cfi_endproc
# -- End function
.section ".note.GNU-stack","",@progbits
This code is still not fully optimized, opt is used for this.
# tools/jitmap-ir "(a & b) | (c & c) | (c ^ d) | (c & b) | (d ^ a)" | opt -O3 -S -mcpu=core-avx2| llc -O3
ninja: no work to do.
.text
.file "jitmap_ir"
.section .rodata.cst8,"aM",@progbits,8
.p2align 3 # -- Begin function query
.LCPI0_0:
.quad 8192 # 0x2000
.LCPI0_1:
.quad -9223372036854775808 # 0x8000000000000000
.text
.globl query
.p2align 4, 0x90
.type query,@function
query: # @query
# %bb.0: # %entry
pushq %rbp
pushq %r15
pushq %r14
pushq %r12
pushq %rbx
# ...
# And the holy grail fully vectorized loop
.LBB0_2: # %vector.body
# =>This Inner Loop Header: Depth=1
vmovdqu (%r14,%rbx), %ymm0
vmovdqu 32(%r14,%rbx), %ymm1
vmovdqu (%r12,%rbx), %ymm2
vmovdqu 32(%r12,%rbx), %ymm3
vmovdqu (%rdi,%rbx), %ymm4
vmovdqu 32(%rdi,%rbx), %ymm5
vpand (%r15,%rbx), %ymm0, %ymm6
vpand 32(%r15,%rbx), %ymm1, %ymm7
vpor %ymm2, %ymm6, %ymm6
vpor %ymm3, %ymm7, %ymm7
vpxor %ymm2, %ymm4, %ymm2
vpxor %ymm3, %ymm5, %ymm3
vpxor %ymm0, %ymm4, %ymm0
vpor %ymm0, %ymm2, %ymm0
vpor %ymm0, %ymm6, %ymm0
vpxor %ymm1, %ymm5, %ymm1
vpor %ymm1, %ymm3, %ymm1
vpor %ymm1, %ymm7, %ymm1
vmovdqu %ymm0, (%rsi,%rbx)
vmovdqu %ymm1, 32(%rsi,%rbx)
addq $64, %rbx
cmpq $8192, %rbx # imm = 0x2000
jne .LBB0_2
.LBB0_5: # %after_loop
popq %rbx
popq %r12
popq %r14
popq %r15
popq %rbp
vzeroupper
retq
.Lfunc_end0:
.size query, .Lfunc_end0-query
# -- End function
.section ".note.GNU-stack","",@progbitsSymbols with linux's perf
By default, perf will not be able to recognize the generated functions since the symbols are not available statically. Luckily, perf has two mechanisms for jit to register symbols. LLVM's jit use the jitdump [1] facility. At the time of writing this, one needs to patch perf with [2], see commit 077a9b7bd1 for more information.
# The `-k1` is required for jitdump to work.
$ perf record -k1 jitmap_benchmark
# By default, the output will be useless, since each instruction will be shown
# instead of grouped by symbols.
$ perf report --stdio
...
# Overhead Command Shared Object Symbol
# ........ ............... ................... ....................................................................................
#
29.09% jitmap_benchmar jitmap_benchmark [.] jitmap::StaticBenchmark<jitmap::IntersectionFunctor<(jitmap::PopCountOption)1> >
20.08% jitmap_benchmar jitmap_benchmark [.] jitmap::StaticBenchmark<jitmap::IntersectionFunctor<(jitmap::PopCountOption)0> >
1.78% jitmap_benchmar [JIT] tid 24013 [.] 0x00007f628c6cb045
1.61% jitmap_benchmar [JIT] tid 24013 [.] 0x00007f628c6cb053
1.59% jitmap_benchmar [JIT] tid 24013 [.] 0x00007f628c6cb197
1.55% jitmap_benchmar [JIT] tid 24013 [.] 0x00007f628c6cb126
1.51% jitmap_benchmar [JIT] tid 24013 [.] 0x00007f628c6cb035
1.39% jitmap_benchmar [JIT] tid 24013 [.] 0x00007f628c6cb027
# We must process the generate perf.data file by injecting symbols name
$ perf inject --jit -i perf.data -o perf.jit.data && mv perf.jit.data perf.data
$ perf report --stdio
...
# Overhead Command Shared Object Symbol
# ........ ............... ................... ....................................................................................
#
29.09% jitmap_benchmar jitmap_benchmark [.] jitmap::StaticBenchmark<jitmap::IntersectionFunctor<(jitmap::PopCountOption)1> >
20.08% jitmap_benchmar jitmap_benchmark [.] jitmap::StaticBenchmark<jitmap::IntersectionFunctor<(jitmap::PopCountOption)0> >
6.48% jitmap_benchmar jitted-24013-16.so [.] and_2_popcount
6.46% jitmap_benchmar jitted-24013-32.so [.] and_4_popcount
6.42% jitmap_benchmar jitted-24013-46.so [.] and_8_popcount
6.19% jitmap_benchmar jitted-24013-77.so [.] and_4
6.19% jitmap_benchmar jitted-24013-61.so [.] and_2
4.59% jitmap_benchmar jitted-24013-91.so [.] and_8
[1] https://elixir.bootlin.com/linux/v4.10/source/tools/perf/Documentation/jitdump-specification.txt
[2] https://lore.kernel.org/lkml/20191003105716.GB23291@krava/T/#u
TODO
- Supports dynamic sized bitmaps
- Implement roaring-bitmap-like compressed bitmaps
- Get https://reviews.llvm.org/D67383 approved and merged to benefit from Tree-Height-Reduction pass.
- Provide a C front-end api.