New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

List#tails and Stream#tails are extremely inefficient #9892

Closed
scabug opened this Issue Aug 16, 2016 · 13 comments

Comments

Projects
None yet
5 participants
@scabug
Copy link

scabug commented Aug 16, 2016

List#tails inherits its implementation from TraversableLike which creates lots of new Lists:

val ts = List(1,2,3).tails.toList
ts(0).tail eq ts(1) // false
@scabug

This comment has been minimized.

Copy link
Author

scabug commented Aug 16, 2016

Imported From: https://issues.scala-lang.org/browse/SI-9892?orig=1
Reporter: @soc
Affected Versions: 2.10.6, 2.11.8, 2.12.0-M5

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Aug 16, 2016

@SethTisue said:
nice catch!

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Aug 27, 2016

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Sep 29, 2016

@SethTisue said:
submitted against 2.12 branch — did you want this in 2.11.9?

@scabug

This comment has been minimized.

Copy link
Author

scabug commented Apr 4, 2017

@SethTisue said:
The PR was abandoned. Would someone else like to pick this one up...?

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented May 8, 2017

note that in the abandoned PR, it came up that Stream has the same bug

@SethTisue SethTisue changed the title List#tails is extremely inefficient List#tails and Stream#tails are extremely inefficient May 8, 2017

@Ichoran

This comment has been minimized.

Copy link

Ichoran commented May 8, 2017

Which probably means that Queue and LinkedListMap and so on are also all suspect.

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented May 31, 2017

some rough initial wip on this at SethTisue/scala@b8614e8, from the Scala open source spree, Copenhagen 2017. to my collaborator on this: sorry I had to leave so abruptly, I didn't catch your name?

it seemed to us, in the time we had, that there was no need to do one thing in TraversableLike and a different thing in LinearSeq/List/Stream, the implementation in TraversableLike should just be fixed to not do its own building with a newBuilder. just call .tail and let it copy or not as it sees fit. the only problem is getting the types to line up (the wip commit deals with this only awkwardly/badly)

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Sep 28, 2017

scala/scala#5950 fixes it at the LinearSeqOptimized level rather than trying for the TraversableLike fix. this could be revisited in the 2.13 collections

@SethTisue SethTisue removed quickfix labels Feb 5, 2018

@pyrocto pyrocto referenced this issue Apr 27, 2018

Merged

RHOL-306: Support for bundle #615

3 of 3 tasks complete
@xuwei-k

This comment has been minimized.

Copy link

xuwei-k commented Aug 11, 2018

this could be revisited in the 2.13 collections

Let's close this? Should we add tests?

Welcome to Scala 2.13.0-M4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_181).
Type in expressions for evaluation. Or try :help.

scala> val list = List(1, 2, 3).tails.toList
list: List[List[Int]] = List(List(1, 2, 3), List(2, 3), List(3), List())

scala> list(0).tail eq list(1)
res0: Boolean = true

scala> val lazyList = LazyList(1, 2, 3).tails.to(LazyList)
lazyList: scala.collection.immutable.LazyList[scala.collection.immutable.LazyList[Int]] = LazyList(_, ?)

scala> lazyList(0).tail eq lazyList(1)
res1: Boolean = true
@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Aug 11, 2018

scala/scala#5950 included tests, so I think it was just inadvertent that this ticket wasn't closed when that was merged

@SethTisue SethTisue modified the milestones: Backlog, 2.12.5 Aug 11, 2018

@SethTisue SethTisue closed this Aug 11, 2018

@SethTisue

This comment has been minimized.

Copy link
Member

SethTisue commented Aug 11, 2018

@hodga after accepting my invitation to https://github.com/orgs/scala/teams/contributors, comment here, and I'll assign this ticket to you

@hodga

This comment has been minimized.

Copy link

hodga commented Aug 11, 2018

@SethTisue I accepted the invitation :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment