Mukul Agarwal AVL Tree Lookup

In spring 2025, I worked on a research team in Purdue CS to benchmark and optimize AVL tree lookups in C/C++ and x86-64 assembly.¹

An AVL tree is a self-balancing binary search tree (so a lookup visits only $O(\log n)$ nodes). But, the height of the tree captures only part of the cost of using AVL Trees for search. At each node, a string-key lookup must compare keys, choose a child, and follow a pointer to another location in memory. String comparisons, branch prediction, and memory access all affect how quickly that search runs. Our goal was to make those steps cheaper without changing the tree’s balancing rules or lookup behavior.

My contributions included:

• Building synthetic workloads to control string comparison cost and model uneven access.
• Profiling lookups and testing AVX2 string comparisons.
• Tuning the assembly with search-key prefetching and adjustments to loop unrolling.
• Building a shared benchmark harness, build scripts, and reporting tools to compare implementations.

Together, the team’s optimizations improved lookup performance by over 20% relative to naïve AVL tree implementation; this is competitive with C++ STL Versions of Search Algorithms packaged with GCC and Clang.

Generating realistic synthetic workloads

Uniformly random keys and lookups miss patterns that occur in real applications: keys can share prefixes, and some entries are accessed more often than others. I built synthetic workloads to model these patterns while keeping their parameters adjustable.

The key generator produces 31 uppercase ASCII letters and a null terminator, filling 32 bytes. A shared prefix of length p is followed by 31 - p random letters from A–Z. Longer prefixes model keys with shared namespaces or paths and force string comparisons to inspect more bytes before finding a difference.

Our insertion benchmarks varied p to exercise different comparison costs. Lookup benchmarks used p = 0, varied dictionary size, and sampled keys from a bounded normal distribution to model uneven access.

Wider comparisons using AVX2

The fixed key size let us compare an entire key with AVX2 instructions. I tested the following approach as part of a replacement for strcmp, with a and b holding the two keys in 256-bit vectors:

auto equal = _mm256_cmpeq_epi8(a, b);
uint32_t different = ~uint32_t(_mm256_movemask_epi8(equal));
if (different == 0) return 0;
unsigned first_difference = __builtin_ctz(different);

This masking scheme means that:

• If the mask is 0, then the keys match.
• Otherwise, the first set bit in the mask identifies the first differing byte. Comparing the values of that byte in the two keys determines their lexicographic order.

Selecting the next child

After each comparison, the lookup must choose the left or right child. A branch asks the processor to predict which direction the search will take; a wrong prediction wastes work. I implemented optimized assembly to replace this child-selection branch with a conditional move. It loads both child pointers, then compares the first positions where the search key is greater (eax) or smaller (edx):

movq   0x30(%rdi), %r8    # right child
movq   0x28(%rdi), %rdi   # default to left
cmpl   %eax, %edx
cmovg  %r8, %rdi          # choose right if its difference occurs first

Tuning memory access and the lookup loop

The vector comparison still needs its input loaded from memory. I added a prefetch for the search key to request that the cache line containing it be brought closer to the processor before use:

# hint: bring the search key's cache line into cache
prefetcht0 (%rsi)
# ...  other work
# ... 

# it is prefetched by now!
# load the 32-byte key into a vector register
vmovdqu    (%rsi), %ymm0

Here, rsi holds the search key’s address, and ymm0 is the 256-bit register used to hold its bytes for comparison. Prefetching aims to reduce time spent waiting for memory, but it needs enough lead time to help performance, which was a problem we ran into.²

I also adjusted the loop-unrolling bound. Unrolling repeats the loop body so that several steps can run before another loop-control check and jump. That can reduce loop overhead, at the cost of a larger instruction sequence. Each comparison still determines which node to visit next. The unrolling bound controls how much work is repeated, making it another parameter to tune through benchmarking. The reported 20% improvement describes the combined implementation.

Benchmarking across implementations

I built a shared harness to measure insertion and lookup performance across our AVL implementation, C++ standard-library containers, and an adapted V8 dictionary. I also wrote GCC and Clang build scripts, Python tools to convert JSON results to CSV, and benchmarks using multiple dictionaries to exercise larger working sets.

Acknowledgements

Thanks to Aaryan Wadhwani, Anish Mangla, Prof. Gustavo Rodriguez-Rivera, Kian Kasad, Lilith Erickson, and Partth Kulkarni.