为什么 max() 有时在相同长度的序列上会快很多?
How can max() sometimes be a lot faster on a sequence of the same length?
我问这个问题只是为了更好地理解 kotlin 序列的工作原理。我以为我掌握得很好,但我无法用我所知道的来解释我在短期测试中观察到的东西,所以显然我在某处有误解。
我的目标是做一个快速基准测试来比较列表与序列在过滤条件时的性能,然后取结果的最大值。这是一个在我拥有的某些代码中经常发生的操作,我正在尝试决定是否值得重写它以使用序列而不是列表。似乎是这样,因为序列始终更快,但这不是这里的问题。
相反,我想请你向我解释一下下面描述的 "artifact" 是如何发生的。
首先,这是我完整的测试 运行:
fun `just checking the performance of sequences`() {
val log = logger()
var totaldif = 0L
var seqFasterThanList = 0
(1..1000).forEach {
val testList = (1..6000000).toList().shuffled()
val testSequence = testList.asSequence()
// filter and find max
val listDuration = measureTimeMillis {
testList.filter { it % 2 == 0 }.max()
}
val sequenceDuration = measureTimeMillis {
testSequence.filter { it % 2 == 0 }.max()
}
log.info("List: {} ms; Sequence: {} ms;", listDuration, sequenceDuration)
if (sequenceDuration < listDuration) {
seqFasterThanList++
totaldif += (listDuration - sequenceDuration)
}
}
log.info("sequence was faster {} out of 1000 runs. average difference: {} ms",
seqFasterThanList, totaldif / seqFasterThanList)
}
结果大多是这样的:
List: 299 ms; Sequence: 217 ms;
List: 289 ms; Sequence: 211 ms;
List: 288 ms; Sequence: 220 ms;
除了每隔一段时间,大约每 20 个中有 1 个,结果看起来更像这样:
List: 380 ms; Sequence: 63 ms
如您所见,在这些情况下,操作要快得多。这是我对 find 或 first 等操作所期望的行为,一旦找到匹配项,它们就可以提前终止。但就其本质而言,max has 遍历整个序列以 gua运行tee 结果。那么,在遍历相同数量的元素的情况下,有时它能以比通常要求快 3 倍以上的速度找到结果,这怎么可能呢?
下面是我的原始答案,正如@Slaw 指出的那样,它实际上并没有回答你的问题(它解释了为什么 Sequence.filter
比 Iterable.filter
快,而不是为什么 Sequence.filter
似乎间歇性地比平时快)。但是,我将它留在下面,因为它与我认为可能是您实际问题的答案有关。
我猜这可能与垃圾收集有关。正如您从我的原始答案中看到的那样,当您调用 Iterable.filter
时,您会导致复制大量数组,即您将大量内容放入内存中,必须在某些点进行清理。我想知道是否是由 List
测试创建的内存中的东西清理,这实际上导致了异常。我认为可能发生的情况是垃圾收集器每隔一段时间就会启动并进行一次完整收集:这导致 List
测试速度比正常情况慢。在此运行之后,内存将全部清理干净,这可能就是 Sequence
测试当时更快的原因。
我怀疑它与垃圾收集有关的原因是因为我复制了你的异常情况,然后做了一个改变:我调用 testList.filterTo
而不是调用 testList.filter
,传入 ArrayList
] 与列表大小相同。这意味着不必进行数组复制,而且 ArrayList
的创建现在不在时间范围内:
val arrayList = ArrayList<Int>(testList.size)
val listDuration = measureTimeMillis {
testList.filterTo(arrayList) { it % 2 == 0 }.max()
}
我一这样做,异常就消失了。也许您可以检查您的系统,看看这是否也会使异常消失。它是断断续续的,所以有点难以确定。
当然,这并不能证明它是垃圾回收,但我认为它可能是罪魁祸首。您可以打开 GC 日志记录以查看您是否想确定地知道。如果您这样做了,请告诉我们您的发现:听到您的结果会很有趣。
下面的原始答案(解释为什么 Iterable.filter
比 Sequence.filter
慢)
如果您查看 Iterable<T>.filter
的源代码,您会发现它是这样做的:
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
return filterTo(ArrayList<T>(), predicate)
}
它创建一个新的 ArrayList
然后循环项目,检查每个项目的谓词,如果它们与谓词匹配,则将它们添加到该数组列表中。这意味着每 X 个项目(无论数组列表的默认大小是多少),数组列表必须调整自身的大小以允许更多项目进入(即创建一个新的底层数组副本,它存储所有数据)。
然而,在一个序列中,代码是不同的:
public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
return FilteringSequence(this, true, predicate)
}
这里没有存储所有项目的底层数组,因此不必进行数组复制。相反,只有一个 Iterator
会 return 每当调用 next
时匹配谓词的下一个项目。
您可以在 FilteringSequence
class:
中查看其实现方式的详细信息
internal class FilteringSequence<T>(
private val sequence: Sequence<T>,
private val sendWhen: Boolean = true,
private val predicate: (T) -> Boolean
) : Sequence<T> {
override fun iterator(): Iterator<T> = object : Iterator<T> {
val iterator = sequence.iterator()
var nextState: Int = -1 // -1 for unknown, 0 for done, 1 for continue
var nextItem: T? = null
private fun calcNext() {
while (iterator.hasNext()) {
val item = iterator.next()
if (predicate(item) == sendWhen) {
nextItem = item
nextState = 1
return
}
}
nextState = 0
}
override fun next(): T {
if (nextState == -1)
calcNext()
if (nextState == 0)
throw NoSuchElementException()
val result = nextItem
nextItem = null
nextState = -1
@Suppress("UNCHECKED_CAST")
return result as T
}
我问这个问题只是为了更好地理解 kotlin 序列的工作原理。我以为我掌握得很好,但我无法用我所知道的来解释我在短期测试中观察到的东西,所以显然我在某处有误解。
我的目标是做一个快速基准测试来比较列表与序列在过滤条件时的性能,然后取结果的最大值。这是一个在我拥有的某些代码中经常发生的操作,我正在尝试决定是否值得重写它以使用序列而不是列表。似乎是这样,因为序列始终更快,但这不是这里的问题。
相反,我想请你向我解释一下下面描述的 "artifact" 是如何发生的。
首先,这是我完整的测试 运行:
fun `just checking the performance of sequences`() {
val log = logger()
var totaldif = 0L
var seqFasterThanList = 0
(1..1000).forEach {
val testList = (1..6000000).toList().shuffled()
val testSequence = testList.asSequence()
// filter and find max
val listDuration = measureTimeMillis {
testList.filter { it % 2 == 0 }.max()
}
val sequenceDuration = measureTimeMillis {
testSequence.filter { it % 2 == 0 }.max()
}
log.info("List: {} ms; Sequence: {} ms;", listDuration, sequenceDuration)
if (sequenceDuration < listDuration) {
seqFasterThanList++
totaldif += (listDuration - sequenceDuration)
}
}
log.info("sequence was faster {} out of 1000 runs. average difference: {} ms",
seqFasterThanList, totaldif / seqFasterThanList)
}
结果大多是这样的:
List: 299 ms; Sequence: 217 ms;
List: 289 ms; Sequence: 211 ms;
List: 288 ms; Sequence: 220 ms;
除了每隔一段时间,大约每 20 个中有 1 个,结果看起来更像这样:
List: 380 ms; Sequence: 63 ms
如您所见,在这些情况下,操作要快得多。这是我对 find 或 first 等操作所期望的行为,一旦找到匹配项,它们就可以提前终止。但就其本质而言,max has 遍历整个序列以 gua运行tee 结果。那么,在遍历相同数量的元素的情况下,有时它能以比通常要求快 3 倍以上的速度找到结果,这怎么可能呢?
下面是我的原始答案,正如@Slaw 指出的那样,它实际上并没有回答你的问题(它解释了为什么 Sequence.filter
比 Iterable.filter
快,而不是为什么 Sequence.filter
似乎间歇性地比平时快)。但是,我将它留在下面,因为它与我认为可能是您实际问题的答案有关。
我猜这可能与垃圾收集有关。正如您从我的原始答案中看到的那样,当您调用 Iterable.filter
时,您会导致复制大量数组,即您将大量内容放入内存中,必须在某些点进行清理。我想知道是否是由 List
测试创建的内存中的东西清理,这实际上导致了异常。我认为可能发生的情况是垃圾收集器每隔一段时间就会启动并进行一次完整收集:这导致 List
测试速度比正常情况慢。在此运行之后,内存将全部清理干净,这可能就是 Sequence
测试当时更快的原因。
我怀疑它与垃圾收集有关的原因是因为我复制了你的异常情况,然后做了一个改变:我调用 testList.filterTo
而不是调用 testList.filter
,传入 ArrayList
] 与列表大小相同。这意味着不必进行数组复制,而且 ArrayList
的创建现在不在时间范围内:
val arrayList = ArrayList<Int>(testList.size)
val listDuration = measureTimeMillis {
testList.filterTo(arrayList) { it % 2 == 0 }.max()
}
我一这样做,异常就消失了。也许您可以检查您的系统,看看这是否也会使异常消失。它是断断续续的,所以有点难以确定。
当然,这并不能证明它是垃圾回收,但我认为它可能是罪魁祸首。您可以打开 GC 日志记录以查看您是否想确定地知道。如果您这样做了,请告诉我们您的发现:听到您的结果会很有趣。
下面的原始答案(解释为什么 Iterable.filter
比 Sequence.filter
慢)
如果您查看 Iterable<T>.filter
的源代码,您会发现它是这样做的:
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
return filterTo(ArrayList<T>(), predicate)
}
它创建一个新的 ArrayList
然后循环项目,检查每个项目的谓词,如果它们与谓词匹配,则将它们添加到该数组列表中。这意味着每 X 个项目(无论数组列表的默认大小是多少),数组列表必须调整自身的大小以允许更多项目进入(即创建一个新的底层数组副本,它存储所有数据)。
然而,在一个序列中,代码是不同的:
public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
return FilteringSequence(this, true, predicate)
}
这里没有存储所有项目的底层数组,因此不必进行数组复制。相反,只有一个 Iterator
会 return 每当调用 next
时匹配谓词的下一个项目。
您可以在 FilteringSequence
class:
internal class FilteringSequence<T>(
private val sequence: Sequence<T>,
private val sendWhen: Boolean = true,
private val predicate: (T) -> Boolean
) : Sequence<T> {
override fun iterator(): Iterator<T> = object : Iterator<T> {
val iterator = sequence.iterator()
var nextState: Int = -1 // -1 for unknown, 0 for done, 1 for continue
var nextItem: T? = null
private fun calcNext() {
while (iterator.hasNext()) {
val item = iterator.next()
if (predicate(item) == sendWhen) {
nextItem = item
nextState = 1
return
}
}
nextState = 0
}
override fun next(): T {
if (nextState == -1)
calcNext()
if (nextState == 0)
throw NoSuchElementException()
val result = nextItem
nextItem = null
nextState = -1
@Suppress("UNCHECKED_CAST")
return result as T
}