Недавно просматривая асинхронные процедуры Clojure, я заметил одну вещь. У этих ребят есть функция pmap() для коллекций. Что он делает, так это делает сопоставление параллельной работой, поэтому получает некоторый импульс для больших коллекций с помощью функции карты с интенсивными вычислениями. Поэтому я, будучи ленивым и завистливым, хотел попробовать, смогу ли я заставить свои 4 ядра выполнять сопоставление в списке kotlin. Если есть хорошие библиотеки, это хорошо. Я хотел сделать функцию сам (и, возможно, прикрутить простые вещи), но просто посмотреть, смогу ли я получить карту быстрее, чем просто карту.
inline fun <A, B> List<A>.asyncMap(crossinline f: (A) -> B): List<B> { // 1 val receiver = this // 2 val cores = Runtime.getRuntime().availableProcessors() // 3 return if (cores == 1) { receiver.map(f) // 4 } else runBlocking() { // 5 val results = mutableListOf<Deferred<List<B>>>() // 6 val chunkSize = Math.max(size / cores, 1) // 7 (1..Math.min(cores, receiver.size)).forEach { val range = chunkIndex(chunkSize, cores, it, receiver) results.add(async(CommonPool) { // 8 receiver.subList(range.first, range.second).map(f) }) } results.flatMap { it.await() } // 9 } }
Итак, это основная функция.
- Определите его как функцию расширения для списка. Я не хочу играть с Iterables и коллекциями, которые я не могу «разрезать» на части без накладных расходов. Итак, я выбираю список для воспроизведения, так как алгоритм в основном — разрезаю список на равные части и даю каждому ядру сопоставить этот кусок, а затем скрепляю их вместе обратно.
- Просто удобство
- Предполагая, что наш CommonPool для асинхронной корутины будет использовать все ядра, я считаю их
- Если у нас есть только одно ядро, я не могу получить большого усиления, поэтому просто делайте старую карту.
- Запускаем нашу сопрограмму
- Мы соберем наши результаты в куски, отображаемые при запуске async. Итак, это список отложенных списков.
- Мы рассчитываем, какой размер куска будет работать для каждого ядра. Если размер коллекции меньше, чем количество ядер, что ж, тогда нам все равно нужно иметь хотя бы один элемент для работы.
- Мы запускаем n задач асинхронного сопоставления, где n — минимальное число ядер и размер коллекции. Никогда не угадаешь, если не вставишь свою коллекцию размером 2000 в машину с ядром 2048.
- Плоское сопоставление результатов обратно в исходный список сопоставленных результатов.
fun chunkIndex(chunkSize: Int, count: Int, nth: Int, c: List<*>): Pair<Int, Int> { val size = c.size return if (nth < count) Pair(chunkSize * (nth - 1), Math.min(c.size, chunkSize * nth)) else Pair(chunkSize * (nth - 1), c.size) }
Это просто вспомогательная функция для получения индекса n-го чанка в зависимости от размера чанка и ядер.
А вот еще одна приятная тестовая функция, которую вы можете использовать не только для составления карт, но и для специальных измерений.
fun <T> time(f: () -> T): T { val start = System.currentTimeMillis() val result = f() println("Elapsed:${System.currentTimeMillis() - start}") return result }
Функция также вдохновлена ребятами из Clojure. Он просто печатает время выполнения переданного блока, возвращая результат блока, поэтому вы можете обернуть любую функцию в лямбда-выражение и измерить время ее выполнения.
Теперь тест.
fun main(args: Array<String>) { val myList = (0..1000).map { it } println("FIRST") time({ myList.map { Thread.sleep(3) it + 1 } }) println("SECOND") time({ myList.asyncMap { Thread.sleep(3) it + 1 } }) }
Выход:
ПЕРВЫЙ
Прошедшее:3293
ВТОРОЕ
Прошедшее:1734
Процесс завершен с кодом выхода 0
Моя машина имеет 4 ядра. Программа для тестирования имитирует «тяжелую» функцию отображения, то есть Thread.sleep(3). Так я почти удвоил время выполнения «тяжелой» работы. Эта рутина не даст вам никакого прироста к маленьким коллекциям или даже к большим коллекциям с «облегченной» функцией отображения. Так что не пытайтесь «оптимизировать» свой список из 200 целых чисел, добавляя к нему 1. В таком случае простая карта будет лучше.
В общем, это было просто упражнение по использованию сопрограмм и ядер моего компьютера. Я почти уверен, что что-то напутал, и не все по kotlin feng-shui, но идея ясна, что хитрая хитрая тактика сопрограмм вы можете использовать свою лень.
Для любопытных: мы можем делать такие трюки, не беспокоясь о параллелизме, потому что математика в игре. Если наши функции отображения являются чистыми функциями, мы можем выполнять отображение в любом желаемом порядке и делать это параллельно.