Итератор против потока Java 8

Ответ 1

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

@Holger правильно понял, указав, что мы должны противостоять, казалось бы, подавляющей тенденции позволить игровому хвосту петь собаку дизайна API.

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

Есть некоторые дополнительные фиксированные накладные расходы на запуск при создании Stream по сравнению с созданием Iterator - еще нескольких объектов, прежде чем вы начнете вычислять. Если ваш набор данных большой, это не имеет значения; это небольшая стартовая стоимость, амортизированная по множеству вычислений. (И если ваш набор данных невелик, это, вероятно, также не имеет значения, потому что, если ваша программа работает с небольшими наборами данных, производительность, как правило, не относится к вашей проблеме №1.) Если это имеет значение, когда вы собираетесь параллельно; любое время, потраченное на создание трубопровода, переходит в серийную фракцию закона Амдала; если вы посмотрите на реализации, мы упорно работаем, чтобы подсчитать объект во время настройки потока, но я был бы рад, чтобы найти способы, чтобы уменьшить его, как и оказывает непосредственное влияние на безубыточность набора данных размера, где параллельно начинает победу над последовательный.

Но более важным, чем фиксированная стоимость запуска, является стоимость доступа к каждому элементу. Здесь потоки фактически выигрывают - и часто выигрывают большие, которые некоторые могут удивить. (В наших тестах производительности мы обычно видим потоковые конвейеры, которые могут превзойти их for-loop над аналогами Collection.) И для этого есть простое объяснение: Spliterator имеет принципиально более низкие затраты на доступ к элементам, чем Iterator, даже последовательно. На это есть несколько причин.

• Протокол Iterator существенно менее эффективен. Это требует вызова двух методов для получения каждого элемента. Кроме того, поскольку итераторы должны быть надежными для таких вещей, как вызов next() без hasNext(), или hasNext() несколько раз без next(), оба этих метода обычно должны выполнять некоторую защитную кодировку (и, как правило, более стойкую и разветвленную) что добавляет неэффективности. С другой стороны, даже медленный способ пересечения разделителя (tryAdvance) не имеет такого бремени. (Это еще хуже для параллельных структур данных, поскольку двойственность next/hasNext является фундаментальной, а реализации Iterator должны делать больше работы для защиты от одновременных изменений, чем реализации Spliterator.)

• Spliterator далее предлагает итерацию с быстрым ходом - forEachRemaining - которая может использоваться большую часть времени (сокращение, для каждого), что дополнительно уменьшает накладные расходы итерационного кода, который обеспечивает доступ к доступу к внутренним структурам данных. Это также имеет тенденцию очень хорошо встраиваться, что, в свою очередь, повышает эффективность других оптимизаций, таких как движение кода, устранение ограничений по границам и т.д.

• Кроме того, обход через Spliterator имеет тенденцию иметь гораздо меньше записей кучи, чем при Iterator. С помощью Iterator каждый элемент вызывает одну или несколько записей кучи (если только Iterator не может быть сканирован с помощью анализа эвакуации, а его поля подняты в регистры.) Среди других проблем это вызывает активность маркеров GC-карты, что приводит к конкуренции в строке кэша для карты. С другой стороны, Spliterators имеют тенденцию к меньшему состоянию, а реализации индустриальной прочности forEachRemaining имеют тенденцию откладывать записывать что-либо в кучу до конца обхода, вместо этого сохраняя свое итерационное состояние в локалях, которые, естественно, сопоставляются с регистрами, что приводит к снижению активности шины памяти.

Резюме: не беспокойтесь, будьте счастливы. Spliterator лучше Iterator, даже без parallelism. (Их вообще просто легче писать и сложнее ошибиться.)

Ответ 2

Давайте сравним общую операцию итерации по всем элементам, считая, что источник является ArrayList. Тогда есть три стандартных способа достижения этого:

• Collection.forEach

  final E[] elementData = (E[]) this.elementData;
  final int size = this.size;
  for (int i=0; modCount == expectedModCount && i < size; i++) {
      action.accept(elementData[i]);
  }
  

• Iterator.forEachRemaining

  final Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length) {
      throw new ConcurrentModificationException();
  }
  while (i != size && modCount == expectedModCount) {
      consumer.accept((E) elementData[i++]);
  }
  

• Stream.forEach, который в конечном итоге вызовет Spliterator.forEachRemaining

  if ((i = index) >= 0 && (index = hi) <= a.length) {
     for (; i < hi; ++i) {
         @SuppressWarnings("unchecked") E e = (E) a[i];
         action.accept(e);
     }
     if (lst.modCount == mc)
         return;
  }
  

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

Подобные вещи применимы ко всем стандартным наборам JRE, все они адаптировали реализации для всех способов сделать это, даже если вы используете обертку только для чтения. В последнем случае API Stream даже слегка выиграет, Collection.forEach должен быть вызван в режиме только для чтения, чтобы делегировать исходные коллекции forEach. Аналогично, итератор должен быть завернут для защиты от попыток вызова метода remove(). Напротив, spliterator() может напрямую возвращать исходные коллекции Spliterator, поскольку он не поддерживает модификацию. Таким образом, поток представления только для чтения точно такой же, как поток исходной коллекции.

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

Вопрос заключается в том, какой вывод сделать из этого. Вы все еще можете вернуть представление обертки только для чтения в исходную коллекцию, поскольку вызывающий объект все еще может вызывать stream().forEach(…) для прямой итерации в контексте исходной коллекции.

Так как производительность не совсем по-другому, вам следует сосредоточиться на дизайне более высокого уровня, как обсуждалось в "Должен ли я возвращать коллекцию или поток?"