迭代器与 Java 8 流

Iterator versus Stream of Java 8

提问by Miguel Gamboa

To take advantage of the wide range of query methods included in java.util.streamof Jdk 8 I am attempted to design domain models where getters of relationship with *multiplicity (with zero or more instances ) return a Stream<T>, instead of an Iterable<T>or Iterator<T>.

为了利用java.util.streamJdk 8 中包含的广泛查询方法，我尝试设计域模型，其中具有*多重性（具有零个或多个实例）的关系的 getter返回 a Stream<T>，而不是Iterable<T>or Iterator<T>。

My doubt is if there is any additional overhead incurred by the Stream<T>in comparison to the Iterator<T>?

我的疑问是Stream<T>，与Iterator<T>?

So, is there any disadvantage of compromising my domain model with a Stream<T>?

那么，使用Stream<T>.

Or instead, should I always return an Iterator<T>or Iterable<T>, and leave to the end-user the decision of choosing whether to use a stream, or not, by converting that iterator with the StreamUtils?

或者，我是否应该始终返回一个Iterator<T>or Iterable<T>，并通过将迭代器转换为StreamUtils?

Notethat returning a Collectionis not a valid option because in this case most of the relationships are lazy and with unknown size.

请注意，返回 aCollection不是有效选项，因为在这种情况下，大多数关系都是惰性的且大小未知。

回答by Brian Goetz

There's lots of performance advice here, but sadly much of it is guesswork, and little of it points to the real performance considerations.

这里有很多性能建议，但遗憾的是大部分都是猜测，很少指出真正的性能考虑。

@Holger gets it rightby pointing out that we should resist the seemingly overwhelming tendency to let the performance tail wag the API design dog.

@Holger说得对，指出我们应该抵制看似压倒性的趋势，让性能尾巴摇摆 API 设计狗。

While there are a zillion considerations that can make a stream slower than, the same as, or faster than some other form of traversal in any given case, there are some factors that point to streams haven a performance advantage where it counts -- on big data sets.

虽然在任何给定的情况下，有无数的考虑可以使流比其他形式的遍历慢、相同或快，但有一些因素表明流在它重要的地方具有性能优势——大数据集。

There is some additional fixed startup overhead of creatinga Streamcompared to creating an Iterator-- a few more objects before you start calculating. If your data set is large, it doesn't matter; it's a small startup cost amortized over a lot of computation. (And if your data set is small, it probably also doesn't matter -- because if your program is operating on small data sets, performance is generally not your #1 concern either.) Where this doesmatter is when going parallel; any time spent setting up the pipeline goes into the serial fraction of Amdahl's law; if you look at the implementation, we work hard to keep the object count down during stream setup, but I'd be happy to find ways to reduce it as that has a direct effect on the breakeven data set size where parallel starts to win over sequential.

与创建一个Stream相比，创建a有一些额外的固定启动开销Iterator——在开始计算之前多几个对象。如果你的数据集很大，那没关系；这是一个很小的启动成本，通过大量计算进行摊销。（如果你的数据集是小，这或许也并不重要-因为如果你的程序在小数据集运行，性能一般不是你的＃1关心无论是。）凡本不重要的是何时并行；建立管道所花费的任何时间都属于阿姆达尔定律的连续部分；如果您查看实现，我们会努力在流设置期间保持对象计数下降，但我很乐意找到减少它的方法，因为这对并行开始获胜的盈亏平衡数据集大小有直接影响顺序的。

But, more important than the fixed startup cost is the per-element access cost. Here, streams actually win -- and often win big -- which some may find surprising. (In our performance tests, we routinely see stream pipelines which can outperform their for-loop over Collectioncounterparts.) And, there's a simple explanation for this: Spliteratorhas fundamentally lower per-element access costs than Iterator, even sequentially. There are several reasons for this.

但是，比固定启动成本更重要的是每个元素的访问成本。在这里，流实际上赢了——而且经常赢大——有些人可能会感到惊讶。（在我们的性能测试中，我们经常看到流管道的性能优于对应的 for 循环Collection。）而且，对此有一个简单的解释：Spliterator从根本上说，每个元素的访问成本低于Iterator，甚至顺序访问成本。有几个原因。

1. The Iterator protocol is fundamentally less efficient. It requires calling two methods to get each element. Further, because Iterators must be robust to things like calling next()without hasNext(), or hasNext()multiple times without next(), both of these methods generally have to do some defensive coding (and generally more statefulness and branching), which adds to inefficiency. On the other hand, even the slow way to traverse a spliterator (tryAdvance) doesn't have this burden. (It's even worse for concurrent data structures, because the next/hasNextduality is fundamentally racy, and Iteratorimplementations have to do more work to defend against concurrent modifications than do Spliteratorimplementations.)

2. Spliteratorfurther offers a "fast-path" iteration -- forEachRemaining-- which can be used most of the time (reduction, forEach), further reducing the overhead of the iteration code that mediates access to the data structure internals. This also tends to inline very well, which in turn increases the effectiveness of other optimizations such as code motion, bounds check elimination, etc.

3. Further, traversal via Spliteratortend to have many fewer heap writes than with Iterator. With Iterator, every element causes one or more heap writes (unless the Iteratorcan be scalarized via escape analysis and its fields hoisted into registers.) Among other issues, this causes GC card mark activity, leading to cache line contention for the card marks. On the other hand, Spliteratorstend to have less state, and industrial-strength forEachRemainingimplementations tend to defer writing anything to the heap until the end of the traversal, instead storing its iteration state in locals which naturally map to registers, resulting in reduced memory bus activity.

1. Iterator 协议从根本上来说效率较低。它需要调用两个方法来获取每个元素。此外，由于迭代器必须对诸如next()不带调用hasNext()或hasNext()多次不带 之类的事情具有鲁棒性next()，这两种方法通常都必须进行一些防御性编码（并且通常更多的状态和分支），这增加了低效率。另一方面，即使是遍历 spliterator ( tryAdvance)的缓慢方法也没有这种负担。（对于并发数据结构来说更糟糕，因为next/hasNext对偶性从根本上来说是活泼的，并且Iterator实现必须比实现做更多的工作来防御并发修改Spliterator。）

2. Spliterator进一步提供了一个“快速路径”迭代——forEachRemaining它可以在大部分时间使用（reduction，forEach），进一步减少迭代代码的开销，它调解对数据结构内部的访问。这也往往很好地内联，这反过来又提高了其他优化的有效性，例如代码移动、边界检查消除等。

3. 此外，遍历 viaSpliterator的堆写入往往比 with 少得多Iterator。使用 时Iterator，每个元素都会导致一个或多个堆写入（除非Iterator可以通过转义分析对其进行标化并将其字段提升到寄存器中。）除其他问题外，这会导致 GC 卡标记活动，导致卡标记的缓存行争用。另一方面，Spliterators往往具有较少的状态，并且工业强度的forEachRemaining实现倾向于将任何内容写入堆直到遍历结束，而不是将其迭代状态存储在自然映射到寄存器的局部变量中，从而导致内存总线活动减少.

Summary: don't worry, be happy. Spliteratoris a better Iterator, even without parallelism. (They're also generally just easier to write and harder to get wrong.)

总结：别着急，开心就好。 Spliterator是更好的Iterator，即使没有并行性。 （它们通常也更容易编写并且更难出错。）

回答by Holger

Let's compare the common operation of iterating over all elements, assuming that the source is an ArrayList. Then, there are three standard ways to achieve this:

让我们比较一下遍历所有元素的常见操作，假设源是一个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.forEachwhich will end up calling 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;
  }
  

• 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;
  }
  

As you can see, the inner loop of the implementation code, where these operations end up, is basically the same, iterating over indices and directly reading the array and passing the element to the Consumer.

如您所见，这些操作结束的实现代码的内部循环基本相同，遍历索引并直接读取数组并将元素传递给Consumer.

Similar things apply to all standard collections of the JRE, all of them have adapted implementations for all ways to do it, even if you are using a read-only wrapper. In the latter case, the StreamAPI would even slightly win, Collection.forEachhas to be called on the read-only view in order to delegate to the original collection's forEach. Similarly, the iterator has to be wrapped to protect against attempts to invoke the remove()method. In contrast, spliterator()can directly return the original collection's Spliteratoras it has no modification support. Thus, the stream of a read-only view is exactly the same as the stream of the original collection.

类似的事情适用于 JRE 的所有标准集合，即使您使用的是只读包装器，它们也都具有适用于所有方法的适应实现。在后一种情况下，StreamAPI 甚至会稍微胜出，Collection.forEach必须在只读视图上调用才能委托给原始集合的forEach. 同样，必须包装迭代器以防止尝试调用该remove()方法。相比之下，spliterator()可以直接返回原始集合的，Spliterator因为它不支持修改。因此，只读视图的流与原始集合的流完全相同。

Though all these differences are hardly to notice when measuring real life performance as, as said, the inner loop, which is the most performance relevant thing, is the same in all cases.

尽管在测量现实生活中的性能时很难注意到所有这些差异，因为如上所述，与性能最相关的内循环在所有情况下都是相同的。

The question is which conclusion to draw from that. You still can return a read-only wrapper view to the original collection, as the caller still may invoke stream().forEach(…)to directly iterate in the context of the original collection.

问题是从中得出什么结论。您仍然可以将只读包装视图返回到原始集合，因为调用者仍然可以调用stream().forEach(…)以直接在原始集合的上下文中进行迭代。

Since the performance isn't really different, you should rather focus on the higher level design like discussed in “Should I return a Collection or a Stream?”

由于性能并没有真正不同，您应该更关注更高级别的设计，如“我应该返回集合还是流？”中讨论的那样。