Fibonacci, czyli wprawki (część 2: porównanie efektywności algorytmów, JMH)

W poprzednim odcinku…
Zdefiniowano zadanie, interfejs, testy i przedstawiono trzy implementacje spełniające zadane kryteria.
Teraz czas na porównanie wydajności poszczególnych implementacji

JMH wprowadzenie

JMH (Java Microbenchmark Harness) jest elementem OpenJDK. Potrafi policzyć czas wykonania dla każdej oznakowanej metody. Każdą z testowanych metod możemy odpowiednio parametryzować, określając ilość wątków, ilość niezależnych instancji (fork) na których metoda będzie testowana, ilość cykli rozgrzewania się JVM, ilość cykli testowych itd.

Na początku musimy dodać odpowiednie zależności:

    <!-- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-core -->
    <dependency>
      <groupId>org.openjdk.jmh</groupId>
      <artifactId>jmh-core</artifactId>
      <version>1.21</version>
    </dependency>
    <!-- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-generator-annprocess -->
    <dependency>
      <groupId>org.openjdk.jmh</groupId>
      <artifactId>jmh-generator-annprocess</artifactId>
      <version>1.21</version>
      <scope>provided</scope>
    </dependency>
Porównanie wydajności poszczególnych implementacji

W tym teście zadano sobie pytania:

  • Czy rzeczywiście wydajność implementacji rekursywnej spada drastycznie wraz z ilością wzajemnych wywołań i co w tym wypadku znaczy drastycznie?
  • Jak ma się wydajność implementacji rekursywnej do dwóch pozostałych implementacji?

Stąd dobór danych.
Porównano, rekurencję (dla n=8, 16, 24, 32, 40) z iteracją n=40 i implementacją strumieniową (n=40).

Sama konstrukcja testu jest prosta:

  • @State – adnotacja ta ma dwie istotne funkcje. Po pierwsze informuje, że zmienne zdefiniowane wewnątrz adnotacji są używane w teście i wymusza się żeby JIT nie optymalizował użycia tych zmiennych. Po drugie wewnątrz tej adnotacji możemy przygotować dane do testu, dane których czas przygotowania nie jest mierzony w czasie testowania. W naszym przykładzie, gdybyśmy konstruowali obiekty wewnątrz testowanych metod, czas działania konstruktora wchodziłby do wyniku testu. Użyta konstrukcja (@Setup wewnątrz @State) powoduje, że klasy są tworzone poza testem.
  • @Benchmark – metoda adnotowana tą adnotacją jest przedmiotem testu. Bezpośrednio po tej adnotacji można umieścić stado adnotacji określających parametry testu, tak że każda testowana metoda może być inaczej sparametryzowana. W tym przypadku zrezygnowano z tego i wszystkie parametry są ustalone globalnie.
  • @Test – to typowa adnotacja JUnit odpalająca test w Mavenie (np. mvn test), ale w środku umieszczono ustawienie parametrów i  wywołanie silnika testu.

Do dokładniejszego zapoznania się z możliwościami JMH odsyłam dokumentacji, przykładowy kod jest wystarczający do skonstruowania własnego, pierwszego testu odpalanego na poziomie Mavena.

Całość klasy testowej:

public class FibonacciCompRecursionImpJMHTest {

  @State(Scope.Thread)
  public static class MyState {

    FibonacciRecursionImp recursionImp;
    FibonacciIterationImp iterationImp;
    FibonacciStreamImp fibonacciStreamImp;

    @Setup
    public void init() {
      recursionImp = new FibonacciRecursionImp();
      iterationImp = new FibonacciIterationImp();
      fibonacciStreamImp = new FibonacciStreamImp();
    }
  }

  @Benchmark
  public void fibRecursionImp_08(MyState state) {
    assertEquals("Result", 21, state.recursionImp.compute(8));
  }

  @Benchmark
  public void fibRecursionImp_16(MyState state) {
    assertEquals("Result", 987, state.recursionImp.compute(16));
  }

  @Benchmark
  public void fibRecursionImp_24(MyState state) {
    assertEquals("Result", 46368, state.recursionImp.compute(24));
  }

  @Benchmark
  public void fibRecursionImp_32(MyState state) {
    assertEquals("Result", 2178309, state.recursionImp.compute(32));
  }

  @Benchmark
  public void fibRecursionImp_40(MyState state) {
    assertEquals("Result", 102334155, state.recursionImp.compute(40));
  }

  @Benchmark
  public void iterationImp_40(MyState state) {
    assertEquals("Result", 102334155, state.iterationImp.compute(40));
  }

  @Benchmark
  public void streamImp_40(MyState state) {
    assertEquals("Result", 102334155, state.fibonacciStreamImp.compute(40));
  }


  @Test
  public void computeNegativeCaseTryCatch() throws RunnerException {

    Options opt = new OptionsBuilder()
        .include(FibonacciCompRecursionImpJMHTest.class.getSimpleName())
        .warmupIterations(2)
        .warmupTime(seconds(1))
        .measurementIterations(2)
        .measurementTime(seconds(2))
        .mode(Throughput)
        .forks(1)
        .build();

    new Runner(opt).run();
  }

}

W wyniku działania testu otrzymujemy następujące wyniki:

Fibonacci - benchmark rekurencji
Fibonacci – benchmark rekurencji

Spodziewaliśmy się, że efektywność algorytmu rekurencyjnego szybko rośnie ale spadek efektywności tego algorytmu jest zaskoczeniem. Powyżej n=30, algorytm przestaje mieć jakiekolwiek praktyczne znaczenie.

W tym wypadku najbardziej przemawia do wyobraźni zobrazowanie na wykresie przy zastosowaniu logarytmicznej skali ilości operacji na sekundę.

Fibonacci - efektywność rekurencji
Fibonacci – efektywność rekurencji

Widać, że złożoność algorytm jest dokładnie logarytmiczna O(log(n)). Warta zapamiętania jest lekcja, że algorytmy o takiej złożoności są bardzo ryzykowne, do zastosowania na produkcji, o ile nie mamy całkowitej kontroli nad wielkością danych wejściowych.

Porównanie wydajności iteracji i implementacji strumieniowej

Tutaj stosujemy podobną technikę, jak w przykładzie opisanym wyżej. Dla szybkości porównajmy oba algorytmy dla trzech wartości wejściowych: 30, 60 i 90 (czyli zaczynamy na granicy zasięgu algorytmu rekurencyjnego).

public class FibonacciComparisonOfImplementationsJMHTest {

  @State(Scope.Thread)
  public static class MyState {

    FibonacciIterationImp iterationImp;
    FibonacciStreamImp fibonacciStreamImp;

    @Setup
    public void init() {
      iterationImp = new FibonacciIterationImp();
      fibonacciStreamImp = new FibonacciStreamImp();
    }
  }

  @Benchmark
  public void iterationImp_30(MyState state) {

    assertEquals("Result", 832040, state.iterationImp.compute(30));
  }

  @Benchmark
  public void iterationImp_60(MyState state) {
    assertEquals("Result", 1548008755920L, state.iterationImp.compute(60));
  }

  @Benchmark
  public void iterationImp_90(MyState state) {
    assertEquals("Result", 2880067194370816120L, state.iterationImp.compute(90));
  }

  @Benchmark
  public void streamImp_30(MyState state) {

    assertEquals("Result", 832040, state.fibonacciStreamImp.compute(30));
  }

  @Benchmark
  public void streamImp_60(MyState state) {
    assertEquals("Result", 1548008755920L, state.fibonacciStreamImp.compute(60));
  }

  @Benchmark
  public void streamImp_90(MyState state) {
    assertEquals("Result", 2880067194370816120L, state.fibonacciStreamImp.compute(90));
  }

  @Test
  public void computeNegativeCaseTryCatch() throws RunnerException {

    Options opt = new OptionsBuilder()
        .include(FibonacciComparisonOfImplementationsJMHTest.class.getSimpleName())
        .warmupIterations(2)
        .warmupTime(TimeValue.seconds(1))
        .measurementIterations(2)
        .measurementTime(TimeValue.seconds(2))
        .mode(Throughput)
        .forks(1)
        .build();

    new Runner(opt).run();
  }

}

I wyniki:

Fibonacci - iteracja vs. strumień
Fibonacci – iteracja vs. strumień

No cóż, widać że nic nie zastąpi nam poczciwej pętli for. Niemniej obydwa algorytmy (tak naprawdę dwie różne implementacje algorytmu iteracyjnego) mają złożoność liniową i w większości wypadków można je stosować zamiennie.

I na tym kończę drugą część trylogii. Trzecia będzie bonusowa, pokażę implementację rekurencyjną w postaci serwera Http, zrealizowanego wg standardu NIO.

Kod całości udostępnię po trzeciej części.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.