8000 Optimised implementation of List.filter/filterNot · scala/scala@eb5c513 · GitHub
[go: up one dir, main page]
Skip to content

Commit eb5c513

Browse files
rorygravesadriaanm
rorygraves
authored and
adriaanm
committed
Optimised implementation of List.filter/filterNot
1 parent d540bf0 commit eb5c513

File tree

6 files changed

+185
-5
lines changed

6 files changed

+185
-5
lines changed

‎bincompat-forward.whitelist.conf

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -924,6 +924,23 @@ filter {
924924
{
925925
matchName="scala.collection.mutable.ArrayOps#ofFloat.emptyImpl"
926926
problemName=DirectMissingMethodProblem
927+
},
928+
// introduce FilteredTraversableInternal
929+
{
930+
matchName="scala.collection.immutable.Nil$"
931+
problemName=MissingTypesProblem
932+
},
933+
{
934+
matchName="scala.collection.immutable.FilteredTraversableInternal"
935+
problemName=MissingClassProblem
936+
},
937+
{
938+
matchName="scala.collection.immutable.List"
939+
problemName=MissingTypesProblem
940+
},
941+
{
942+
matchName="scala.collection.immutable.$colon$colon"
943+
problemName=MissingTypesProblem
927944
}
928945
]
929946
}

‎src/library/scala/collection/immutable/FilteredTraversableInternal.scala

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
/* __ *\
2+
** ________ ___ / / ___ Scala API **
3+
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
4+
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
5+
** /____/\___/_/ |_/____/_/ | | **
6+
** |/ **
7+
\* */
8+
9+
package scala
10+
package collection
11+
package immutable
12+
13+
import scala.annotation.tailrec
14+
15+
/**
16+
* Optimised filter functions for List
17+
* n.b. this is an internal class to help maintain compatibility and should not be used directly.
18+
*/
19+
private[immutable] trait FilteredTraversableInternal[+A, +Repr <: AnyRef with TraversableLike[A, Repr]] extends TraversableLike[A, Repr] {
20+
21+
// Optimized for List
22+
23+
override def filter(p: A => Boolean): Self = filterImpl(p, isFlipped = false)
24+
25+
override def filterNot(p: A => Boolean): Self = filterImpl(p, isFlipped = true)
26+
27+
private[this] def filterImpl(p: A => Boolean, isFlipped: Boolean): Self = {
28+
29+
// everything seen so far so far is not included
30+
@tailrec def noneIn(l: Repr): Repr = {
31+
if (l.isEmpty)
32+
Nil.asInstanceOf[Repr]
33+
else {
34+
val h = l.head
35+
val t = l.tail
36+
if (p(h) != isFlipped)
37+
allIn(l, t)
38+
else
39+
noneIn(t)
40+
}
41+
}
42+
43+
// everything from 'start' is included, if everything from this point is in we can return the origin
44+
// start otherwise if we discover an element that is out we must create a new partial list.
45+
@tailrec def allIn(start: Repr, remaining: Repr): Repr = {
46+
if (remaining.isEmpty)
47+
start
48+
else {
49+
val x = remaining.head
50+
if (p(x) != isFlipped)
51+
allIn(start, remaining.tail)
52+
else
53+
partialFill(start, remaining)
54+
}
55+
}
56+
57+
// we have seen elements that should be included then one that should be excluded, start building
58+
def partialFill(origStart: Repr, firstMiss: Repr): Repr = {
59+
val newHead = new ::(origStart.head, Nil)
60+
var toProcess = origStart.tail
61+
var currentLast = newHead
62+
63+
// we know that all elements are :: until at least firstMiss.tail
64+
while (!(toProcess eq firstMiss)) {
65+
val newElem = new ::(toProcess.head, Nil)
66+
currentLast.tl = newElem
67+
currentLast = newElem
68+
toProcess = toProcess.tail
69+
}
70+
71+
// at this point newHead points to a list which is a duplicate of all the 'in' elements up to the first miss.
72+
// currentLast is the last element in that list.
73+
74+
// now we are going to try and share as much of the tail as we can, only moving elements across when we have to.
75+
var next = firstMiss.tail
76+
var nextToCopy = next // the next element we would need to copy to our list if we cant share.
77+
while (!next.isEmpty) {
78+
// generally recommended is next.isNonEmpty but this incurs an extra method call.
79+
val head: A = next.head
80+
if (p(head) != isFlipped) {
81+
next = next.tail
82+
} else {
83+
// its not a match - do we have outstanding elements?
84+
while (!(nextToCopy eq next)) {
85+
val newElem = new ::(nextToCopy.head, Nil)
86+
currentLast.tl = newElem
87+
currentLast = newElem
88+
nextToCopy = nextToCopy.tail
89+
}
90+
nextToCopy = next.tail
91+
next = next.tail
92+
}
93+
}
94+
95+
// we have remaining elements - they are unchanged attach them to the end
96+
if (!nextToCopy.isEmpty)
97+
currentLast.tl = nextToCopy.asInstanceOf[List[A]]
98+
99+
newHead.asInstanceOf[Repr]
100+
}
101+
102+
noneIn(repr)
103+
}
104+
}

‎src/library/scala/collection/immutable/List.scala

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@ sealed abstract class List[+A] extends AbstractSeq[A]
8686
with Product
8787
with GenericTraversableTemplate[A, List]
8888
with LinearSeqOptimized[A, List[A]]
89+
with FilteredTraversableInternal[A, List[A]]
8990
with Serializable {
9091
override def companion: GenericCompanion[List] = List
9192

@@ -416,6 +417,7 @@ sealed abstract class List[+A] extends AbstractSeq[A]
416417
// Create a proxy for Java serialization that allows us to avoid mutation
417418
// during de-serialization. This is the Serialization Proxy Pattern.
418419
protected final def writeReplace(): AnyRef = new List.SerializationProxy(this)
420+
419421
}
420422

421423
/** The empty list.

‎src/reflect/scala/reflect/runtime/JavaUniverseForce.scala

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -442,8 +442,8 @@ trait JavaUniverseForce { self: runtime.JavaUniverse =>
442442
definitions.DoubleTpe
443443
definitions.BooleanTpe
444444
definitions.ScalaNumericValueClasses
445-
definitions.ScalaValueClassesNoUnit
446445
definitions.ScalaValueClasses
446+
definitions.ScalaValueClassesNoUnit
447447

448448
uncurry.VarargsSymbolAttachment
449449
uncurry.DesugaredParameterType

‎test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package scala.collection.immutable
2+
3+
import java.util.concurrent.TimeUnit
4+
5+
import org.openjdk.jmh.annotations._
6+
7+
object ListBenchmark {
8+
case class Content(value: Int)
9+
}
10+
11+
@BenchmarkMode(Array(Mode.AverageTime))
12+
@Fork(2)
13+
@Threads(1)
14+
@Warmup(iterations = 10)
15+
@Measurement(iterations = 10)
16+
@OutputTimeUnit(TimeUnit.NANOSECONDS)
17+
@State(Scope.Benchmark)
18+
class ListBenchmark {
19+
import ListBenchmark._
20+
@Param(Array("0", "1", "10", "100", "1000"))
21+
var size: Int = _
22+
23+
var values: List[Content] = _
24+
var mid: Content = _
25+
var last: Content = _
26+
27+
28+
@Setup(Level.Trial) def initKeys(): Unit = {
29+
values = List.tabulate(size)(v => Content(v))
30+
mid = Content(size / 2)
31+
last = Content(Math.max(0,size -1))
32+
}
33+
34+
@Benchmark def filter_includeAll: Any = {
35+
values.filter(v => true)
36+
}
37+
38+
@Benchmark def filter_excludeAll: Any = {
39+
values.filter(_ => false)
40+
}
41+
42+
@Benchmark def filter_exc_mid: Any = {
43+
values.filter(v => v.value != mid.value)
44+
}
45+
46+
@Benchmark def filter_from_mid: Any = {
47+
values.filter(v => v.value <= mid.value)
48+
}
49+
50+
@Benchmark def filter_exc_last: Any = {
51+
values.filter(v => v.value != last.value)
52+
}
53+
54+
@Benchmark def filter_only_last: Any = {
55+
values.filter(v => v.value == last.value)
56+
}
57+
}

‎test/files/run/repl-colon-type.check

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,7 @@ TypeRef(
7575
)
7676
TypeRef(
7777
TypeSymbol(
78-
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
78+
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
7979

8080
)
8181
args = List(
@@ -142,7 +142,7 @@ TypeRef(
142142
args = List(
143143
TypeRef(
144144
TypeSymbol(
145-
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
145+
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
146146

147147
)
148148
args = List(
@@ -175,7 +175,7 @@ PolyType(
175175
args = List(
176176
TypeRef(
177177
TypeSymbol(
178-
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
178+
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
179179

180180
)
181181
args = List(TypeParamTypeRef(TypeParam(T <: AnyVal)))
@@ -198,7 +198,7 @@ PolyType(
198198
params = List(TermSymbol(x: T), TermSymbol(y: List[U]))
199199
resultType = TypeRef(
200200
TypeSymbol(
201-
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with Serializable
201+
sealed abstract class List[+A] extends AbstractSeq[A] with LinearSeq[A] with Product with GenericTraversableTemplate[A,List] with LinearSeqOptimized[A,List[A]] with FilteredTraversableInternal[A,List[A]] with Serializable
202202

203203
)
204204
args = List(TypeParamTypeRef(TypeParam(U >: T)))

0 commit comments

Comments
 (0)
0