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

Abierto
  • ¿Algo no está bien?
#20,887 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 2 días

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
43/100
Tipo de issue
Error
Claridad
Bastante claro
Estado de actividad
Activo
Stack tecnológico
fsharp
Área
compilers, performance

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.
Lenguaje dominante
F#
Estrellas
4.3k
Forks
884
Merge medio
2 d 11 h
PR fusionados (30 d)
73

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de dotnet/fsharp

Todos los issues de dotnet/fsharp

Issues similares

Más issues de Compilers

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.