Skip to content
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
Closed

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

scabug opened this issue Aug 16, 2016 · 13 comments

Comments

@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
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
Copy link
Author

scabug commented Aug 16, 2016

@SethTisue said:
nice catch!

@scabug
Copy link
Author

scabug commented Aug 27, 2016

@soc said:
scala/scala#5363

@scabug
Copy link
Author

scabug commented Sep 29, 2016

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

@scabug
Copy link
Author

scabug commented Apr 4, 2017

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

@SethTisue
Copy link
Member

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
Copy link

Ichoran commented May 8, 2017

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

@SethTisue
Copy link
Member

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
Copy link
Member

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

@xuwei-k
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
Copy link
Member

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
Copy link
Member

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

@hodga
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
Projects
None yet
Development

No branches or pull requests

5 participants