Scala compiler failure: offset too big to fit in 16bits: 36197

Hi, I'm trying out porting some of our code to Scala 2.8 from Scala 2.7.7 final.
I successfully got a small library to compile and build.  I'm now working on a bigger library, building it using maven, I've got the code to generally compile (e.g. I think I've made all the changes necessary to be compatible with 2.8), but it fails to build in maven:
(I encountered this error once in 2.7.7 and had to change my source code to work around the issue.)
any ideas?
[INFO] java.lang.reflect.InvocationTargetException [INFO] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)[INFO] at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39) [INFO] at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)[INFO] at java.lang.reflect.Method.invoke(Method.java:597) [INFO] at org_scala_tools_maven_executions.MainHelper.runMain(MainHelper.java:161)[INFO] at org_scala_tools_maven_executions.MainWithArgsInFile.main(MainWithArgsInFile.java:26) [ERROR] Caused by: java.lang.Error: ch.epfl.lamp.fjbg.JCode$OffsetTooBigException: offset too big to fit in 16 bits: 36197[INFO] at ch.epfl.lamp.fjbg.JFieldOrMethod.writeTo(JFieldOrMethod.java:114) [INFO] at ch.epfl.lamp.fjbg.JClass.writeTo(JClass.java:315)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$BytecodeGenerator.emitClass(GenJVM.scala:141) [INFO] at scala.tools.nsc.backend.jvm.GenJVM$BytecodeGenerator.genClass(GenJVM.scala:262)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase.apply(GenJVM.scala:56) [INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase$$anonfun$run$3.apply(GenJVM.scala:52)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase$$anonfun$run$3.apply(GenJVM.scala:52) [INFO] at scala.collection.mutable.HashMap$$anon$2$$anonfun$foreach$3.apply(HashMap.scala:89)[INFO] at scala.collection.mutable.HashMap$$anon$2$$anonfun$foreach$3.apply(HashMap.scala:89) [INFO] at scala.collection.Iterator$class.foreach(Iterator.scala:631)[INFO] at scala.collection.mutable.HashTable$$anon$1.foreach(HashTable.scala:161) [INFO] at scala.collection.mutable.HashTable$class.foreachEntry(HashTable.scala:194)[INFO] at scala.collection.mutable.HashMap.foreachEntry(HashMap.scala:39) [INFO] at scala.collection.mutable.HashMap$$anon$2.foreach(HashMap.scala:89)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase.run(GenJVM.scala:52) [INFO] at scala.tools.nsc.Global$Run.compileSources(Global.scala:733)[INFO] at scala.tools.nsc.Global$Run.compile(Global.scala:813) [INFO] at scala.tools.nsc.Main$.process(Main.scala:108)[INFO] at scala.tools.nsc.Main$.main(Main.scala:122) [INFO] at scala.tools.nsc.Main.main(Main.scala)[INFO] ... 6 more[INFO] Caused by: ch.epfl.lamp.fjbg.JCode$OffsetTooBigException: offset too big to fit in 16 bits: 36197 [INFO] at ch.epfl.lamp.fjbg.JCode.checkOffset16(JCode.java:896)[INFO] at ch.epfl.lamp.fjbg.JCode.patchAllOffset(JCode.java:975) [INFO] at ch.epfl.lamp.fjbg.JCode.freeze(JCode.java:95)[INFO] at ch.epfl.lamp.fjbg.JMethod.freeze(JMethod.java:81) [INFO] at ch.epfl.lamp.fjbg.JFieldOrMethod.writeTo(JFieldOrMethod.java:111)

Are you using big nested extractors? If so, pls see https://lampsvn.epfl.ch/trac/scala/ticket/1133 .
It's not a bug in scala but a limitation on the size of methods within the jvm. If you search the list a while back paulp commented. The work around is to simplify your extractors by breaking them up.


On Tue, Aug 10, 2010 at 12:37 PM, Alex Black <alex [at] alexblack [dot] ca> wrote:

Hi, I'm trying out porting some of our code to Scala 2.8 from Scala 2.7.7 final.
I successfully got a small library to compile and build.  I'm now working on a bigger library, building it using maven, I've got the code to generally compile (e.g. I think I've made all the changes necessary to be compatible with 2.8), but it fails to build in maven:
(I encountered this error once in 2.7.7 and had to change my source code to work around the issue.)
any ideas?
[INFO] java.lang.reflect.InvocationTargetException [INFO] at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)[INFO] at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39) [INFO] at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)[INFO] at java.lang.reflect.Method.invoke(Method.java:597) [INFO] at org_scala_tools_maven_executions.MainHelper.runMain(MainHelper.java:161)[INFO] at org_scala_tools_maven_executions.MainWithArgsInFile.main(MainWithArgsInFile.java:26) [ERROR] Caused by: java.lang.Error: ch.epfl.lamp.fjbg.JCode$OffsetTooBigException: offset too big to fit in 16 bits: 36197[INFO] at ch.epfl.lamp.fjbg.JFieldOrMethod.writeTo(JFieldOrMethod.java:114) [INFO] at ch.epfl.lamp.fjbg.JClass.writeTo(JClass.java:315)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$BytecodeGenerator.emitClass(GenJVM.scala:141) [INFO] at scala.tools.nsc.backend.jvm.GenJVM$BytecodeGenerator.genClass(GenJVM.scala:262)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase.apply(GenJVM.scala:56) [INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase$$anonfun$run$3.apply(GenJVM.scala:52)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase$$anonfun$run$3.apply(GenJVM.scala:52) [INFO] at scala.collection.mutable.HashMap$$anon$2$$anonfun$foreach$3.apply(HashMap.scala:89)[INFO] at scala.collection.mutable.HashMap$$anon$2$$anonfun$foreach$3.apply(HashMap.scala:89) [INFO] at scala.collection.Iterator$class.foreach(Iterator.scala:631)[INFO] at scala.collection.mutable.HashTable$$anon$1.foreach(HashTable.scala:161) [INFO] at scala.collection.mutable.HashTable$class.foreachEntry(HashTable.scala:194)[INFO] at scala.collection.mutable.HashMap.foreachEntry(HashMap.scala:39) [INFO] at scala.collection.mutable.HashMap$$anon$2.foreach(HashMap.scala:89)[INFO] at scala.tools.nsc.backend.jvm.GenJVM$JvmPhase.run(GenJVM.scala:52) [INFO] at scala.tools.nsc.Global$Run.compileSources(Global.scala:733)[INFO] at scala.tools.nsc.Global$Run.compile(Global.scala:813) [INFO] at scala.tools.nsc.Main$.process(Main.scala:108)[INFO] at scala.tools.nsc.Main$.main(Main.scala:122) [INFO] at scala.tools.nsc.Main.main(Main.scala)[INFO] ... 6 more[INFO] Caused by: ch.epfl.lamp.fjbg.JCode$OffsetTooBigException: offset too big to fit in 16 bits: 36197 [INFO] at ch.epfl.lamp.fjbg.JCode.checkOffset16(JCode.java:896)[INFO] at ch.epfl.lamp.fjbg.JCode.patchAllOffset(JCode.java:975) [INFO] at ch.epfl.lamp.fjbg.JCode.freeze(JCode.java:95)[INFO] at ch.epfl.lamp.fjbg.JMethod.freeze(JMethod.java:81) [INFO] at ch.epfl.lamp.fjbg.JFieldOrMethod.writeTo(JFieldOrMethod.java:111)

On Tue, Aug 10, 2010 at 12:42:24PM -0400, Doug Tangren wrote:
> Are you using big nested extractors? If so, pls see
> https://lampsvn.epfl.ch/trac/scala/ticket/1133 .
>
> It's not a bug in scala but a limitation on the size of methods within
> the jvm.

I wouldn't go quite that far: scala is responsible for dealing with the
constraints imposed by the jvm in a sensible way.  It's not fixed yet
because fixing it requires an understanding of the pattern matcher that
I do not think anyone possesses.  It will be fixed someday, no question.

--
Paul Phillips      | Eschew mastication.
Moral Alien        |
Empiricist         |
pal, i pill push   |----------* http://www.improving.org/paulp/ *----------

On Tue, Aug 10, 2010 at 12:42:24PM -0400, Doug Tangren wrote:
> Are you using big nested extractors? If so, pls see
> https://lampsvn.epfl.ch/trac/scala/ticket/1133 .
>
> It's not a bug in scala but a limitation on the size of methods within
> the jvm.

I wouldn't go quite that far: scala is responsible for dealing with the
constraints imposed by the jvm in a sensible way. It's not fixed yet
because fixing it requires an understanding of the pattern matcher that
I do not think anyone possesses. It will be fixed someday, no question.

Compile with:

scalac -verbose -Ydebug -Ylog:erasure

The last debug output should point you to the right area of your code.

-jason

On Tue, Aug 10, 2010 at 6:47 PM, Alex Black wrote:
> I'm not sure if our extractors qualify as "big nested".
> The code compiles fine in 2.7.7. damn.
> Any idea how I can narrow down *which* code in my project scala2.8 doesn't
> like so I can change it?

On Tue, Aug 10, 2010 at 01:04:41PM -0400, Alex Black wrote:
> Its definitely a bug in scala. Its compiling code without error, then
> crashing.

It is? Then it isn't ticket #1133, which manifests during compilation.

I'm sure it's (at least partly) a bug in scala regardless, but you have
suddenly made it somewhat less clear what bug it is.

Compile with:

scalac -verbose -Ydebug -Ylog:erasure

The last debug output should point you to the right area of your code.

-jason

On Tue, Aug 10, 2010 at 6:47 PM, Alex Black <alex [at] alexblack [dot] ca> wrote:
> I'm not sure if our extractors qualify as "big nested".
> The code compiles fine in 2.7.7. damn.
> Any idea how I can narrow down *which* code in my project scala2.8 doesn't
> like so I can change it?

On Tue, Aug 10, 2010 at 01:04:41PM -0400, Alex Black wrote:
> Its definitely a bug in scala.  Its compiling code without error, then
> crashing.

It is? Then it isn't ticket #1133, which manifests during compilation.

I'm sure it's (at least partly) a bug in scala regardless, but you have
suddenly made it somewhat less clear what bug it is.

--
Paul Phillips      | The most dangerous man to any government is the man who
Apatheist          | is able to think things out [...] Almost inevitably he
Empiricist         | comes to the conclusion that the government he lives under
pp: i haul pills   | is dishonest, insane, intolerable.   -- H. L. Mencken

On Tue, Aug 10, 2010 at 01:56:54PM -0400, Alex Black wrote:
> The problem does manifest during compilation. What I meant was: the
> compiler appears to accept the syntax of the code.

It seems unlikely you expect us to deflect hard limitations of the
underlying virtual machine via syntax, so I'm not sure what you mean
here. It'll keep accepting the syntax. The bug is that this particular
limitation makes its entrance sooner than is necessary, not that it
turns up at all.

On Tue, Aug 10, 2010 at 01:56:54PM -0400, Alex Black wrote:
> The problem does manifest during compilation.  What I meant was: the
> compiler appears to accept the syntax of the code.

It seems unlikely you expect us to deflect hard limitations of the
underlying virtual machine via syntax, so I'm not sure what you mean
here.  It'll keep accepting the syntax.  The bug is that this particular
limitation makes its entrance sooner than is necessary, not that it
turns up at all.

--
Paul Phillips      | If this is raisin, make toast with it.
Everyman           |
Empiricist         |
all hip pupils!    |----------* http://www.improving.org/paulp/ *----------

I'll try again:
I think its reasonable to expect that scalac can compile scala code.   If it fails to compile scala code, I'd call that a bug.  Not only did it fail to compile scala code, but it failed to compile scala code that the 2.7.7 compiles successfully.
While I appreciate the power of pattern matching, and the complexity of dealing with JVM limitations, that doesn't change the issue I don't think, it only increases the cost/time/difficulty of a fix.



On Tue, Aug 10, 2010 at 3:06 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:

On Tue, Aug 10, 2010 at 01:56:54PM -0400, Alex Black wrote:
> The problem does manifest during compilation.  What I meant was: the
> compiler appears to accept the syntax of the code.

It seems unlikely you expect us to deflect hard limitations of the
underlying virtual machine via syntax, so I'm not sure what you mean
here.  It'll keep accepting the syntax.  The bug is that this particular
limitation makes its entrance sooner than is necessary, not that it
turns up at all.

--
Paul Phillips      | If this is raisin, make toast with it.
Everyman           |
Empiricist         |
all hip pupils!    |----------* http://www.improving.org/paulp/ *----------

On Tue, Aug 10, 2010 at 8:13 PM, Alex Black wrote:
> I think its reasonable to expect that scalac can compile scala code.   If it
> fails to compile scala code, I'd call that a bug.  Not only did it fail to
> compile scala code, but it failed to compile scala code that the 2.7.7
> compiles successfully.

This goes without saying. It is why there's a bug open[1] as mentioned
elsewhere. Paul also confirmed in this thread that it's a bug and that
it will be fixed eventually.

Best,
Ismael

[1] https://lampsvn.epfl.ch/trac/scala/ticket/1133

also, regarding syntax, my naive outsider's perspective is: Scala has this wonderfully powerful pattern matching syntax that cannot be fully used right now because of this issue.  
One possible solution seems to improve scalac so it can handle any complexity of pattern matching.  
Another possible solution might be: change the syntax so scalac can handle any legal input
Another possible solution might be: change scalac to recognize when the syntax is too complex and fail nicely with an error indicating a possible solution (instead of crashing).

On Tue, Aug 10, 2010 at 3:13 PM, Alex Black <alex [at] alexblack [dot] ca> wrote:

I'll try again:
I think its reasonable to expect that scalac can compile scala code.   If it fails to compile scala code, I'd call that a bug.  Not only did it fail to compile scala code, but it failed to compile scala code that the 2.7.7 compiles successfully.
While I appreciate the power of pattern matching, and the complexity of dealing with JVM limitations, that doesn't change the issue I don't think, it only increases the cost/time/difficulty of a fix.



On Tue, Aug 10, 2010 at 3:06 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:

On Tue, Aug 10, 2010 at 01:56:54PM -0400, Alex Black wrote:
> The problem does manifest during compilation.  What I meant was: the
> compiler appears to accept the syntax of the code.

It seems unlikely you expect us to deflect hard limitations of the
underlying virtual machine via syntax, so I'm not sure what you mean
here.  It'll keep accepting the syntax.  The bug is that this particular
limitation makes its entrance sooner than is necessary, not that it
turns up at all.

--
Paul Phillips      | If this is raisin, make toast with it.
Everyman           |
Empiricist         |
all hip pupils!    |----------* http://www.improving.org/paulp/ *----------

On Tue, Aug 10, 2010 at 01:56:54PM -0400, Alex Black wrote:
> The problem does manifest during compilation.  What I meant was: the
> compiler appears to accept the syntax of the code.

It seems unlikely you expect us to deflect hard limitations of the
underlying virtual machine via syntax, so I'm not sure what you mean
here.  It'll keep accepting the syntax.  The bug is that this particular
limitation makes its entrance sooner than is necessary, not that it
turns up at all.

--
Paul Phillips      | If this is raisin, make toast with it.
Everyman           |
Empiricist         |
all hip pupils!    |----------* http://www.improving.org/paulp/ *----------

For a summary, I think we can distinguish three different (yet,
dependent) issues here:

1.) Generated code from Scala's pattern matches may explode in size.
This may be bug in itself. Or, it may be unavoidable even in the
'normal' cases, in which cases Scala should in some way or another
distribute the code into several methods and/or emit a warning. This
is the hard one to fix since, as Paul said, noone right now has the
knowledge and courage to tackle this issue right now.
2.) FJBG has a bogus check for valid short values, which produces
these spurious errors even if the JVM limit is not yet reached.
3.) Given, that 3 might not be fixed in the immediate future, the
compiler shouldn't freak out in the cases reported here and in #1133
and report a sensible error message mentioning the method in question.

On Wed, Aug 11, 2010 at 4:28 AM, David Pollak
wrote:
> My 2 cents.  This is a problem with the 2.8 Scala compiler.  Simple patterns
> (ones that contain 3 or 4 cases) trigger this problem under 2.8, but not
> under 2.7.7.  I'll work up some examples to demonstrate the problem on
> Friday afternoon.
>
> On Tue, Aug 10, 2010 at 12:06 PM, Paul Phillips wrote:
>>
>> On Tue, Aug 10, 2010 at 01:56:54PM -0400, Alex Black wrote:
>> > The problem does manifest during compilation.  What I meant was: the
>> > compiler appears to accept the syntax of the code.
>>
>> It seems unlikely you expect us to deflect hard limitations of the
>> underlying virtual machine via syntax, so I'm not sure what you mean
>> here.  It'll keep accepting the syntax.  The bug is that this particular
>> limitation makes its entrance sooner than is necessary, not that it
>> turns up at all.
>>
>> --
>> Paul Phillips      | If this is raisin, make toast with it.
>> Everyman           |
>> Empiricist         |
>> all hip pupils!    |----------* http://www.improving.org/paulp/
>> *----------
>
>
>
> --
> Lift, the simply functional web framework http://liftweb.net
> Beginning Scala http://www.apress.com/book/view/1430219890
> Follow me: http://twitter.com/dpp
> Blog: http://goodstuff.im
> Surf the harmonics
>

On Wed, Aug 11, 2010 at 2:22 PM, Johannes Rudolph
wrote:
> 2.) FJBG has a bogus check for valid short values, which produces
No, I'm wrong here technically. The check is ok, but it should emit a
wide instruction if the pc deltas are big enough.

On Wed, Aug 11, 2010 at 02:22:18PM +0200, Johannes Rudolph wrote:
> 1.) Generated code from Scala's pattern matches may explode in size.
> This may be bug in itself. Or, it may be unavoidable even in the
> 'normal' cases, in which cases Scala should in some way or another
> distribute the code into several methods and/or emit a warning.

Yes, it should alter the code generation algorithm in such cases. I
know how to handle this in principle, but as anyone who has followed my
messages about the pattern matcher can guess, I am not in a huge hurry
to pick it up again.

> 2.) FJBG has a bogus check for valid short values, which produces
> these spurious errors even if the JVM limit is not yet reached.

I don't have any natural sounding expressions of suprise, but "holy
smokes, you're right." Did you report this and I missed it? It's using
Short.MaxValue as the ceiling, which is half the correct one.

I check in a better error message as soon as I can run tests, and now I
better see about fixing fjbg.

On Wed, Aug 11, 2010 at 02:31:58PM +0200, Johannes Rudolph wrote:
> No, I'm wrong here technically. The check is ok, but it should emit a
> wide instruction if the pc deltas are big enough.

OK, I just came back to ask about this because I couldn't find the
explicit check, and I see I missed this email before. So to clarify, is
there a bug you can see in fjbg or no?

I already tried fixing it, but there is no easy fix available, since
that's pretty much by design.

The problem is, that for forward jumps the target address is not
available when the jump bytecode is emitted. So fjbg collects a list
of target positions to fill in later when all the information are
available. The problem is that there are two kinds of GOTO
instructions. One, GOTO, that is 3 bytes long that uses two bytes for
specifying the offset for the target, and GOTO_W, which is 5 bytes
long and uses 4 of them to specify the offset for the target. But for
the patching mechanism to work you have to know beforehand which one
you want to use. And you cannot easily change a GOTO to GOTO_W later
on because you would have to insert bytes into the bytecode stream
which isn't possible because it would invalidate all the targets going
into the area after the insertion. And even if you would track all
targets it isn't even said that you are done in one iteration because
changing a bunch of GOTOs into GOTO_W could trigger the need for even
more GOTOs to be changed.

Given the fact, that only unconditional branching (GOTO) has a wide
variant, and all other conditional branches not, it is not said that
you could use all the available bytecode space at all without having
to resort to some kind of an optimization algorithm laying out the
basic code blocks in a way to minimize the relative jumping offsets.

BTW, I filed https://lampsvn.epfl.ch/trac/scala/ticket/3745 for this issue.

On Wed, Aug 11, 2010 at 6:02 PM, Paul Phillips wrote:
> On Wed, Aug 11, 2010 at 02:31:58PM +0200, Johannes Rudolph wrote:
>> No, I'm wrong here technically. The check is ok, but it should emit a
>> wide instruction if the pc deltas are big enough.
>
> OK, I just came back to ask about this because I couldn't find the
> explicit check, and I see I missed this email before.  So to clarify, is
> there a bug you can see in fjbg or no?
>
> --
> Paul Phillips      | Those who can make you believe absurdities
> Stickler           | can make you commit atrocities.
> Empiricist         |     -- Voltaire
> pal, i pill push   |----------* http://www.improving.org/paulp/ *----------
>

On Tue, Aug 10, 2010 at 07:28:15PM -0700, David Pollak wrote:
> My 2 cents. This is a problem with the 2.8 Scala compiler. Simple
> patterns (ones that contain 3 or 4 cases) trigger this problem under
> 2.8, but not under 2.7.7. I'll work up some examples to demonstrate
> the problem on Friday afternoon.

I can see it's true by compiling the test case in #1133, where the size
jumps from 30K+ to 50K+.

scalac27 Match.scala
Exception in thread "main" java.lang.Error: ch.epfl.lamp.fjbg.JCode$OffsetTooBigException: offset too big to fit in 16 bits: 36580

scalac28 Match.scala
Exception in thread "main" java.lang.Error: ch.epfl.lamp.fjbg.JCode$OffsetTooBigException: offset too big to fit in 16 bits: 53273

But let's not pin this on the 2.8 compiler too quickly, because at least
in the cases where it took place intentionally, the generated code is
larger because the old code was just wrong. #2337 (still unfixed) is an
example of a bug which occurs because a tree which should be duplicated
across a decision is omitted. Other bugs involving things like
"consistency problem in target generation" (#313131, #3e3e3e) and various
unapply bugs come down to the same thing.

It's entirely possible it's bigger because of mistakes on my part.
Likely even. But about all I have to offer wrt the 2.8 pattern matcher
is a) I'll reintegrate the 2.7 matcher, all bugs included or b) wait for
me to rewrite it from scratch. Or c) find the next sucker.

I started b) a while ago and it's going very well but it's not the next
thing I'm going to do and I can't make any guarantees about when it will
be done. I am categorically, absolutely done wasting time trying to fix
bugs in the current pattern matcher. If people had the least inkling
how much time I've spent on those shifting sands they would (depending
on their level of sympathy) either laugh or cry at my persistence in the
face of repeated failure. There comes a time when one has to go back to
the drawing board, and I am way, way past it.

My 2 cents.  This is a problem with the 2.8 Scala compiler.  Simple patterns (ones that contain 3 or 4 cases) trigger this problem under 2.8, but not under 2.7.7.  I'll work up some examples to demonstrate the problem on Friday afternoon.

On Tue, Aug 10, 2010 at 12:06 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:

On Tue, Aug 10, 2010 at 01:56:54PM -0400, Alex Black wrote:
> The problem does manifest during compilation.  What I meant was: the
> compiler appears to accept the syntax of the code.

It seems unlikely you expect us to deflect hard limitations of the
underlying virtual machine via syntax, so I'm not sure what you mean
here.  It'll keep accepting the syntax.  The bug is that this particular
limitation makes its entrance sooner than is necessary, not that it
turns up at all.

--
Paul Phillips      | If this is raisin, make toast with it.
Everyman           |
Empiricist         |
all hip pupils!    |----------* http://www.improving.org/paulp/ *----------

--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Blog: http://goodstuff.im
Surf the harmonics

On Sun, Aug 15, 2010 at 09:57:52AM -0700, David Pollak wrote:
> The thing I noticed is that there are 4,608 lines that compare against
> the String "foo" in each file. I would have expected 2 lines.

Amidst this expectation resides the issue which must be understood to
make sense of the current behaviors. The algorithm implemented by the
matcher (chosen before extractors and sequence matches existed, with
those grafted on afterward) involves constructing a DFA out of the case
statements. The upside of a DFA is no backtracking. The downside is
that to avoid backtracking, when you reach a decision you have to
duplicate all remaining decisions across both paths, so there is a
potential space explosion.

Before extractors that downside was pretty manageable, but since you
can't tell much at all about extractors statically, every single one is
a decision. Start stacking cases with nested extractors and you will
see it gets ugly fast.

There is no shortage of ways to address this - I have all kinds of nice
algorithms lined up. The difficulty is all in the implementation. In
addition to being algorithmically opaque, the pattern matcher is one of
those smack-in-the-middle phases where you must set everything up juuust
right or it's straight to crashytown. Or worse yet, not straight to
crashytown -- it'll take you by a nice indirect route and by the time
you see it you don't know what change caused it. It often feels
designed to frustrate. And I have to figure out everything empirically,
because there's not even anyone to ask.

> Where each case statement compiles into its own PartialFunction, there
> are in fact only 2 comparisons to "foo" (on in apply() and the other
> in isDefinedAt()).

Try hidden option -Ypmat-naive which does somethine like this (but
should not be relied upon to generate correct code.) I wrote it for use
with bug 2337. With only one case there are no transitions and thus no
space explosion. Among my "give up and retrench" plans for 2.8 was a
pattern matcher which compiled much like you describe. And I tried it,
and even that much was much harder to make work than I thought it ought
to be. There was only so hard I was going to work on pure short term
stopgap code, so I put another notch in the failure belt.

On Sun, Aug 15, 2010 at 09:57:52AM -0700, David Pollak wrote:
> The thing I noticed is that there are 4,608 lines that compare against
> the String "foo" in each file.  I would have expected 2 lines.

Amidst this expectation resides the issue which must be understood to
make sense of the current behaviors.  The algorithm implemented by the
matcher (chosen before extractors and sequence matches existed, with
those grafted on afterward) involves constructing a DFA out of the case
statements.  The upside of a DFA is no backtracking.  The downside is
that to avoid backtracking, when you reach a decision you have to
duplicate all remaining decisions across both paths, so there is a
potential space explosion.

Before extractors that downside was pretty manageable, but since you
can't tell much at all about extractors statically, every single one is
a decision.  Start stacking cases with nested extractors and you will
see it gets ugly fast.

There is no shortage of ways to address this - I have all kinds of nice
algorithms lined up.  The difficulty is all in the implementation.  In
addition to being algorithmically opaque, the pattern matcher is one of
those smack-in-the-middle phases where you must set everything up juuust
right or it's straight to crashytown.  Or worse yet, not straight to
crashytown -- it'll take you by a nice indirect route and by the time
you see it you don't know what change caused it.  It often feels
designed to frustrate.  And I have to figure out everything empirically,
because there's not even anyone to ask.

> Where each case statement compiles into its own PartialFunction, there
> are in fact only 2 comparisons to "foo" (on in apply() and the other
> in isDefinedAt()).

Try hidden option -Ypmat-naive which does somethine like this (but
should not be relied upon to generate correct code.) I wrote it for use
with bug 2337.  With only one case there are no transitions and thus no
space explosion.  Among my "give up and retrench" plans for 2.8 was a
pattern matcher which compiled much like you describe.  And I tried it,
and even that much was much harder to make work than I thought it ought
to be.  There was only so hard I was going to work on pure short term
stopgap code, so I put another notch in the failure belt.

--
Paul Phillips      | It is hard to believe that a man is
Moral Alien        | telling the truth when you know that you
Empiricist         | would lie if you were in his place.
i pull his palp!   |     -- H. L. Mencken

Hi, I have the problem with the version 2.8.1 :
does scala 2.9.0 solve it?

Thank you

Benoit

On Saturday April 2 2011, Benoit Hericher wrote:
> Hi, I have the problem with the version 2.8.1 :
> does scala 2.9.0 solve it?
>
> Thank you
>
> Benoit

It's not a coding bug. It's a limitation of the JVM .class file format.

Randall Schulz

Randall R Schulz sonic.net> writes:

>
> On Saturday April 2 2011, Benoit Hericher wrote:
> > Hi, I have the problem with the version 2.8.1 :
> > does scala 2.9.0 solve it?
> >
> > Thank you
> >
> > Benoit
>
> It's not a coding bug. It's a limitation of the JVM .class file format.
>
> Randall Schulz
>
>
Ok, thank you

I'll try to split my code!

Benoit