Умножается быстрее, чем доступ к массиву?

Question

К моему удивлению, я получаю более длительное время (10 миллисекунд) при «оптимизации» умножений путем предварительного генерации результатов в массиве по сравнению с исходными 8 миллисекундами. Это просто причуда Java или это общая архитектура ПК? У меня есть Core i5 760 с Java 7, Windows 8 64 бит.

public class Test { 
    public static void main(String[] args) { 
     long start = System.currentTimeMillis(); 
     long sum=0; 
     int[] sqr = new int[1000]; 
     for(int a=1;a<1000;a++) {sqr[a]=a*a;} 

     for(int b=1;b<1000;b++) 
//   for(int a=1;a<1000;a++) {sum+=a*a+b*b;} 
      for(int a=1;a<1000;a++) {sum+=sqr[a]+sqr[b];} 
     System.out.println(System.currentTimeMillis()-start+"ms"); 
     System.out.println(sum); 
    } 
} 

Answer 1

Konrad Rudolph commented on the issues с бенчмаркинга. Поэтому я игнорирую контрольный показатель и фокусируюсь на вопросе:

Является ли умножение быстрее, чем доступ к массиву?

Да, это очень вероятно. Раньше это было наоборот 20-30 лет назад.

Грубо говоря, вы можете сделать целое умножение в 3-х циклов (пессимистический, если вы не получаете векторных инструкций), а также затраты на доступ к памяти у вас 4 цикла, если вы получите его прямо из кэша L1, но прямо вниз оттуда. Для справки см

• латентности и пропускной способности в Приложении С Intel 64 and IA-32 Architectures Optimization Reference Manual

• Approximate cost to access various caches and main memory?

• презентация Герба Саттера на этой самой теме: Machine Architecture: Things Your Programming Language Never Told You

---

Один вещь, специфичная для Java была в комментариях ниже pointed out by Ingo: Вы также получить проверки границ в Java, что делает уже медленнее доступ к массиву еще медленнее ...

Answer 2

Более разумный ориентир будет:

public abstract class Benchmark { 

    final String name; 

    public Benchmark(String name) { 
     this.name = name; 
    } 

    abstract int run(int iterations) throws Throwable; 

    private BigDecimal time() { 
     try { 
      int nextI = 1; 
      int i; 
      long duration; 
      do { 
       i = nextI; 
       long start = System.nanoTime(); 
       run(i); 
       duration = System.nanoTime() - start; 
       nextI = (i << 1) | 1; 
      } while (duration < 1000000000 && nextI > 0); 
      return new BigDecimal((duration) * 1000/i).movePointLeft(3); 
     } catch (Throwable e) { 
      throw new RuntimeException(e); 
     } 
    } 

    @Override 
    public String toString() { 
     return name + "\t" + time() + " ns"; 
    } 

    private static void shuffle(int[] a) { 
     Random chaos = new Random(); 
     for (int i = a.length; i > 0; i--) { 
      int r = chaos.nextInt(i); 
      int t = a[r]; 
      a[r] = a[i - 1]; 
      a[i - 1] = t; 
     } 
    } 


    public static void main(String[] args) throws Exception { 
     final int[] table = new int[1000]; 
     final int[] permutation = new int[1000]; 

     for (int i = 0; i < table.length; i++) { 
      table[i] = i * i; 
      permutation[i] = i; 
     } 
     shuffle(permutation); 

     Benchmark[] marks = { 
      new Benchmark("sequential multiply") { 
       @Override 
       int run(int iterations) throws Throwable { 
        int sum = 0; 
        for (int j = 0; j < iterations; j++) { 
         for (int i = 0; i < table.length; i++) { 
          sum += i * i; 
         } 
        } 
        return sum; 
       } 
      }, 
      new Benchmark("sequential lookup") { 
       @Override 
       int run(int iterations) throws Throwable { 
        int sum = 0; 
        for (int j = 0; j < iterations; j++) { 
         for (int i = 0; i < table.length; i++) { 
          sum += table[i]; 
         } 
        } 
        return sum; 
       } 
      }, 
      new Benchmark("random order multiply") { 
       @Override 
       int run(int iterations) throws Throwable { 
        int sum = 0; 
        for (int j = 0; j < iterations; j++) { 
         for (int i = 0; i < table.length; i++) { 
          sum += permutation[i] * permutation[i]; 
         } 
        } 
        return sum; 
       } 
      }, 
      new Benchmark("random order lookup") { 
       @Override 
       int run(int iterations) throws Throwable { 
        int sum = 0; 
        for (int j = 0; j < iterations; j++) { 
         for (int i = 0; i < table.length; i++) { 
          sum += table[permutation[i]]; 
         } 
        } 
        return sum; 
       } 
      } 
     }; 

     for (Benchmark mark : marks) { 
      System.out.println(mark); 
     } 
    } 
} 

который печать на моей основной Intel дуэт (да, это старый):

sequential multiply 2218.666 ns 
sequential lookup  1081.220 ns 
random order multiply 2416.923 ns 
random order lookup 2351.293 ns 

Так что, если я достигаю последовательно поиск массива, который сводит к минимуму количество промахов кэша и позволяет HotSpot JVM оптимизировать проверку границ на доступ к массиву , есть небольшое impr ovement на массиве из 1000 элементов. Если мы делаем произвольный доступ к массиву, это преимущество исчезает. Кроме того, если таблица больше, поиск становится медленнее. Например, на 10000 элементов, я получаю:

sequential multiply 23192.236 ns 
sequential lookup  12701.695 ns 
random order multiply 24459.697 ns 
random order lookup 31595.523 ns 

Таким образом, поиск массива не быстрее, чем умножение, если модель доступа не является (почти) последовательной и массив поиска мало.

В любом случае мои измерения показывают, что умножение (и добавление) занимает всего 4 процессорных цикла (2,3 нс на итерацию в петле на 2 ГГц ЦП). Вы вряд ли получите гораздо быстрее, чем это. Кроме того, если вы не делаете полмиллиарда умножений в секунду, умножения не являются вашим узким местом, и оптимизация других частей кода будет более плодотворной.