switch statements in Java run in O(n) time for n cases.

[Ollie]

After running some tests, I have concluded that switch statements in Java on my machine do not run in O(1) time, but rather clearly O(n) time until about 450 switch cases. I suspect all or most other JVMs including those that run on other operating systems will have the same results, testing would be needed to be certain.

This has some interesting implications and raises some questions such as "Why?" and "What the hell?".

Of interest is that efficiency is commonly cited as the reason switch statements in Java only take integer types and use constant cases. I imagine however that if implemented by a hash table, constant time performance could be given for string based switch statements.

I am speaking of the most simple and easily optimized switch statements: switches with n cases, cases from 0 to n-1.
So for n = 3 it looks like
switch(s) { case 0: something; break; case 1: something; break; case 2: something; break; }

I believe the Java bytecode, as verified by Clam in #xkcd, is in fact the standard lookup table type of implementation, which should run in constant time. However, it does not.

This undermines the value of switch statements as used to make programs efficient.

If very fast switch statements are needed a couple work arounds could be tested:
Method 1: if/else binary search. Theoretically gives at least O(log n) performance for n cases which is practically constant time. edit: tested, see results below. This method is faster than switches until about 330 cases, when the if/else binary search method suddenly takes much more time.
Method 2: Replacing a switch statement with n cases: Create one abstract class c with method f(). For each switch case s, derive a class "c[s]" from c, write function f() as what would have been in the switch case. Create an array of type c. At each index s of the array, put an object of type c[s] there. Where the switch statement was needed, do an array lookup into the array you made and filled in, and then call f() on the object at the index you were looking for in the switch. As convoluted as this method is, it may still be faster than switch statements, depending on how fast the derived methods can be called. Some testing suggested this method was in fact always faster than switches larger than a certain number of cases.

Finally, the machine I'm using.
* Windows XP, 32 bit.
* Code written in Processing 1.01. As I understand it, Processing uses the standard Windows JVM for Java 1.5 on my machine.

The results.

Spoiler:

Code: Select all

Switch cases, time in milliseconds for 10,000,000 runs.
0   219
20   375
40   468
60   532
80   593
100   610
120   719
140   734
160   797
180   890
200   922
220   1000
240   1047
260   1094
280   1141
300   1218
320   1250
340   1328
360   1375
380   1438
400   1484
420   1532
440   1609
460   2250
480   2234
500   2266
520   2266
540   2234
560   2250
580   2234
600   2250
620   2235
640   2234
660   2250
680   2250
700   2234
720   2250
740   2250
760   2235
780   2250
800   2234
820   2250
840   2235
860   2250
880   2234
900   2250
920   2234
940   2250
960   2235
980   2235

0   219
1   234
2   282
3   296
4   250
5   266
6   297
7   297
8   297
9   297
10   328
11   343
12   344
13   344
14   359
15   360
16   359
17   359
18   375
19   375
20   375
21   360
22   406
23   375
24   406
25   375
26   375
27   407
28   390
29   391
30   422
31   406
32   406
33   422
34   406
35   422
36   438
37   406
38   437
39   422


The code that generates the testing code, both of which run in Processing 1.01: http://www.processing.org.

Spoiler:

Code: Select all

// generates test files.


String[] snipTo(String[] lines, int count)
{
  String[] ret = new String[count];
  for(int i = 0; i < count; i++)
    ret[i] = lines[i];
  return ret;
}


void setup()
{
  int minCount = 0;
  int maxCount = 1000;
  int step = 20;
 
  int iterations = 10000000;
 
  String[] lines = new String[(maxCount - minCount) / step * 14 + (maxCount - minCount) / step * maxCount + 9];
 
  int curLine = 0;
 
  lines[curLine++] = "int t = 0;";
  lines[curLine++] = "int f = 0;";
  lines[curLine++] = "";
 
  for(int count = minCount; count < maxCount; count += step)
  {
    lines[curLine++] = "void foo" + count + "()";
    lines[curLine++] = "{";
    lines[curLine++] = "  switch(t)";
    lines[curLine++] = "  {";
    for(int i = 0; i < count; i++)
      lines[curLine++] = "    case " + i + ": f -= 47; break;";
    lines[curLine++] = "  }";
    lines[curLine++] = "";
    lines[curLine++] = "  t += 7919; t %= " + (count > 0 ? count : 1) + ";";
    lines[curLine++] = "}";
  }
 
  lines[curLine++] = "";
  lines[curLine++] = "void setup()";
  lines[curLine++] = "{";
  lines[curLine++] = "  long startTime;";
  lines[curLine++] = "";
 
  for(int count = minCount; count < maxCount; count += step)
  {
    lines[curLine++] = "  startTime = System.currentTimeMillis();";
    lines[curLine++] = "  t = 0;";
    lines[curLine++] = "  for(int i = 0; i < " + iterations + "; i++)";
    lines[curLine++] = "    foo" + count + "();";
    lines[curLine++] = "  println(System.currentTimeMillis() - startTime);";
    lines[curLine++] = "";
  }
  lines[curLine++] = "}";
 
  lines = snipTo(lines, curLine);
 
  saveStrings("testFile.txt", lines);
}


[tetsujin]

Huh? Switch statements are supposed to use lookup tables? That's news to me...

[InstinctSage]

I always used if/else in place of switch statements wherever possible. Switches look nice and neat, but a well implemented if/else solution has always been more efficient in practice for me.

[Unparallelogram]

The lookup table would probably be usually more expensive, given that switch isn't usually used with more than a handful of cases.

[Sc4Freak]

Huh? Switch statements are supposed to use lookup tables? That's news to me...

This is a common optimisation in C and C++ programs, at least. If the switch case labels are integers and are fairly contiguous, they can be used as an index into a jump table. So evaluating a switch takes nothing more than looking up an address in a table, then jumping to that address.

[Unparallelogram]

Huh? Switch statements are supposed to use lookup tables? That's news to me...

This is a common optimisation in C and C++ programs, at least. If the switch case labels are integers and are fairly contiguous, they can be used as an index into a jump table. So evaluating a switch takes nothing more than looking up an address in a table, then jumping to that address.

Java arrays have their own overhead. Not that a table internal to the VM would necessarily have the same. But even so, this isn't a necessary optimization in most cases. When was the last time you had more than ten cases to a switch? Moreover, what other problems did that cause?

[Rysto]

When was the last time you had more than ten cases to a switch? Moreover, what other problems did that cause?

When I used JFlex to generate a scanner for me. If switch statements aren't O(1), the performance of those generated scanners would be horrendous.

I have a feeling that the OP is running up against something subtle in the VM, like it isn't running long enough for the optimizer to kick in. I have a hard time believing that the JVM won't use a jump table: it's very unlikely to be slower.

[Ollie]

When was the last time you had more than ten cases to a switch? Moreover, what other problems did that cause?

When I used JFlex to generate a scanner for me. If switch statements aren't O(1), the performance of those generated scanners would be horrendous.

I have a feeling that the OP is running up against something subtle in the VM, like it isn't running long enough for the optimizer to kick in. I have a hard time believing that the JVM won't use a jump table: it's very unlikely to be slower.

Please download Processing, or convert the code to straight Java code, and test it. I'd be interested to see if you get different results. The code which generates the testing code is in the original post. Note that as is the code will generate a 25,000 line Processing source code file (32 KB).

[Rysto]

I have no idea what Processing or how to use it, so I wrote my own test. I wrote a program to generate a switch statement with 8K entries. I then call the switch statement 100 million times with random values, to try and ensure that the VM would kick in and optimize the switch. Finally, I tried each index in turn. The result is pretty clearly O(1):

Spoiler:

OO sucks at graphs

switch_chart.png (23.61 KiB) Viewed 8322 times

Note the big drop half-way through. I guess the optimizer kicked again. Still, the result is clearly constant.

# java -version
java version "1.6.0_07"
Java(TM) SE Runtime Environment (build 1.6.0_07-b06)
Java HotSpot(TM) 64-Bit Server VM (build 10.0-b23, mixed mode)

[Ollie]

I wrote a program to generate a switch statement with 8K entries. I then call the switch statement 100 million times with random values

There is a difference between what we are both talking about.

Consider this code:

Code: Select all

switch(v) {
  case(0): something; break;
  case(1): something; break;
  ...
  case(n): something; break;
}

You are saying that switch runs in O(1) (constant time) based on v, the case being looked for.
I am saying that switch runs in O(n), n being the number of cases.

Constant time access to any given case is useless if the time of access to any case increases linearly with the number of cases. The constant time access you are seeing is fool's gold. Java is not properly implementing a switch or there is something very funny going on.

[OOPMan]

Have either of you considered...

A) Examing the Open Source JDK code with regards to this?

B) Asking one of the OpenJDK devs?

I have to say, I'm leaning with Rysto here. It is *highly* unlikely that the Java switch statement is broken as you say it is and it is more than likely that the problem lies somewhere within your own code than that of javac and the JVM.

In general, problems almost always trace down to ones own code, rather than that of the compiler and/or VM. (Although there are cases where this is not true...)

[Ollie]

Have either of you considered...

A) Examing the Open Source JDK code with regards to this?

B) Asking one of the OpenJDK devs?

I have to say, I'm leaning with Rysto here. It is *highly* unlikely that the Java switch statement is broken as you say it is and it is more than likely that the problem lies somewhere within your own code than that of javac and the JVM.

In general, problems almost always trace down to ones own code, rather than that of the compiler and/or VM. (Although there are cases where this is not true...)

You're welcome to examine my code. I haven't found any way to make the switches act quicker, but then I've overlooked many things before.

[Sc4Freak]

Huh? Switch statements are supposed to use lookup tables? That's news to me...

This is a common optimisation in C and C++ programs, at least. If the switch case labels are integers and are fairly contiguous, they can be used as an index into a jump table. So evaluating a switch takes nothing more than looking up an address in a table, then jumping to that address.

Java arrays have their own overhead. Not that a table internal to the VM would necessarily have the same. But even so, this isn't a necessary optimization in most cases. When was the last time you had more than ten cases to a switch? Moreover, what other problems did that cause?

The compiler automatically performs this optimisation. I think you'd have to be insane to do that manually, and I don't think it's even possible to create an optimised jump table out of a switch like the compiler can, since the compiler has more information than you do.

Like I said, most optimising C++ compilers will automatically perform this compile-time optimisation - you don't need to make any changes to your code.

[Unparallelogram]

Oops misread. You're running the code with a ton of switches through Processing as well? That may be why. No doubt it has its own overhead. Processing uses Java but has its own stuff alongside as well. You should be using whatever to write a long Java program.

[segmentation fault]

what did you use to test? could it be somehow possible youre seeing some sort of heisenberg shit, and trying to calculate the complexity therefore increases it?

[Karrion]

My results:

Spoiler:

X axis is number of branches in the switch
Y axis is the wall time in milliseconds to randomly switch 100000 times.

Results

results.png (18.98 KiB) Viewed 8110 times

f(x) = 0.00649424x + 130.33

Observations:

Since we're measuring wall time, execution time can be affected by other activity in the system. This is likely the cause of the odd spike at around n=3300 (the system probably kicked off an overnight task like checking for updates.

There is a very shallow positive slope to the fit line. This does suggest that execution time increases linearly with n, meaning it is technically O(n). However, the slope is so very shallow that for all intents and purposes I believe it can be considered O(1).


Methodology:

Used a shell script to generate and execute the test class with n branches:

Spoiler:

Code: Select all

#! /bin/sh

n=$1
j=TestSwitch.java
cat > $j <<EOF
import java.io.*;
import java.util.*;

class TestSwitch {
   public static void main(String args[]) {
      String str;
      long start = System.currentTimeMillis();
      for (int i=0; i<100000; i++) {
EOF
echo "int sel = new Random().nextInt($n); switch (sel) {" >> $j
for i in $(seq 0 $(( $n - 1 )) ); do
   echo "case $i: str = \"$i\"; break;" >> $j
done
cat >> $j <<EOF
            default: str = "?"; break;
         }
      }
      long end = System.currentTimeMillis();
      System.out.println(end-start);
   }
}
EOF
javac $j
java TestSwitch


The script was then run in a loop, one run for every n in [1,5000], and the results plotted with gnuplot

Spoiler:

Code: Select all

for i in $(seq 1 10); do echo -n "$i "; sh test.sh $i; done > results.txt


Code: Select all

#! /usr/bin/gnuplot -persist
f(x) = a*x + c
fit f(x) 'results.txt' via a, c
plot [1:5000] 'results.txt', f(x)


Test system:

Linux 2.6.27.9-73.fc9.i686
java version "1.6.0"
OpenJDK Runtime Environment (build 1.6.0-b09)
OpenJDK Server VM (build 1.6.0-b09, mixed mode)

[AndyG314]

First off big O notation represents the worst case time, not necessarily the observed time. The observed time could be less than what big O notation would indicate.

Secondly, notice that at 460 we nearly double the needed time from 1609 at 440 to 2250 at 460. This jump is not in line with the previous increases. Here we see that the optimizer has switched strategies on how to run your code efficiently. It's hard to know exactly what the optimizer is doing, if we were writing it in C, we could run the compiler and take a look at the generated assembly code, that would tell us what it is actually running. I bet if you wrote the same thing in C and look at the generated assembly it would give you a hint.

Take a look at the numbers for 20 case statements, it takes 219 ms to run 10,000,000 iterations. That boils down to about 22ns per iteration. There is no way that the virtual machine is running your code that fast. The system is running your code faster than how it's written because the optimizer is cutting out the fat.

[Rysto]

Constant time access to any given case is useless if the time of access to any case increases linearly with the number of cases. The constant time access you are seeing is fool's gold. Java is not properly implementing a switch or there is something very funny going on.

Ok, if you can come up with a implementation of a switch(v) statement with n cases that is:

O(1) for fixed n, varying v
O(n) for varying n

then I could be persuaded that you might be on to something.


As a baseline, I think that it'd be useful to do the same thing in C, and see what the graph looks like there. We've all said that "of course it's O(1) in C" but nobody's actually gone and proved that.

[stephentyrone]

Secondly, notice that at 460 we nearly double the needed time from 1609 at 440 to 2250 at 460. This jump is not in line with the previous increases. Here we see that the optimizer has switched strategies on how to run your code efficiently.

That's one possible explanation, but certainly not the only. You could be blowing cache beyond that point, encountering paging effects or false aliasing; there are many, many possible explanations other than the optimizer.

I'm not saying the optimizer isn't changing its strategy at this point, just that one needs to do a lot more experiments to make that conclusion.

[Karrion]

As a baseline, I think that it'd be useful to do the same thing in C, and see what the graph looks like there. We've all said that "of course it's O(1) in C" but nobody's actually gone and proved that.

Repeating my experiment in C:

Results:

Spoiler:

Results (C)

results.png (18.68 KiB) Viewed 8049 times

f(x) = -0.0000445411x + 7.51024

Observations:

C is an order of magnitude faster than Java at doing nothing.

The fit line is flat; C's switch is O(1).

The results tend to clump in two fairly distinct lines; I'm not sure why this is happening. Possibly an artifact of process scheduling by the OS?

Methodology:

As before, script to generate the C code, compile and execute:

Spoiler:

Code: Select all

#! /bin/sh

n=$1
j=testswitch.c
cat > $j <<EOF
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

#define TIMEDELTA(s,e) ( ( ((e).tv_sec*1000000+(e).tv_usec) - ((s).tv_sec*1000000+(s).tv_usec) ) / 1000.0 )

int main() {
   int i, sel;
   char* str;
   struct timeval start, end;
   srand(time(NULL));
   gettimeofday(&start, NULL);
   for (i=0; i<100000; i++) {
EOF
echo "sel = (int) ($n.0 * (rand() / (RAND_MAX + 1.0))); switch (sel) {" >> $j
for i in $(seq 0 $(( $n - 1 )) ); do
   echo "case $i: str = \"$i\"; break;" >> $j
done
cat >> $j <<EOF
         default: str = "?"; break;
      }
   }
   gettimeofday(&end, NULL);
   printf("%f\n", TIMEDELTA(start,end));
   return 0;
}
EOF
gcc -o testswitch -O0 -Wall $j
./testswitch


Compiler optimisation is disabled to ensure that the compiler doesn't optimise the whole loop away.

[Ollie]

what did you use to test? could it be somehow possible youre seeing some sort of heisenberg shit, and trying to calculate the complexity therefore increases it?

I sure hope not, all bets are off at that point! My basic presumption is that Java can be tested at all.

Oops misread. You're running the code with a ton of switches through Processing as well? That may be why. No doubt it has its own overhead. Processing uses Java but has its own stuff alongside as well. You should be using whatever to write a long Java program.

When finally run, Processing boils down to nothing more than a library. There are no Processing function calls in my code and so there should be no overhead. You can think of it as an easier way to write Java code if you'd like. You could, as Clam in #xkcd did, convert my code to Java code and see for yourself. I am seeing similar results to mine with Karrion's test which is straight Java.

My results:
Observations:

Since we're measuring wall time, execution time can be affected by other activity in the system. This is likely the cause of the odd spike at around n=3300 (the system probably kicked off an overnight task like checking for updates.

There is a very shallow positive slope to the fit line. This does suggest that execution time increases linearly with n, meaning it is technically O(n). However, the slope is so very shallow that for all intents and purposes I believe it can be considered O(1).

Methodology:

...

Nice test! Take another look at the run times before 450 switch cases. It seems that Java changes the way it executes switches after 450 cases; before that switches seem to run in linear time with respect to the number of switch cases as I pointed out in the original post.

[Ollie]

Constant time access to any given case is useless if the time of access to any case increases linearly with the number of cases. The constant time access you are seeing is fool's gold. Java is not properly implementing a switch or there is something very funny going on.

Ok, if you can come up with a implementation of a switch(v) statement with n cases that is:

O(1) for fixed n, varying v
O(n) for varying n

then I could be persuaded that you might be on to something.


As a baseline, I think that it'd be useful to do the same thing in C, and see what the graph looks like there. We've all said that "of course it's O(1) in C" but nobody's actually gone and proved that.

Here is how you would make these switches run in constant time for any number of cases and for any parameter. Note that we are only currently speaking of switches with cases 0 to cases n-1. Note also that this is not C code, but psuedo assembly/C code.

Code: Select all

if(v < 0 || v >= n) jump to after switch;
jmp curInstruction + v + 1;
jmp case 0;
jmp case 1;
...
jmp case n-1;
end;

Each case will have a separate area of code, they will each jump to after switch at the end of their segment.


[phlip]

Code: Select all

gcc -o testswitch -O0 -Wall $j

Out of curiosity, what happens if you throw in -Os? And maybe make your cases spread further apart, instead of all contiguous? How much does it take to make gcc generate a sequence of tests, instead of a jump table?

[Rysto]

Here is how you would make these switches run in constant time for any number of cases and for any parameter. Note that we are only currently speaking of switches with cases 0 to cases n-1. Note also that this is not C code, but psuedo assembly/C code.

I know how to do it properly. I'm asking you to provide an implementation that does what you claim Java does. Because frankly, I'm at an utter loss to do so.

Edit: But the data about 450 cases clarifies things immensely. 450 is a huge number to start implementing that optimization at, really.

[Ollie]

Here is how you would make these switches run in constant time for any number of cases and for any parameter. Note that we are only currently speaking of switches with cases 0 to cases n-1. Note also that this is not C code, but psuedo assembly/C code.

I know how to do it properly. I'm asking you to provide an implementation that does what you claim Java does. Because frankly, I'm at an utter loss to do so.

To be clear, I'm not claiming Java has an O(1) switch time, (at least until about 450 cases), although it should, and once compiled the bytecode implies it. I'm having trouble finding the Sun page on how Java switch statements are compiled, but essentially it uses a jump table unless the cases are too sparse etc.

Edit: But the data about 450 cases clarifies things immensely. 450 is a huge number to start implementing that optimization at, really.

Yes, that's why I'm baffled as well. I want to run some tests with nested if/else binary searches and see if they are faster than switches. Too much to do right now, you're welcome to give it a shot .

[Sc4Freak]

Here is how you would make these switches run in constant time for any number of cases and for any parameter. Note that we are only currently speaking of switches with cases 0 to cases n-1. Note also that this is not C code, but psuedo assembly/C code.

I know how to do it properly. I'm asking you to provide an implementation that does what you claim Java does. Because frankly, I'm at an utter loss to do so.

Edit: But the data about 450 cases clarifies things immensely. 450 is a huge number to start implementing that optimization at, really.

It's strange, it's usually the other way around. The constant time optimisation should be implemented until you reach a certain point - and then after that it you should resort to branching. This is because, the more cases you have, the larger your jump table needs to be. Once a jump table gets too large, it becomes too expensive to use because of cache and memory effects.

If each case block compiles to the exact same number of instructions, you can perform arithmetic on the value to be tested in order to jump to the correct position. But unless all your case block are exactly the same, that's not going to happen.

[Ollie]

Here is how you would make these switches run in constant time for any number of cases and for any parameter. Note that we are only currently speaking of switches with cases 0 to cases n-1. Note also that this is not C code, but psuedo assembly/C code.

If each case block compiles to the exact same number of instructions, you can perform arithmetic on the value to be tested in order to jump to the correct position. But unless all your case block are exactly the same, that's not going to happen.

If they are not all the same, you can still use a jump table of course. If they are almost the same, you could pad them with NOPs as well if that one extra jump is a problem.

[Sc4Freak]

Here is how you would make these switches run in constant time for any number of cases and for any parameter. Note that we are only currently speaking of switches with cases 0 to cases n-1. Note also that this is not C code, but psuedo assembly/C code.

If each case block compiles to the exact same number of instructions, you can perform arithmetic on the value to be tested in order to jump to the correct position. But unless all your case block are exactly the same, that's not going to happen.

If they are not all the same, you can still use a jump table of course. If they are almost the same, you could pad them with NOPs as well if that one extra jump is a problem.

But once again, I wonder if you'd run into cache and memory effects here. Padding with NOPs increases the code size - and after a certain number of cases it could be cheaper to perform branching instead.

[Rysto]

The other option is to fill your jump table with jump statements. It means an extra jump, but unless the first condition is happening way more often than the rest it's still faster.

More data:

Spoiler:

switch2.png (9.05 KiB) Viewed 7984 times

The Y access is time in ms, the X axis is the number of cases in the switch. I don't understand the extreme variability here: you'd think that when I do enough iterations for it to take 5-6 seconds that the variability would even itself out.

[hotaru]

The results tend to clump in two fairly distinct lines; I'm not sure why this is happening. Possibly an artifact of process scheduling by the OS?

probably. i remember seeing a similar graph in the results from some linux/freebsd/netbsd/openbsd comparison benchmarks somewhere. the graph with the two distinct lines was from linux, which i'm guessing is what you're using.

[Ollie]

I built a binary search out of if/else statements and it is faster than a switch until there are around ~330 cases, at which point the binary if/else search tree breaks down for reasons beyond my current understanding.

Behold, more data!

edit: lower cases (0-20] added. A binary search tree appears to be faster or as fast as a switch in all cases until the if/else binary search tree breaks down. Expect a performance gain of about 10% when using binary if/else trees for 10 cases, 20% for 20 cases, and 50% for around 300 cases.

Spoiler:

Code: Select all

cases, time in ms for switch, time in ms for if/else binary search. (10,000,000 iterations each)
0   219   219
20   375   313
40   468   359
60   532   438
80   593   437
100   610   469
120   719   500
140   734   500
160   797   547
180   890   531
200   922   547
220   1000   547
240   1047   562
260   1094   641
280   1141   578
300   1218   594
320   1250   593
340   1328   4719
360   1375   4594
380   1438   4766
400   1484   4812
420   1532   4922
440   1609   4766
460   2250   4921
480   2234   4766
500   2266   4891
520   2266   4906
540   2234   4859
560   2250   4907
580   2234   4937
600   2250   4953
620   2235   4969
640   2234   4922
660   2250   4890
680   2250   5063
700   2234   5031
720   2250   4906
740   2250   5063
760   2235   5094
780   2250   5140
800   2234   5110
820   2250   5093
840   2235   5172
860   2250   5157
880   2234   5016
900   2250   5156
920   2234   5188
940   2250   5218
960   2235   5141
980   2235   5219

0   219   219
1   234   203
2   282   297
3   296   281
4   250   266
5   266   281
6   297   266
7   297   281
8   297   266
9   297   281
10   328   297
11   343   281
12   344   297
13   344   297
14   359   297
15   360   297
16   359   312
17   359   328
18   375   313
19   375   328


[Berengal]

Looks like java does a linear if/else until it reaches 450 cases, then switches to some kind of lookup mechanism. Could be a table, but it looks like it has a huge overhead...

The binary if/else breaking down could be some cache effect. How does it compare to a linear if/else?

[Ollie]

Looks like java does a linear if/else until it reaches 450 cases, then switches to some kind of lookup mechanism. Could be a table, but it looks like it has a huge overhead...

I don't think that is the case. If java were using a linear if/else implementation then certain cases would be quicker to execute than others, but one of my early tests I think showed that every case takes an equal amount of execution time to reach and execute. The test would need to be run again to be certain.

The binary if/else breaking down could be some cache effect. How does it compare to a linear if/else?

Well beyond me. I was surprised to see it spike up.

Not feeling too motivated to run a linear if/else right now, although I did before and I remember it being slower than the switch.

[Ollie]

Incidentally the testing program for the if/else binary tree has 74,000 lines of code.

[boss_mc]

Incidentally the testing program for the if/else binary tree has 74,000 lines of code.

But how long was the script that outputted that?

[mrkite]

When was the last time you had more than ten cases to a switch? Moreover, what other problems did that cause?

I wrote an Apple IIgs emulator once, the 85618 cpu module had a 256 case switch. It optimizes to a jump table in C and C++, making more efficient than any other solution.

Efficiency is necessary when your loop is going to need to pump at 2.8 million cycles per second non-stop just to emulate 20 year old hardware.