数据结构与算法 / 系统课时

算法性能基准测试

算法性能基准测试

一次计时不能证明算法更快。本课将建立可重复的 Java 基准流程:固定输入,先预热,再进行多轮测量,校验结果一致,并用中位数而不是偶然的最快值比较实现。

学习目标

  • 设计可重复的性能测试流程
  • 正确处理预热、结果消费与多轮统计
  • 先验证结果一致,再解释性能差异

为什么单次计时不可信

System.nanoTime() 只能提供高精度时间戳,不能自动消除类加载、JIT 编译、垃圾回收和系统调度造成的波动。若两个实现使用不同输入,或计时区域包含日志与数据构造,比较结果也没有意义。

可靠测试应让所有实现处理同一批数据,并把准备阶段、预热阶段、测量阶段和统计阶段分开。

Java 算法基准测试流程

可重复测试流程

先明确指标。单次请求通常关注延迟,批量任务可关注吞吐量;内存占用和对象分配应单独测量,不要与耗时混成一个结论。

测试数据要覆盖规模、命中位置和未命中情况。涉及随机输入时固定种子,确保每次运行得到同一数据。正式计时前执行预热,测量时重复多轮,并保存全部样本后计算中位数。Java 微基准需要更高精度时,应使用 JMH。

主示例

下面的 Java 17 示例比较 ArrayList.contains 与 HashSet.contains。它使用固定随机种子生成查询,先预热,再交替测量 7 轮,并通过 blackhole 消费结果,降低无用计算被优化掉的风险。

java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class AlgorithmBenchmarkDemo {
    private static volatile int blackhole;

    public static void main(String[] args) {
        int size = 5_000;
        int rounds = 10;
        int[] queries = createQueries(size, 200, 20260802L);

        // 两种实现共享同一数据与查询,避免输入差异污染结果。
        List<Integer> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        Set<Integer> set = new HashSet<>(list);

        // 预热与正式测量分离,让类加载和 JIT 尽量提前发生。
        for (int i = 0; i < 5; i++) {
            blackhole ^= runList(list, queries, rounds);
            blackhole ^= runSet(set, queries, rounds);
        }

        long[] listSamples = new long[7];
        long[] setSamples = new long[7];
        int listMatches = 0;
        int setMatches = 0;

        // 交替测量顺序,降低固定先后顺序带来的系统性偏差。
        for (int i = 0; i < listSamples.length; i++) {
            if (i % 2 == 0) {
                listMatches = measureList(list, queries, rounds, listSamples, i);
                setMatches = measureSet(set, queries, rounds, setSamples, i);
            } else {
                setMatches = measureSet(set, queries, rounds, setSamples, i);
                listMatches = measureList(list, queries, rounds, listSamples, i);
            }
        }

        Arrays.sort(listSamples);
        Arrays.sort(setSamples);
        System.out.println("样本数: " + listSamples.length);
        System.out.println("结果一致: " + (listMatches == setMatches));
        System.out.println("List 中位耗时(ns): " + listSamples[listSamples.length / 2]);
        System.out.println("Set 中位耗时(ns): " + setSamples[setSamples.length / 2]);
    }

    private static int[] createQueries(int size, int count, long seed) {
        Random random = new Random(seed);
        int[] queries = new int[count];
        for (int i = 0; i < count; i++) {
            queries[i] = random.nextBoolean() ? random.nextInt(size) : -random.nextInt(size) - 1;
        }
        return queries;
    }

    private static int measureList(
            List<Integer> list, int[] queries, int rounds, long[] samples, int index) {
        long start = System.nanoTime();
        int matches = runList(list, queries, rounds);
        samples[index] = System.nanoTime() - start;
        // 将结果写入 volatile 字段,避免计算结果完全无人使用。
        blackhole ^= matches;
        return matches;
    }

    private static int measureSet(
            Set<Integer> set, int[] queries, int rounds, long[] samples, int index) {
        long start = System.nanoTime();
        int matches = runSet(set, queries, rounds);
        samples[index] = System.nanoTime() - start;
        blackhole ^= matches;
        return matches;
    }

    private static int runList(List<Integer> list, int[] queries, int rounds) {
        int matches = 0;
        for (int r = 0; r < rounds; r++) {
            for (int query : queries) {
                if (list.contains(query)) {
                    matches++;
                }
            }
        }
        return matches;
    }

    private static int runSet(Set<Integer> set, int[] queries, int rounds) {
        int matches = 0;
        for (int r = 0; r < rounds; r++) {
            for (int query : queries) {
                if (set.contains(query)) {
                    matches++;
                }
            }
        }
        return matches;
    }
}

将代码保存为 AlgorithmBenchmarkDemo.java,再编译运行:

bash
javac AlgorithmBenchmarkDemo.java
java AlgorithmBenchmarkDemo

预期输出结构如下,<NANOS> 是随机器和运行状态变化的实际纳秒数:

text
样本数: 7
结果一致: true
List 中位耗时(ns): <NANOS>
Set 中位耗时(ns): <NANOS>

结果解读与边界

示例可以说明固定数据、预热、多轮采样和结果校验,但它仍不是严格微基准框架。不要仅凭一次运行断言固定倍数,也不要把不同机器的绝对耗时直接比较。

若要发布可信结论,应使用 JMH 控制预热、分叉进程和统计方式,同时报告 JDK、硬件、数据规模、输入分布与样本数量。对短任务还要关注对象分配和 GC,避免只看 CPU 时间。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

算法性能基准测试

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通