From 13225f1dbff54619476f2d8f6bc779dbb4983e3e Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Sun, 5 Apr 2020 03:24:46 +0200 Subject: Filter: Faster prefix sets Use 16-way (4bit) branching in prefix trie instead of basic binary branching. The change makes IPv4 prefix sets almost 3x faster, but with more memory consumption and much more complicated algorithm. Together with a previous filter change, it makes IPv4 prefix sets about ~4.3x faster and slightly smaller (on my test data). --- lib/birdlib.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'lib/birdlib.h') diff --git a/lib/birdlib.h b/lib/birdlib.h index 431b7c0d..81d4908a 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -32,6 +32,9 @@ struct align_probe { char x; long int y; }; #define MAX(a,b) MAX_(a,b) #endif +#define ROUND_DOWN_POW2(a,b) ((a) & ~((b)-1)) +#define ROUND_UP_POW2(a,b) (((a)+((b)-1)) & ~((b)-1)) + #define U64(c) UINT64_C(c) #define ABS(a) ((a)>=0 ? (a) : -(a)) #define DELTA(a,b) (((a)>=(b))?(a)-(b):(b)-(a)) -- cgit v1.2.3