Ускорение плохо написанных примеров Джулии - PullRequest
Новая
       8

Ускорение плохо написанных примеров Джулии

71 голосов
/ 02 апреля 2012

Примеры Julia для сравнения производительности с R кажутся особенно запутанными .https://github.com/JuliaLang/julia/blob/master/test/perf/perf.R

Какую максимальную производительность вы можете получить из двух приведенных ниже алгоритмов (желательно с объяснением того, что вы изменили, чтобы сделать его более похожим на R)?

Ответы [ 2 ]

97 голосов
/ 23 мая 2012

Ключевым словом в этом вопросе является «алгоритм»:

Какую максимальную производительность вы можете получить из двух алгоритмов ниже (желательно с объяснением того, чтоВы изменили, чтобы сделать его более похожим на R)?

Как в "как быстро вы можете сделать эти алгоритмы в R?"Рассматриваемые алгоритмы - это стандартный алгоритм итерации сложного цикла Мандельброта и стандартное рекурсивное ядро ​​быстрой сортировки.

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

Если вы действительно хотите вычислять множества Мандельброта в R или сортировать числа, да, это не то, как вы бы написали код.Вы должны либо максимально векторизовать его - тем самым перенести всю работу в предварительно определенные ядра C - или просто написать собственное расширение C и выполнить там вычисления.В любом случае, вывод заключается в том, что R недостаточно быстр для того, чтобы получить действительно хорошую производительность - вам нужно, чтобы C выполнял большую часть работы, чтобы добиться хорошей производительности.

И в этом сутьэти тесты: в Julia вам никогда не придется полагаться на код C, чтобы получить хорошую производительность.Вы можете просто написать, что вы хотите делать на чистой Юлии, и это будет иметь хорошую производительность.Если алгоритм итеративного скалярного цикла является наиболее естественным способом сделать то, что вы хотите сделать, то просто сделайте это.Если рекурсия является наиболее естественным способом решения проблемы, то это тоже нормально.Ни при каких обстоятельствах вы не будете вынуждены полагаться на производительность C - будь то с помощью неестественной векторизации или написания пользовательских расширений C.Конечно, вы можете писать векторизованный код, когда он естественен, как это часто бывает в линейной алгебре;и вы можете вызвать C, если у вас уже есть библиотека, которая делает то, что вы хотите.Но вам не нужно.

Мы хотим провести максимально точное сравнение одних и тех же алгоритмов на разных языках:

  1. Если у кого-то есть более быстрые версии в R, то используйте тот же алгоритм , пожалуйста, отправьте патчи!
  2. Я считаю, что тесты R на сайте julia уже скомпилированы, но если я делаю это неправильно исравнение несправедливо по отношению к R, пожалуйста, дайте мне знать, и я исправлю это и обновлю тесты.
42 голосов
/ 02 апреля 2012

Хм, в примере Мандельброта матрица M имеет свои размеры, транспонированные 

M = matrix(0.0,nrow=length(im), ncol=length(re))

, потому что она заполнена путем увеличения count во внутреннем цикле (последовательные значения im).Моя реализация создает вектор комплексных чисел в mandelperf.1 и работает со всеми элементами, используя индекс и поднабор для отслеживания того, какие элементы вектора еще не удовлетворяют условию Mod(z) <= 2

mandel.1 = function(z, maxiter=80L) {
    c <- z
    result <- integer(length(z))
    i <- seq_along(z)
    n <- 0L
    while (n < maxiter && length(z)) {
        j <- Mod(z) <= 2
        if (!all(j)) {
            result[i[!j]] <- n
            i <- i[j]
            z <- z[j]
            c <- c[j]
        }
        z <- z^2 + c
        n <- n + 1L
    }
    result[i] <- maxiter
    result
}

mandelperf.1 = function() {
    re = seq(-2,0.5,.1)
    im = seq(-1,1,.1)
    mandel.1(complex(real=rep(re, each=length(im)),
                     imaginary=im))
}

для 13-кратного ускорения (результаты равны, но не идентичны, поскольку оригинал возвращает числовые, а не целые значения). 

> library(rbenchmark)
> benchmark(mandelperf(), mandelperf.1(),
+           columns=c("test", "elapsed", "relative"),
+           order="relative")
            test elapsed relative
2 mandelperf.1()   0.412  1.00000
1   mandelperf()   5.705 13.84709

> all.equal(sum(mandelperf()), sum(mandelperf.1()))
[1] TRUE

Пример быстрой сортировки фактически не сортирует 

> set.seed(123L); qsort(sample(5))
[1] 2 4 1 3 5

но моим основным ускорением было векторизация раздела вокруг центра 

qsort_kernel.1 = function(a) {
    if (length(a) < 2L)
        return(a)
    pivot <- a[floor(length(a) / 2)]
    c(qsort_kernel.1(a[a < pivot]), a[a == pivot], qsort_kernel.1(a[a > pivot]))
}

qsort.1 = function(a) {
    qsort_kernel.1(a)
}

sortperf.1 = function(n) {
    v = runif(n)
    return(qsort.1(v))
}

для 7-кратного ускорения (по сравнению с неоткорректированным оригиналом) 

> benchmark(sortperf(5000), sortperf.1(5000),
+           columns=c("test", "elapsed", "relative"),
+           order="relative")
              test elapsed relative
2 sortperf.1(5000)    6.60 1.000000
1   sortperf(5000)   47.73 7.231818

Св исходном сравнении Джулия примерно в 30 раз быстрее, чем R для Манделя, и в 500 раз быстрее для быстрой сортировки, приведенные выше реализации все еще не очень конкурентоспособны.

...