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

Jump to bottom

Iterator.single and Iterator.++ when used together are very slow #7316

Closed
scabug opened this issue Mar 30, 2013 · 3 comments
Closed

Iterator.single and Iterator.++ when used together are very slow #7316

scabug opened this issue Mar 30, 2013 · 3 comments
Assignees
@paulp
Milestone
2.11.0-M3

Comments

@scabug
Copy link

scabug commented Mar 30, 2013

Consider the following code:

def iterate(n: Int): Iterator[Int] = Iterator.single(n) ++ (if (n == 0) Iterator.empty else iterate(n-1))

def time[T](label: String)(thunk: => T): T = {
	val start = System.currentTimeMillis
	val result = thunk
	val end = System.currentTimeMillis
	println(s"$label took ${end-start} ms")
	result
}

for (n <- 0 to 2000 by 200) {
	time(s"iterate($n)") {
		iterate(n).foreach(_ => ())
	}
}

when run I get:

$ scala iterate.scala 
iterate(0) took 1 ms
iterate(200) took 9 ms
iterate(400) took 27 ms
iterate(600) took 96 ms
iterate(800) took 237 ms
iterate(1000) took 475 ms
iterate(1200) took 834 ms
iterate(1400) took 1360 ms
iterate(1600) took 2123 ms
iterate(1800) took 3091 ms
iterate(2000) took 4078 ms

One would expect linear increase of the time we need to iterate all elements returned by iterate method. I didn't dig deeper to understand why this code is so slow but I decided to log a ticket instead. Original inspiration for this code comes from scala/scala#2331
@scabug
Copy link
Author

scabug commented Mar 30, 2013

Imported From: https://issues.scala-lang.org/browse/SI-7316?orig=1
Reporter: @gkossakowski
Affected Versions: 2.10.1

@scabug
Copy link
Author

scabug commented Apr 8, 2013

@retronym said:
Seems like Paul got this one at the second swing, in scala/scala@e3ddb2d.

I don't want to add an ad-hoc and potentially brittle performance test for this. I do lament the lack of a place to write and run a real test. What became of scala-meter?

~/code/scala RUNNER=scala scala-hash e3ddb2d~1 -nc sandbox/t7316.scala
[info] e3ddb2d~1 => /Users/jason/usr/scala-v2.11.0-M2-43-g59d4998
iterate(0) took 1 ms
iterate(200) took 8 ms
iterate(400) took 28 ms
iterate(600) took 97 ms
iterate(800) took 255 ms
iterate(1000) took 505 ms
iterate(1200) took 851 ms
iterate(1400) took 1390 ms
iterate(1600) took 2079 ms
iterate(1800) took 3080 ms
iterate(2000) took 4155 ms
ticket/7335 ~/code/scala RUNNER=scala scala-hash e3ddb2d -nc sandbox/t7316.scala
[info] e3ddb2d => /Users/jason/usr/scala-v2.11.0-M2-44-ge3ddb2d
iterate(0) took 1 ms
iterate(200) took 5 ms
iterate(400) took 1 ms
iterate(600) took 3 ms
iterate(800) took 3 ms
iterate(1000) took 6 ms
iterate(1200) took 7 ms
iterate(1400) took 9 ms
iterate(1600) took 11 ms
iterate(1800) took 14 ms
iterate(2000) took 16 ms

@scabug scabug closed this as completed Apr 8, 2013
@scabug
Copy link
Author

scabug commented Apr 8, 2013

@paulp said:
That's funny; that was the FIRST swing! I knew that commit did something useful, but what it didn't do was fix the issue I was after, which was fixed (for the purposes of util.TreeSet) in 61308be6dc. But it seemed to leave the underlying Iterator issue unaddressed.

@scabug scabug added this to the 2.11.0-M3 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@paulp paulp

Labels
None yet
Projects
None yet
Milestone
2.11.0-M3
Development

No branches or pull requests
2 participants
@paulp @scabug