Avoid allocations of reusable CanBuildFroms by mkeskells · Pull Request #8467 · scala/scala

mkeskells · 2019-10-14T20:51:25Z

(For 2.12.x's eyes only.)

Use vals to cache a single instance of stateless CanBuildFrom instances.
These are cast by the existing implicit def to the suitable generic
type. This pattern was already used in some places -- this PR applies
it systematically across collection.{mutable,immutable}.

The CanBuildFrom instances for arrays and wrapped arrays are
cached for each primitive type, Unit, and Object. Each of these
instances is backed by a dedicated subclass of CanBuildFrom that
avoids subsequent dispatch on the ClassTag[T].

src/library/scala/collection/mutable/WrappedArray.scala

src/library/scala/Array.scala

src/library/scala/collection/TraversableView.scala

sjrd · 2019-10-14T21:47:18Z

src/library/scala/Array.scala

-  implicit def canBuildFrom[T](implicit t: ClassTag[T]): CanBuildFrom[Array[_], T, Array[T]] =
+  implicit def canBuildFrom[T](implicit t: ClassTag[T]): CanBuildFrom[Array[_], T, Array[T]] = {
+    val tag = implicitly[ClassTag[T]]
+    (tag.runtimeClass match {


Is this match really an improvement on the JVM? Because at least on JS this is going to be detrimental.

its a saving on the allocation of the CanBuildFrom, not the CPU

previously a use of a CBF would switch on the runtime class twice for each array, this changes it it 3 times. If its really an issue then we can specialise the code for each case and reduce to calls to one for each usage

what is the measured effect on JS? If so its already an issue

Well in JS de can entirely stack allocate the CanBuildFrom and the ArrayBuilder down to completely eliminating them and constant-folding the ClassTags. We can do that because they are new instances. If they first switch to fetch an existing instance on the heap, we don't know what's in the heap and we can't constant-fold its members.

But I realized that we already override Array.scala with our own implementation to achieve this. So I guess the change in this PR won't affect us. At least not beyond the fact that it widens the gap between the JVM and the JS implementation of the library.

Also, on the JVM, it is best to first switch on tag.runtimeClass.isPrimitive to have a fast path for non-primitive cases.

@sjrd I'd be open to keeping an private[scala] final val isScalaJS = false constant in the library if that would help you avoid copy/paste. You could recompile with that constant flipped and get the original code here, for example.

I did consider the isPrimitive check, but wanted to discuss.
Will rework, but it should also apply in other cases. There seem to be 9 locations to apply this

I see that @retronym fixed these

sjrd · 2019-10-14T21:50:50Z

src/library/scala/collection/mutable/WrappedArray.scala

-  implicit def canBuildFrom[T](implicit m: ClassTag[T]): CanBuildFrom[WrappedArray[_], T, WrappedArray[T]] =
+  implicit def canBuildFrom[T](implicit m: ClassTag[T]): CanBuildFrom[WrappedArray[_], T, WrappedArray[T]] = {
+    val tag = implicitly[ClassTag[T]]
+    (tag.runtimeClass match {


Same question: is this really an improvement?

same answer

src/library/scala/Array.scala

src/library/scala/collection/mutable/HashSet.scala

src/reflect/mima-filters/2.12.0.forwards.excludes

(For 2.12.x's eyes only.) Use vals to cache a single instance of stateless CanBuildFrom instances. These are cast by the existing `implicit def` to the suitable generic type. This pattern was already used in some places -- this PR applies it systematically across `collection.{mutable,immutable}`. The `CanBuildFrom` instances for arrays and wrapped arrays are cached for each primitive type, Unit, and Object. Each of these instances is backed by a dedicated subclass of CanBuildFrom that avoids subsequent dispatch on the `ClassTag[T]`.

The with AnyRef idiom avoids a cast.

retronym

Approving of the idea. We should get another set of 👀 to review this as I was involved in the code change as well.

hrhino

Looks great! I'd like Stefan's opinion, too.

mkeskells · 2019-10-31T06:20:18Z

@retronym thanks for progressing this PR ⭐️

src/library/scala/Array.scala

retronym · 2019-11-19T06:29:31Z

paging @szeiger for a look at this one. I'm happy with the PR myself.

src/library/scala/Array.scala

src/library/scala/collection/BitSet.scala

src/library/scala/collection/TraversableView.scala

src/library/scala/collection/IterableView.scala

src/library/scala/collection/mutable/WrappedArray.scala

order matches in expected frequency order (Array, WrappedArray + associated builders, and ClassTag.newArray) avoid extra def in BitSets don't optimise for NoBuilder cases

szeiger

Other than the remaining unnecessary forwarders this looks good.

szeiger · 2019-12-02T17:09:16Z

src/library/scala/collection/immutable/BitSet.scala

  /** $bitsetCanBuildFrom */
-  implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
+  implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = ReusableCBF
+  private[this] val ReusableCBF = bitsetCanBuildFrom


Here's another case where we don't need a new val. All monomorphic ones can use val canBuildFrom.

szeiger · 2019-12-02T17:10:01Z

src/library/scala/collection/immutable/WrappedString.scala

+  implicit def canBuildFrom: CanBuildFrom[WrappedString, Char, WrappedString] =
+    ReusableCBF.asInstanceOf[CanBuildFrom[WrappedString, Char, WrappedString]]
+  private[this] val ReusableCBF = new CanBuildFrom[WrappedString, Char, WrappedString] {
    def apply(from: WrappedString) = newBuilder


This one, too

szeiger · 2019-12-02T17:10:26Z

src/library/scala/collection/mutable/BitSet.scala

  /** $bitsetCanBuildFrom */
-  implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
+  implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = ReusableCBF
+  private[this] val ReusableCBF = bitsetCanBuildFrom


another one

use direct vals where no casting is required

scala-jenkins added this to the 2.12.11 milestone Oct 14, 2019

hrhino previously requested changes Oct 14, 2019

View reviewed changes

src/library/scala/collection/mutable/WrappedArray.scala Outdated Show resolved Hide resolved

src/library/scala/Array.scala Outdated Show resolved Hide resolved

mkeskells force-pushed the mike/2.12_CanBuildFrom branch from c5ff417 to f8b5889 Compare October 14, 2019 21:43

hrhino reviewed Oct 14, 2019

View reviewed changes

src/library/scala/collection/TraversableView.scala Outdated Show resolved Hide resolved

src/library/scala/collection/TraversableView.scala Outdated Show resolved Hide resolved

sjrd reviewed Oct 14, 2019

View reviewed changes

retronym reviewed Oct 15, 2019

View reviewed changes

src/library/scala/Array.scala Outdated Show resolved Hide resolved

retronym reviewed Oct 15, 2019

View reviewed changes

src/library/scala/collection/mutable/HashSet.scala Show resolved Hide resolved

hrhino reviewed Oct 15, 2019

View reviewed changes

src/reflect/mima-filters/2.12.0.forwards.excludes Outdated Show resolved Hide resolved

retronym force-pushed the mike/2.12_CanBuildFrom branch 3 times, most recently from 969337c to 9e956b8 Compare October 21, 2019 04:50

retronym force-pushed the mike/2.12_CanBuildFrom branch from 58fb28d to b6ba518 Compare October 31, 2019 00:58

retronym changed the title ~~use val for CanBuildFrom where possible~~ Avoid allocations of reusable CanBuildFroms Oct 31, 2019

retronym approved these changes Oct 31, 2019

View reviewed changes

retronym requested a review from szeiger October 31, 2019 01:01

hrhino approved these changes Oct 31, 2019

View reviewed changes

hrhino reviewed Oct 31, 2019

View reviewed changes

src/library/scala/Array.scala Outdated Show resolved Hide resolved

diesalbla added the library:collections PRs involving changes to the standard collection library label Oct 31, 2019

use existing ClassTag

f986e03

SethTisue added the performance:do_not_allocate Changes to avoid object allocations label Nov 11, 2019

lrytz assigned szeiger Nov 19, 2019

szeiger reviewed Nov 27, 2019

View reviewed changes

mkeskells force-pushed the mike/2.12_CanBuildFrom branch 2 times, most recently from 7935399 to 89bff62 Compare December 1, 2019 22:54

review comments

18bf349

order matches in expected frequency order (Array, WrappedArray + associated builders, and ClassTag.newArray) avoid extra def in BitSets don't optimise for NoBuilder cases

mkeskells force-pushed the mike/2.12_CanBuildFrom branch from 89bff62 to 18bf349 Compare December 1, 2019 23:09

szeiger approved these changes Dec 2, 2019

View reviewed changes

review comments

f9d9136

use direct vals where no casting is required

szeiger merged commit de3451d into scala:2.12.x Dec 5, 2019

mkeskells mentioned this pull request Dec 6, 2019

[nomerge] optimise the addition of immutable HashMap #8466

Merged

lrytz added performance the need for speed. usually compiler performance, sometimes runtime performance. and removed performance:do_not_allocate Changes to avoid object allocations labels Mar 16, 2020

Conversation

mkeskells commented Oct 14, 2019 • edited by retronym Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

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!

mkeskells Oct 14, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

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!

retronym Oct 15, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

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!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

retronym left a comment

Choose a reason for hiding this comment

Uh oh!

hrhino left a comment

Choose a reason for hiding this comment

Uh oh!

mkeskells commented Oct 31, 2019

Uh oh!

Uh oh!

retronym commented Nov 19, 2019

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

szeiger left a comment

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!

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!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

9 participants

mkeskells commented Oct 14, 2019 •

edited by retronym

Loading

mkeskells Oct 14, 2019 •

edited

Loading

retronym Oct 15, 2019 •

edited

Loading