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

Question

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

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

## mandel 

mandel = function(z) { 
    c = z 
    maxiter = 80 
    for (n in 1:maxiter) { 
     if (Mod(z) > 2) return(n-1) 
     z = z^2+c 
    } 
    return(maxiter) 
} 

mandelperf = function() { 
    re = seq(-2,0.5,.1) 
    im = seq(-1,1,.1) 
    M = matrix(0.0,nrow=length(re),ncol=length(im)) 
    count = 1 
    for (r in re) { 
     for (i in im) { 
      M[count] = mandel(complex(real=r,imag=i)) 
      count = count + 1 
     } 
    } 
    return(M) 
} 

assert(sum(mandelperf()) == 14791) 

## quicksort ## 

qsort_kernel = function(a, lo, hi) { 
    i = lo 
    j = hi 
    while (i < hi) { 
     pivot = a[floor((lo+hi)/2)] 
     while (i <= j) { 
      while (a[i] < pivot) i = i + 1 
      while (a[j] > pivot) j = j - 1 
      if (i <= j) { 
       t = a[i] 
       a[i] = a[j] 
       a[j] = t 
      } 
      i = i + 1; 
      j = j - 1; 
     } 
     if (lo < j) qsort_kernel(a, lo, j) 
     lo = i 
     j = hi 
    } 
    return(a) 
} 

qsort = function(a) { 
    return(qsort_kernel(a, 1, length(a))) 
} 

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

sortperf(5000) 

Answer 1

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

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-кратной скорости -up (результаты равны, но не идентичны, потому что оригинал возвращает числовые, а не целочисленные значения).

> 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 

Поскольку в исходном сравнении Julia примерно в 30 раз быстрее, чем R для mandel, и в 500 раз быстрее для quicksort, реализации выше по-прежнему не очень конкурентоспособны.

Answer 2

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

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

Как и в «как быстро вы можете сделать эти алгоритмы в R?» Рассматриваемые здесь алгоритмы представляют собой стандартный алгоритм итерации сложного цикла Мандельброта и стандартное рекурсивное ядро ​​quicksort.

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

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

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

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

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