investigate moving `extract_bits` to `Address` performance cost

[nicolaskagami]

One of the most important parts of lookup is the extraction of the bits from the address. Currently we do so from a generic function over Address:

#[inline(always)]
pub(crate) fn extract_bits<A>(address: A, offset: u8, len: u8) -> u8
where
    A: Address,
{
    (address.rotate_right((A::BITS - offset).wrapping_sub(len) as u32)).to_u8()
        & ((1u16 << len) - 1) as u8
}

Moving it to Address (so we could allow more flexible custom implementations) brings lookup performance down by 25%, even though the asm for the (u32, u8), u32 version is exactly the same:

#[no_mangle]
pub fn lookup_u32(trie: &Poptrie<(u32, u8), u32>, address: u32) -> Option<&u32> {
    trie.lookup(address)
}

lookup_u32:
	.cfi_startproc
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset %rbx, -16
	movl	%esi, %eax
	movq	16(%rdi), %rsi
	testq	%rsi, %rsi
	je	.LBB4_15
	movq	8(%rdi), %rdx
	movl	%eax, %r9d
	shrl	$26, %r9d
	movq	(%rdx), %r8
	btq	%r9, %r8
	jae	.LBB4_2
	movb	$20, %cl
	xorl	%r10d, %r10d
	movq	%rdx, %r11
	.p2align	4
.LBB4_7:
	movl	%r9d, %ebx
	negb	%bl
	shlxq	%rbx, %r8, %r8
	popcntq	%r8, %r8
	testb	%r9b, %r9b
	cmovel	%r10d, %r8d
	addl	16(%r11), %r8d
	cmpq	%r8, %rsi
	jbe	.LBB4_14
	leaq	(%r8,%r8,2), %r8
	movl	%eax, %ebx
	rorl	%cl, %ebx
	addb	$-6, %cl
	movl	%ebx, %r9d
	leaq	(%rdx,%r8,8), %r11
	movq	(%rdx,%r8,8), %r8
	andb	$63, %r9b
	btq	%rbx, %r8
	jb	.LBB4_7
	jmp	.LBB4_3
.LBB4_2:
	movq	%rdx, %r11
.LBB4_3:
	notb	%r9b
	movl	20(%r11), %ecx
	movq	40(%rdi), %rsi
	shlxq	%r9, 8(%r11), %rax
	popcntq	%rax, %rax
	leal	-1(%rcx,%rax), %eax
	cmpq	%rax, %rsi
	jbe	.LBB4_9
	movq	32(%rdi), %rcx
	movl	(%rcx,%rax,4), %eax
	movl	$4294967295, %ecx
	cmpq	%rcx, %rax
	je	.LBB4_5
	movq	64(%rdi), %rsi
	cmpq	%rax, %rsi
	jbe	.LBB4_13
	shlq	$2, %rax
	addq	56(%rdi), %rax
	popq	%rbx
	.cfi_def_cfa_offset 8
	retq
.LBB4_5:
	.cfi_def_cfa_offset 16
	xorl	%eax, %eax
	popq	%rbx
	.cfi_def_cfa_offset 8
	retq
.LBB4_14:
	.cfi_def_cfa_offset 16
	leaq	.Lanon.6cd52589c493adbdb3841982b6f2bcb9.4(%rip), %rdx
	movq	%r8, %rdi
	callq	*_ZN4core9panicking18panic_bounds_check17hb15443e8431033c2E@GOTPCREL(%rip)
.LBB4_15:
	leaq	.Lanon.6cd52589c493adbdb3841982b6f2bcb9.1(%rip), %rdx
	xorl	%edi, %edi
	xorl	%esi, %esi
	callq	*_ZN4core9panicking18panic_bounds_check17hb15443e8431033c2E@GOTPCREL(%rip)
.LBB4_9:
	leaq	.Lanon.6cd52589c493adbdb3841982b6f2bcb9.2(%rip), %rdx
	movq	%rax, %rdi
	callq	*_ZN4core9panicking18panic_bounds_check17hb15443e8431033c2E@GOTPCREL(%rip)
.LBB4_13:
	leaq	.Lanon.6cd52589c493adbdb3841982b6f2bcb9.3(%rip), %rdx
	movq	%rax, %rdi
	callq	*_ZN4core9panicking18panic_bounds_check17hb15443e8431033c2E@GOTPCREL(%rip)
.Lfunc_end4:
	.size	lookup_u32, .Lfunc_end4-lookup_u32
	.cfi_endproc