Блог пользователя Xazker

Java's street magic
Автор Xazker, 13 лет назад, перевод, По-русски

Следующий код на моей машине (Core2Duo 1.83Ghz, L2 cache 2Mb, ram 2Gb) с ключами запуска "-ea -Xmx256m -Xss64m" выдает:

1.751140997 sec
0.216811633 sec

Рекурсия работает очень медленно. Что с ней не так?

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");
}
}
}

Если я изменяю N на (1 << 19) то результат:

0.129561439 sec
0.129751965 sec

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У меня (win 7 x64, intel e8500):

n = 1 << 20
0.180024999 sec
0.13123485 sec

n = 1 << 19
0.028830631 sec
0.033080713 sec
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Win7 x86, Intel i3 M350
n = 1 << 20
2.590676143 sec
0.266981001 sec
n = 1 << 19
0.176323427 sec
0.185077734 sec

Смех, да и только. Может, опять виновата разрядность?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Win7 x86, Core 2 Duo P8700 (2.53 GHz)

При N = 833952:
0.258207241 sec
0.105802985 sec

При N = 833953:
1.243763906 sec
0.052655934 sec 
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Стек перестает помещаться в кеш?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Похоже, я сам не знаю как именно со стеком работает java, хотелось бы услышать поподробнее. На контесте было потрачено очень много времени на ловле этого ТЛ.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      У меня один совет - не стоит делать рекурсию там, где она очевидным образом преобразуется в цикл
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Не совсем тривиально строить динамику по дереву или считывать рекурсивный инпут нерекурсивно, но можно, конечно :) (задача Н с последнего опенкапа)
        → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Запустил бинпоиск по времени (больше секунды/меньше секунды, перед измерением три раза запускаю System.gc) в рамках одной JVM. Увидел, что функция не монотонна. Стал запускать с каждым N по два раза и брать за основу второе время. Получил такую картину:

N
первое время (нс)
второе время (нс)
20050003766359024532417325
30025009138536487698947
3501250103761360101520886
37506254514183014109370748
3875312112885704120212305

Вывод - это опять приколы оптимизатора. Возможно, он умудряется развернуть рекурсию, но иногда у него это не получается.

Кстати, под 64-битной серверной JVM с настройками по умолчанию и достаточно глубокой рекурсией в случае "тормозного" выполнения можно легко слопать всю память и своп. Так что осторожнее.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
→ Ответить