Сопоставьте арифметическую операцию с коллекцией Scala и суммируйте результат

Question

Вот код, которым я поделился со своей учебной группой вчера: https://gist.github.com/natemurthy/019e49e6f5f0d1be8719. После компиляции я запускаю map.scala со следующими параметрами кучи:

$ scala -J"-Xmx4G" map

и получите следующие результаты для 4 отдельных тестов:

// (1L to 20000000L).map(_*2)
(Map) multiplying 20 million elements by 2
(Reduce) sum: 400000020000000
Total MapReduce time: 7.562381

// (1L to 20000000L).toArray.map(_*2)
(Map) multiplying 20 million elements by 2
(Reduce) sum: 400000020000000
Total MapReduce time: 1.233997

// (1L to 20000000L).toVector.map(_*2)
(Map) multiplying 20 million elements by 2
(Reduce) sum: 400000020000000
Total MapReduce time: 15.041896 

// (1L to 20000000L).par.map(_*2)
(Map) multiplying 20 million elements by 2
(Reduce) sum: 400000020000000
Total MapReduce time: 18.586220

Я пытаюсь выяснить, почему эти результаты различаются для разных типов коллекций и, что более важно, почему производительность оказывается хуже для коллекций, которые должны интуитивно оцениваться быстрее. Любопытно услышать ваше понимание этих результатов. Я также экспериментировал с выполнением этих операций на Breeze и Saddle (которые работают намного лучше в тех же тестах), но я хочу посмотреть, насколько далеко я могу продвинуть встроенный API Scala Collections.

Эти тесты проводились на Asus Zenbook UX31A, двухъядерном процессоре Intel Core i7 3517U с частотой 1,9 ГГц и гиперпоточностью, 4 ГБ оперативной памяти и Ubuntu 12.04 Desktop. Использование Scala 2.11.1 с JDK 1.7

Answer 1

Здесь, очевидно, происходит много всего, но вот пара:

Во-первых, to метод создает RangeЭто очень эффективная структура данных, поскольку она фактически не создает коллекцию с 20 миллионами элементов. Он просто знает, как получить следующий элемент во время итерации. Когда вы звоните map на Rangeвыходной Vector, поэтому он перебирает Range (дешево), умножает каждое число на 2 (все еще дешево), но затем должен создать Vector (дорого; я думаю, около 7,5 секунд).

Во-вторых, когда вы звоните .toVector на Range, он должен на самом деле создать Vector и генерировать все эти 20 миллионов ценностей. Это занимает время (опять же 7,5 секунды). Когда вы звоните map, он перебирает Вектор (дешево), умножает каждое число на 2 (все еще дешево), но затем должен создать новый Vector за результат (дорого). Итак, вы выполнили те же операции, но на этот раз создали два новых вектора по 20 миллионов элементов. (7,5*2=15 секунд.)

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

Наконец, .par позвонить на Range производит ParRange, Результат map это ParVectorтак что стоит создать этот объект и поместить в него 20 миллионов элементов. Когда вы звоните .map он создает потоки для выполнения расчетов. Тем не менее, операция, которую вы отображаете, очень быстрая, поэтому нет смысла делать это параллельно. Вы тратите гораздо больше времени на обработку параллелизации, чем на самом деле вычисление умножений.

Подумай об этом так. Если бы вы хотели сделать эту операцию в реальной жизни, вы бы собрали кучу друзей в свои темы. Тогда вам придется разделить свои 20 миллионов чисел и дать каждому другу несколько умножений. Тогда ваш друг умножит каждое число на 2 и даст, вернет удвоенные числа и будет ждать, когда вы раздадите следующий набор чисел. Затем вам нужно будет ввести каждое умноженное число в новую таблицу. Но задача умножения числа на 2 настолько быстрая, что вы могли бы просто сделать это самостоятельно за меньшее время, чем потребовалось вам, чтобы собраться с друзьями и передавать сообщения туда и обратно. Более того, если у вас есть только два ядра, это не место для распараллеливания, так что одновременно работают только пара потоков, и ваше соотношение накладных расходов к работе не очень хорошее.