Makes Range#sum an O(1) operation instead of an O(n) one. #16
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Partially fixes SI-4658. NumericRange stays slow, thanks to the brilliant idea that Numeric doesn't need a division operation.
gkossakowski
added a commit
to gkossakowski/scala
that referenced
this pull request
Jan 11, 2012
Factory manifests compiler plug-in.
heathermiller
pushed a commit
to heathermiller/scala
that referenced
this pull request
Oct 11, 2012
Grouping for reflection and macros
retronym
referenced
this pull request
in retronym/scala
Nov 6, 2014
In Scala 2.8.2, an optimization was added to create a static
cache for Symbol literals (ie, the results of `Symbol.apply("foo"))`.
This saves the map lookup on the second pass through code.
This actually was broken somewhere during the Scala 2.10 series,
after the addition of an overloaded `apply` method to `Symbol`.
The cache synthesis code was made aware of the overload and brought
back to working condition recently, in scala#3149.
However, this has uncovered a latent bug when the Symbol literals are
defined with traits.
One of the enclosed tests failed with:
jvm > t8933b-run.log
java.lang.IllegalAccessError: tried to access field MotherClass.symbol$1 from class MixinWithSymbol$class
at MixinWithSymbol$class.symbolFromTrait(A.scala:3)
at MotherClass.symbolFromTrait(Test.scala:1)
This commit simply disables the optimization if we are in a trait.
Alternative fixes might be: a) make the static Symbol cache field
public / b) "mixin" the static symbol cache. Neither of these
seem worth the effort and risk for an already fairly situational
optimization.
Here's how the optimization looks in a class:
% cat sandbox/test.scala; qscalac sandbox/test.scala && echo ":javap C" | qscala;
class C {
'a; 'b
}
Welcome to Scala version 2.11.5-20141106-145558-aa558dce6d (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_20).
Type in expressions to have them evaluated.
Type :help for more information.
scala> :javap C
Size 722 bytes
MD5 checksum 6bb00189166917254e8d40499ee7c887
Compiled from "test.scala"
public class C
{
public static {};
descriptor: ()V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=0, args_size=0
0: getstatic #16 // Field scala/Symbol$.MODULE$:Lscala/Symbol$;
3: ldc #18 // String a
5: invokevirtual #22 // Method scala/Symbol$.apply:(Ljava/lang/String;)Lscala/Symbol;
8: putstatic #26 // Field symbol$1:Lscala/Symbol;
11: getstatic #16 // Field scala/Symbol$.MODULE$:Lscala/Symbol$;
14: ldc #28 // String b
16: invokevirtual #22 // Method scala/Symbol$.apply:(Ljava/lang/String;)Lscala/Symbol;
19: putstatic #31 // Field symbol$2:Lscala/Symbol;
22: return
public C();
descriptor: ()V
flags: ACC_PUBLIC
Code:
stack=1, locals=1, args_size=1
0: aload_0
1: invokespecial #34 // Method java/lang/Object."<init>":()V
4: getstatic #26 // Field symbol$1:Lscala/Symbol;
7: pop
8: getstatic #31 // Field symbol$2:Lscala/Symbol;
11: pop
12: return
}
retronym
referenced
this pull request
in retronym/scala
Nov 6, 2014
In Scala 2.8.2, an optimization was added to create a static
cache for Symbol literals (ie, the results of `Symbol.apply("foo"))`.
This saves the map lookup on the second pass through code.
This actually was broken somewhere during the Scala 2.10 series,
after the addition of an overloaded `apply` method to `Symbol`.
The cache synthesis code was made aware of the overload and brought
back to working condition recently, in scala#3419.
However, this has uncovered a latent bug when the Symbol literals are
defined with traits.
One of the enclosed tests failed with:
jvm > t8933b-run.log
java.lang.IllegalAccessError: tried to access field MotherClass.symbol$1 from class MixinWithSymbol$class
at MixinWithSymbol$class.symbolFromTrait(A.scala:3)
at MotherClass.symbolFromTrait(Test.scala:1)
This commit simply disables the optimization if we are in a trait.
Alternative fixes might be: a) make the static Symbol cache field
public / b) "mixin" the static symbol cache. Neither of these
seem worth the effort and risk for an already fairly situational
optimization.
Here's how the optimization looks in a class:
% cat sandbox/test.scala; qscalac sandbox/test.scala && echo ":javap C" | qscala;
class C {
'a; 'b
}
Welcome to Scala version 2.11.5-20141106-145558-aa558dce6d (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_20).
Type in expressions to have them evaluated.
Type :help for more information.
scala> :javap C
Size 722 bytes
MD5 checksum 6bb00189166917254e8d40499ee7c887
Compiled from "test.scala"
public class C
{
public static {};
descriptor: ()V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=0, args_size=0
0: getstatic #16 // Field scala/Symbol$.MODULE$:Lscala/Symbol$;
3: ldc #18 // String a
5: invokevirtual #22 // Method scala/Symbol$.apply:(Ljava/lang/String;)Lscala/Symbol;
8: putstatic #26 // Field symbol$1:Lscala/Symbol;
11: getstatic #16 // Field scala/Symbol$.MODULE$:Lscala/Symbol$;
14: ldc #28 // String b
16: invokevirtual #22 // Method scala/Symbol$.apply:(Ljava/lang/String;)Lscala/Symbol;
19: putstatic #31 // Field symbol$2:Lscala/Symbol;
22: return
public C();
descriptor: ()V
flags: ACC_PUBLIC
Code:
stack=1, locals=1, args_size=1
0: aload_0
1: invokespecial #34 // Method java/lang/Object."<init>":()V
4: getstatic #26 // Field symbol$1:Lscala/Symbol;
7: pop
8: getstatic #31 // Field symbol$2:Lscala/Symbol;
11: pop
12: return
}
fixup
retronym
referenced
this pull request
in retronym/scala
Nov 7, 2014
In Scala 2.8.2, an optimization was added to create a static
cache for Symbol literals (ie, the results of `Symbol.apply("foo"))`.
This saves the map lookup on the second pass through code.
This actually was broken somewhere during the Scala 2.10 series,
after the addition of an overloaded `apply` method to `Symbol`.
The cache synthesis code was made aware of the overload and brought
back to working condition recently, in scala#3149.
However, this has uncovered a latent bug when the Symbol literals are
defined with traits.
One of the enclosed tests failed with:
jvm > t8933b-run.log
java.lang.IllegalAccessError: tried to access field MotherClass.symbol$1 from class MixinWithSymbol$class
at MixinWithSymbol$class.symbolFromTrait(A.scala:3)
at MotherClass.symbolFromTrait(Test.scala:1)
This commit simply disables the optimization if we are in a trait.
Alternative fixes might be: a) make the static Symbol cache field
public / b) "mixin" the static symbol cache. Neither of these
seem worth the effort and risk for an already fairly situational
optimization.
Here's how the optimization looks in a class:
% cat sandbox/test.scala; qscalac sandbox/test.scala && echo ":javap C" | qscala;
class C {
'a; 'b
}
Welcome to Scala version 2.11.5-20141106-145558-aa558dce6d (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_20).
Type in expressions to have them evaluated.
Type :help for more information.
scala> :javap C
Size 722 bytes
MD5 checksum 6bb00189166917254e8d40499ee7c887
Compiled from "test.scala"
public class C
{
public static {};
descriptor: ()V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=0, args_size=0
0: getstatic #16 // Field scala/Symbol$.MODULE$:Lscala/Symbol$;
3: ldc #18 // String a
5: invokevirtual #22 // Method scala/Symbol$.apply:(Ljava/lang/String;)Lscala/Symbol;
8: putstatic #26 // Field symbol$1:Lscala/Symbol;
11: getstatic #16 // Field scala/Symbol$.MODULE$:Lscala/Symbol$;
14: ldc #28 // String b
16: invokevirtual #22 // Method scala/Symbol$.apply:(Ljava/lang/String;)Lscala/Symbol;
19: putstatic #31 // Field symbol$2:Lscala/Symbol;
22: return
public C();
descriptor: ()V
flags: ACC_PUBLIC
Code:
stack=1, locals=1, args_size=1
0: aload_0
1: invokespecial #34 // Method java/lang/Object."<init>":()V
4: getstatic #26 // Field symbol$1:Lscala/Symbol;
7: pop
8: getstatic #31 // Field symbol$2:Lscala/Symbol;
11: pop
12: return
}
fixup
retronym
referenced
this pull request
in retronym/scala
Jul 14, 2015
And do the same for the specialized variants.
Tested by a Java source file that uses lambda syntax to create
instances of generic and specialized `Function{0,1}`.
Here's how the interfaces look now:
```
% javap -c -classpath /tmp/function 'scala.Function1'
Compiled from "Function1.scala"
public interface scala.Function1<T1, R> {
public abstract R apply(T1);
public <A> scala.Function1<A, R> compose(scala.Function1<A, T1>);
Code:
0: aload_0
1: aload_1
2: invokestatic #18 // Method scala/Function1$class.compose:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
5: areturn
public <A> scala.Function1<T1, A> andThen(scala.Function1<R, A>);
Code:
0: aload_0
1: aload_1
2: invokestatic #24 // Method scala/Function1$class.andThen:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
5: areturn
public abstract java.lang.String toString();
public int apply$mcII$sp(int);
Code:
0: aload_0
1: iload_1
2: invokestatic #110 // Method scala/Function1$class.apply$mcII$sp:(Lscala/Function1;I)I
5: ireturn
public long apply$mcJI$sp(int);
Code:
0: aload_0
1: iload_1
2: invokestatic #115 // Method scala/Function1$class.apply$mcJI$sp:(Lscala/Function1;I)J
5: lreturn
...
}
% javap -c -classpath /tmp/function 'scala.Function1$mcII$sp'
Compiled from "Function1.scala"
public interface scala.Function1$mcII$sp extends scala.Function1<java.lang.Object, java.lang.Object> {
public java.lang.Object apply(java.lang.Object);
Code:
0: aload_0
1: aload_1
2: invokestatic #16 // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
5: invokeinterface #19, 2 // InterfaceMethod apply:(I)I
10: invokestatic #23 // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
13: areturn
public abstract int apply$mcII$sp(int);
public int apply(int);
Code:
0: aload_0
1: iload_1
2: invokeinterface #30, 2 // InterfaceMethod apply$mcII$sp:(I)I
7: ireturn
}
```
retronym
referenced
this pull request
in retronym/scala
Jul 23, 2015
And do the same for the specialized variants.
Tested by a Java source file that uses lambda syntax to create
instances of generic and specialized `Function{0,1}`.
Here's how the interfaces look now:
```
% javap -c -classpath /tmp/function 'scala.Function1'
Compiled from "Function1.scala"
public interface scala.Function1<T1, R> {
public abstract R apply(T1);
public <A> scala.Function1<A, R> compose(scala.Function1<A, T1>);
Code:
0: aload_0
1: aload_1
2: invokestatic #18 // Method scala/Function1$class.compose:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
5: areturn
public <A> scala.Function1<T1, A> andThen(scala.Function1<R, A>);
Code:
0: aload_0
1: aload_1
2: invokestatic #24 // Method scala/Function1$class.andThen:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
5: areturn
public abstract java.lang.String toString();
public int apply$mcII$sp(int);
Code:
0: aload_0
1: iload_1
2: invokestatic #110 // Method scala/Function1$class.apply$mcII$sp:(Lscala/Function1;I)I
5: ireturn
public long apply$mcJI$sp(int);
Code:
0: aload_0
1: iload_1
2: invokestatic #115 // Method scala/Function1$class.apply$mcJI$sp:(Lscala/Function1;I)J
5: lreturn
...
}
% javap -c -classpath /tmp/function 'scala.Function1$mcII$sp'
Compiled from "Function1.scala"
public interface scala.Function1$mcII$sp extends scala.Function1<java.lang.Object, java.lang.Object> {
public java.lang.Object apply(java.lang.Object);
Code:
0: aload_0
1: aload_1
2: invokestatic #16 // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
5: invokeinterface #19, 2 // InterfaceMethod apply:(I)I
10: invokestatic #23 // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
13: areturn
public abstract int apply$mcII$sp(int);
public int apply(int);
Code:
0: aload_0
1: iload_1
2: invokeinterface #30, 2 // InterfaceMethod apply$mcII$sp:(I)I
7: ireturn
}
```
SethTisue
pushed a commit
to SethTisue/scala
that referenced
this pull request
Aug 7, 2015
And do the same for the specialized variants.
Tested by a Java source file that uses lambda syntax to create
instances of generic and specialized `Function{0,1}`.
Here's how the interfaces look now:
```
% javap -c -classpath /tmp/function 'scala.Function1'
Compiled from "Function1.scala"
public interface scala.Function1<T1, R> {
public abstract R apply(T1);
public <A> scala.Function1<A, R> compose(scala.Function1<A, T1>);
Code:
0: aload_0
1: aload_1
2: invokestatic scala#18 // Method scala/Function1$class.compose:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
5: areturn
public <A> scala.Function1<T1, A> andThen(scala.Function1<R, A>);
Code:
0: aload_0
1: aload_1
2: invokestatic scala#24 // Method scala/Function1$class.andThen:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
5: areturn
public abstract java.lang.String toString();
public int apply$mcII$sp(int);
Code:
0: aload_0
1: iload_1
2: invokestatic scala#110 // Method scala/Function1$class.apply$mcII$sp:(Lscala/Function1;I)I
5: ireturn
public long apply$mcJI$sp(int);
Code:
0: aload_0
1: iload_1
2: invokestatic scala#115 // Method scala/Function1$class.apply$mcJI$sp:(Lscala/Function1;I)J
5: lreturn
...
}
% javap -c -classpath /tmp/function 'scala.Function1$mcII$sp'
Compiled from "Function1.scala"
public interface scala.Function1$mcII$sp extends scala.Function1<java.lang.Object, java.lang.Object> {
public java.lang.Object apply(java.lang.Object);
Code:
0: aload_0
1: aload_1
2: invokestatic scala#16 // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
5: invokeinterface scala#19, 2 // InterfaceMethod apply:(I)I
10: invokestatic scala#23 // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
13: areturn
public abstract int apply$mcII$sp(int);
public int apply(int);
Code:
0: aload_0
1: iload_1
2: invokeinterface scala#30, 2 // InterfaceMethod apply$mcII$sp:(I)I
7: ireturn
}
```
adriaanm
pushed a commit
that referenced
this pull request
Mar 31, 2016
Rather than in implementation of the abstract method in the
expanded anonymous class.
This leads to more more efficient use of the constant pool,
code shapes more amenable to SAM inlining, and is compatible
with the old behaviour of `-Xexperimental` in Scala 2.11,
which ScalaJS now relies upon.
Manual test:
```
scala> :paste -raw
// Entering paste mode (ctrl-D to finish)
package p1; trait T { val x = 0; def apply(): Any }; class DelambdafyInline { def t: T = (() => "") }
// Exiting paste mode, now interpreting.
scala> :javap -c p1.DelambdafyInline
Compiled from "<pastie>"
public class p1.DelambdafyInline {
public p1.T t();
Code:
0: new #10 // class p1/DelambdafyInline$$anonfun$t$1
3: dup
4: aload_0
5: invokespecial #16 // Method p1/DelambdafyInline$$anonfun$t$1."<init>":(Lp1/DelambdafyInline;)V
8: areturn
public final java.lang.Object p1$DelambdafyInline$$$anonfun$1();
Code:
0: ldc #22 // String
2: areturn
public p1.DelambdafyInline();
Code:
0: aload_0
1: invokespecial #25 // Method java/lang/Object."<init>":()V
4: return
}
scala> :javap -c p1.DelambdafyInline$$anonfun$t$1
Compiled from "<pastie>"
public final class p1.DelambdafyInline$$anonfun$t$1 implements p1.T,scala.Serializable {
public static final long serialVersionUID;
public int x();
Code:
0: aload_0
1: getfield #25 // Field x:I
4: ireturn
public void p1$T$_setter_$x_$eq(int);
Code:
0: aload_0
1: iload_1
2: putfield #25 // Field x:I
5: return
public final java.lang.Object apply();
Code:
0: aload_0
1: getfield #34 // Field $outer:Lp1/DelambdafyInline;
4: invokevirtual #37 // Method p1/DelambdafyInline.p1$DelambdafyInline$$$anonfun$1:()Ljava/lang/Object;
7: areturn
public p1.DelambdafyInline$$anonfun$t$1(p1.DelambdafyInline);
Code:
0: aload_1
1: ifnonnull 6
4: aconst_null
5: athrow
6: aload_0
7: aload_1
8: putfield #34 // Field $outer:Lp1/DelambdafyInline;
11: aload_0
12: invokespecial #42 // Method java/lang/Object."<init>":()V
15: aload_0
16: invokespecial #45 // Method p1/T.$init$:()V
19: return
}
scala> :quit
```
Adriaan is to `git blame` for `reflection-mem-typecheck.scala`.
OlivierBlanvillain
pushed a commit
to OlivierBlanvillain/scala
that referenced
this pull request
Jun 27, 2017
Remove more name ops
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Partially fixes SI-4658. NumericRange stays slow, thanks to the brilliant idea that Numeric doesn't need a division operation.
Some notes:
ifinstead ofmatchbecause I was not sure if there is a difference in performance especially with the work on the new pattern matcher.(len.toLong * (head + last) / 2)instead of(len.toLong * (head.toLong + last) / 2)because I couldn't find a situation in which working with a Long here avoided an overflow error in the result. (There are no inputs wherehead + lastwould overflow but the result wouldn't.) The first one is more or less "overflow error compatible" to the slow O(n) way, while the second one produces different overflow errors. The only case where it avoided an overflow error was in Ranges with a single element, but the code before catches this, thanks to notnoop spotting it (Makes Range#sum an O(1) operation instead of an O(n) one. legacy-svn-scala#83).