Xazker's blog

Java's street magic
By Xazker, 13 years ago, In English

The following code with run keys "-ea -Xmx256m -Xss64m" gives on my computer (Core2Duo 1.83Ghz, L2 cache 2Mb, ram 2Gb)  this output:

1.751140997 sec
0.216811633 sec

Recursion works extremely slow. What's wrong with it?

public class DoYouWantToSeeSomeMagic {
static class List {
List next;

public List(List next) {
this.next = next;
}
}

private static List createListSlow(int n) {
if (n == 0) {
return new List(null);
} else {
return new List(createListSlow(n - 1));
}
}

private static List createListFast(int n) {
List[] list = new List[n + 1];
list[0] = new List(null);
for (int i = 1; i <= n; ++i) {
list[i] = new List(list[i - 1]);
}
return list[n];
}

public static void main(String[] args) {
final int N = 1 << 20;
{
long time = System.nanoTime();
createListSlow(N);
System.err.println((System.nanoTime() - time) / 1e9 + " sec");
}
{
long time = System.nanoTime();
createListFast(N);
System.err.println((System.nanoTime() - time) / 1e9 + " sec");
}
}
}

If I change N to (1 << 19) the output is:

0.129561439 sec
0.129751965 sec

  • Vote: I like it
  • +10
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I'm guessing the garbage collector is having trouble when you need to use pretty much the whole stack size? For instance, on a 64bit system, each pointer requires 64 bits, multiplied by 1 mega (1 << 20)  = 64m which is exactly the stack limit you set. Just a guess though. The iterative way uses heap memory instead, to declare the array.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sorry, but 64bits = 8bytes, (1 << 20) * 64bits = 8Mb. Or I understand something wrong.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      64Mb = 8MB.
      I'm not sure which one "m" stands for, thats why I said it was just a guess :)
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It seems that "-Xss64m" reserved 64MB not Mb.
        → Reply