Вопрос по arrays, performance – Clojure: почему aget такой медленный?

4

На мой взгляд, векторы clojure имеют небольшой выигрыш в производительности по сравнению с массивами Java. В результате я подумал, что «общепринятая мудрость» было то, что для тех критически важных для вашего кода частей вам было бы лучше использовать Java-массивы.

Однако мои тесты показывают, что это не так:

<code>Clojure 1.3.0
user=> (def x (vec (range 100000)))
#'user/x
user=> (def xa (int-array x))
#'user/xa
user=> (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ s (nth x i))) s)))
"Elapsed time: 16.551 msecs"
4999950000
user=> (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ s (aget xa i))) s)))
"Elapsed time: 1271.804 msecs"
4999950000
</code>

Как вы можете видеть, aget добавляет около 800% времени к этому дополнению. Оба метода по-прежнему медленнее, чем родной Java:

<code>public class Test {                                                                                                                                                                                                                                                                                                           
    public static void main (String[] args) {                                                                                                                                                                                                                                                                                 
        int[] x = new int[100000];                                                                                                                                                                                                                                                                                            
        for (int i=0;i<100000;i++) {                                                                                                                                                                                                                                                                                          
            x[i]=i;                                                                                                                                                                                                                                                                                                           
        }                                                                                                                                                                                                                                                                                                                     
        long s=0;                                                                                                                                                                                                                                                                                                             
        long end, start = System.nanoTime();                                                                                                                                                                                                                                                                                  
        for (int i=0;i<100000;i++) {                                                                                                                                                                                                                                                                                          
            s+= x[i];                                                                                                                                                                                                                                                                                                         
        }                                                                                                                                                                                                                                                                                                                     
        end = System.nanoTime();                                                                                                                                                                                                                                                                                              
        System.out.println((end-start)/1000000.0+" ms");                                                                                                                                                                                                                                                                      
        System.out.println(s);                                                                                                                                                                                                                                                                                                
    }                                                                                                                                                                                                                                                                                                                         
}                              

> java Test
1.884 ms
4999950000
</code>

Итак, должен ли я сделать вывод, что aget в 80 раз медленнее, чем nth, и примерно в 800 раз медленнее, чем [] -доступ в java?

Опубликовал продолжение странного поведения оптимизации aget наstackoverflow.com/questions/10144937/… NielsK
Много работы ушло на то, чтобы удержать вас от необходимости такого рода оптимизации :) Arthur Ulfeldt

Ваш Ответ

3   ответа
4

user> (set! *warn-on-reflection* true)
true
user> (def x (vec (range 100000)))
#'user/x
user>  (def xa (int-array x))
#'user/xa
user>  (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ s (nth x i))) s)))
NO_SOURCE_FILE:1 recur arg for primitive local: s is not matching primitive, had: Object, needed: long
Auto-boxing loop arg: s
"Elapsed time: 12.11893 msecs"
4999950000
user> (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ s (aget xa i))) s)))
Reflection warning, NO_SOURCE_FILE:1 - call to aget can't be resolved.
NO_SOURCE_FILE:1 recur arg for primitive local: s is not matching primitive, had: Object, needed: long
Auto-boxing loop arg: s
Reflection warning, NO_SOURCE_FILE:1 - call to aget can't be resolved.
"Elapsed time: 2689.865468 msecs"
4999950000
user> 

второй просто имеет больше отражения в этом.

При запуске такого теста обязательно запустите его много раз, чтобы компилятор hotSpot прогрелся

user> (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ s (aget xa i))) (long s))))
"Elapsed time: 3135.651399 msecs"
4999950000
user> (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ (long s) (aget xa i))) (long s))))
"Elapsed time: 1014.218461 msecs"
4999950000
user> (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ (long s) (aget xa i))) (long s))))
"Elapsed time: 998.280869 msecs"
4999950000
user> (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ (long s) (aget xa i))) (long s))))
"Elapsed time: 970.17736 msecs"
4999950000

в этом случае несколько прогонов снизили его до 1/3 от первоначального времени (хотя рефлексия все еще остается главной проблемой)

если я согрею их обоих временем, результаты значительно улучшатся:

(dotimes [_ 1000]  (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ s (nth x  i))) s))))
"Elapsed time: 3.704714 msecs"

(dotimes [_ 1000] (time  (loop [i 0 s 0] (if (< i 100000) (recur (inc i) (+ (long s) (aget xa i))) (long s)))))
"Elapsed time: 936.03987 msecs"
На самом деле, это лучший ответ на реальный вопрос: почему он медленный. Тем не менее, подразумеваемый вопрос - как ускорить его - действительно заключается в использовании подсказки типа в массиве. Спасибо за разъяснение, хотя! Claude
github.com/hugoduncan/criterium хорошо подходит для бенчмаркинга с разогревом JIT и т. д.
4

что подсказки типа не нужны вообще, Clojure оптимизирует из коробки.

Когда нужно выполнить полиадическую функцию над коллекцией, просто используйте apply и функцию. Когда вам нужна функция, примененная к элементам в коллекции, и результат, сохраненный в аккумуляторе, используйте Reduce. В этом случае применяются оба.

=> (def xa (into-array (range 100000)))
#'user/xa

=> (time (apply + xa))
"Elapsed time: 12.264753 msecs"
4999950000

=>(time (reduce + xa))
"Elapsed time: 2.735339 msecs"
4999950000

И даже проще выравнивает эти различия, хотя и немного медленнее, чем приведенный выше лучший случай:

=> (def xa (range 100000))
#'user/xa

=> (time (apply + xa))
"Elapsed time: 4.547634 msecs"
4999950000

=> (time (reduce + xa))
"Elapsed time: 4.506572 msecs"

Просто попробуйте написать самый простой код, и, только если это недостаточно быстро, оптимизируйте.

В этом случае вы правы, но, очевидно, мой пример из реальной жизни гораздо сложнее, чем просто добавление материала и требуетagetс разных массивов. На самом деле, различия в ваших первых тестах связаны с оптимизацией компилятора: когда вы сначала запускаете Reduce, а затем AppI, применяется быстрее. Claude
Тесты проводились неоднократно; Применить оставалось примерно на 12 мс, снижение началось примерно на 12 с, но стабилизировалось на уровне примерно 2,7 мс. Вот почему тесты со временем выгорания важны для JVM. Я проголосовал за ответ Sw1nn, если действительно нужен произвольный доступ. Часто могут быть применены функциональные алгоритмы, основанные на основных функциях Clojure, использующих преимущества его внутренней оптимизации и такие преимущества, как лень.
9

что это связано с отражением и автобоксом примитивных типов функцией aget ....

К счастью, aget / aset имеют существенные перегрузки для примитивных массивов, которые избегают отражения и просто осуществляют прямой доступ к массиву [i] (см.Вот а такжеВот).

Вам просто нужно передать подсказку типа, чтобы подобрать правильную функцию.

(type xa)
[I    ; indicates array of primitive ints

; with type hint on array
;
(time (loop [i 0 s 0] 
        (if (< i 100000) (recur (inc i) 
          (+ s (aget ^ints xa i))) s))) 
"Elapsed time: 6.79 msecs"
4999950000

; without type hinting
;
(time (loop [i 0 s 0] 
        (if (< i 100000) (recur (inc i) 
          (+ s (aget xa i))) s)))
"Elapsed time: 1135.097 msecs"
4999950000
в обоих случаях происходит автоматическая упаковка
Спасибо! Благодаря подсказке типов мое решение для Java-массива теперь в два раза быстрее, чем векторное замыкание. Тем не менее, он в 5 раз медленнее, чем нативная Java, так что я думаю, что "реальный" Решение было бы выделить эту часть кода в простой Java-класс, верно? Claude
@Claude - это было интересное упражнение, сравнивающее относительную эффективность двух подходов, и поэтому немного искусственное. Однако был ли у вас вопрос: «Каков наилучший / самый быстрый способ суммировать последовательность в 100 000 дюймов?» тогда простой(reduce + xa) как предложено NielsK, это явно превосходящий (и самый идиоматический) подход. Я предполагаю, что вам нужно сделать что-то большее, чем это, и именно это привело вас на этот путь.

Похожие вопросы