Время умножения в BigInteger

Мой мини-тест:

import java.math.*;
import java.util.*;
import java.io.*;
public class c
{
    static Random rnd = new Random();
    public static String addDigits(String a, int n)
    {
        if(a==null) return null;
        if(n<=0) return a;
        for(int i=0; i<n; i++)
            a+=rnd.nextInt(10);
        return a;
    }
    public static void main(String[] args) throws IOException
    {
        int n = 10000; \\number of iterations
        int k = 10;    \\number of digits added at each iteration

        BigInteger a;
        BigInteger b;

        String as = "";
        String bs = "";
        as += rnd.nextInt(9)+1;
        bs += rnd.nextInt(9)+1;
        a = new BigInteger(as);
        b = new BigInteger(bs);
        FileWriter fw = new FileWriter("c.txt");
        long t1 = System.nanoTime();
        a.multiply(b);
        long t2 = System.nanoTime();
        //fw.write("1,"+(t2-t1)+"\n");
        if(k>0) {
            as = addDigits(as, k-1);
            bs = addDigits(as, k-1);
        }
        for(int i=0; i<n; i++)
        {
            a = new BigInteger(as);
            b = new BigInteger(bs);
            t1 = System.nanoTime();
            a.multiply(b);
            t2 = System.nanoTime();
            fw.write(((i+1)*k)+","+(t2-t1)+"\n");
            if(i < n-1)
            {
                as = addDigits(as, k);
                bs = addDigits(as, k);
            }
            System.out.println((i+1)*k);
        }       

        fw.close();
    }
}

Он измеряет время умножения n-разрядного BigInteger

Результат: enter image description here

Вы можете легко увидеть тенденцию, но почему существует такой большой шум выше 50000 цифр? Это из-за сборщика мусора или есть что-то еще, что влияет на мои результаты? При выполнении теста других приложений не было.

Результат теста только с нечетными цифрами. Тест был короче (n = 1000, k = 100)

enter image description here

Нечетные цифры (n = 10000, k = 10) enter image description here

Как вы видите, существует огромный шум между 65000 и 70000. Интересно, почему...

Нечетные цифры (n = 10000, k = 10), System.gc() каждые 1000 итераций enter image description here Результаты с шумом между 50000-70000

Ответы

Ответ 1

Я также подозреваю, что это эффект прогрева JVM. Не разминка, связанная с загрузкой классов или компилятором JIT, но разминкой кучи.

Поместите цикл (java) вокруг всего эталона и запустите его несколько раз. (Если это дает вам те же графики, что и раньше... у вас будет доказательство, что это не эффект разогрева. В настоящее время у вас нет каких-либо эмпирических доказательств так или иначе.)

Другая возможность заключается в том, что шум вызван вашими бенчмарками взаимодействия с ОС и/или другими вещами, запущенными на машине.

  • Вы записываете данные синхронизации в небуферизованный поток. Это означает, что LTS syscalls и (потенциально) много мелкозернистых дисков записываются.
  • Вы делаете LOTS вызовов nanoTime(), и это может вызвать шум.
  • Если что-то еще работает на вашем компьютере (например, вы просматриваете веб-страницы), это немного замедлит ваш тест и вызовет шум.
  • Там может быть конкуренция за физическую память... если на вашем компьютере слишком много работы для объема оперативной памяти.

Наконец, определенный шум неизбежен, потому что каждый из этих вызовов multiply создает мусор, и сборщик мусора должен будет работать, чтобы справиться с ним.

Наконец, если вы вручную запускаете сборщик мусора (или увеличиваете размер кучи), чтобы "сгладить" точки данных, то, что вы на самом деле делаете, скрывает одну из затрат на вызовы multiply. Полученные графики выглядят неплохо, но это вводит в заблуждение:

  • Шумы отражают то, что произойдет в реальной жизни.
  • Истинная стоимость multiply фактически включает амортизированную стоимость запуска GC для обработки мусора, сгенерированного вызовом.

Чтобы получить измерения, которые отражают поведение BigInteger в реальной жизни, вам нужно запустить тест много раз, рассчитать среднее время и подогнать кривую к средним точкам данных.

Помните, что настоящая цель игры - получить научно обоснованные результаты... не гладкую кривую.

Ответ 2

Если вы делаете микрообъект, вы должны сначала "разогреть" JVM, чтобы JIT оптимизировал код, а затем вы можете измерить производительность. В противном случае вы измеряете работу, выполняемую JIT, и которая может изменить результат при каждом прогоне.

"Шум" происходит, вероятно, потому, что кеш процессора превышен, и производительность начинает ухудшаться.