Checking a seq, list or array with thousands of yield statements is far slower than linear

オープン
  • 何か問題がありますか？
#20,887 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 2 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
43/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
活発
技術スタック
fsharp
領域
compilers, performance

調査の方向性

Start in CheckSequenceExpressions.fs and compare typechecking of the generated flat and yield-based files with the reported --times command. The issue says the cause is unknown and points to StackGuard behavior as an unverified suspicion, so first profile the typecheck path and inspect the related benchmarks in dotnet/fsharp#20759. Done means large yield collections typecheck with time growing roughly linearly, as the flat literal does.

索引モデルが issue の本文から書いたものです。

説明

Needs-Triage

Checking a seq, list or array expression whose body is a sequence of yield statements takes time that grows much faster than linearly with the number of statements. The same elements as a flat literal, [ 0; 1; 2; … ], take the same time at every size. A computed collection of a few thousand elements is easy to reach in generated code and data tables.

Repro steps

  1. Generate the files with dotnet fsi gen.fsx:
// gen.fsx
let write name count element =
    let elements = [ for i in 0 .. count - 1 -> element i ] |> String.concat "; "
    System.IO.File.WriteAllText(name, $"module M\nlet xs = [ {elements} ]\n")

for count in [ 1000; 2000; 3000 ] do
    write $"flat{count}.fs" count string
    write $"yield{count}.fs" count (fun i -> $"yield {i}")
  1. Run dotnet fsc --nologo --target:library --typecheckonly --times yield3000.fs with a Release compiler and read the Typecheck row. Compare it with flat3000.fs.

Expected behavior

The Typecheck phase grows in proportion to the number of elements, as it does for the flat literal.

Actual behavior

Duration of the Typecheck phase, main at fbc9be3aa8, Release build, two runs each for yield:

Elements flat literal yield statements
1000 1.5 s 1.9 s, 2.0 s
2000 1.4 s 5.1 s, 5.5 s
3000 1.6 s 42 s, 60 s

The steps are not smooth: on a busy machine the same files took 72 s (2000) and 110 s (3000). The collection kind does not matter; one busy run with 2000 yield statements took 72 s as a list, 24 s as an array and 32 s as a seq { … }. --times puts all of it in the Typecheck phase, with 53 gen0, 6 gen1 and 4 gen2 collections at 2000 elements.

The shipped SDK compiler (11.0.100-rc.1) overflows its stack at 1250 statements. Main no longer crashes since #20480 guards the sequence spine, but it is slow instead.

Known workarounds

Split the collection into pieces of a few hundred elements and join them: List.concat [ [ yield 0; … ]; [ yield 500; … ] ] with six pieces of 500 took 9.8 s for 3000 elements in the busy run that took 110 s as one list.

Related information

  • The cause is not known. Swapping the argument order of the two per-element UnifyTypes genOuterTy (mkSeqTy genResultTy) calls in CheckSequenceExpressions.fs, to avoid growing a chain of type variables, did not help: 2000 elements took 18 to 23 s instead of 5 s. The jump between 2000 and 3000 elements is steeper than quadratic and looks like StackGuard moving the work to new threads once the spine outgrows the stack; this is a suspicion, not measured.
  • Related: #20480 (stack guard for the spine), #13084, #12421 (quadratic optimizer on nested applications), #20788 (quotation list literals).
  • dotnet/fsharp#20759 adds compiler benchmarks (MixedRangeBenchmarks) for flat, mixed-range and explicit yield! collections, and the FS-1031 RFC states that checking MUST stay linear in the number of elements.
  • Windows 11, 32 logical cores, .NET SDK 11.0.100-rc.1.26420.103, compiler built from main.
主要言語
F#
スター
4.3k
フォーク
884
平均マージ
2日 11時間
マージ済み PR（30日）
73

環境構築

Codespaces で開く

このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

dotnet/fsharp のほかの issue

dotnet/fsharp の issue をすべて見る

似ている issue

Compilers の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。