Iterator termination


#1

I've always loved the syntax of using "for..in" loops for iteration. However, I've found that historically there's been a hole in the way languages use iterator objects. That is, there's no notification to the iterator object that it's been terminated. Places where this becomes a problem is in areas like games where you have to avoid producing garbage, so ideally you'd reuse your iterator objects. If the iterator objects only have a maintenance condition (next) and no termination condition, they have no opportunity to free themselves back to a pool.

I don’t really have a proposed solution, but thought I’d pose the problem to see what smarter people than myself think about it.


#2

In C#, iterators (Enumerators there) have special behavior when used in foreach. If iterator implements resource-control interface (IDisposable in C#), it's Dispose method will be called in finally block when loop finishes, either by exhausting iterator or by early return or exception. This is core aspect of C# language, and some language constructs like yield/await depend on it.

Note, that compiler cannot statically decide if given iterator implements IDisposable (or Closable/AutoClosable in JVM), because you can pass some PooledIterator as just Iterator around. Hence, runtime type check is required for every loop generated by compiler.

Whether Kotlin will or will not implement this behavior is to be decided.


#3

I must be missing something as I don't understand why try with resources and AutoClosable is not the correct thing to do here on the jvm.  

Specifically, you’d want to close the resources whether you finished iteration or if some error occured before then (and it didn’t get to finish iteration) … so to me this should not be about ‘finishing the iteration’ but about ‘leaving the try with resources block’.  Otherwise you’d leak resources when exceptions occured etc.

What am I missing? … I guess I need to have a play with ‘try with resources’ in Kotlin.

Cheers, Rob.


#4

Ok, I think I get it.  

Something like an ‘enhanced for loop’ that always calls close() on an AutoClosable iterator … and does so without needing to use a closure.

With some imaginary ‘forWithClose’ …

  // Always close the elements iterator when   // exiting this forWithClose loop ...   forWithClose(Element elements) {   // do something with each element   element.sayHi()   }

The alternative being to use a function that does the try with resources and takes a closure.


#5

Have you proven with a benchmark that you need to do iterator pooling?

In theory, short lived objects like iterators don’t cost very much on modern JVMs. Whether this is really true or not, I could not say, as I have not written a game in java.


#6

yes, with games, creating the iterator objects in your game loop will make garbage collection necessary, and every few seconds you will see a hiccup. It's not necessary for applications. Producing any amount of garbage in your game loop will eventually cause a collection, if the collection is very infrequent, you won't notice the stutter, but if it's happening every few seconds then it's very noticeable. The iterator objects themselves aren't enough to care, but every little bit of litter leads to the garbage man cometh :)

LibGdx handles this by preventing nested iterators and swapping between two final objects, invalidating one when the other is taken. I was hoping to figure out a way to keep allowing nesting but not producing garbage, I couldn’t think of a way though without knowing when they’re no longer used.


#7

what if you added a static extension to iterator, so you're always calling dispose, but only the ones that implement it will do anything?


#8

Can you explain what do you mean by "static extension"?


#9

I was thinking about how Extension Functions work in Kotlin. (I haven't used them yet, so I might be misunderstanding some things)

 
fun foo() {
  val t = Foo()
  t.dispose() // If dispose is implemented in Foo, "Implemented", if it isn't, "Extension"
}

class Foo {
  fun dispose() {
  println(“Implemented”)
  }
}
fun Foo.dispose() {
  println(“Extension”)
}

So my line of thought is just that-- If Extension Functions can understand whether or not a method is implemented, why couldn't for loops?


#10

Well, no. Extension functions vs instance are decided at compile time, not run-time and they are based on the type known at the point of invocation, i.e. they are not polymorphic.


#11

Ah, I see. So if the extension function is on Iterator, then an implementation of Iterator wouldn't be able to 'override' that extension function. That makes sense.

Thanks for the dialog, it seems like a tricky problem.


#12

Basically, you cannot solve it using library with "for" statement, because current bytecode generated by compiler for a "for" statement doesn't signal any exit out of the loop.

But you can do it with a little bit of DSL:

 
trait PooledIterator<T> : Iterator<T> {
    fun dispose()
}

inline fun <T> Iterable<T>.pooledFor(body: (T) -> Unit) {
  val iterator = iterator()
  try {
  while (iterator.hasNext()) {
           body(iterator.next())
  }
  } finally {
  if (iterator is PooledIterator) iterator.dispose()
  }
}

fun gamePart(names: Iterable<String>) {
  names.pooledFor { name ->
  // use name
  }
}


#13

Yeah, I was thinking about that solution.

I especially like the “fun gamePart”.


#14

In theory, objects that don't survive the young generation should be effectively free to collect. But the JVM is very susceptible to GC performance tuning. It can't figure out the right settings by itself. What I've read is, you should always try experimenting with the GC settings before making big efforts to avoid short lived garbage. Especially as the JVM has been able to do escape analysis for a while now. Things like iterators which do not escape should (in theory) be stack allocated.

Of course all this assumes HotSpot. If you are targeting Dalvik or some other very weak JVM then yes, avoiding garbage is the only way.


#15

At the moment I'm not doing anything 'real' with Kotlin, I'm only studying it, partly in anticipation of LWJGL's move to it, but also because I'm chomping at the bit for a good language that I can share code cross-platform and in a browser. Kotlin isn't quite there yet, but it's getting close. So I am targeting Dalvik, but also JavaScript. I didn't know that the JVM could avoid allocation with short term objects, that's interesting, I have some reading to do. If you have any reference recommendations I'd love to dig into them.


#16

I like the inline function approach, however it got a little funky with the syntax

You can no longer break out of the loop, so your body() has to return a boolean indicating whether or not to continue. Then if you’re using it within a closure it doesn’t seem like you can return anywhere other than the end of the closure.

 
Test fun iterate() {
   val l = LinkedList<Int>()
   l.addAll(1, 2, 3, 4, 5)
   l.iterate { i ->
      println(i)
      l.iterate { j ->
         println("  $j")
         j < 2
      }
      true
   }
   println("done")
}

The result seems nice, no garbage, and able to do nested iteration, but the syntax to me is awkward. For example, I find it unclear that j < 2 is the maintenance condition of that inner loop.


#17

It's not really a big deal, it's just a small friction point I've had with LibGDX and was wondering if there's new magic in Kotlin that gets around it. Easy to work around if you know the explicit type of object.


#18

We have a feature in the roadmap – "non-local break and continue" – that is supposed to address exactly this, i.e. break or continue the loop that is in containing inline function. It is not implemented yet, and we are still collecting use-cases for it.

Could you please add your thoughts and experience here for future reference: https://youtrack.jetbrains.com/issue/KT-1436


#19

Replying to old posts

  • Thanks for this feature, non-local break and continue has been very useful.