| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
| |
- Language imports are preceding other imports
- Deleted empty file: InlineErasure
- Removed some unused private[parallel] methods in
scala/collection/parallel/package.scala
This removes hundreds of warnings when compiling with
"-Xlint -Ywarn-dead-code -Ywarn-unused -Ywarn-unused-import".
|
| |
|
|
|
|
|
|
| |
only trivial merge conflicts here.
not dealing with PR #4333 in this merge because there is a substantial
conflict there -- so that's why I stopped at
63daba33ae99471175e9d7b20792324615f5999b for now
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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) }
}
```
|
| |
|
|
|
|
|
|
| |
because the code uses '==' instead of 'equiv'
== instead of equiv (from Ordering) was used by mistake. Fixed.
Also created a test to make sure that == is not used by throwing an exception if it is (as suggested by Jason).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Some names I missed in 55b609458fd .
How one might know when one is done:
mkdir scratch && cd scratch
mkdir annotation beans collection compat concurrent io \
math parallel ref reflect runtime scala sys testing \
text tools util xml
scalac $(find ../src/library -name '*.scala')
Until recently that would fail with about a billion errors. When it
compiles, that's when you're done. And that's where this commit
takes us, for src/library at least.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Before 2.10 we had a notion of ClassManifest that could be used to retain
erasures of abstract types (type parameters, abstract type members) for
being used at runtime.
With the advent of ClassManifest (and its subtype Manifest)
it became possible to write:
def mkGenericArray[T: Manifest] = Array[T]()
When compiling array instantiation, scalac would use a ClassManifest
implicit parameter from scope (in this case, provided by a context bound)
to remember Ts that have been passed to invoke mkGenericArray and
use that information to instantiate arrays at runtime (via Java reflection).
When redesigning manifests into what is now known as type tags, we decided
to explore a notion of ArrayTags that would stand for abstract and pure array
creators. Sure, ClassManifests were perfectly fine for this job, but they did
too much - technically speaking, one doesn't necessarily need a java.lang.Class
to create an array. Depending on a platform, e.g. within JavaScript runtime,
one would want to use a different mechanism.
As tempting as this idea was, it has also proven to be problematic.
First, it created an extra abstraction inside the compiler. Along with class tags
and type tags, we had a third flavor of tags - array tags. This has threaded the
additional complexity though implicits and typers.
Second, consequently, when redesigning tags multiple times over the course of
Scala 2.10.0 development, we had to carry this extra abstraction with us, which
exacerbated the overall feeling towards array tags.
Finally, array tags didn't fit into the naming scheme we had for tags.
Both class tags and type tags sound logical, because, they are descriptors for
the things they are supposed to tag, according to their names.
However array tags are the odd ones, because they don't actually tag any arrays.
As funny as it might sound, the naming problem was the last straw
that made us do away with the array tags. Hence this commit.
|
| |
|
|
|
|
| |
All tags and reflection-related stuff requires a prefix,
be it scala.reflect for simple tags (ArrayTags and ClassTags),
or scala.reflect.basis/scala.reflect.runtime.universe for type tags.
|
| |
|
|
|
| |
* all usages of ClassManifest and Manifest are replaced with tags
* all manifest tests are replaced with tag tests
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
| |
Reducing the sbt launcher footprint by eliminating val references
which go through the scala package object, since they lead to
otherwise unnecessary classes becoming required at startup. Mostly
this means library files with constructors like "Iterator.empty" or
"Stream.continually" receive a direct import of that companion. The one
slightly less than cosmetic change was moving the strange xml value
"$scope" back into Predef, because otherwise I have to touch the xml
code generation. No review.
|
| |
|
|
|
|
|
| |
Added implicits to create Orderings from java's Comparable and
Comparator interfaces. Also some cleanup in Sorting. Review by
community.
|
| |
|
|
|
| |
Removed more than 3400 svn '$Id' keywords and related junk.
|
| |
|
|
|
| |
Some library reorganization I discussed with martin. No review.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
rewriting the Sorting methods to accept Orderings and adding a sorted
method to SeqLike, because we should all be pretty tired of writing
".sortWith(_ < _)" by now. I think it should be called "sort", not
"sorted", but that refuses to coexist gracefully with the deprecated
sort in List.
Review by moors (chosen pretty arbitrarily, someone at epfl should
review it but I don't know who deserves the nomination.)
|
| |
|
|
|
|
| |
Fixed a number of faulty Scaladoc comments in library and compiler
sources. No review.
|
| |
|
|
|
|
|
| |
object, updating some @deprecated messages to give realistic
alternatives, properly resolving the semantic mismatch between List.--
and diff, its once-recommended but inequivalent alternative.
|
| |
|
|
|
|
|
| |
added manifests to most parts of standard library which deal with
arrays. One test is temporarily disabled, as it shows a deep problem
with multi-dimensional arrays (which was present all along).
|
| |
|
|
|
| |
removed deprecated warning, updated svn props, cleaned up code
|
| | |
|
| | |
|
| |
|
|
|
|
| |
commented some lines in Sorting.scala (they where only for testing)
which doesn't compile in .NET.
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
