总计算量恒定，学校数量增加时计算耗时为何上升？

总学生数固定，按学校数量拆分出对应数量的数组，每个数组对应一所学校的学生。为每个学生基于旧成绩和随机系数计算新成绩，总计算量恒定，但增加学校数量（即减少单校学生数）时，多次迭代取平均的计算耗时随学校数量增加而上升。已确保学生数可被学校数整除，问题仍存在。

核心计算代码：

public static Long changeNotesComputationTime(Random random, int nIterations, int nSchools, int nStudents) {
    long[] timePerIteration = new long[nIterations];
    int nStudentsPerSchool = nStudents / nSchools;
    for (int iIteration = 0; iIteration < nIterations; iIteration++) {
        System.out.println(iIteration + " iteration");
        long computationTime = 0;
        for (int iSchool = 0; iSchool < nSchools; iSchool++) {
            int[] gradesOfStudents = random.ints(nStudentsPerSchool, 0, 20).toArray();
            double coeff = random.nextDouble();
            int[] gradesChangedOfStudents = new int[nStudentsPerSchool];
            long startComputations = System.currentTimeMillis();
            for (int iStudent = 0; iStudent < nStudentsPerSchool; iStudent++) {
                gradesChangedOfStudents[iStudent] = (int) (gradesOfStudents[iStudent] * coeff);
            }
            long endComputations = System.currentTimeMillis();
            computationTime += endComputations - startComputations;
        }

        timePerIteration[iIteration] = computationTime;
    }
    return Arrays.stream(timePerIteration).sum() / nIterations;
}

测试代码：

@Test
public void Test() throws PerformanceException, IOException {
    final Writer writer = Files.newBufferedWriter(Paths
            .get(outputPathFolder, "ComputationTime.csv"), Charset.defaultCharset());

    final int nIterations = 100;
    final int nStudents = 10000000;

    writer.write(
            "number of schools; computation time [ms]\n");
    for (int nSchools = 5000000; nSchools < nStudents; nSchools += 500000) {
        writer.write(Long.toString(nSchools) + ";");
        writer.write(
                Long.toString(Fixture.changeNotesComputationTime(random, nIterations, nSchools, nStudents))
                        + "\n");
    }
    writer.close();
}

• 频繁小对象分配与GC开销：学校数量越多，需要创建的gradesOfStudents和gradesChangedOfStudents数组数量就越多。这些都是长度极小的对象，频繁分配会触发JVM垃圾回收器更频繁地工作，小对象的分配、初始化和回收过程本身也会产生额外耗时，累加后推高总耗时。
• CPU缓存命中率暴跌：CPU的L1/L2缓存擅长处理连续、大容量的数据访问。当单校学生数很少时，每个数组长度极短，处理完一个数组后缓存数据无法复用，下一个数组需要重新从内存加载，缓存命中率极低。而学校数量少的时候，大数组能充分利用缓存特性，连续访问元素时缓存持续命中，计算效率大幅提升。
• 计时方法的累加开销：每处理一所学校都要调用两次System.currentTimeMillis()，学校数量越多，该方法的调用次数就越多。单次调用开销微乎其微，但数百万级的调用累加后，耗时会变得非常显著。
• Random类调用的额外开销：学校数量增加时，random.ints()和random.nextDouble()的调用次数同步增加。Random类的方法涉及种子更新操作，频繁调用会带来额外的计算和线程本地变量操作开销，进一步拉高总耗时。

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