|
|
Строка 1: |
Строка 1: |
− | {{CC-BY-4.0|author=автором Артём Клевцов}}
| |
| | | |
− | {{Pkg-req-notice}}
| |
− |
| |
− | Для измерения времени выполнения выражений используют следующие инструменты:
| |
− | * Функция <code>system.time()</code> из базового пакета;
| |
− | * Cпециализированные функции (benchmarks, бенчмарки);
| |
− | * Функция профилирования времени выполнения кода <code>Rprof()</code>.
| |
− |
| |
− | == Функция <code>system.time</code> ==
| |
− |
| |
− | Самый простой инструмент для измерения времени выполнения кода - функция <code>system.time()</code> из пакета {{r-package|base|core=true}}. В качестве аргумента функция <code>system.time()</code> принимает выражения и возвращает время выполнения данного выражения. Измерим время выполнения функции <code>Sys.sleep()</code>, которая останавливает выполнение кода на заданный интервал времени (в секундах):
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> system.time(Sys.sleep(1))
| |
− | пользователь система прошло
| |
− | 0.003 0.004 1.000
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Как видим, на выполнение данной операции заняло ровно одну секунду.
| |
− |
| |
− | Приведём ещё один пример. Сравним время вычисления встроенной в R функции <code>mean()</code> и среднего, вычисленного по формуле <math>\frac{1}{n}\sum_{i=1}^{n}x_{i}</math>. на сгенерированном массиве нормально распределенных значений:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> x <- rnorm(10^7L)
| |
− | > system.time(mean(x))
| |
− | пользователь система прошло
| |
− | 0.020 0.000 0.023
| |
− | > system.time(sum(x) / length(x))
| |
− | пользователь система прошло
| |
− | 0.013 0.000 0.012
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Функция возвращает 3 значения:
| |
− | * <code>user</code> - время CPU, которое занял пользователь;
| |
− | * <code>system</code> - время CPU, которое заняла система;
| |
− | * <code>elapsed</code> - реальное время, которое заняло выполнение команды.
| |
− |
| |
− | Соответственно, в выводе функции нас интересует значение <code>elapsed</code>, который показывает время выполнения функции (выражения) в секундах. Как мы видим, внешне более сложное выражение <code>sum(x) / length(x)</code> выполняется быстрее стандартной функции <code>mean(x)</code>.
| |
− |
| |
− | К сожалению, подобный способ достаточно ненадежен, так как для оценки времени выполнения выражения функция <code>system.time()</code> обращается к системным значениям времени. Следовательно, если во время выполнения кода параллельно производятся и другие операции на компьютере (а такое случается практически в ста процентах случаев), то возможно увеличение времени выполнения R-кода. Некоторую вариативность результатов можно увидеть, даже если выполнить функцию <code>system.time()</code> несколько раз подряд. Подобной неточности оценки можно избежать путём многократного повторения выполняемых выражений и вычислением среднего времени, что позволит сгладить часть вариаций.
| |
− |
| |
− | Проиллюстрируем вышесказанное на примере:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> replicate(10, system.time(mean(x))[["elapsed"]])
| |
− | [1] 0.024 0.020 0.019 0.018 0.017 0.016 0.015 0.015 0.015 0.015
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | В этом примере с помощью функции <code>replicate()</code> мы повторили выражение <code>system.time(mean(x))</code> 10 раз, отфильтровав вывод функции <code>system.time()</code> так, чтобы нам выводилось только время выполнения команды, дописав <code>[["elapsed"]]</code>. Как мы видим, время выполнения при повторном выполнении выражения может отличаться.
| |
− |
| |
− | Базовый пакет позволяет реализовать процедуру многократного повторения выражения функции как минимум двумя способами. Первый - функция <code>replicate()</code>. Приведенное выше сопоставление времени выполнения двух выражений при использовании функции <code>replicate()</code> будет выглядеть следующим образом:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> system.time(replicate(100, mean(x)))
| |
− | пользователь система прошло
| |
− | 1.580 0.000 1.586
| |
− | > system.time(replicate(100, sum(x) / length(x)))
| |
− | пользователь система прошло
| |
− | 0.817 0.016 0.835
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Тот же самый эффект можно получить и с помощью обычного цикла <code>for()</code>:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> system.time(for (i in seq_len(100)) mean(x))
| |
− | пользователь система прошло
| |
− | 1.583 0.000 1.590
| |
− | > system.time(for (i in seq_len(100)) sum(x) / length(x))
| |
− | пользователь система прошло
| |
− | 0.797 0.000 0.800
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Можно также использовать описательные статистики в сочетании с множественными повторениями:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> median(replicate(100, system.time(mean(x))[["elapsed"]]))
| |
− | [1] 0.0155
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | В примере выше мы взяли только значения <code>elapsed</code> и рассчитали медиану <ref>Медиана является более устойчивой мерой центральной тенденции при асимметрии распределения, что, как правило, характерно для измерения времени.</ref>.
| |
− |
| |
− | Вместо подобных решений можно использовать специальные пакеты, предназначенные для измерения производительности кода, в частности, пакеты {{r-package|rbenchmark}} и {{r-package|microbenchmark}}. Основной принцип работы этих пакетов заключается в многократном выполнении выражений и расчёта ряда интегральных показателей, в частности, суммы, среднего значения или медианы времени выполнения всех попыток.
| |
− |
| |
− | == Пакет {{r-package|rbenchmark}} ==
| |
− |
| |
− | Основа пакета {{r-package|rbenchmark}} - функция <code>benchmark()</code>. Данная функция работает следующим образом: указанные в качестве аргументов выражения выполняются заданное количество раз (по умолчанию 100) и вычисляется время, затраченное на выполнение всех попыток. В качестве аргументов функции <code>benchmark()</code> необходимо передать выражения или функции, а также количество повторений, передаваемых аргументом replications<ref>Анализ функции <code>benchmark()</code> показал, что, данная функция использует <code>system.time()</code> и <code>replicate()</code>, рассмотренные в предыдущем разделе.</ref>.
| |
− |
| |
− | Для примера возьмём несколько способов расчёта среднего арифметического для сгенерированного массива данных.
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> x <- replicate(10, rnorm(10^6L))
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Использованные нами способы - функции векторизованных вычислений (<code>apply()</code>, <code>vapply()</code>), стандартный цикл и специальная функция вычисления средних по столбцам <code>ColMeans()</code>. Представим эти способы в виде самостоятельных функций для удобства их вызова при работе с <code>benchmark()</code>:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>colMeansApply <- function(x) {
| |
− | apply(x, 2, mean)
| |
− | }
| |
− |
| |
− | colMeansVapply <- function(x) {
| |
− | vapply(seq_len(ncol(x)), function(i) mean(x[, i]), FUN.VALUE = numeric(1))
| |
− | }
| |
− |
| |
− | colMeansLoop <- function(x) {
| |
− | n.vars <- ncol(x)
| |
− | res <- double(n.vars)
| |
− | for (i in seq_len(n.vars))
| |
− | res[i] <- mean(x[, i])
| |
− | return(res)
| |
− | }
| |
− |
| |
− | colMeansLoopVec <- function(x) {
| |
− | n.vars <- ncol(x)
| |
− | n <- nrow(x)
| |
− | res <- double(n.vars)
| |
− | for (i in seq_len(n.vars))
| |
− | res[i] <- sum(x[, i]) / n
| |
− | return(res)
| |
− | }
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Убедимся, что функции возвращают одинаковый результат. Сделать это можно с помощью функций <code>identical()</code> или <code>all.equal()</code>:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> identical(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x))
| |
− | [1] TRUE
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Теперь, подключив пакет {{r-package|rbenchmark}}, мы можем сравнить время работы каждого из выбранных нами способов вычисления средних по столбцам:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> library(rbenchmark)
| |
− | > benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x),
| |
− | + colMeansLoopVec(x), colMeans(x), replications = 100)
| |
− | test replications elapsed relative user.self sys.self user.child sys.child
| |
− | 1 colMeansApply(x) 100 13.206 16.802 11.893 1.260 0 0
| |
− | 4 colMeansLoopVec(x) 100 6.931 8.818 6.793 0.113 0 0
| |
− | 3 colMeansLoop(x) 100 7.729 9.833 7.583 0.113 0 0
| |
− | 2 colMeansVapply(x) 100 7.724 9.827 7.630 0.067 0 0
| |
− | 5 colMeans(x) 100 0.786 1.000 0.784 0.000 0 0
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Наиболее важны для нас в выводе функции <code>benchmark()</code> столбцы <code>elapsed</code> и <code>relative</code>. Столбец <code>elapsed</code> показывает время в секундах, затраченное на выполнение интересующей нас функции. Как видим из примера, самыми медленными оказались функции <code>colMeansApply()</code> и <code>colMeansLoop()</code>, а самой быстрой <code>colMeans()</code>, причём превосходит остальные по скорости выполнения как минимум в 7 раз.
| |
− |
| |
− | Показатель <code>relative</code> дает информацию о разнице во времени относительно самого быстрого выражения (в нашем случае это <code>ColMeans()</code>), т.е. время самого быстрого выражения берётся за единицу, и рассчитывается относительное время для остальных выражений.
| |
− |
| |
− | Для более удобного просмотра можно отфильтровать вывод функции <code>benchmark()</code> с помощью аргумента <code>columns</code>. Также может быть полезен аргумент <code>order</code>, позволяющий отсортировать вывод по любому из столбцов. Для примера зададим набор показателей, которые мы хотим включить в таблицу (в данном случае это «test», «replications», «elapsed», «relative»), и отсортируем выдачу по столбцу «elapsed» по возрастанию значений:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x),
| |
− | + replications = 100, order = "relative",
| |
− | + columns = c("test", "replications", "elapsed", "relative"))
| |
− | 5 colMeans(x) 100 0.782 1.000
| |
− | 4 colMeansLoopVec(x) 100 6.890 8.811
| |
− | 3 colMeansLoop(x) 100 7.684 9.826
| |
− | 2 colMeansVapply(x) 100 7.716 9.867
| |
− | 1 colMeansApply(x) 100 13.142 16.806
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Таким образом, сравнив несколько альтернатив решения нашей задачи, мы можем сделать обоснованный выбор в пользу наиболее эффективного варианта.
| |
− |
| |
− | Чтобы не указывать нужные столбцы каждый раз, когда используется функция <code>benchmark()</code>, можно закрепить заданный формат выдачи результатов (далее используется именно такой формат вывода, с сортировкой по столбцу «relative»). Для этого следует воспользоваться функцией <code>formals()</code>:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> formals(benchmark)$columns <- c("test", "replications", "elapsed", "relative")
| |
− | > formals(benchmark)$order <- "relative"
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | == Пакет {{r-package|microbenchmark}} ==
| |
− |
| |
− | Функция <code>microbenchmark()</code> одноименного пакета работает сходным с функцией <code>benchmark()</code> образом, но предоставляет более гибкие средства по управлению процессом выполнения выражений<ref>Но в отличии от функции benchmark() использует собственную реализацию измерения времени выполнения и организацию повторных испытаний.</ref>. Особенностями реализованных в пакете {{r-package|microbenchmark}} являются:
| |
− |
| |
− | * Возможность измерения времени выполнения выражения вплоть до наносекунд;
| |
− | * Возможность контролировать последовательность выполнения выражений: случайно или последовательно;
| |
− | * Возможность проведения предварительных испытаний до начала процесса измерений.
| |
− |
| |
− | Также с помощью функции <code>microbenchmark()</code> можно получить исходную информацию о времени выполнения каждой попытки, что даёт достаточно широкие возможности по обработке и анализу полученных результатов.
| |
− |
| |
− | В таблице ниже представлено время выполнения пяти функций вычисления среднего значения из предыдущего примера, полученное с помощью функции <code>microbenchmark()</code>:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> res <- microbenchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x),
| |
− | + colMeansLoopVec(x), colMeans(x), times = 100)
| |
− | > print(res, unit = "ms", order = "median")
| |
− | Unit: milliseconds
| |
− | expr min lq median uq max neval
| |
− | colMeans(x) 7.796 7.828 7.87 7.943 8.063 100
| |
− | colMeansLoopVec(x) 67.495 68.524 75.11 81.684 101.999 100
| |
− | colMeansVapply(x) 75.791 76.648 85.47 90.325 94.803 100
| |
− | colMeansLoop(x) 75.632 76.920 85.65 90.346 99.707 100
| |
− | colMeansApply(x) 102.908 127.148 132.24 136.095 144.833 100
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Все результаты представлены в виде описательных статистик, рассчитанных из времени выполнения каждой попытки. Наиболее информативный столбец - это столбец median, который показывает медиану времени выполнения выражения для всех попыток.
| |
− |
| |
− | Вся полученная информация о попытках применения функций вычисления средних записана в отдельную переменную <code>res</code>. С помощью функции <code>str()</code> можно увидеть структуру переменной:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> str(res)
| |
− | Classes ‘microbenchmark’ and 'data.frame': 500 obs. of 2 variables:
| |
− | $ expr: Factor w/ 5 levels "colMeansApply(x)",..: 4 2 1 1 1 3 3 5 5 1 ...
| |
− | $ time: num 1.02e+08 8.55e+07 1.04e+08 1.10e+08 1.29e+08 ...
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Переменная <code>res</code>, как можно увидеть в выводе функции <code>str()</code>, представляет собой список (list) и включает в себя две переменные: <code>expr</code> (выражение) и <code>time</code> (время выполнения). На основе этой информации и рассчитываются описательные статистики, приведённые в примере применения функции <code>microbenchmark()</code>. Наличие исходных данных о каждой попытке позволяет самостоятельно выбирать, рассчитывать и сравнивать предпочтитаемые показатели. Например, расчет медианного времени выполнения попытки и общего времени выполнения всех попыток для каждого выражения выглядит следующим образом:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> aggregate(time ~ expr, data = res, function(x) median(x) * 10^-6L)
| |
− | expr time
| |
− | 1 colMeansApply(x) 132.24
| |
− | 2 colMeansVapply(x) 85.47
| |
− | 3 colMeansLoop(x) 85.65
| |
− | 4 colMeansLoopVec(x) 75.11
| |
− | 5 colMeans(x) 7.87
| |
− | > aggregate(time ~ expr, data = res, function(x) sum(x) * 10^-6L)
| |
− | expr time
| |
− | 1 colMeansApply(x) 13015.8
| |
− | 2 colMeansVapply(x) 8400.4
| |
− | 3 colMeansLoop(x) 8447.8
| |
− | 4 colMeansLoopVec(x) 7576.8
| |
− | 5 colMeans(x) 788.8
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Умножение на <math>10^{-6}</math> --- это перевод в миллисекунды. Чтобы получить секунды, нужно, соответственно, умножить на <math>10^{-9}</math>.
| |
− |
| |
− | Помимо настройки формата вывода, выбора показателей, наличие информации о времени выполнения выражения в каждой попытке позволяет визуализировать результаты оценки времени выполнения выражения. Например, с помощью функции <code>autoplot()</code> из пакета {{r-package|ggplot2}}, можно получить следующий график:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> library(ggplot2)
| |
− | > autoplot(res)
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | [[Файл:Microbenchmark-autoplot-colMeans.png|600px|центр]]
| |
− |
| |
− | Ещё один довольно интересный способ графического представления результатов измерения скорости выполнения кода с помощью функции <code>qplot()</code> представлен ниже:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> qplot(y = time, data = res, colour = expr)
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | [[Файл:Microbenchmark-dotplot-colMeans.png|600px|центр]]
| |
− |
| |
− | Так же можно, если возникнет необходимость, оценить статистическую значимость различий во времени выполнения выражений. Благодаря тому, что в переменной <code>res</code> хранятся данные о времени выполнения каждой попытки из заданного числа, становится возможным использование статистических критериев. Выбор критерия - на усмотрение аналитика, в примере ниже использовался параметрический критерий сравнения групп t-Стьюдента с поправкой уровня статистической значимости Холма для множественных сравнений:
| |
− |
| |
− | {{r-code|code=
| |
− | <nowiki>> pairwise.t.test(res$time, res$expr)
| |
− |
| |
− | Pairwise comparisons using t tests with pooled SD
| |
− |
| |
− | data: res$time and res$expr
| |
− |
| |
− | colMeansApply(x) colMeansVapply(x) colMeansLoop(x) colMeansLoopVec(x)
| |
− | colMeansVapply(x) <2e-16 - - -
| |
− | colMeansLoop(x) <2e-16 0.62 - -
| |
− | colMeansLoopVec(x) <2e-16 <2e-16 <2e-16 -
| |
− | colMeans(x) <2e-16 <2e-16 <2e-16 <2e-16
| |
− |
| |
− | P value adjustment method: holm
| |
− | </nowiki>
| |
− | }}
| |
− |
| |
− | Из вышеприведённого вывода видно, что скорость выполнения всех функций статистически значимо разлиается у всех функций, за исключением пары <code>colMeansLoop(x)</code> - <code>colMeansVapply(x)</code> (p-уровень = 0.62).
| |
− |
| |
− | == Примечания ==
| |
− | <references />
| |
− |
| |
− | == Ссылки ==
| |
− |
| |
− | * Olaf Mersmann (2013). microbenchmark: Sub microsecond accurate timing functions.. R package version 1.3-0.
| |
− | *: http://CRAN.R-project.org/package=microbenchmark
| |
− | * Wacek Kusnierczyk (2012). rbenchmark: Benchmarking routine for R. R package version 1.0.0.
| |
− | *: http://CRAN.R-project.org/package=rbenchmark
| |
− |
| |
− | [[Категория:R]]
| |
− | [[Категория:Оптимизация кода]]
| |