Suggested new construct for tight code

Language Design
1

If you have an algorithm that is already O(n^2), that’s already bad. But if your inner loop creates new objects that need to be garbage-collected, that’s terrible! Here’s a suggestion how we could help both the programmer and the compiler to deal with tight loops by introducing a new construct that restricts a block of code such that no new objects must be created.

fun doSomething() {
   val stuff = Stuff() // new object, OK, outside tight block
   tight {
      val arr = stuff.data // getter must be tight, otherwise compiler error here
      for (i in stuff.start ..< stuff.size) {
         for (j in something.start ..< something.size) {
            arr[i] = compute(i, j) // compute marked tight (see below)
         }
      }
   }
}
tight fun compute(i: Int, j: Int) = TODO()

Inside the tight{} block, Kotlin code is restricted:

  • It must not create any new objects on the Heap, whether explicitly nor implicitly; the Kotlin compiler must guarantee this
  • Compiler error if you’re trying to create a new object inside the tight block (helps the programmer)
  • It tells the compiler that this code should be particularly optimised for speed (more aggressive optimization)
  • It must not call any functions except Kotlin language functions that are known to be “tight”, or functions that are marked to be “tight”, or functions that the compiler can infer to be tight

The tight keyword marks a function to be tight:

  • The entire body of such a function must be tight
  • Functions that are marked like this may be called from another tight function or tight block
  • Functions that are not marked to be tight may only be called from another tight function or tight block if the compiler can infer that the function is tight (e.g. a getter that returns a value and no side-effects).

What do you think? I would appreciate this, because Kotlin is my language of choice, and I’m using it for game programming and other areas where other people would probably prefer C++.

2

I think that looks like a terrible idea. it would pollute Kotlin even more than it already is.

1 Like
3

Interesting idea. But I’m not sure it’s possible — in the JVM case, at least.

The Java runtime has got pretty clever. If it can determine that a heap allocation is never visible outside the block/thread, then it can shift it to a stack allocation instead. And some allocations could be optimised away entirely. So you can’t always be sure that code isn’t ‘tight’.

(And conversely, I think almost any code can end up allocating heap space if e.g. it throws an Error. Though of course that should be rare.)

So I don’t think any new compiler keyword can give a firm guarantee on the JVM either way. And of course other platforms have different characteristics anyway.

It might be possible to provide a looser guarantee, in a similar way to the tailrec keyword. (Though this would probably be an annotation rather than a new keyword.) But would that be sufficiently useful?

(Ultimately, if you need strong guarantees, a dynamic platform like the JVM might not be a good match for your requirements.)

2 Likes
4

First of all, the compiler should do the optimisations. We (humans) would be in the business of writing clear code.

if you really don’t want to use allocations, then write your code not to use allocations in tight loops and pre-allocate before you enter the tight loop.

And agreed with giddy said on the string guarantees, use c or c++ if you need something better guaranteed.

2 Likes