List optimizations for List.from, ::: and prependedAll#8601
List optimizations for List.from, ::: and prependedAll#8601szeiger merged 1 commit intoscala:2.13.xfrom
Conversation
8602022 to
186739d
Compare
e0fb2a3 to
15f729b
Compare
|
I've pushed an optimization of |
|
For those benchmarks, could you also show the |
|
@diesalbla results were too big to post inline, you can see them here though: https://gist.github.com/joshlemer/63ea43be7cdd57c7b5cf605b5d8eebdb |
|
thanks. The results indicate no changes for the |
|
@diesalbla yeah that's right. That's kinda confusing though, why there aren't any savings for |
|
what's the reason for the huge speedup vs I feel like it would be better to fix |
|
|
||
| @Test def colonColonColon(): Unit = { | ||
|
|
||
| assertEquals(Nil, Nil ::: Nil) |
There was a problem hiding this comment.
it may be worth adding some assertNonAllocating on the appropriate cases
There was a problem hiding this comment.
I'm not familiar with this method, what's the import? Or are you saying I could implement it?
There was a problem hiding this comment.
I misremembered the name - its just nonAllocating
see HashSetTest
your test class needs to extend scala.tools.testing.AllocationTest
then you can call
def nonAllocating[T: Manifest](fn: => T)(implicit execution: AllocationExecution = AllocationExecution()): T
def onlyAllocates[T: Manifest](size: Int)(fn: => T)(implicit execution: AllocationExecution = AllocationExecution()): T
so you can get tests like this (in HashSetTest)
@Test
def nonAllocatingEqualsNotShared(): Unit = {
val base = generate()
val notShared = generate()
assertTrue(nonAllocating {
base == notShared
})
assertTrue(nonAllocating {
notShared == base
})
}
@NthPortal this seems like a reasonable suggestion 😄 . Might not get to that for a few days though. |
|
@NthPortal I tried this implementation of override final def addAll(xs: IterableOnce[A]): this.type = {
val it = xs.iterator
if (it.hasNext) {
ensureUnaliased()
val last1 = new ::[A](it.next(), Nil)
var _last0 = last0
var _len = len + 1
if (_len == 1) first = last1 else _last0.next = last1
_last0 = last1
while (it.hasNext) {
val last1 = new ::[A](it.next(), Nil)
_last0.next = last1
_last0 = last1
_len += 1
}
last0 = _last0
len = _len
}
this
} |
|
hmm, oh well. was worth a shot I guess. I don't have any other ideas as to why it's so much worse |
|
It looks like this is ready to merge. Is there anything you still want to change? In case of |
eea23af to
2169dd6
Compare
Optimize List#prependedAll Optimize List.from Property tests for List.from, ::: and prependedAll
2169dd6 to
55821d5
Compare
|
@SethTisue This would be a really excellent speedup to include in 2.13.2 if possible |
|
Stefan's out of commission at the moment, but it seems plausible he'll have time for a final review/merge here in time for 2.13.2 |
List optimizations for List.from, ::: and prependedAll
List optimizations for List.from, ::: and prependedAll
::::ListBuffer, andlist.iteratorobjects, and also avoid doing extra work in ListBuffer's++=method such asensureUnaliased()calls andthis.last0 = ...; this.size += ...;updates etc.prependedAll:prependedAllwill also copy all ofthissince thesuper.prependedAllimplementation is:This PR avoids that extra copying by doing a similar approach to the
:::algorithm.Also note: This is the method that underlies list concatenation (
++/concat/appendedAll)Benchmarks
code:
this branch:
2.13.x:
TODO
Write more property/unit tests for
:::andprependedAllBenchmark more thoroughly with more forks and iterations and