与直接"IEnumerable <T>"实现相比,具有while与for-do理解的序列的性能
Abe*_*bel 15 performance ienumerable f# seq
(对不起,很长的帖子,直接跳到问题,见底部)
(更新:如果您正在重新访问,请参阅标记为"更新"的部分;)
我让自己更好地了解F#序列引擎盖下发生了什么.我需要优化的任务包括将字符串转换为Unicode代码点序列,我想知道是否可以在不牺牲太多性能的情况下将我们使用的可变循环替换为不可变循环.
其中一个挑战是返回的序列与输入序列的长度不同,因为代理对一起返回一个整数.这是原始代码,如下所示:
let stocp0(value: string) : seq<int> =
let pos = ref 0
seq {
while !position < value.Length do
let c = System.Char.ConvertToUtf32(value, !pos)
pos := !position + if c >= 0x10000 then 2 else 1
yield c
}
尝试1: for-do
我认为最简单的方法是将其转换为for-do循环(不是for-for-do循环,它们有太多的额外开销):
let inline stocp1(value: string) =
seq {
for i = 0 to value.Length - 1 do
if(not <| Char.IsLowSurrogate(value.[i]))
then yield Char.ConvertToUtf32(value, i)
}
这比上面的可变对应物慢了3.2倍.比我想象的更高的因素.
尝试2: Seq.mapi
由于字符串已经是一个序列(好的,有一个IEnumerable<char>包装器)我想用它来Seq模块中的现有序列函数,希望这可能会带来更好的性能:
let inline stocp2(value: string) =
value
|> Seq.mapi (fun i c ->
if(Char.IsLowSurrogate(c)) then 0
else Char.ConvertToUtf32(value, i))
|> Seq.filter ((<>) 0)
它的速度慢了3.5倍.
奇怪的是,如果我替换value用value.AsEnumerable(),它的性能比显著快stocp1:3.0的因素.
经过几次测试后,我发现每个都|>创建了一个新IEnumerable<T>层,包含所有链接操作(这也可以在FSharp源代码中观察到Seq).但开销的规模让我感到惊讶.由于以上都没有与原始版本具有远程相同的性能,因此我决定尝试防止额外的序列开销,并创建一个Seq.mapiAndFilter函数来同时执行两个操作.
尝试3: Seq.mapiAndFilter
因为它是如此精致的循环,我只需要过滤当前字符并根据当前位置返回,也许我可以删除所涉及的额外步骤Seq.mapi,这看起来很昂贵.
为此,我需要模仿现有Seq.xxx函数的行为,我的第一次尝试是使用while-yield循环来实现.这将与最初的可变方法最接近,但会增加一层IEnumerable<T>开销.
我编写了以下函数,它接受一个返回布尔值的函数,如果为true,则将第二个函数应用于当前元素的位置.
let inline mapiAndFilter f g (e: seq<_>) : seq<_> =
let position = ref -1
let e = e.GetEnumerator()
seq {
while e.MoveNext() do
position := !position + 1
if f e.Current then yield g !position
}
// and the application of it:
let inline stocp3(value: string) =
value.AsEnumerable()
|> mapiAndFilter (not << Char.IsLowSurrogate) (fun i -> Char.ConvertToUtf32 (value, i))
结果比以前的尝试要好得多,它的性能是可变解决方案性能的1.5倍.然而,仍然令人失望地缓慢,这似乎意味着在紧密循环中,调查员增加的开销约为50%.
尝试4:改进 Seq.mapiAndFilter
为了弄清楚幕后发生了什么,我决定明确地编写可枚举类型,这应该让我有机会找出FSharp库中添加的任何样板检查是否与低性能特征有关.
如果没有安全保护FSharp Seq函数在内部使用(在非法使用Current等时引发错误),我想出了这个:
let mapiAndFilter f g (e : seq<'a>) : seq<'b> =
let i = ref -1
let e = e.GetEnumerator()
let inline getEnum() = {
new IEnumerator<'b> with
member x.Current = g !i
interface System.Collections.IEnumerator with
member x.Current = box <| g !i
member x.MoveNext() =
let rec next() =
i := !i + 1
e.MoveNext() && (f e.Current || next())
next()
member x.Reset() = noReset()
interface System.IDisposable with
member x.Dispose() = e.Dispose()
}
{
new System.Collections.Generic.IEnumerable<'b> with
member x.GetEnumerator() = getEnum()
interface System.Collections.IEnumerable with
member x.GetEnumerator() = getEnum() :> System.Collections.IEnumerator
}
// apply the same way as before:
let inline stocp4(value: string) =
value.AsEnumerable()
|> mapiAndFilter (not << Char.IsLowSurrogate) (fun i -> Char.ConvertToUtf32 (value, i))
这成了我们目前的赢家!它似乎比原始的可变功能慢了1.1倍.当然,它使用可变状态,但Seq.xxx内部所有函数也是如此.
绩效比较概述
关于上述所有尝试的一般说明:我也进行了测试ToCharArray(),它改善了中小输入的性能,但对大输入字符串尤其有害.当不是所有项目都需要枚举.许多其他的方法我离开了,因为他们的表现是如此糟糕得多(Seq.choose以上Seq.filter为多慢,Seq.collect很慢等等).
我使用以下内容进行性能比较(显然,这Seq.length是强制迭代的最快方法,Seq.last而且Seq.iter速度要慢得多):
let input = "ab\U0001ABCDcde\U0001ABCEfghi\U0001ABCF"
let run f = for i in 1 .. 1000000 do f input |> Seq.length |> ignore;;
run stocp1
// etc
结果:
Function CPU Factor
stocp0 0.296 1.0
stocp1 0.951 3.2
stocp2 1.029 3.5
stocp2' 0.873 3.0
stocp3 0.436 1.5
stocp4 0.327 1.1
stocp5 0.405 1.3 (latkin's answer, adj. with Array.toSeq)
stocp'是AsEnumerable()在将字符串传递给Seq.xxx函数之前在字符串上使用的版本.所有其他功能都已使用此功能.
我还测试了较长的和非常大的(50MB)弦,这是我们的典型用例,虽然时间在后续运行中不太稳定,但有效因素与上述大致相同.
更新:我添加了latkin的答案stocp5,但必须通过添加一个Array.toSeq来调整.如果没有它,它会进入at 0.234,这比原来的while循环更快.不幸的是,我需要一个序列(我们必须使用延迟加载,并且不能在内存中保存整个字符串).
(更新)性能比较包括元素访问
上面的比较仅测试迭代,这有助于找到堆叠迭代器引起的问题.但是,如果添加元素访问方程式,时间会略有不同.我通过添加Seq.map id以下内容强制执行:
let runmap f = for i in 1 .. 1000000 do f input |> Seq.map id |> Seq.length |> ignore;;
结果:
Function CPU Factor
stocp0 0.795 1.0
stocp1 1.528 1.9
stocp2 1.731 2.2
stocp2' 1.812 2.3
stocp3 0.936 1.2
stocp4 0.842 1.1
stocp5 0.873 1.1 (credit: latkin, see his answer and notes above)
(更新)性能比较包括有限元素访问
由于我们的典型用例不需要完全迭代,因此我添加了一个测试,该测试仅迭代到位置6的第二个代理对,输入较大(3932160个字符).
let runmapnth f = for i in 1 .. 1000000 do f input |> Seq.map id |> Seq.nth 6 |> ignore;;
结果:
Function CPU Factor
stocp0 0.624 1.0
stocp1 1.029 1.6
stocp2 1.263 2.0
stocp2' 1.107 1.8
stocp3 0.717 1.1
stocp4 0.624 1.0
stocp5 --- --- OOM
在OutOfMemoryException与latkin的回答让我吃惊了一下,这意味着在一个紧密环的上述使用时所创建的阵列,没有清理.我的机器在几秒钟内分配了8GB的几次,然后在它们之间掉落(GC')？但最终仍然失败了.奇怪:
其他性能特征可以根据早期的观察结果预期.
结论,问题
通过上面的最后一个练习,我发现了一些我没想到的东西:F#编译器只调用非泛型IEnumerator.Current而且从不调用IEnumerator<T>.Current.这可能部分解释了为什么当你执行它的对象是一个值类型时,链式序列过滤器的性能下降是如此明显:拳击将它放在堆上并再次返回,这很糟糕.
为什么编译器不使用通用接口？
为什么for循环如此缓慢,内部会发生什么？是不是应该变成尾调用,然后在内部编译成快速循环？
是否有更自然或其他方式编写过滤器,就像我所做的那样(mapi,然后过滤器),它没有我描述的有害性能的缺点？
为什么直接(慢)和
string.AsEnumerable()(快)管道串起来有这么大的区别？
我还有很多问题,但SO格式通常只要求你提一个简单的问题,我显然没有.很抱歉这么精致,我希望我不会让太多人接受一些有见地的观察.
更新:正如评论中指出的那样,拳击似乎只在从FSharp Interactive(FSI)运行时出现.如果您stocp4通过添加冗余Seq.filter ((<>) 0)(或类似的东西)来获取和更改调用代码,它将调用未装箱的访问者.为什么？不知道.
好的我会开枪.所有代码和基准测试结果都可以在这里找到.
Lazy v Eager Seqs很慢.理解很慢.它们是一种方便的抽象,涉及大量编译器生成的goop和分配,如果perf很重要,通常应该完全避免.所有这些问题都可以通过以下简单的非懒惰解决方案轻松击败.
// ~50% faster for given test case
// still ~20% faster even for length 1.5M string
let eager1 (value: string) =
let result = ResizeArray(value.Length)
for i in 0 .. value.Length - 1 do
if not (Char.IsLowSurrogate(value.[i]))
then result.Add(Char.ConvertToUtf32(value, i))
result.ToArray()
通用v非你的通用代码是在基准函数被调用.
向两个.Currentimpls 添加一个日志记录语句,并将输出序列传递给|> Seq.iter (printfn "%d"),并且您将看到它是被调用的通用语句.
你在FSI测试了吗？无论出于何种原因,FSI的"将此序列的一些元素打印到控制台"代码确实在非通用路径中结束,但这不会影响执行代码.也许这就是你所看到的？
seq {}中的循环seq { }和其他计算表达式中的循环不是常规循环.(事实上,计算表达式内部几乎没有任何"正常外观"实际上是正常的,这是一点点:))如计算表达式docs中所示,for循环最终会作为迭代结束另一个可枚举. while循环有点简单.
这或多或少地解释了为什么你的"尝试1"如此慢 - for循环导致你的seq中的另一个seq的分配和迭代.
通过Seq API管道是的,这将在每一步创建新的seq.如果涉及的"实际工作"非常小,就像这个例子一样,那么开销就开始占据主导地位.
变得更快您的后续优化每个都会删除抽象层,因此虽然我没有精确的解释,但它们更快一点似乎是合理的.
.AsEnumerable()这很古怪,我可以重复你看到的显着加速.非常奇怪,因为AsEnumerable扩展方法什么也不做,只是直接返回它的输入!
在这些情况下生成的代码的结构是非常不同的.也许这是优化器中的病态案例.有趣的发现.
变化我发现,当您启用/禁用优化时,以及当您将x64与x86对齐时,结果会有很大差异.把它拿走它的价值.
从OP更改基准和要求后更新
Array.toSeq没有必要在Array.toSeq这里使用,并且可以预测地降低我建议的解决方案的性能. Array.toSeq并且Seq.ofArray有更多的安全性(确保生成的seq不能被消费者转换回数组并变异),而不是类型转换.
更好的选择:
seq<_>返回时只需将数组转换为数组- 更新您的其他API以接受灵活类型
#seq<'t>,然后即使是普通数组也可以
更新的要求鉴于新发现的限制:
- 处理字符串如此之大,即使1或2个副本也会导致OOM
- 处理时经常提前纾困
那么很明显,懒惰的方法会更合适,至少在某些情况下是这样.
然而,即使有这些要求,在我使用新基准测试时,非懒惰解决方案在所有情况下仍然表现得非常好,除了OOM或早期救助的大量输入.
请参阅上面链接的我的要点以获得结果.它包括替代的非延迟实现:
let eager2 (value: string) =
let result = ResizeArray(value.Length)
for i in 0 .. value.Length - 1 do
if not (Char.IsLowSurrogate(value.[i]))
then result.Add(Char.ConvertToUtf32(value, i))
// cast result so that return type isn't array
(result.ToArray()) :> seq<_>
let eager3 (value: string) =
let result = ResizeArray(value.Length)
for i in 0 .. value.Length - 1 do
if not (Char.IsLowSurrogate(value.[i]))
then result.Add(Char.ConvertToUtf32(value, i))
// ToArray() causes another copy to be generated.
// Avoiding that is a win in large-input scenarios, but at a cost
// of otherwise slower processing
(result) :> seq<_>
改善懒惰的解决方案
这是对惰性方法的进一步优化,直接集成所有逻辑,避免使用字符串枚举器,并避免递归.
在大多数情况下,这个人实际上似乎打败了非懒惰的解决方案!
let lazy5 (value : string) =
let inline getEnum() =
let i = ref -1
{ new IEnumerator<int> with
member __.Current = Char.ConvertToUtf32(value, !i)
interface System.Collections.IEnumerator with
member __.Current = box (Char.ConvertToUtf32(value, !i))
member __.MoveNext() =
incr i
if !i >= value.Length then false else
if not (Char.IsLowSurrogate(value.[!i])) then true else
incr i
!i < value.Length
member __.Reset() = failwith "reset"
interface IDisposable with
member __.Dispose() = () }
{ new IEnumerable<int> with
member __.GetEnumerator() = getEnum()
interface IEnumerable with
member __.GetEnumerator() = getEnum() :> IEnumerator }
摘要
第一个基于while的seq解决方案看起来很棒并且在给定约束条件下表现良好 我试图给出一些关于为什么提出的替代方案可能会变慢的背景,希望这有用.我通过将所有内容IEnumerable直接集成到一个explict中,设法挤出了更多的性能.
根据约束和输入,非惰性解决方案可能是一个不错的选择.我在这里提出了一些选择.与往常一样,您需要在真实环境中进行测试.
| 归档时间： |
|
| 查看次数： |
827 次 |
| 最近记录： |