Optimised implementation of List.filter/filterNot #5653

mkeskells · 2017-01-18T19:24:57Z

No description provided.

Ichoran · 2017-01-18T20:17:46Z

I agree that this kind of strategy seems like it should be an optimization, but have you tested with microbenchmarking? The concern is that it's pretty complicated code, and that sometimes can result in less effective optimization and thus worse performance for the majority of cases.

rorygraves · 2017-01-18T20:33:12Z

@Ichoran I have, I need to tidy up the my benchmark code and share it - for this kind of work I agree that we need to demonstrate the performance/complexity tradeoff.

Ichoran · 2017-01-18T20:41:08Z

Well, I won't make the same comment on every PR, but I am thinking the same thing on each one, so maybe you can update them all.

som-snytt · 2017-01-18T22:04:14Z

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

@@ -405,6 +405,90 @@ sealed abstract class List[+A] extends AbstractSeq[A]
  // Create a proxy for Java serialization that allows us to avoid mutation
  // during de-serialization.  This is the Serialization Proxy Pattern.
  protected final def writeReplace(): AnyRef = new List.SerializationProxy(this)
+
+  override def filter(p: A => Boolean): List[A] = filterImpl(p, isFlipped = false)


Mima has the last word. Apparently, return type should be TraversableLike.this.Self.

Thanks @som-snytt - will sort this out over the weekend.

@som-snytt My type foo is not strong enough - I can't work out what the correct type signature here looks like - any hints greatly appreciated

Me neither, apparently it makes no diff. Sorry about that. The current filter is on AbstractTraversable. You always get both sigs, returning Object and List, when you define it on List, because that's what Self is.

retronym · 2017-01-20T02:29:20Z

@rorygraves My benchmark linked and described over in #5650 (comment) might serve as an example for your benchmark for this PR.

rorygraves · 2017-01-20T07:12:57Z

@retronym Thanks - will add one over the weekend.

rorygraves · 2017-01-22T18:54:57Z

@retronym I've added a benchmark - I will run it on a stable machine this evening and post the results.

szeiger · 2017-01-25T12:44:05Z

I don't think there is a correct type signature that would make this work in a forward binary compatible way. The old version gets filter from AbstractTraversable where it only returns Object:

$ javap -cp /Users/szeiger/.ivy2/cache/org.scala-lang/scala-library/jars/scala-library-2.11.0.jar scala.collection.AbstractTraversable|grep filter
  public java.lang.Object filter(scala.Function1);
  public java.lang.Object filterNot(scala.Function1);

The new version with the overrides has:

$ javap -cp . scala.collection.immutable.List | grep filter
  public scala.collection.immutable.List<A> filter(scala.Function1<A, java.lang.Object>);
  public scala.collection.immutable.List<A> filterNot(scala.Function1<A, java.lang.Object>);
  public java.lang.Object filterNot(scala.Function1);
  public java.lang.Object filter(scala.Function1);

The return type is statically known to be List when overriding in List, so you get the new signature with bridge methods for the Object-returning versions. You cannot declare it in a way that erases to Object because Scala knows it has to be List.

som-snytt · 2017-01-25T18:18:53Z

Here's a mindless refactor to a trait:

https://github.com/som-snytt/scala/blob/review/2.11.x_filter_opt/src/library/scala/collection/immutable/FilteredTraversable.scala

where

https://github.com/som-snytt/scala/blob/review/2.11.x_filter_opt/src/library/scala/collection/immutable/List.scala#L89

then

apm@mara:~/clones/review/scalac_perf$ ./build/pack/bin/scala -Dscala.color 
Welcome to Scala 2.11.9-20170122-174149-73222c7 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_111).
Type in expressions for evaluation. Or try :help.

scala> :javap -public scala.collection.immutable.List#filter
  public java.lang.Object filter(scala.Function1);

scala>

rorygraves · 2017-01-25T18:22:05Z

Thanks @som-snytt (and @szeiger ) I will look at this in a couple of hours.

rorygraves · 2017-01-25T21:49:11Z

@som-snytt Thats for your input and suggestions - hopefully this will pass MIMA.
@retronym Thanks for the example benchmarks.

Below are the benchmarks for the attached changes.
There are a couple of cases where I expect to see a speedup and dont - and will investigate further, but in general I think this is good to merge.

With changes

[info] Benchmark                        (size)  Mode  Cnt      Score     Error  Units
[info] ListBenchmark.filter_exc_last         0  avgt   20      2.423 ±   0.001  ns/op
[info] ListBenchmark.filter_exc_last         1  avgt   20      3.745 ±   0.003  ns/op
[info] ListBenchmark.filter_exc_last        10  avgt   20    136.421 ±   2.594  ns/op
[info] ListBenchmark.filter_exc_last       100  avgt   20   1298.372 ±   8.424  ns/op
[info] ListBenchmark.filter_exc_last      1000  avgt   20  13131.800 ± 118.335  ns/op
[info] ListBenchmark.filter_exc_mid          0  avgt   20      2.433 ±   0.009  ns/op
[info] ListBenchmark.filter_exc_mid          1  avgt   20      3.757 ±   0.014  ns/op
[info] ListBenchmark.filter_exc_mid         10  avgt   20     46.475 ±   0.277  ns/op
[info] ListBenchmark.filter_exc_mid        100  avgt   20    416.364 ±   1.590  ns/op
[info] ListBenchmark.filter_exc_mid       1000  avgt   20   3804.188 ± 145.257  ns/op
[info] ListBenchmark.filter_excludeAll       0  avgt   20      2.422 ±   0.001  ns/op
[info] ListBenchmark.filter_excludeAll       1  avgt   20      3.602 ±   0.001  ns/op
[info] ListBenchmark.filter_excludeAll      10  avgt   20     14.295 ±   0.004  ns/op
[info] ListBenchmark.filter_excludeAll     100  avgt   20    165.181 ±   0.187  ns/op
[info] ListBenchmark.filter_excludeAll    1000  avgt   20   2199.272 ±  79.980  ns/op
[info] ListBenchmark.filter_from_mid         0  avgt   20      2.422 ±   0.001  ns/op
[info] ListBenchmark.filter_from_mid         1  avgt   20      3.354 ±   0.017  ns/op
[info] ListBenchmark.filter_from_mid        10  avgt   20     45.298 ±   0.182  ns/op
[info] ListBenchmark.filter_from_mid       100  avgt   20    402.474 ±   2.106  ns/op
[info] ListBenchmark.filter_from_mid      1000  avgt   20   3828.923 ±  96.946  ns/op
[info] ListBenchmark.filter_includeAll       0  avgt   20      2.422 ±   0.001  ns/op
[info] ListBenchmark.filter_includeAll       1  avgt   20      2.830 ±   0.001  ns/op
[info] ListBenchmark.filter_includeAll      10  avgt   20     14.583 ±   0.032  ns/op
[info] ListBenchmark.filter_includeAll     100  avgt   20    189.767 ±   0.057  ns/op
[info] ListBenchmark.filter_includeAll    1000  avgt   20   2272.429 ±   1.820  ns/op
[info] ListBenchmark.filter_only_last        0  avgt   20      2.422 ±   0.001  ns/op
[info] ListBenchmark.filter_only_last        1  avgt   20      3.351 ±   0.002  ns/op
[info] ListBenchmark.filter_only_last       10  avgt   20     21.394 ±   0.009  ns/op
[info] ListBenchmark.filter_only_last      100  avgt   20    194.980 ±   0.603  ns/op
[info] ListBenchmark.filter_only_last     1000  avgt   20   2219.157 ±   3.691  ns/op

Before changes:

[info] Benchmark                        (size)  Mode  Cnt      Score     Error  Units
[info] ListBenchmark.filter_exc_last         0  avgt   20     15.285 ±   0.045  ns/op
[info] ListBenchmark.filter_exc_last         1  avgt   20     16.945 ±   0.394  ns/op
[info] ListBenchmark.filter_exc_last        10  avgt   20    213.614 ±   0.480  ns/op
[info] ListBenchmark.filter_exc_last       100  avgt   20   1896.310 ±  10.929  ns/op
[info] ListBenchmark.filter_exc_last      1000  avgt   20  19747.893 ± 243.361  ns/op
[info] ListBenchmark.filter_exc_mid          0  avgt   20     15.554 ±   0.051  ns/op
[info] ListBenchmark.filter_exc_mid          1  avgt   20     16.688 ±   0.140  ns/op
[info] ListBenchmark.filter_exc_mid         10  avgt   20    201.408 ±   0.762  ns/op
[info] ListBenchmark.filter_exc_mid        100  avgt   20   1995.707 ±   5.595  ns/op
[info] ListBenchmark.filter_exc_mid       1000  avgt   20  19805.543 ±  42.047  ns/op
[info] ListBenchmark.filter_excludeAll       0  avgt   20     15.443 ±   0.082  ns/op
[info] ListBenchmark.filter_excludeAll       1  avgt   20     16.758 ±   0.065  ns/op
[info] ListBenchmark.filter_excludeAll      10  avgt   20     30.629 ±   0.114  ns/op
[info] ListBenchmark.filter_excludeAll     100  avgt   20    205.645 ±   0.524  ns/op
[info] ListBenchmark.filter_excludeAll    1000  avgt   20   1998.409 ±  34.507  ns/op
[info] ListBenchmark.filter_from_mid         0  avgt   20     15.343 ±   0.073  ns/op
[info] ListBenchmark.filter_from_mid         1  avgt   20     33.028 ±   0.723  ns/op
[info] ListBenchmark.filter_from_mid        10  avgt   20    147.669 ±   0.423  ns/op
[info] ListBenchmark.filter_from_mid       100  avgt   20   1180.650 ±  20.477  ns/op
[info] ListBenchmark.filter_from_mid      1000  avgt   20  11357.762 ± 177.352  ns/op
[info] ListBenchmark.filter_includeAll       0  avgt   20     15.427 ±   0.065  ns/op
[info] ListBenchmark.filter_includeAll       1  avgt   20     32.480 ±   0.918  ns/op
[info] ListBenchmark.filter_includeAll      10  avgt   20    212.435 ±   0.965  ns/op
[info] ListBenchmark.filter_includeAll     100  avgt   20   1900.766 ±   3.264  ns/op
[info] ListBenchmark.filter_includeAll    1000  avgt   20  17941.353 ±  38.941  ns/op
[info] ListBenchmark.filter_only_last        0  avgt   20     15.399 ±   0.144  ns/op
[info] ListBenchmark.filter_only_last        1  avgt   20     33.348 ±   0.394  ns/op
[info] ListBenchmark.filter_only_last       10  avgt   20     41.587 ±   0.148  ns/op
[info] ListBenchmark.filter_only_last      100  avgt   20    246.962 ±   1.266  ns/op
[info] ListBenchmark.filter_only_last     1000  avgt   20   2248.106 ±  18.818  ns/op

retronym · 2017-01-25T22:35:46Z

BTW, if the primary goal here is compiler performance, and you've identified a hot path using List#filter (perhaps Transformer#transformStats?), another alternative is to put a List specific version of filter in trait Collections and call that. I've done that in the past with mapList. The next major release of Scala included those optimization in List#map.

rorygraves · 2017-01-26T08:07:08Z

@retronym The compiler performance was definitely the target - it seemed nice to fix the generic performance whilst I was there. I will look at moving it to collections - thanks

szeiger · 2017-01-26T15:17:10Z

@som-snytt Nice trick. I hadn't considered moving the overrides to a separate trait.

rorygraves · 2017-01-26T15:26:33Z

Unfortunately it means hat he basic list performance does not improve. I guess this will always break MIMA does that mean the change as is could never go in (until 2.13) might be moot if 2.13 rewrites all he collections anyway.

szeiger · 2017-01-26T15:31:01Z

It's still a worthwhile change for 2.13.x. We're changing the design of the collections library but we will rely heavily on the existing implementations, so any change that adds a more efficient implementation of a collection method for a specific collection type is useful.

szeiger · 2017-01-26T15:37:39Z

@rorygraves Did you run benchmarks for the new binary compatible version? Is it slower than the original one?

rorygraves · 2017-01-26T15:49:03Z

The updated ones are similar to the above, but MIMA still fails after the change. I updated my gist which I can't post right now

szeiger · 2017-01-26T16:59:39Z

Oh, right, it still fails. I didn't pay attention to the fact that this is the 2.11.x branch where we don't run all tests and accumulate the errors. The errors are different though:

[info] Checking forward binary compatibility
Found 4 binary incompatibilities (57 were filtered out)
=======================================================
 * the type hierarchy of object scala.collection.immutable.Nil is different
   in current version. Missing types
   {scala.collection.immutable.FilteredTraversable}
 * trait scala.collection.immutable.FilteredTraversable does not have a
   correspondent in current version
 * the type hierarchy of class scala.collection.immutable.List is different
   in current version. Missing types
   {scala.collection.immutable.FilteredTraversable}
 * the type hierarchy of class scala.collection.immutable.:: is different in
   current version. Missing types
   {scala.collection.immutable.FilteredTraversable}

These are caused by FilteredTraversable being public at the JVM level. There is no way to define a JVM-level package-private trait in Scala.

I'm not sure whether we should accept such a change. It is forward binary compatible for any Scala code compiled against the newer version but not for Java code (which could exploit the fact that FilteredTraversable is public).

adriaanm · 2017-01-26T18:52:20Z

Let's change the name so it ends in 'Internal'. If no one else objects, I'm fine whitelisting it then.

rorygraves · 2017-01-26T18:53:40Z

@adriaanm That I can do :)

rorygraves · 2017-01-26T22:10:17Z

@adriaanm Updated trait name as suggested - have not updated MIMA rules as I was unsure how to do that.

som-snytt · 2017-01-26T23:14:22Z

This morning I looked at the actual test failures. One is just an update due to List's parents. But maybe the symbol forcing test means something substantial? It looks like something happens out of order with the change. The test uses scope.sorted.filter but I didn't dig deep. (Because it's a work day.)

szeiger · 2017-01-27T14:49:39Z

The change is in the ordering of

    definitions.ScalaValueClassesNoUnit
    definitions.ScalaValueClasses

in JavaUniverseForce. These two entries are reversed in the new version according to t6240-universe-code-gen. The sort order is defined as:

  trait MemberScopeApi extends ScopeApi {
    /** Sorts the symbols included in this scope so that:
     *    1) Symbols appear in the linearization order of their owners.
     *    2) Symbols with the same owner appear in same order of their declarations.
     *    3) Synthetic members (e.g. getters/setters for vals/vars) might appear in arbitrary order.
     */
    def sorted: List[Symbol]
  }

It looks like the change is simply due to the changed order of declaration. In fact, merely adding these overrides to List

  override def filter(p: A => Boolean): Self = super.filter(p)
  override def filterNot(p: A => Boolean): Self = super.filterNot(p)

without FilteredTraversableInternal or any new implementation will trigger it as well.

adriaanm · 2017-01-28T19:09:42Z

I'm preparing a PR to consolidate the three PRs currently open and address the remaining bureaucratic mima/test issues ;-) (See #5664)

adriaanm · 2017-02-02T18:47:16Z

Commits moved to #5664. Thanks!

scala-jenkins added this to the 2.11.9 milestone Jan 18, 2017

som-snytt reviewed Jan 18, 2017

View reviewed changes

rorygraves force-pushed the 2.11.x_filter_opt branch from 389a532 to 73222c7 Compare January 22, 2017 17:49

rorygraves force-pushed the 2.11.x_filter_opt branch from 73222c7 to e12844f Compare January 25, 2017 20:59

rorygraves force-pushed the 2.11.x_filter_opt branch from e12844f to 0ec7228 Compare January 26, 2017 21:04

Optimised implementation of List.filter/filterNot

c03811b

rorygraves force-pushed the 2.11.x_filter_opt branch from 0ec7228 to c03811b Compare January 26, 2017 21:06

adriaanm mentioned this pull request Jan 28, 2017

Optimise common operations on Array and List #5664

Merged

adriaanm closed this Feb 2, 2017

SethTisue removed this from the 2.11.9 milestone Feb 17, 2017

rorygraves deleted the 2.11.x_filter_opt branch March 5, 2017 18:23

lrytz mentioned this pull request Apr 3, 2017

Revert #5664 because the binary incompatible change leaks via erasure #5821

Merged

retronym mentioned this pull request Jul 17, 2019

[backport] List.filter optimizations from 2.13.x #8226

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Optimised implementation of List.filter/filterNot #5653

Optimised implementation of List.filter/filterNot #5653

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Optimised implementation of List.filter/filterNot #5653

Optimised implementation of List.filter/filterNot #5653

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!