From 6e93417d275be9436b986f48b39b2dbacee730b4 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Mon, 10 Feb 2025 11:04:26 -0500 Subject: trie: Micro-optimize trie_representative() popcount(map & (bit - 1) & mask) has a longer critical path than popcount(map & (bit - 1)) & mask. --- src/trie.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/trie.c b/src/trie.c index a4829e3..aac79d7 100644 --- a/src/trie.c +++ b/src/trie.c @@ -211,10 +211,11 @@ static struct trie_leaf *trie_representative(const struct trie *trie, const void if ((offset >> 1) < length) { unsigned char nibble = trie_key_nibble(key, length, offset); unsigned int bit = 1U << nibble; - // bits = bitmap & bit ? bitmap & (bit - 1) : 0 - unsigned int mask = -!!(node->bitmap & bit); - unsigned int bits = node->bitmap & (bit - 1) & mask; - index = count_ones(bits); + unsigned int map = node->bitmap; + unsigned int bits = map & (bit - 1); + unsigned int mask = -!!(map & bit); + // index = (map & bit) ? count_ones(bits) : 0; + index = count_ones(bits) & mask; } ptr = node->children[index]; } -- cgit v1.2.3