| Commit message (Collapse) | Author | Age | Files | Lines |
|\
| |
| | |
SI-4147 Add an implementation of `mutable.TreeMap`
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
This commit contains an implementation of a mutable red-black tree with focus on performance. It also contains a new `mutable.TreeMap` Scala collection that is backed by the aforementioned tree. The common generic factories and traits related to mutable sorted maps didn't exist yet, so this commit also adds them.
Regarding performance, `TreeMap` overrides (from `MapLike` and `SortedMapLike`) all of the most common methods for maps and also those whose default implementations are asymptotically worse than direct red-black tree algorithms (e.g. `last`, `clear`).
The `rangeImpl` method of `TreeMap` returns an instance of `TreeMapView`, an inner class of `TreeMap`. This view is backed by the same `RedBlackTree.Tree` instance, and therefore changes to the original map are reflected in the view and vice-versa. The semantics of mutating a view by adding and removing keys outside the view's range are the same of the current `mutable.TreeSet`. A bit less focus was given on the performance of views - in particular, getting the `size` of a `TreeMapView` is O(n) on the number of elements inside the view bounds. That can be improved in the future.
In a future commit, `mutable.TreeSet` can be changed to be backed by this red-black tree implementation.
|
|\ \
| | |
| | | |
Documentation for split [ci: last-only]
|
| |/
| |
| |
| |
| |
| | |
Reverts to calling String.split(re: String), but change escape to
always put us on the JDK7 fast-path if possible, which is for everything
but Chars representing surrogate codeunits
|
|\ \
| |/
|/| |
|
| |\
| | |
| | | |
Fix 25 typos (g-i)
|
| | | |
|
| |\ \
| | | |
| | | | |
SI-9206 Fix REPL code indentation
|
| | | |
| | | |
| | | |
| | | | |
But sans test.
|
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
To make code in error messages line up with the original line of
code, templated code is indented by the width of the prompt.
Use the raw prompt (without ANSI escapes or newlines) to determine
the indentation.
Also, indent only once per line.
|
| |\ \ \
| | |_|/
| |/| | |
SI-9359 Fix InnerClass entry flags for nested Java enums
|
| | | | |
|
| | |/
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
The access flags in InnerClass entries for nested Java enums were
basically completely off.
A first step is to use the recently introduced backend method
`javaClassfileFlags`, which is now moved to BCodeAsmCommon.
See its doc for an explanation.
Then the flags of the enum class symbol were off. An enum is
- final if none of its values has a class body
- abstract if it has an abstract method
(https://docs.oracle.com/javase/specs/jls/se7/html/jls-8.html#jls-8.9)
When using the ClassfileParser:
- ENUM was never added. I guess that's just an oversight.
- ABSTRACT (together with SEALED) was always added. This is to
enable exhaustiveness checking, see 3f7b8b5. This is a hack and we
have to go through the class members in the backend to find out if
the enum actually has the `ACC_ABSTRACT` flag or not.
When using the JavaParser:
- FINAL was never added.
- ABSTRACT was never added.
This commit fixes all of the above and tests cases (Java enum read
from the classfile and from source).
|
| |/ |
|
| |\
| | |
| | | |
Fix some typos (a-c)
|
| | |
| | |
| | |
| | |
| | |
| | | |
I just used text search to check whether there are no more typos like
these corrected by janekdb, and by the way fixed also some other ones
which I saw.
|
| | | |
|
| |\ \
| | |/
| |/| |
Fix illegal inlining of instructions accessing protected members
|
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
There were two issues in the new inliner that would cause a
VerifyError and an IllegalAccessError.
First, an access to a public member of package protected class C can
only be inlined if the destination class can access C. This is tested
by t7582b.
Second, an access to a protected member requires the receiver object
to be a subtype of the class where the instruction is located. So
when inlining such an access, we need to know the type of the receiver
object - which we don't have. Therefore we don't inline in this case
for now. This can be fixed once we have a type propagation analyis.
https://github.com/scala-opt/scala/issues/13.
This case is tested by t2106.
Force kmpSliceSearch test to delambdafy:inline
See discussion on https://github.com/scala/scala/pull/4505. The issue
will go away when moving to indy-lambda.
|
| |\ \
| | | |
| | | | |
fix BigDecimal losing MathContext
|
| | | | |
|
| | | | |
|
| | | | |
|
| |\ \ \
| | | | |
| | | | | |
SI-9356 more careful assertion in back-end
|
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
Calling `exists` on a `Symbol` triggers unpickling,
which failed for reasons I did not investigate.
Replaced `sym.exists` by `sym != NoSymbol`, which is good enough here.
Also replaced assertion by a `devWarning`, since the
logic seems too ad-hoc to actually crash the compiler when it's invalidated.
Partially reverts b45a91fe22. See also #1532.
|
| |\ \ \ \
| | | | | |
| | | | | | |
SI-9348 Fix missing last element in exclusive floating point ranges
|
| | |/ / /
| | | | |
| | | | |
| | | | |
| | | | | |
Fix exclusive floating point ranges to contain also the last element
when the end-start difference is not an integer multiple of step.
|
| |\ \ \ \
| | |/ / /
| |/| | | |
Fix toolbox with varargs constructors
|
| | | | |
| | | | |
| | | | |
| | | | | |
It was already working for methods, but not for constructors.
|
| |\ \ \ \
| | | | | |
| | | | | | |
Clean implementation of sorts for scala.util.Sorting.
|
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
Removed code based on Sun JDK sorts and implemented new (basic) sorts from
scratch. Deferred to Java Arrays.sort whenever practical. Behavior of
`scala.util.Sorting` should be unchanged, but changed documentation to
specify when the Java methods are being used (as they're typically very fast).
A JUnit test is provided.
Performance is important for sorts. Everything is better with this patch,
though it could be better yet, as described below.
Below are sort times (in microseconds, SEM < 5%) for various 1024-element
arrays of small case classes that compare on an int field (quickSort), or
int arrays that use custom ordering (stableSort). Note: "degenerate"
means there are only 16 values possible, so there are lots of ties.
Times are all with fresh data (no re-using cache from run to run).
Results:
```
random sorted reverse degenerate big:64k tiny:16
Old Sorting.quickSort 234 181 178 103 25,700 1.4
New Sorting.quickSort 170 27 115 74 18,600 0.8
Old Sorting.stableSort 321 234 236 282 32,600 2.1
New Sorting.stableSort 239 16 194 194 25,100 1.2
java.util.Arrays.sort 124 4 8 105 13,500 0.8
java.util.Arrays.sort|Box 126 15 13 112 13,200 0.9
```
The new versions are uniformly faster, but uniformly slower than Java sorting. scala.util.Sorting has use cases that don't map easily in to Java unless everything is pre-boxed, but the overhead of pre-boxing is minimal compared to the sort.
A snapshot of some of my benchmarking code is below.
(Yes, lots of repeating myself--it's dangerous not to when trying to get
somewhat accurate benchmarks.)
```
import java.util.Arrays
import java.util.Comparator
import math.Ordering
import util.Sorting
import reflect.ClassTag
val th = ichi.bench.Thyme.warmed()
case class N(i: Int, j: Int) {}
val a = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt, i)) )
var ai = 0
val b = Array.fill(1024)( Array.tabulate(1024)(i => N(i, i)) )
var bi = 0
val c = Array.fill(1024)( Array.tabulate(1024)(i => N(1024-i, i)) )
var ci = 0
val d = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt(16), i)) )
var di = 0
val e = Array.fill(16)( Array.tabulate(65536)(i => N(util.Random.nextInt, i)) )
var ei = 0
val f = Array.fill(65535)( Array.tabulate(16)(i => N(util.Random.nextInt, i)) )
var fi = 0
val o = new Ordering[N]{ def compare(a: N, b: N) = if (a.i < b.i) -1 else if (a.i > b.i) 1 else 0 }
for (s <- Seq("one", "two", "three")) {
println(s)
th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Sorting.quickSort(x)(o); x(x.length/3) }
}
def ix(ns: Array[N]) = {
val is = new Array[Int](ns.length)
var i = 0
while (i < ns.length) {
is(i) = ns(i).i
i += 1
}
is
}
val p = new Ordering[Int]{ def compare(a: Int, b: Int) = if (a > b) 1 else if (a < b) -1 else 0 }
for (s <- Seq("one", "two", "three")) {
println(s)
val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
th.pbench{ val x = ix(a(ai)); ai = (ai+1)%a.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(b(bi)); bi = (bi+1)%b.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(c(ci)); ci = (ci+1)%c.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(d(di)); di = (di+1)%d.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(e(ei)); ei = (ei+1)%e.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(f(fi)); fi = (fi+1)%f.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
}
for (s <- Seq("one", "two", "three")) {
println(s)
th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Arrays.sort(x, o); x(x.length/3) }
}
def bx(is: Array[Int]): Array[java.lang.Integer] = {
val Is = new Array[java.lang.Integer](is.length)
var i = 0
while (i < is.length) {
Is(i) = java.lang.Integer.valueOf(is(i))
i += 1
}
Is
}
def xb(Is: Array[java.lang.Integer]): Array[Int] = {
val is = new Array[Int](Is.length)
var i = 0
while (i < is.length) {
is(i) = Is(i).intValue
i += 1
}
is
}
val q = new Comparator[java.lang.Integer]{
def compare(a: java.lang.Integer, b: java.lang.Integer) = o.compare(a.intValue, b.intValue)
}
for (s <- Seq("one", "two", "three")) {
println(s)
val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
th.pbench{ val x = bx(ix(a(ai))); ai = (ai+1)%a.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(b(bi))); bi = (bi+1)%b.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(c(ci))); ci = (ci+1)%c.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(d(di))); di = (di+1)%d.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(e(ei))); ei = (ei+1)%e.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(f(fi))); fi = (fi+1)%f.length; Arrays.sort(x, q); xb(x)(x.length/3) }
}
```
|
| |\ \ \ \ \
| | |_|/ / /
| |/| | | | |
SI-7747 Make REPL wrappers serialization friendly.
|
| | | | | | |
|
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
We only need to introduce the temporary val in the imports
wrapper when we are importing a val or module defined in the REPL.
The test case from the previous commit still passes, but
we are generating slightly simpler code.
Compared to 2.11.6, these two commits result in the following
diff:
https://gist.github.com/retronym/aa4bd3aeef1ab1b85fe9
|
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
Spark has been shipping a forked version of our REPL for
sometime. We have been trying to fold the patches back into
the mainline so they can defork. This is the last outstanding
issue.
Consider this REPL session:
```
scala> val x = StdIn.readInt
scala> class A(a: Int)
scala> serializedAndExecuteRemotely {
() => new A(x)
}
```
As shown by the enclosed test, the REPL, even with the
Spark friendly option `-Yrepl-class-based`, will re-initialize
`x` on the remote system.
This test simulates this by running a REPL session, and then
deserializing the resulting closure into a fresh classloader
based on the class files generated by that session. Before this
patch, it printed "evaluating x" twice.
This is based on the Spark change described:
https://github.com/mesos/spark/pull/535#discussion_r3541925
A followup commit will avoid the `val lineN$read = ` part if we
import classes or type aliases only.
[Original commit from Prashant Sharma, test case from Jason Zaugg]
|
| |\ \ \ \ \
| | | | | | |
| | | | | | | |
Nullness Analysis for GenBCode
|
| | | | | | | |
|
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | | |
Address feedback in #4516 / 57b8da4cd8. Save allocations of
NullnessValue - there's only 4 possible instances. Also save tuple
allocations in InstructionStackEffect.
|
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | | |
When inlining an instance call, the inliner has to ensure that a NPE
is still thrown if the receiver object is null. By using the nullness
analysis, we can avoid emitting this code in case the receiver object
is known to be not-null.
|
| | | |_|_|/
| | |/| | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
Tracks nullness of values using an ASM analyzer.
Tracking nullness requires alias tracking for local variables and
stack values. For example, after an instance call, local variables
that point to the same object as the receiver are treated not-null.
|
| | |_|/ /
| |/| | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
-Xlint:stars-align warns only if elementarity > 0, that is,
if an extracted sequence is not matched entirely by a pattern
sequence, that is, in SLS 8.1.9 on pattern sequences, n = 1
and that pattern is a pattern sequence.
This is still only triggered if productarity > 0, that is,
a non-pattern-sequence pattern is required for the match.
This is a sensitive area because it borders on exhaustiveness
checking: it would be preferable to verify just that the match
is exhaustive, and to emit this warning only if it is not.
|
| |\ \ \ \
| | | | | |
| | | | | | |
SI-9332 Iterator.span exhausts leading iterator
|
| | | |_|/
| | |/| |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
Since the leading and trailing iterators returned by span
share the underlying iterator, the leading iterator must
flag when it is exhausted (when the span predicate fails)
since the trailing iterator will advance the underlying
iterator.
It would also be possible to leave the failing element in
the leading lookahead buffer, where it would forever fail
the predicate, but that entails evaluating the predicate
twice, on both enqueue and dequeue.
|
| |/ / /
| | | |
| | | |
| | | |
| | | | |
This fix is just for the false negative warning. Probably we can skip
setters entirely, but I'm not 100% sure.
|
| |\ \ \
| | | | |
| | | | | |
Fix several tests under GenBCode
|
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
Recently, in 029cce7, I changed uncurry to selectively fallback
to the old method of emitting lambdas when we detect that
`-Ydelambdafy:method`.
The change in classfile names breaks the expectations of
the test `innerClassAttribute`.
This commit changes that test to avoid using specialized
functions, so that under -Ydelambdafy:method all functions
are uniform. This changes a few fresh suffixes for anonymous
class names under both `-Ydelambdafy:{inline,method}`, so the
expectations have been duly updated.
Similarly, I have changed `javaReflection` in the same manner.
Its checkfiles remained unchanged.
|
| | |/ /
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
- private-inline, t8601-closure-elim, inline-in-constructors
- test closure inlining / elimination, which is not yet implemented
in GenBCode. noted in https://github.com/scala-opt/scala/issues/14.
- constant-optimization, t7006
- no constant folding in GenBCode yet.
noted in https://github.com/scala-opt/scala/issues/29.
- patmat_opt_ignore_underscore, patmat_opt_no_nullcheck, patmat_opt_primitive_typetest
- not all optimizations in GenBCode yet.
noted in https://github.com/scala-opt/scala/issues/30.
- t3234
- tests a warning of trait inlining - trait inlining works in
GenBCode
- synchronized
- ignore inliner warnings (they changed a bit)
- t6102
- account for the changed outputo of -Ydebug has under GenBCode
|
| |\ \ \
| | |/ /
| |/| | |
SI-9321 Clarify spec for inheritance of qualified private
|
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
I checked the intent with Martin, who said:
> [...] qualified private members are inherited like other members,
> it’s just that their access is restricted.
I've locked this in with a test as well.
|
| |\ \ \
| | | | |
| | | | | |
SI-9286 Check subclass privates for "same type after erasure"
|