Increased compilation times for pattern matching with extractors #4576

scabug · 2011-05-12T23:12:06Z

After upgrading from Scala 2.8.1 to 2.9.0, one of my projects is no longer able to typecheck. All library dependencies have been recompiled successfully to 2.9.0, but my final project is "stuck" during compilation.

Included are stacktrace snapshot (for excel and visualvm) of the recursive behaviour. Below is also the final memory error.

=== What is the expected behavior? ===
Detection of typing error.

=== What do you see instead? ===

java.lang.OutOfMemoryError: Java heap space
	at scala.tools.nsc.util.HashSet.growTable(HashSet.scala:98)
	at scala.tools.nsc.util.HashSet.findEntryOrUpdate(HashSet.scala:40)
	at scala.tools.nsc.symtab.Types$$class.scala$$tools$$nsc$$symtab$$Types$$$$unique(Types.scala:2891)
	at scala.tools.nsc.symtab.Types$$TypeRef$$.apply(Types.scala:1948)
	at scala.tools.nsc.symtab.Types$$class.typeRef(Types.scala:2677)
	at scala.tools.nsc.symtab.SymbolTable.typeRef(SymbolTable.scala:13)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.toType(Types.scala:3482)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.toType(Types.scala:3480)
	at scala.tools.nsc.symtab.Types$$SubstMap.subst(Types.scala:3435)
	at scala.tools.nsc.symtab.Types$$SubstMap.apply(Types.scala:3470)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3499)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3480)
	at scala.tools.nsc.symtab.Types$$TypeMap$$$$anonfun$$mapOverArgs$$1.apply(Types.scala:3107)
	at scala.tools.nsc.symtab.Types$$TypeMap$$$$anonfun$$mapOverArgs$$1.apply(Types.scala:3103)
	at scala.tools.nsc.symtab.Types$$class.map2Conserve(Types.scala:4867)
	at scala.tools.nsc.symtab.SymbolTable.map2Conserve(SymbolTable.scala:13)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOverArgs(Types.scala:3103)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3010)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3495)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3480)
	at scala.tools.nsc.symtab.Types$$TypeMap$$$$anonfun$$16.apply(Types.scala:3125)
	at scala.tools.nsc.symtab.Types$$TypeMap$$$$anonfun$$16.apply(Types.scala:3122)
	at scala.collection.LinearSeqOptimized$$class.exists(LinearSeqOptimized.scala:79)
	at scala.collection.immutable.List.exists(List.scala:45)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3122)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3024)
	at scala.tools.nsc.symtab.Types$$SubstMap.apply(Types.scala:3455)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3499)
	at scala.tools.nsc.symtab.Types$$Type.substSym(Types.scala:590)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3036)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.apply(Types.scala:3415)
	at scala.tools.nsc.symtab.Types$$Type.asSeenFrom(Types.scala:544)

=== Additional information ===
Project also had a typing error reported in #4417 which got resolved by removing the access modifier on the constructor.

=== What versions of the following are you using? ===

Scala: 2.9.0
Java: 1.6.24
Operating system: Windows 7 (32-bit)

scabug · 2011-05-12T23:12:06Z

Imported From: https://issues.scala-lang.org/browse/SI-4576?orig=1
Reporter: Trond Olsen (tolsen77)
Attachments:

log-phase-inliner1.txt (created on May 13, 2011 11:12:20 PM UTC, 62233 bytes)
typing-bug-trace1.zip (created on May 12, 2011 11:13:04 PM UTC, 172964 bytes)

scabug · 2011-05-12T23:13:04Z

Trond Olsen (tolsen77) said:
Stacktrace of looping behaviour (excel and visualvm image)

scabug · 2011-05-13T00:00:44Z

Trond Olsen (tolsen77) said:
The last debug entries before the memory error was:

raw type trait IndexedSeq -> <root>#scala#collection#IndexedSeq
raw type trait IndexedSeq -> <root>#scala#collection#IndexedSeq
raw type trait IndexedSeq -> collection.this.IndexedSeq[?0] forSome { <deferred> <existential/mixedin> type ?0 }
raw type trait IndexedSeq -> collection.this.IndexedSeq[?0] forSome { <deferred> <existential/mixedin> type ?0 }
[loaded class file D:\project-photonistorg\Photonist\lib\scala-2.9.0\scala-library.jar(scala/Predef$$$$anon$$8.class) in 2ms]
[loaded class file D:\project-photonistorg\Photonist\lib\scala-2.9.0\scala-library.jar(scala/Predef$$$$anon$$9.class) in 1ms]
raw type class Predef$$<:< -> <root>#scala#Predef$$<:<
[loaded class file D:\project-photonistorg\Photonist\lib\scala-2.9.0\scala-library.jar(scala/Predef$$$$anon$$3.class) in 1ms]
[loaded class file D:\project-photonistorg\Photonist\lib\scala-2.9.0\scala-library.jar(scala/Predef$$$$anon$$6.class) in 0ms]
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type trait CanBuildFrom -> <root>#scala#collection#generic#CanBuildFrom
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type class WrappedArray -> <root>#scala#collection#mutable#WrappedArray
raw type trait CanBuildFrom -> <root>#scala#collection#generic#CanBuildFrom

scabug · 2011-05-13T00:02:18Z

Trond Olsen (tolsen77) said:
And another stacktrace from when debugger ran:

java.lang.OutOfMemoryError: Java heap space
	at scala.tools.nsc.util.HashSet.growTable(HashSet.scala:98)
	at scala.tools.nsc.util.HashSet.findEntryOrUpdate(HashSet.scala:40)
	at scala.tools.nsc.symtab.Types$$class.scala$$tools$$nsc$$symtab$$Types$$$$unique(Types.scala:2891)
	at scala.tools.nsc.symtab.Types$$TypeRef$$.apply(Types.scala:1948)
	at scala.tools.nsc.symtab.Types$$class.typeRef(Types.scala:2677)
	at scala.tools.nsc.symtab.SymbolTable.typeRef(SymbolTable.scala:13)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3013)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3495)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3480)
	at scala.tools.nsc.symtab.Types$$TypeMap$$$$anonfun$$16.apply(Types.scala:3125)
	at scala.tools.nsc.symtab.Types$$TypeMap$$$$anonfun$$16.apply(Types.scala:3122)
	at scala.collection.LinearSeqOptimized$$class.exists(LinearSeqOptimized.scala:79)
	at scala.collection.immutable.List.exists(List.scala:45)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3122)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3024)
	at scala.tools.nsc.symtab.Types$$SubstMap.apply(Types.scala:3455)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3499)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3480)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3026)
	at scala.tools.nsc.symtab.Types$$SubstMap.apply(Types.scala:3455)
	at scala.tools.nsc.symtab.Types$$SubstSymMap.apply(Types.scala:3499)
	at scala.tools.nsc.symtab.Types$$Type.substSym(Types.scala:590)
	at scala.tools.nsc.symtab.Types$$TypeMap.mapOver(Types.scala:3036)
	at scala.tools.nsc.symtab.Types$$AsSeenFromMap.apply(Types.scala:3415)
	at scala.tools.nsc.symtab.Types$$Type.asSeenFrom(Types.scala:544)
	at scala.tools.nsc.symtab.Types$$Type.computeMemberType(Types.scala:573)
	at scala.tools.nsc.symtab.Symbols$$MethodSymbol.typeAsMemberOf(Symbols.scala:1867)
	at scala.tools.nsc.symtab.Types$$Type.memberType(Types.scala:564)
	at scala.tools.nsc.symtab.Types$$Type.findMember(Types.scala:919)
	at scala.tools.nsc.symtab.Types$$Type.nonPrivateMembers(Types.scala:482)
	at scala.tools.nsc.symtab.Types$$class.lub1$$1(Types.scala:5200)
	at scala.tools.nsc.symtab.Types$$class.lub0$$1(Types.scala:5154)

scabug · 2011-05-13T23:12:20Z

Trond Olsen (tolsen77) said:
Logg of inliner phase on main application class.

scabug · 2011-05-13T23:13:33Z

Trond Olsen (tolsen77) said:
Added a more detailed logging file log-phase-inliner1.txt from compilation. The long pause in compilation occurs at line 689. The file being inlined is my main application class, which have heavy usage of traits and pattern-matching.

I've been able to complete the compilation now but there is still an abnormal long time spent at point in log.

scabug · 2011-05-14T01:09:17Z

Trond Olsen (tolsen77) said:
I've tested some more and the problem seems to be related to pattern-matching, cons, and extractors. The segment of code has a form similar to:

(name,arr.toList) match {
  case ("a",Extractor1(a) :: Extractor2(b) :: Extractor3(c) :: Nil) =>
  case ("b",(x: String) :: (y: String) :: Nil) =>
}

Running example code with similar to this form does not lead to any increased compilation time, so might be related to the context of it being part of the large application class.

Compilation time slightly improved by changing cons to List().

scabug · 2011-05-14T01:27:58Z

Trond Olsen (tolsen77) said:
Some timing results for comparison:

Total time: 2 minutes 17 seconds (v2.9.0, only cases of typed variables sequenced with List())
Total time: 2 minutes 35 seconds (v2.8.1, all cases sequenced with List())
Total time: 2 minutes 35 seconds (v2.8.1, all cases sequenced with ::)
Total time: 3 minutes 26 seconds (v2.9.0, only cases of extractors sequenced with List())
Total time: 7 minutes 43 seconds (v2.9.0, all cases sequenced with List())
Total time: 10+ minutes (v2.9.0, all cases sequenced with ::)

scabug · 2011-05-14T12:31:36Z

Trond Olsen (tolsen77) said:
The previous measurements is a little botched. Here are updated ones for 2.9.0:

Total time: 13 minutes 55 seconds (cases sequenced with List())
Total time: 7 minutes 34 seconds (cases sequenced with ::)
Total time: 13 minutes 57 seconds  (cases sequenced with List())
Total time: 2 minutes 17 seconds (cases sequenced with Array())
Total time: 7 minutes 33 seconds (cases sequenced with ::)
Total time: 2 minutes 18 seconds (cases sequenced with Array())

scabug · 2011-05-14T12:34:01Z

Trond Olsen (tolsen77) said:
This issue is resolved as far as I'm concerned. Maybe you want to investigate the performance degration of pattern matching lists still?

scabug · 2011-05-17T08:01:38Z

@dragos said:
Are you using -optimize? Otherwise I don't understand where the inliner comes into play. It would help if you could provide us with the code that you measured.

scabug · 2011-05-17T10:28:31Z

Trond Olsen (tolsen77) said:
Yes, I was using the optimize flag. Compilation times went back to normal when I removed it. I can send my project code privately if you want to examine it further? If so, just let me know where to send it.

scabug · 2011-06-14T16:22:02Z

@paulp said:
We're aware of general issues, so the ticket isn't useful without a limited reproduction.

scabug closed this as completed Jun 14, 2011

scabug added the needinfo label Apr 7, 2017

scabug assigned paulp Apr 7, 2017

scabug mentioned this issue Apr 7, 2017

infinite loop in the inliner #4579

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Increased compilation times for pattern matching with extractors #4576

Increased compilation times for pattern matching with extractors #4576

scabug commented May 12, 2011

scabug commented May 12, 2011

scabug commented May 12, 2011

scabug commented May 13, 2011

scabug commented May 13, 2011

scabug commented May 13, 2011

scabug commented May 13, 2011

scabug commented May 14, 2011

scabug commented May 14, 2011

scabug commented May 14, 2011

scabug commented May 14, 2011

scabug commented May 17, 2011

scabug commented May 17, 2011

scabug commented Jun 14, 2011

Increased compilation times for pattern matching with extractors #4576

Increased compilation times for pattern matching with extractors #4576

Comments

scabug commented May 12, 2011

scabug commented May 12, 2011

scabug commented May 12, 2011

scabug commented May 13, 2011

scabug commented May 13, 2011

scabug commented May 13, 2011

scabug commented May 13, 2011

scabug commented May 14, 2011

scabug commented May 14, 2011

scabug commented May 14, 2011

scabug commented May 14, 2011

scabug commented May 17, 2011

scabug commented May 17, 2011

scabug commented Jun 14, 2011