Kotlin内置List binarySearch性能偏低？移除compareValues后为何大幅提速？

Great catch on that massive performance delta—8 minutes vs. 584 milliseconds is an incredible difference! Let’s break down exactly what’s driving this gap:

1. Redundant Null Check Overhead #

Kotlin’s built-in compareValues function is designed to handle all nullable Comparable types safely, which means it runs three extra checks every time it’s called:

public inline fun <T : Comparable<T>> compareValues(a: T?, b: T?): Int {
    if (a === b) return 0  // Identity check
    if (a == null) return -1 // Null check for first argument
    if (b == null) return 1  // Null check for second argument
    return a.compareTo(b)
}

If your test scenario uses lists with no null elements (or you’re only searching for non-null values), these checks are completely unnecessary. In a binary search loop, this happens once per iteration—multiply that by thousands or millions of search operations, and those tiny redundant checks add up to enormous time costs.

2. Improved Branch Prediction Efficiency #

Every conditional branch in code gives the CPU’s branch predictor a chance to guess wrong, which stalls execution while the pipeline clears. The null checks in compareValues introduce extra branches that, in your use case, never actually trigger (since there are no nulls). Your custom implementation removes these branches entirely, letting the CPU predict execution paths far more accurately and avoid costly stalls.

3. Ditching Generic Safety for Targeted Optimization #

The built-in binarySearch is designed to be universally safe: it works with any List<T?> where T is Comparable, no matter if elements are null or not. This generality comes with a performance tradeoff. Your custom implementation skips all the generic safety logic that doesn’t apply to your specific scenario, cutting straight to the core comparison (compareTo) that actually matters for your use case.

Even though compareValues is marked inline, the compiler can’t eliminate the redundant null checks when it has to account for all possible nullable inputs. By removing this wrapper, you’re stripping away all the overhead required for generality but useless in your tested scenario.

内容的提问来源于stack exchange，提问作者Hamad AlMarri