Вычисление факториала или мощь Stream API

    На днях появилась статья 5nw Два способа быстрого вычисления факториала, в которой приводится идея ускорения подсчёта факториала с помощью группировки перемножаемых чисел в дерево по принципу «разделяй и властвуй». Взглянув на это, я сразу понял, что тут параллельные потоки Java проявят себя во всей красе: ведь они делят задачу на подзадачи с помощью сплитераторов именно таким образом. Получается, что быстрая реализация будет ещё и красивой:

    public static BigInteger streamedParallel(int n) {
        if(n < 2) return BigInteger.valueOf(1);
        return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
    }


    К сожалению, в статье 5nw нет подробностей замера производительности. Сколько тестов проводилось? Был ли разогрев? Оценивалась ли погрешность замеров времени? Не выкосил ли JIT-компилятор часть вычислений, потому что их результаты не использовались? А если использовались (например, полученное число выводилось в файл), то исключён ли факт использования из подсчёта времени? В этом плане хочу сказать спасибо Алексею Шипилёву, который своей библиотекой JMH, а также многочисленными презентациями и статьями привил какую-никакую культуру бенчмаркинга в Java-сообществе.

    У меня будет такой код бенчмарка:
    import org.openjdk.jmh.infra.Blackhole;
    import org.openjdk.jmh.annotations.*;
    import java.util.concurrent.TimeUnit;
    import java.util.stream.IntStream;
    import java.math.BigInteger;
    
    @Warmup(iterations=5)
    @Measurement(iterations=10)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    @State(Scope.Benchmark)
    @Fork(2)
    public class Factorial {
        @Param({"10", "100", "1000", "10000", "50000"})
        private int n;
    
        public static BigInteger naive(int n) {
            BigInteger r = BigInteger.valueOf(1);
            for (int i = 2; i <= n; ++i)
                r = r.multiply(BigInteger.valueOf(i));
            return r;
        }
    
        public static BigInteger streamed(int n) {
            if(n < 2) return BigInteger.valueOf(1);
            return IntStream.rangeClosed(2, n).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
        }
        
        public static BigInteger streamedParallel(int n) {
            if(n < 2) return BigInteger.valueOf(1);
            return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
        }
    
        @Benchmark    
        public void testNaive(Blackhole bh) {
            bh.consume(naive(n));
        }
        
        @Benchmark    
        public void testStreamed(Blackhole bh) {
            bh.consume(streamed(n));
        }
        
        @Benchmark    
        public void testStreamedParallel(Blackhole bh) {
            bh.consume(streamedParallel(n));
        }
    }


    Я сравнил три реализации — наивную, на обычном потоке и на параллельном потоке. Разумно проверить алгоритм для различных значений n — 10, 100, 1000, 10000 и 50000, чтобы представить динамику изменения результатов. Проводится пять итераций разогрева и десять итераций с замером, всё это повторяется дважды (с перезапуском Java-машины), то есть для каждого теста делается 20 замеров. Обратите внимание на чёрную дыру (Blackhole): она нужна, чтобы JIT-компилятор не удалил результат вычислений, решив, что он всё равно не используется.

    Протестировал я на ноутбуке с процессором Core i7-4702MQ (8 хардварных тредов). Получаются вот такие результаты:

    Benchmark                         (n)  Mode  Cnt       Score       Error  Units
    Factorial.testNaive                10  avgt   20       0.298 ±     0.005  us/op
    Factorial.testNaive               100  avgt   20       5.113 ±     0.195  us/op
    Factorial.testNaive              1000  avgt   20     278.601 ±     9.586  us/op
    Factorial.testNaive             10000  avgt   20   32232.618 ±   889.512  us/op
    Factorial.testNaive             50000  avgt   20  972369.158 ± 29287.950  us/op
    Factorial.testStreamed             10  avgt   20       0.339 ±     0.021  us/op
    Factorial.testStreamed            100  avgt   20       5.432 ±     0.246  us/op
    Factorial.testStreamed           1000  avgt   20     268.366 ±     4.859  us/op
    Factorial.testStreamed          10000  avgt   20   30429.526 ±   435.611  us/op
    Factorial.testStreamed          50000  avgt   20  896719.207 ±  7995.599  us/op
    Factorial.testStreamedParallel     10  avgt   20       6.470 ±     0.515  us/op
    Factorial.testStreamedParallel    100  avgt   20      11.280 ±     1.094  us/op
    Factorial.testStreamedParallel   1000  avgt   20      74.174 ±     2.647  us/op
    Factorial.testStreamedParallel  10000  avgt   20    2826.643 ±    52.831  us/op
    Factorial.testStreamedParallel  50000  avgt   20   49196.070 ±   464.634  us/op

    Наивный тест в целом подтверждает теоретическое предположение о квадратичой сложности алгоритма. Разделим время на n²:

    n = 10:    0.002980
    n = 100:   0.000511
    n = 1000:  0.000279
    n = 10000: 0.000322
    n = 50000: 0.000389

    Прирост на больших значениях, вероятно, связан с увеличением расхода памяти и активизацией сборщика мусора.

    Нераспараллеленный поток для малых n работает ожидаемо несколько большее время (на 13% для n = 10 и на 6% для n = 100): всё же обвязка Stream API что-то съедает. Однако удивительно, что для больших n потоковый вариант работает на 4-8% быстрее, хотя алгоритмически выглядит так же. Очередное подтверждение тому, что о производительности опасно рассуждать теоретически, не проводя замеры. Оптимизации JIT-компилятора, кэширование процессора, предсказание ветвления и прочие факторы очень трудно учесть в теории.

    Распараллеленный поток ожидаемо существенно медленнее для очень коротких операций. Однако прирост скорости наблюдается уже при n = 1000, когда полный расчёт занимает около 270 мкс в последовательном режиме и только 75 в параллельном. Это отлично согласуется со Stream Parallel Guidance (спасибо apangin за ссылку), где сказано, что распараллеливать имеет смысл задачи, которые выполняются дольше 100 мкс. При больших же значениях n распараллеленный поток на коне: мы получаем прирост скорости в 18 раз. В целом это согласуется с приростом у 5nw, помноженным на число потоков (1.7/0.8*8 = 17).

    У ForkJoinPool очень маленький оверхед, поэтому даже миллисекундная задача получает выигрыш по скорости. При этом алгоритмы вида «разделяй и властвуй» естественным образом перекладываются на параллельные потоки, благодаря чему параллельный поток может оказаться существенно быстрее последовательного. Stream API многие ругают, но за параллелизмом всё же будущее.
    Поделиться публикацией

    Похожие публикации

    Комментарии 44

      0
      Я правильно понимаю, что без распараллеливания «быстрый» алгоритм оказался лишь незначительно быстрее наивного?
        +2
        Нераспараллеленный поток не является «быстрым» алгоритмом, потому что он выполняется слева направо без всяких хитростей. А вот если распараллеленный ограничить одним ядром (например, используя свойство java.util.concurrent.ForkJoinPool.common.parallelism), он будет жрать одно ядро, но выполнится быстрее последовательного потока.
        +1
        Добавьте, пожалуйста, улучшенный наивный алгоритм в сравнение, интересно, сколько получится
          0
          Я бы не назвал ваш алгоритм наивным. Он по сути ближе к древовидному, просто вы устанавливаете фиксированную глубину дерева. Пусть он называется fourBlocks :-) Если уж сравнивать, интересно ещё проверить версию с отдельным подсчётом степеней двойки (причём в параллельном и в последовательном варианте).

          Изменённый код бенчмарка
          import org.openjdk.jmh.infra.Blackhole;
          import org.openjdk.jmh.annotations.*;
          import java.util.concurrent.TimeUnit;
          import java.util.stream.IntStream;
          import java.math.BigInteger;
          
          @Warmup(iterations=5)
          @Measurement(iterations=10)
          @BenchmarkMode(Mode.AverageTime)
          @OutputTimeUnit(TimeUnit.MICROSECONDS)
          @State(Scope.Benchmark)
          @Fork(2)
          public class Factorial {
              private static final BigInteger ONE = BigInteger.valueOf(1);
          
              @Param({"10", "100", "1000", "10000", "50000"})
              private int n;
          
              public static BigInteger naive(int n) {
                  BigInteger r = ONE;
                  for (int i = 2; i <= n; ++i)
                      r = r.multiply(BigInteger.valueOf(i));
                  return r;
              }
          
              public static BigInteger streamed(int n) {
                  if(n < 2) return ONE;
                  return IntStream.rangeClosed(2, n).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
              }
              
              public static BigInteger streamedParallel(int n) {
                  if(n < 2) return ONE;
                  return IntStream.rangeClosed(2, n).parallel().mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
              }
          
              public static BigInteger fourBlocks(int n) {
                  if(n < 2) return ONE;
                  BigInteger r1 = ONE, r2 = ONE, r3 = ONE, r4 = ONE;
                  int i;
                  for (i = n; i > 4; i -= 4)
                  {
                      r1 = r1.multiply(BigInteger.valueOf(i));
                      r2 = r2.multiply(BigInteger.valueOf(i - 1));
                      r3 = r3.multiply(BigInteger.valueOf(i - 2));
                      r4 = r4.multiply(BigInteger.valueOf(i - 3));
                  }
                  int mult = i == 4 ? 24 : i == 3 ? 6 : i == 2 ? 2 : 1;
                  return r1.multiply(r2).multiply(r3.multiply(r4)).multiply(BigInteger.valueOf(mult));
              }
              
              public static BigInteger streamedShift(int n) {
                  if(n < 2) return ONE;
                  int p = 0, c = 0;
                  while ((n >> p) > 1) {
                      p++;
                      c += n >> p;
                  }
                  return IntStream.rangeClosed(2, n).map(i -> i >> Integer.numberOfTrailingZeros(i))
                          .mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get().shiftLeft(c);
              }
          
              public static BigInteger streamedParallelShift(int n) {
                  if(n < 2) return ONE;
                  int p = 0, c = 0;
                  while ((n >> p) > 1) {
                      p++;
                      c += n >> p;
                  }
                  return IntStream.rangeClosed(2, n).parallel().map(i -> i >> Integer.numberOfTrailingZeros(i))
                          .mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get().shiftLeft(c);
              }
          
              @Benchmark    
              public void testNaive(Blackhole bh) {
                  bh.consume(naive(n));
              }
              
              @Benchmark    
              public void testStreamed(Blackhole bh) {
                  bh.consume(streamed(n));
              }
              
              @Benchmark    
              public void testStreamedParallel(Blackhole bh) {
                  bh.consume(streamedParallel(n));
              }
          
              @Benchmark    
              public void testFourBlocks(Blackhole bh) {
                  bh.consume(fourBlocks(n));
              }
              
              @Benchmark    
              public void testStreamedShift(Blackhole bh) {
                  bh.consume(streamedShift(n));
              }
              
              @Benchmark    
              public void testStreamedParallelShift(Blackhole bh) {
                  bh.consume(streamedParallelShift(n));
              }
          }

          Результаты будут чуть позже.
            0
            Вот результаты:

            Benchmark                              (n)  Mode  Cnt       Score       Error  Units
            Factorial.testFourBlocks                10  avgt   20       0.409 ±     0.027  us/op
            Factorial.testFourBlocks               100  avgt   20       4.752 ±     0.147  us/op
            Factorial.testFourBlocks              1000  avgt   20     113.801 ±     7.159  us/op
            Factorial.testFourBlocks             10000  avgt   20   10626.187 ±    54.785  us/op
            Factorial.testFourBlocks             50000  avgt   20  281522.808 ± 13619.674  us/op
            Factorial.testNaive                     10  avgt   20       0.297 ±     0.002  us/op
            Factorial.testNaive                    100  avgt   20       5.060 ±     0.036  us/op
            Factorial.testNaive                   1000  avgt   20     277.902 ±     1.311  us/op
            Factorial.testNaive                  10000  avgt   20   32471.921 ±  1092.640  us/op
            Factorial.testNaive                  50000  avgt   20  970355.227 ± 64386.653  us/op
            Factorial.testStreamed                  10  avgt   20       0.326 ±     0.002  us/op
            Factorial.testStreamed                 100  avgt   20       5.393 ±     0.190  us/op
            Factorial.testStreamed                1000  avgt   20     265.550 ±     1.772  us/op
            Factorial.testStreamed               10000  avgt   20   29871.366 ±   234.457  us/op
            Factorial.testStreamed               50000  avgt   20  894549.237 ±  5453.425  us/op
            Factorial.testStreamedParallel          10  avgt   20       6.114 ±     0.500  us/op
            Factorial.testStreamedParallel         100  avgt   20      10.719 ±     0.786  us/op
            Factorial.testStreamedParallel        1000  avgt   20      72.225 ±     0.509  us/op
            Factorial.testStreamedParallel       10000  avgt   20    2811.977 ±    14.599  us/op
            Factorial.testStreamedParallel       50000  avgt   20   49501.716 ±   729.646  us/op
            Factorial.testStreamedParallelShift     10  avgt   20       6.684 ±     0.549  us/op
            Factorial.testStreamedParallelShift    100  avgt   20      11.176 ±     0.779  us/op
            Factorial.testStreamedParallelShift   1000  avgt   20      71.056 ±     3.918  us/op
            Factorial.testStreamedParallelShift  10000  avgt   20    2641.108 ±   142.571  us/op
            Factorial.testStreamedParallelShift  50000  avgt   20   46480.544 ±   405.648  us/op
            Factorial.testStreamedShift             10  avgt   20       0.402 ±     0.006  us/op
            Factorial.testStreamedShift            100  avgt   20       5.086 ±     0.039  us/op
            Factorial.testStreamedShift           1000  avgt   20     237.279 ±     1.566  us/op
            Factorial.testStreamedShift          10000  avgt   20   27572.709 ±   135.489  us/op
            Factorial.testStreamedShift          50000  avgt   20  874699.213 ± 53645.087  us/op

            fourBlocks сравним с наивным при n = 100 и даёт существенный выигрыш уже на 1000. Думаю, внутри 18-кратного увеличения производительности параллельного метода выигрыш от параллелизма максимум четырёхкратный (всё же 4 ядра HT — это не 8 ядер), а остальное — от правильного разбиения данных, так как параллельный алгоритм выигрывает у вашего всего в 5.7 раз при n = 50000. Битовый сдвиг вопреки ожиданиям большого прироста не дал. Вероятно, внутри себя BigInteger сам хорошо с этим справляется и незначительную экономию мы видим лишь за счёт уменьшения потребляемой памяти и облегчения работы сборщику мусора.
              0
              Спасибо, интересные результаты. Жалко на шарпе не могу проверить — не нашел пока бенчмарков, поддерживающих многопоток. Существующие только запускают на неактивном ядре все тесты, чтобы от переключения контекста на «виндовых» ядрах не менялись результаты тестирования. Тем более, стандартная библиотека по каким-то эвристикам не всегда параллелит на все ядра, типа если задача не тяжелая… Хотя очевидно, что выигрыш мог бы быть достигнут этим.
                +1
                Где-нибудь можно посмотреть исходники этих реализаций? *зачёркнуто* Чукча не читатель
                У меня получилось вот так:

                Naive
                2,214s
                Tree
                1,118s
                OptimizedThreading
                0,273s

                Время — среднее за 10 проходов, каких-то исключительных пиков не наблюдалось в отдельных методах
                Система — Core i5 2500, Win7 x64

                Другими словами — мне дописывать статью, или уже бессмысленно? :)

                  +1
                  Я не знаю, о чём вы собрались писать статью :-) Моя была о том, что Java Stream API исключительно круто сочетается с алгоритмами вида «разделяй и властвуй». Если вы хотите о чём-то другом написать, пожалуйста, пишите :-)
                    0
                    Эх, аналог на шарпе ускоряет максимум в 2 раза, увы… Даже не знаю, кого винить, оригинальную имплементацию BigInteger или кривой TPL…

                    static BigInteger StreamedParallel(int n)
                    {
                        return n < 2 ? 1 : Enumerable.Range(2, n - 1).AsParallel().Aggregate(BigInteger.One, (acc, elm) => acc * elm, (i, j) => i * j, i => i);
                    }
                    


                    Особенно печально, что у вас StreamedParallel выполняется за 700 микросекунд, в то время как на шарпе это 700 миллисекунд. Ну и ускорение относительно naive только в 2 раза, как я уже сказал… Всегда считал, что шарп быстрее джавы во всем. Серьезный удар.
                      0
                      Честно говоря, даже не верится, что на джаве такие результаты. Вон, человек скидывал тестирование на GMP, даже на плюсах получается 23мс, что в 4 раза больше testStreamed 5,5 мс, в которой нет никакой параллелизации, на которую можно было бы списать такой прирост.
                        0
                        Вы путаете что-то. В колонке (n) число, от которого брали факториал. Вас должны интересовать строки с n = 50000. А результата 700 микросекунд я вообще не вижу.
                          +1
                          Блин, я осел, всё это время смотрел на колонку СКО, а не на результаты измерений. Тогда всё в порядке, извиняюсь за ложную тревогу.

                          Но всё-равно обидно. Streamed в шарпе и в джаве по скорости совпадают, а вот многопоточный вариант абсолютно в выполнении ничего не меняет — 5% прирост относительно однопоточного варианта. Никакого x19 прироста не наблюдается.
                            0
                            x19 от простого мультитридинга быть не может. В идеальном варианте только ускорение в N раз, где N — число физических ядер. Там ещё что-то происходит.

                            Мне на await/async удалось получить ускорение порядка 3.5 раза на 4х ядрах, но там есть пара извращений.
              0
              А я правильно понимаю, что таким же образом можно распараллелить и посчитать на GPU?
                +1
                В принципе можно, но с помощью Java и в одну строчку — вряд ли. Ждём результатов проекта Sumatra.
                  0
                  Если использовать целочисленные вектора размерности 3 или 4 то можно еще быстрее посчитать?
                    0
                    Не понимаю, о чём вы. Приведите код, иллюстрирующий вашу идею.
                      0
                      Я про OpenGL www.opengl.org/wiki/Data_Type_(GLSL)#Vectors

                      Если правильно понял идею, то формируя входной буфер из целочисленных векторов int4(x,y,z,w) и скармливая шейдеру, который для каждого вектора посчитает произведение его координат, шейдер вернет новый буфер в 4 раза короче исходного, его снова отдаем на вычисление тому же шейдеру и тд, пока не останется буфер из одного числа. Таким образом используя ядра GPU, можно достигнуть большей степени параллелизации. Единственное ограничение 32-битный int, так мы быстро упремся.
                        0
                        У меня очень маленький опыт программирования шейдеров. Тут основная проблема в том, что нужно перемножать числа длиной в тысячи и десятки тысяч цифр. Умножение длинных чисел весьма нетривиальная процедура. В Java BigInteger используется три алгоритма в зависимости от длины чисел — наивный, алгоритм Карацубы и алгоритм Тума—Кука. GPU не заточены напрямую под длинную арифметику, вам потребуется библиотека. Не знаю, насколько хорошо с этим в GLSL.
                          0
                          Факториал 12 уже не влезает в int32, соответственно 24! не влезет уже в лонги, поэтому на видюхе вряд ли что удастся посчитать. Если изобрести собственный Biginteger, чтобы считать на видео/SSE, манипулируя только байтами-вордами да интами, то тогда наверное можно.
                            0
                            Ага, уже пыл сплыл)
                    0
                    Вангую, что в Open CL на крайний случай есть 64-bit и вектора длиной до 16. Вполне вероятно, что и аналогичные алгоритмы тоже могут иметь место.
                      0
                      Гм. А как значения из таблицы перевести в среднее время? Подскажите для не знакомых с этим фреймворком.
                        0
                        Колонка Score — это и есть среднее время в микросекундах.
                          0
                          Score = время работы в микросекундах. Там в последнем столбце единицы измерения указаны.
                          0
                          А как этот фреймворк параллелит длинное умножение? Мне просто интересно, откуда 20ти кратный прирост, что я упустил
                          И не смогли бы вы запустить на вашей машине оригинальный код?
                          Измерить время можно с помощью System.Diagnostics.Stopwatch. Либо я могу скинуть тестовый код
                            0
                            Каждое отдельное умножение не параллелится, разумеется. Параллелятся ветки дерева умножений. Не сказал бы, что это фреймворк — это стандартная библиотека Java. Фреймворк JMH использовался только для замера производительности, а сама реализация факториала (в самом верху поста) не требует ничего кроме Java SE 1.8.

                            Сравнивать напрямую Java и C# может быть не очень уместно. Не факт, что реализация BigInteger в них похожа. И представлять в памяти, и умножать длинные целые можно кучей способов.

                            А что требуется установить, чтобы скомпилировать ваш код? Я с шарпами как-то не работаю. Лучше вы мой код у себя запустите ;-)
                              0
                              Я пытался параллелить только корень, но это уже даёт 100% загрузку процессора. В идеале, распаралеливание, на 4 потока может дать только 4х кратный прирост.
                              Узким местом, впрочем, оказалось умножение последнего элемента — при любая финальной комбинация вызывается за 0.54 секунды

                              Собственно вот (однократная проверка, быстродействие, по наблюдениям, плавает в пределах 5%):

                              2-25000: 00:00:00.2458574 // thread 1
                              25001-50000: 00:00:00.3246583 // thread 2
                              finalizing: 00:00:00.5395141
                              total: 00:00:00.8882113

                              C# использует алгоритм Карацубы для умножения длинных чисел.
                              Но умножение, как мне показалось, реализовано крайне неэффективно. Собственно, тот же битовый сдвиг даёт прирост скорости почти в 2 раза для финальной операции. Собственно большенство плясок там именно вокруг этого.

                              Для того, чтобы скомпилировать код можно обойтись одним .NET Framework'ом, но лучше — какую-нибудь Visual Studio с поддержкой C#. Скинуть код смогу только этак в 22:00 МСК
                                0
                                В Java для таких больших чисел уже Тоом—Кук используется. Ну очевидно, что у Java получается гораздо быстрее сделать последнее умножение. Я добавил отладочный вывод, получилось, что задача разбивается на 16 последовательных подзадач 2..3125, 3126..6250 и т. д. до 46876..50000, а потом результаты перемножаются древовидным способом, но по факту всё равно получается, что последнее умножение — это произведение результатов 2..25000 и 25001..50000. В перемножаемых числах 329183 и 379175 бит. Возможно, в Java реализация умножения действительно сделана лучше. Либо вам всё же стоит разогреть свой код.
                                  0
                                  Вряд ли в С# Карацуба, я больше склоняюсь к тому что там немного оптимизированный квадрат
                                    0
                                    System.Numerics.BigInteger uses the Karatsuba algorithm or standard schoolbook multiplication, depending on the size of

                                    stackoverflow.com/a/3066062/2559709
                                      0
                                      Я тоже руководствовался этим ответом, но надо бы декомпилировать System.Numerics. Я этого не сделал из-за того, что рефлектор с первого раза неймспейс не подцепил :)
                                      0
                                      Вот здесь пишут что квадрат. Я не специалист в дотнете, проверить сам не могу. Но асимптотика у него довольно странная, это да.
                              –1
                              Спасибо за интересную статью. Хотелось бы ещё в тесте увидеть такую реализацию факториала:
                              public static BigInteger recursiveFactorial(int i) {
                              BigInteger r = BigInteger.valueOf(1);
                                  if (i == 1) {
                              	return r;
                                  }
                                  r = BigInteger.valueOf(i);
                                  return r.multiply(factorial(i - 1));
                              }
                              
                                0
                                Нет, не хочется :)

                                А если серьезно, то имхо, стек сдохнет. Сколько каждый BigInteger занимает памяти, умножаем на по крайней мере 50000 кадров стека, а стек-то всего пара мегабайт, если мне память не изменяет.

                                Повезет, если компилятор развернет хвостовой вызов. Но в таком случае получим тот же цикл, пример которого в сравнении есть.
                                  +2
                                  Java-компилятор не может развернуть хвостовой вызов.
                                  Сколько занимает BigInteger — никого не волнует, он лежит в куче. Но глубина стека в 50000 — это действительно очень много, StackOverflowError случится гораздо раньше.
                                    0
                                    В clojure есть специальная форма (recur ...), которая позволяет сделать вид, что выполняется tail recursive вызов.

                                    В scala есть автоматическая оптимизация tail rec с ограничениями (proper tail call). Т. е. оптимизируется только в случае возможности переиспользования stack frame. Плюс есть аннотация @tailrec, гарантирующая, что при невозможности этой оптимизации будет compile-time error. Причём, в случае scala для применения оптимизации необходимо гарантировать, что метод не будет переопределён (private или final). См. tech.pro/blog/2112/scala-tail-recursion-optimisation-and-comparison-to-java
                                      +1
                                      Я всё это знаю. Я говорил конкретно про Java. В Java хвостовая рекурсия, насколько я понимаю, не может быть реализована без нарушения JLS.
                                        0
                                        А она не отдана просто на откуп JIT'у? Т. е. unspecified? На SO видел что-то в этом роде, но пруфлинки на сайт ibm уже к тому моменту протухли.
                                        0
                                        В .Net также есть директива хвостового вызова (вернее опкод tail. — 0xFE 0x14). Да и в джаве появится, раз пошли функциональные эти приколы.
                                          +2
                                          Не похоже, чтобы это было в приоритете. На JPoint ничего про это не говорили.
                                    +1
                                    А мне бы не хотелось её видеть :-)

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

                                  Самое читаемое