Блог

Я запустил набор тестов производительности для 10 000 000 элементов и обнаружил, что результаты сильно различаются в каждой реализации.

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

Создайте 10 000 000 элементов и распечатайте те, которые состоят из модулей по 1 000 000. Размер JVM всегда устанавливается одинаковым минимальным и максимальным: -Xms?m -Xmx?m

 import java.util.concurrent.TimeUnit
import java.util.concurrent.TimeUnit._

object LightAndFastRange extends App {

def chrono[A](f: => A, timeUnit: TimeUnit = MILLISECONDS): (A,Long) = {
  val start = System.nanoTime()
  val result: A = f
  val end = System.nanoTime()
  (result, timeUnit.convert(end-start, NANOSECONDS))
}

  def millions(): List[Int] =  (0 to 10000000).filter(_ % 1000000 == 0).toList

  val results = chrono(millions())
  results._1.foreach(x => println ("x: "   x))
  println("Time: "   results._2);
}
  

Это занимает 141 миллисекунду при размере JVM 27m

Для сравнения, преобразование в список значительно влияет на производительность:

 import java.util.concurrent.TimeUnit
import java.util.concurrent.TimeUnit._

object LargeLinkedList extends App {
  def chrono[A](f: => A, timeUnit: TimeUnit = MILLISECONDS): (A,Long) = {
  val start = System.nanoTime()
  val result: A = f
  val end = System.nanoTime()
  (result, timeUnit.convert(end-start, NANOSECONDS))
}

  val results = chrono((0 to 10000000).toList.filter(_ % 1000000 == 0))
  results._1.foreach(x => println ("x: "   x))
  println("Time: "   results._2)
}
  

Это занимает 8514-10896 мс при 460-455 м

В отличие от этого, эта реализация Java использует массив примитивов

 import static java.util.concurrent.TimeUnit.*;

public class LargePrimitiveArray {

    public static void main(String[] args){
            long start = System.nanoTime();
            int[] elements = new int[10000000];
            for(int i = 0; i < 10000000; i  ){
                    elements[i] = i;
            }
            for(int i = 0; i < 10000000; i  ){
                    if(elements[i] % 1000000 == 0) {
                            System.out.println("x: "   elements[i]);
                    }
            }
            long end = System.nanoTime();
            System.out.println("Time: "   MILLISECONDS.convert(end-start, NANOSECONDS));
    }
}
  

Требуется 116 мс при размере JVM 59m

Java список целых чисел

 import java.util.List;
import java.util.ArrayList;
import static java.util.concurrent.TimeUnit.*;

public class LargeArrayList {

    public static void main(String[] args){
            long start = System.nanoTime();
            List<Integer> elements = new ArrayList<Integer>();
            for(int i = 0; i < 10000000; i  ){
                    elements.add(i);
            }
            for(Integer x: elements){
                    if(x % 1000000 == 0) {
                            System.out.println("x: "   x);
                    }
            }
            long end = System.nanoTime();
            System.out.println("Time: "   MILLISECONDS.convert(end-start, NANOSECONDS));
    }
  

}

It takes 3993 ms with JVM size of 283m

My question is, why is the first example so performant, while the second is so badly affected. I tried creating views, but wasn’t successful at reproducing the performance benefits of the range.

All tests running on Mac OS X Snow Leopard,
Java 6u26 64-Bit Server
Scala 2.9.1.final

EDIT:

для завершения приведем фактическую реализацию с использованием LinkedList (что является более справедливым сравнением с точки зрения пространства, чем ArrayList, поскольку, как справедливо указано, списки scala связаны)

 import java.util.List;
import java.util.LinkedList;
import static java.util.concurrent.TimeUnit.*;

public class LargeLinkedList {

    public static void main(String[] args){
            LargeLinkedList test = new LargeLinkedList();
            long start = System.nanoTime();
            List<Integer> elements = test.createElements();
            test.findElementsToPrint(elements);
            long end = System.nanoTime();
            System.out.println("Time: "   MILLISECONDS.convert(end-start, NANOSECONDS));
    }

    private List<Integer> createElements(){
            List<Integer> elements = new LinkedList<Integer>();
            for(int i = 0; i < 10000000; i  ){
                    elements.add(i);
            }
            return elements;
    }

    private void findElementsToPrint(List<Integer> elements){
            for(Integer x: elements){
                    if(x % 1000000 == 0) {
                            System.out.println("x: "   x);
                    }
            }
    }

}
  

Занимает 3621-6749 мс при 480-460 Мбит/с. Это намного больше соответствует производительности второго примера scala.

наконец, LargeArrayBuffer

 import collection.mutable.ArrayBuffer
import java.util.concurrent.TimeUnit
import java.util.concurrent.TimeUnit._

object LargeArrayBuffer extends App {

 def chrono[A](f: => A, timeUnit: TimeUnit = MILLISECONDS): (A,Long) = {
  val start = System.nanoTime()
  val result: A = f
  val end = System.nanoTime()
  (result, timeUnit.convert(end-start, NANOSECONDS))
 }

 def millions(): List[Int] = {
    val size = 10000000
    var items = new ArrayBuffer[Int](size)
    (0 to size).foreach (items  = _)
    items.filter(_ % 1000000 == 0).toList
 }

 val results = chrono(millions())
  results._1.foreach(x => println ("x: "   x))
  println("Time: "   results._2);
 }
  

Занимает около 2145 мс и 375 Мб

Большое спасибо за ответы.

О, здесь так много всего происходит!!!

Давайте начнем с Java int[] . Массивы в Java — это единственная коллекция, в которой не стирается тип. Представление an во время выполнения int[] отличается от представления во время выполнения Object[] тем, что оно фактически использует int напрямую. Из-за этого при его использовании нет необходимости в боксе.

С точки зрения памяти, у вас есть 40.000.000 последовательных байт в памяти, которые считываются и записываются по 4 за раз, когда элемент считывается или записывается.

В отличие от этого, ArrayList<Integer> — как и практически любая другая универсальная коллекция — состоит из 40.000.000 или 80.000.00 последовательных байт (в 32 и 64-битной JVM соответственно), плюс 80.000.000 байт, распределенных по всей памяти группами по 8 байт. Каждое чтение и запись в элемент должны проходить через два пространства памяти, и время, затрачиваемое на обработку всей этой памяти, является значительным, когда фактическая задача, которую вы выполняете, выполняется так быстро.

Итак, вернемся ко второму примеру Scala, где вы манипулируете List . Теперь Scala List гораздо больше похожа на Java LinkedList , чем на сильно искаженное название ArrayList . Каждый элемент a List состоит из объекта с именем Cons , который имеет 16 байт, с указателем на элемент и указателем на другой список. Таким образом, List из 10.000.000 элементов состоит из 160.000.000 элементов, распределенных по всей памяти группами по 16 байт, плюс 80.000.000 байт, распределенных по всей памяти группами по 8 байт. Итак, то, что было верно для ArrayList , еще более верно для List

Наконец, Range . Range — это последовательность целых чисел с нижней и верхней границами плюс шаг. Range 10.000.000 элементов составляют 40 байт: три целых числа (не общие) для нижней и верхней границ и шага, плюс несколько предварительно вычисленных значений ( last , numRangeElements ) и два других целых числа, используемых для lazy val потокобезопасности. Просто чтобы прояснить, это НЕ в 40 раз больше 10.000.000: всего 40 байт. Размер диапазона совершенно не имеет значения, потому что В НЕМ НЕ ХРАНЯТСЯ ОТДЕЛЬНЫЕ ЭЛЕМЕНТЫ. Только нижняя граница, верхняя граница и шаг.

Теперь, поскольку a Range является Seq[Int] , для большинства применений ему все равно придется проходить боксирование: int будет преобразован в Integer , а затем снова в int , что, к сожалению, расточительно.

Вычисление размера минусов

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

1. Java использует 8 байт для обычных объектов и 12 для массивов объектов, для «домашней» информации (какой класс этого объекта и т.д.).
2. Объекты распределяются в виде блоков по 8 байт. Если ваш объект меньше этого, он будет дополнен, чтобы дополнить его.

На самом деле я думал, что это 16 байт, а не 8. Во всяком случае, Минусов тоже меньше, чем я думал. Его поля являются:

 public static final long serialVersionUID; // static, doesn't count
private java.lang.Object scala$collection$immutable$$colon$colon$$hd;
private scala.collection.immutable.List tl;
  

Ссылки имеют размер не менее 4 байт (может быть больше в 64-битной JVM). Итак, у нас есть:

 8 bytes Java header
4 bytes hd
4 bytes tl
  

Что делает его длиной всего 16 байт. На самом деле, довольно неплохо. В приведенном примере hd будет указывать на Integer объект, который, как я предполагаю, имеет длину 8 байт. Что касается tl , то это указывает на еще одни минусы, которые мы уже подсчитываем.

Я собираюсь пересмотреть оценки, добавив, по возможности, фактические данные.

В первом примере вы создаете связанный список из 10 элементов, вычисляя шаги диапазона.

Во втором примере вы создаете связанный список с 10 миллионами элементов и фильтруете его до нового связанного списка с 10 элементами.

В третьем примере вы создаете буфер с поддержкой массива с 10 миллионами элементов, которые вы просматриваете и печатаете, новый буфер с поддержкой массива не создается.

Заключение:

Каждый фрагмент кода выполняет что-то свое, вот почему производительность сильно варьируется.

Это обоснованное предположение…

Я думаю, это потому, что в быстрой версии компилятор Scala способен преобразовать оператор key во что-то вроде этого (на Java):

 List<Integer> millions = new ArrayList<Integer>();
for (int i = 0; i <= 10000000; i  ) {
    if (i % 1000000 == 0) {
        millions.add(i);
    }
}
  

Как вы можете видеть, (0 to 10000000) не генерирует промежуточный список из 10 000 000 Integer объектов.

В отличие от этого, в медленной версии компилятор Scala не способен выполнить такую оптимизацию и генерирует этот список.

(Промежуточной структурой данных может быть int[] , но наблюдаемый размер JVM предполагает, что это не так.)

Трудно прочитать исходный код Scala на моем iPad, но похоже, что Range конструктор на самом деле не создает список, а просто запоминает начало, приращение и конец. Он использует их для получения своих значений по запросу, так что итерация по диапазону намного ближе к простому циклу for, чем проверка элементов массива.

Как только вы говорите, range.toList вы заставляете Scala создавать связанный список «значений» в диапазоне (выделяя память как для значений, так и для ссылок), а затем вы повторяете это. Поскольку это связанный список, производительность этого будет хуже, чем в вашем примере Java ArrayList.