Friday, April 23, 2010

Break Performance

In the Breaks comments there were several questions about the performance of the Scala break command vs the Java break command. So I decided to take a look.

The code for the tests is available on GitHub at: Scala Benchmarks. Feel free to play around with it.

I personally don't think these tests say anything of particular import because they only test how fast the Java break is vs the Scala break without doing any work in the loop. So I don't expect these number would ever been seen in the real world. However that said if you have a tight loop with minimal processing then a Scala break may not be the correct construct to use.

Here is the Java test (labelled JavaSimpleBreak)
  1. int i = 0;
  2. while (i < 10) {
  3.   if(i==1) break;
  4.   i += 1;
  5. }

Here is the Scala test (labelled ScalaSimpleBreak)
  1. var i = 0;
  2. breakable {
  3.   while (i < 10) {
  4.     if(i==1) break;
  5.     i += 1;
  6.   }
  7. }

Out of curiosity I also added a test that created a new Exception each iteration (labelled ScalaException):
  1. var i = 0;
  2.   while (i < 10) {
  3.     if(i==1) throw new Exception();
  4.     i += 1;
  5.   }

And also a test that just throws the same ScalaBreak exception each time. This one is weird since Scala Simple Break also throws the same exception but is much much faster so I think there is something about popping the stack in the example compared to the ScalaSimpleBreak test.
  1. var i = 0;
  2. breakable {
  3. while (i < 10) {
  4. if(i==1) break;
  5. i += 1;
  6. }
  7. }

The results of the tests:

First, don't compare the break tests to the Exception tests. They are sufficiently different to not be worth comparing.
Second, remember that this is a micro benchmark and has very little relationship to reality.

90000000 iterations. Swapping every 90000000 tests
JavaSimpleBreak = 254 (0.0016279129387033098)
ScalaSimpleBreak = 2475 (0.015862537493270438)
ScalaBreakException = 18806 (0.12052964852462379)
ScalaException = 156028 (1.0)

90000000 iterations. Swapping every 500000 tests
JavaSimpleBreak = 772 (0.005138547761203965)
ScalaSimpleBreak = 2351 (0.015648608531853004)
ScalaBreakException = 19346 (0.12876987692778744)
ScalaException = 150237 (1.0)

90000000 iterations. Swapping every 500 tests
JavaSimpleBreak = 790 (0.005242446563543097)
ScalaSimpleBreak = 2247 (0.014911110668710557)
ScalaBreakException = 19213 (0.1274976276270298)
ScalaException = 150693 (1.0)

7 comments:

  1. Thanks! (I was the anonymous poster posting the question first)

    I expected something like this. As far as I know (at least in C++) exceptions are handled by using the corresponding data in the stack frame and doing stack unwinding.

    Break is on the other hand a simple jump (with some popping of scoped variables).

    To quote from Programmin Language Pragmatics:

    "The only real purpose of the handler list is to determine which handler is active. Since blocks of source code tend to translate into contiguous blocks
    of machine-language instructions, we can capture the correspondence between handlers and protected blocks in the form of a table generated at compile time.

    Each entry in the table contains two fields: the starting address of a block of code and the address of the corresponding handler. The table is sorted on the first field. When an exception occurs, the language run-time systemperforms binary search in the table, using the program counter as key, to find the handler for the current block. If that handler reraises the exception, the process repeats: handlers themselves
    are blocks of code, and can be found in the table. The only subtlety arises in the case of the implicit handlers associated with propagation out of subroutines: such a handler must ensure that the reraise code uses the return address of the
    subroutine, rather than the current program counter, as the key for table lookup.

    The cost of raising an exception is higher in this second implementation, by a factor logarithmic in the number of handlers in the program. But this cost is paid only when an exception actually occurs. On the assumption that exceptions are unusual events, the net impact on performance is clearly beneficial: the cost in the common case is zero. In its pure form the table-based approach requires that the compiler have access to the entire program, or that the linker provide a mechanism to glue subtables together. For a language like Java, in which code fragments are compiled independently, we can employ a hybrid approach in which the compiler creates a separate table for each subroutine, and each stack frame contains a pointer to the appropriate table."

    ReplyDelete
  2. Other words, break is scoped at the method level, while exceptions can propagate trough subrutine boundaries -- therefore it is more costly to implement.

    ReplyDelete
  3. @Endre Varga

    Mind you, "break is scoped at the method level" is only true in the absence of closures. For instance, consider this simple code (assuming an hypothetical break as a Scala language feature):

    var i = 0
    while (i < 10) {
    numbers foreach { j =>
    if (i == j) break
    }
    i += 1
    }

    Note that the break is _not_ in the same stack level as the while. In fact, it is at least two subroutines down: numbers.foreach and the function passed to it.

    ReplyDelete
  4. Yes, you are right, closures change break scope. The simple Java and C break however is method level scoped, and therefore implemented by JMP.

    ReplyDelete
  5. Thank you for running these tests, very interesting.

    ReplyDelete
  6. @Daniel: Tried that example. Got:

    :11: error: not found: value break
    if (i == j) break;

    ReplyDelete
  7. The code you posted for ScalaBreakException was the same as the one you posted for ScalaSimpleBreak. Is that a typo? :)

    ReplyDelete