„Dziel i zwyciężaj” sentencja, która przydaje się w codziennym programistycznym życiu. Mamy problem, podzielmy go na mniejsze i rozwiążmy. Podobną idę mamy we frameworku Fork/Join, mamy dużo danych lub coś nam się liczy długo. To wtedy, trzeba: podzieli, zrównoleglić i na samym końcu połączyć. Możemy się wtedy spodziewać, że otrzymamy przyśpieszenie.

Nie należy jednak przeginać, z tą ilością pracujących równolegle wątków. Bo jeżeli stworzymy więcej wątków niż mamy rdzeni procesora, to defakto stracimy czas na przełączanie zadań. Oczywiście w javie nie do końca będzie to prawdą, bo wirtualana maszyna javy sama zarządza sobie przełączaniem zadań i pracą wątków, ale warto o tym wspomnieć.

Aby wykorzystać Fork/Join, to warto wiedzieć:

  • jeżeli klasa ma zwrócić wynik to ma dziedziczyć po RecursiveTask<V>
  • jeżeli klasa nie zwraca wyniku to dziedziczy po RecursiveAction
  • uruchamianych jest tyle wątków ile mamy rdzeni procesora
  • egekutor ForkJoinPool zajmuje się rozdzielaniem zadań między wątkami
  • ważne jest określenie wielkości minimalnej paczki na której będziemy wykonywać obliczenia, żeby nie było tworzących zbyt dużo wątków roboczych.

Poniżej jest przykład wykorzystania frameworka Fork/Join, przy pomocy którego generowany jest fraktal Mandelbrota (start w przestrzeni: -1.5:-0.2, wielkość przestrzeni: 0.4:0.4, iteracji: 4096, rozdzielczość generowanego fraktala: 8192×8192 pikseli). Specjalnie tak dobrane parametry żeby wyliczenia trochę trwały. Na grafice kolorowymi ramkami zaznaczone są obszary renderowane przez różne wątki.

Mandelbrot Fork/Join

Generowane na Javie 8, procesor Core i7-4020HQ, 4 fizyczne rdzenie, 8 wątków. 1 stopień podziału to uruchomienie 4 instancji dzielących obraz na 4 części, i tak rekurencyjnie do osiągnięcia głębokości rysowania. Czasy generacji przedstawiają się następująco:

  • bez podziału – 1 wątek renderujący/0 dzielących – 454,56 sek.
  • podział 1 stopnia – 4 wątki dokonujących wyliczenia – 199,13 s
  • podział 2 stopnia – 16 wątków renderujących – 79,57 s
  • podział 3 stopnia – 64 wątki renderujące – 64,38 s
  • podział 4 stopnia – 256 wątki renderujące – 74,12 s
  • podział 5 stopnia – 1024 wątki renderujące – 67,97 s
  • podział 6 stopnia – 4094 wątki renderujące – 47,29 s
  • podział 7 stopnia – 16345 wątki renderujące – 35,36 s
  • podział 8 stopnia – 65092 wątki renderujące – 24,47 s
  • podział 9 stopnia – 256277 wątki renderujące – 20,28 s

Poprzez zastosowanie zrównoleglenie obliczeń mamy 22 razy szybciej, to się chwali.

Można było by zobaczyć po czasach generowania fraktala, że im więcej tym lepiej, jednak stworzenie kilku tysięcy wątków może spowodować niestabilność aplikacji. Trzeba wziąć również pod uwagę sprawę, że wirtualna maszyna javy optymalizuje kod bajtowy. Po parudziesięciu-paruset wywołaniach danej metody następuje kompilacja danego fragmentu do kodu maszynowego procesora przez kompilator JIT. Podejrzewam również błąd związany z dokładnością double, przy przeliczaniu przestrzeni fraktala, bo większe podziały za szybko mi się liczą 😕

Dlatego w ruch poszedł profiler JVM, gdzie poniżej prezentuję zrzuty ekranów z profilera VisualVM, dla uruchomienia bez podziału, z wykorzystaniem 4 wątków (podział 1 stopnia), oraz podział 9 stopnia (256277 instancje wątków renderujących, 87303 dzielących), oraz uruchomienie z trybem zapisu wyników kompilacji i zapisu pracy hotspota do pliku. Dla potomnych przełączniki:

-XX:+UnlockDiagnosticVMOptions -XX:+PrintCompilation -XX:+PrintInlining -XX:+LogCompilation

Na podstawie obserwacji dochodzę do takich wniosków (zaznaczam, że to są moje subiektywne odczucia):

  • przy jednym wątku to szkoda mówić, procesor nudzi się
  • jak widać podział na duże bloki danych nie wykorzystuje potencjału wielu rdzeni
  • ForkJoinPool bardzo łanie wykorzystuje wiele rdzeni. Uruchamia tyle wątków roboczych, ile mamy rdzeni procesora. Nawet jeżeli zrobimy kilka tysięcy instancji obiektów które mają wykonywać obliczenia, to w danej chwili jest uruchamianych tyle ile jest rdzeni cpu. Taki sposób zapobiega ze marnuje się czas na przełączanie wątków.

Resumując można używać.

Jak widać po logu optymalizacji, metody która były wywoływana często została zrekompuilowana do kodu maszynowego przez kompilator JIT (pl.jclab.examples.thread.Mandelbrot::generate, java.util.concurrent.RecursiveTask, com.badlogic.gdx.graphics.Pixmap::drawPixel, itd) oraz została przeprowadzona optymalizacja inline, metody (pl.jclab.examples.thread.Mandelbrot::generate, .badlogic.gdx.graphics.Pixmap::drawPixel, com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel) zostały połączone w jedną:

  21584  875     n 0       com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel (native)   (static)
  21584  876 %     3       pl.jclab.examples.thread.Mandelbrot::generate @ 84 (235 bytes)
                              @ 205   com.badlogic.gdx.graphics.Pixmap::drawPixel (11 bytes)
                                @ 7   com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel (11 bytes)
                                  @ 7   com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel (0 bytes)   native method
  21585  877       4       com.badlogic.gdx.graphics.Pixmap::drawPixel (11 bytes)
  21585  878       3       java.util.concurrent.RecursiveTask::<init> (5 bytes)
                              @ 1   java.util.concurrent.ForkJoinTask::<init> (5 bytes)
                                @ 1   java.lang.Object::<init> (1 bytes)
                              @ 7   com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel (11 bytes)   inline (hot)
                                @ 7   com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel (0 bytes)   native method
  21586  880 %     3       pl.jclab.examples.thread.Mandelbrot::generate @ 33 (235 bytes)
  21586  873       3       com.badlogic.gdx.graphics.Pixmap::drawPixel (11 bytes)   made not entrant
                              @ 205   com.badlogic.gdx.graphics.Pixmap::drawPixel (11 bytes)
                                @ 7   com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel (11 bytes)
                                  @ 7   com.badlogic.gdx.graphics.g2d.Gdx2DPixmap::setPixel (0 bytes)   native method
  21587  882 %     3       pl.jclab.examples.thread.Mandelbrot::generate @ 58 (235 bytes)

Tak samo widać z loga hot spota, że często używane fragmenty były kompilowane przez kompilator JIT.

Ekrany z profilera dla uruchomienia bez używania frameworka Fork/Join

p0_s1

p0_s2

p0_s3

Uruchomienie z 4 instancjami wątków roboczych (1 podział)

p1_s1 p1_s2 p1_s3

Uruchomienie z maksymalną ilością instancji wątków roboczych (9 podziałów)

p9_s1 p9_s2 p9_s3

import com.badlogic.gdx.ApplicationAdapter;
import com.badlogic.gdx.Gdx;
import com.badlogic.gdx.backends.lwjgl.LwjglApplication;
import com.badlogic.gdx.backends.lwjgl.LwjglApplicationConfiguration;
import com.badlogic.gdx.graphics.Color;
import com.badlogic.gdx.graphics.GL20;
import com.badlogic.gdx.graphics.Pixmap;
import com.badlogic.gdx.graphics.Texture;
import com.badlogic.gdx.graphics.g2d.SpriteBatch;
import com.badlogic.gdx.scenes.scene2d.ui.Label;
 
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
 
/**
 * Klasa dokonująca generowania madelbrotaz wykożystaniem frameworka Fork/Join
 */
class Mandelbrot extends RecursiveTask<Pixmap>{
 
   public static int threadCount = 0;
 
   //
   // Pozycje ekranowe
   //
   private int xStart;
   private int yStart;
 
   private int width;
   private int height;
 
   private Pixmap pixmap;
 
   //
   // Pozycje w przestrzeni fraktala
   //
   private double calcXStart;
   private double calcYStart;
 
   private double calcXStep;
   private double calcYStep;
 
   private int maxIterations;
   private int depth;
 
   private int calcDepth;
 
   private Color debug;
 
   public Mandelbrot(final Pixmap pixmap, int calcDepth){
 
      this.pixmap = pixmap;
 
      this.xStart = 0;
      this.yStart = 0;
 
      this.width = pixmap.getWidth();
      this.height = pixmap.getHeight();
 
      this.calcXStart = -1.5;
      this.calcYStart = -0.2;
 
      this.calcXStep = (0.2 * 2) / width;
      this.calcYStep = (0.2 * 2) / height;
 
      this.maxIterations = 4096;
 
      this.depth = 0;
      this.calcDepth = calcDepth;
 
      this.debug = Color.GREEN;
      threadCount = 0;
   }
 
   public Mandelbrot(final Pixmap pixmap, int xStart, int yStart, int width, int height,
                 double calcXStart, double calcYStart, double calcXStep, double calcYStep,
                 int maxIterations, int depth, int calcDepth, Color debug){
 
      this.pixmap = pixmap;
 
      this.xStart = xStart;
      this.yStart = yStart;
 
      this.width = width;
      this.height = height;
 
      this.calcXStart = calcXStart;
      this.calcYStart = calcYStart;
 
      this.calcXStep = calcXStep;
      this.calcYStep = calcYStep;
 
      this.maxIterations = maxIterations;
      this.depth = depth;
      this.calcDepth = calcDepth;
      this.debug = debug;
   }
 
   @Override
   public Pixmap compute(){
 
      //
      // Jeżeli osiągnieto maksymalną głębokość podziału to rysujemy wybrany fragment
      //
      if (depth >= calcDepth){
         threadCount++;
         generate();
      } else {
 
         //
         // Dzielenie ekranu i obliczanie przestrzeni podziału dla wyliczanego fraktala,
         // które są przekazywane do poszczególnych części
         // jest tutaj błąd: żle następuhe przeliczanie przestrzeni fraktala
         // w przypadku podziału na więcej części renderujących
         //
 
         int xOffset = width / 2;
         int yOffset = height / 2;
         int level = depth + 1;
 
         double calcOffsetX = calcXStart + (calcXStep * xStart);
         double calcOffsetY = calcYStart + (calcYStep * yStart);
 
         double calcOffsetX2 = calcXStart + (calcXStep * xStart) + (calcXStep * xOffset);
         double calcOffsetY2 = calcYStart + (calcYStep * yStart) + (calcYStep * yOffset);
 
         invokeAll(
         new Mandelbrot(pixmap, xStart, yStart, xOffset, yOffset, calcOffsetX, calcOffsetY, calcXStep, calcYStep, maxIterations, level, calcDepth,
                     Color.RED),
         new Mandelbrot(pixmap, xStart + xOffset, yStart, xOffset, yOffset, calcOffsetX2, calcOffsetY, calcXStep, calcYStep, maxIterations, level, calcDepth,
                     Color.YELLOW),
         new Mandelbrot(pixmap, xStart, yStart + yOffset, xOffset, yOffset, calcOffsetX, calcOffsetY2, calcXStep, calcYStep, maxIterations, level, calcDepth,
                     Color.BLUE),
         new Mandelbrot(pixmap, xStart + xOffset, yStart + yOffset, xOffset, yOffset, calcOffsetX2, calcOffsetY2, calcXStep, calcYStep, maxIterations, level,
                     calcDepth, Color.GREEN)
         );
      }
 
      debug();
 
      return pixmap;
   }
 
   /**
    * Rysowanie danego fragmentu fraktala
    */
   public void generate(){
 
      double px = 0, py = 0;
      double zx = 0.0, zy = 0.0, zx2 = 0.0, zy2 = 0.0;
      int value = 0;
      float grey = 0;
 
      py = calcYStart;
      for (int y = yStart; y < yStart + height; y++){
         px = calcXStart;
         for (int x = xStart; x < xStart + width; x++){
 
            zx = 0;
            zy = 0;
            value = 0;
 
            for (int m = 0; m < maxIterations; m++){
               zx2 = zx;
               zx = zx * zx - zy * zy + px;
               zy = 2 * zx2 * zy + py;
               if ((zx * zx + zy * zy) > 4){
                  break;
               }
               value++;
            }
            grey = ((maxIterations - value) * (54654564 / maxIterations));
            pixmap.drawPixel(x, y, ((int) grey << 24) | ((int) grey << 16) | ((int) grey << 8) | 255);
 
            px += calcXStep;
         }
         py += calcYStep;
      }
   }
 
 
   /**
    * Rysowanie ramiki debugującej
    */
   protected void debug(){
 
      if (debug != null){
         pixmap.setColor(debug);
         pixmap.drawRectangle(xStart, yStart, width, height);
      }
 
   }
}
 
/**
 * Główna pętla libGdx'a
 */
class Thread7ForkJoinMadelbrot extends ApplicationAdapter{
 
   SpriteBatch batch;
   Texture image;
   Pixmap pixmap;
   Mandelbrot mandelbrot;
   Label label;
   ForkJoinPool forkJoinPool;
 
   long single = 0;
   long multi = 0;
 
   @Override
   public void create(){
 
      batch = new SpriteBatch();
      pixmap = new Pixmap(2048, 2048, Pixmap.Format.RGB888);
      mandelbrot = new Mandelbrot(pixmap, 1);
      image = new Texture(pixmap);
      forkJoinPool = new ForkJoinPool();
 
 
      //
      // Generowanie w pojedyńczym wątku
      //
      long start = System.currentTimeMillis();
      mandelbrot.generate();
      long end = System.currentTimeMillis();
      single = (end - start);
      image.draw(pixmap, 0, 0);
 
      //
      // Generowanie z wykożystaniem frameworka Fork/Join
      //
      start = System.currentTimeMillis();
      final Pixmap mtPixmap = forkJoinPool.invoke(mandelbrot);
      end = System.currentTimeMillis();
      multi = (end - start);
      image.draw(mtPixmap, 0, 0);
 
      Gdx.app.log("Calc", "Thread:" + Mandelbrot.threadCount + " single: " + single + " ms multi Fork/Join: " + multi + " ms");
   }
 
   @Override
   public void render(){
 
      Gdx.gl.glClearColor(1, 0, 0, 1);
      Gdx.gl.glClear(GL20.GL_COLOR_BUFFER_BIT);
      batch.begin();
      batch.draw(image, 0, 0);
      batch.end();
   }
 
   @Override
   public void dispose(){
 
      batch.dispose();
      image.dispose();
   }
}
 
/**
 * Klasa uruchamiająca
 */
public class Run{
 
   public static void main(String[] args){
 
      LwjglApplicationConfiguration config = new LwjglApplicationConfiguration();
      config.width = 1024;
      config.height = 720;
      new LwjglApplication(new Thread7ForkJoinMadelbrot(), config);
   }
}

Aby uruchomić podany przykład należy utworzyć projekt mavena, do poma dodać zależności do libGdx’a, albo użyć poniższego.

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
   <modelVersion>4.0.0</modelVersion>
 
   <groupId>Mandelbrot</groupId>
   <artifactId>Mandelbrot</artifactId>
   <version>0.01</version>
 
   <name>Mandelbrot Fork/Join</name>
   <description>Demo project for Mandelbrot Fork/Join</description>
 
   <properties>
      <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
      <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
      <java.version>1.8</java.version>
   </properties>
 
   <dependencies>
 
      <dependency>
         <groupId>com.badlogicgames.gdx</groupId>
         <artifactId>gdx</artifactId>
         <version>1.9.5</version>
      </dependency>
 
      <dependency>
         <groupId>com.badlogicgames.gdx</groupId>
         <artifactId>gdx-platform</artifactId>
         <classifier>natives-desktop</classifier>
         <version>1.9.5</version>
      </dependency>
 
      <dependency>
         <groupId>com.badlogicgames.gdx</groupId>
         <artifactId>gdx-backend-lwjgl</artifactId>
         <version>1.9.5</version>
      </dependency>
 
   </dependencies>
 
   <build>
      <resources>
         <resource>
            <directory>./assets</directory>
         </resource>
      </resources>
      <plugins>
         <plugin>
            <groupId>org.apache.maven.plugins</groupId>
            <artifactId>maven-source-plugin</artifactId>
            <executions>
               <execution>
                  <id>attach-sources</id>
                  <phase>generate-resources</phase>
                  <goals>
                     <goal>jar-no-fork</goal>
                  </goals>
               </execution>
            </executions>
         </plugin>
         <plugin>
            <groupId>com.googlecode.mavennatives</groupId>
            <artifactId>maven-nativedependencies-plugin</artifactId>
            <version>0.0.6</version>
            <executions>
               <execution>
                  <id>unpacknatives</id>
                  <phase>pre-integration-test</phase>
                  <goals>
                     <goal>copy</goal>
                  </goals>
               </execution>
            </executions>
         </plugin>
         <plugin>
            <artifactId>maven-antrun-plugin</artifactId>
            <version>1.6</version>
            <executions>
               <execution>
                  <phase>integration-test</phase>
                  <configuration>
                     <target>
                        <java fork="true" classname="${mainClass}" classpathref="maven.test.classpath">
                           <sysproperty key="java.library.path" value="target/natives"/>
                        </java>
                     </target>
                  </configuration>
                  <goals>
                     <goal>run</goal>
                  </goals>
               </execution>
            </executions>
         </plugin>
 
         <plugin>
            <artifactId>maven-assembly-plugin</artifactId>
            <version>2.4</version>
            <configuration>
               <descriptorRefs>
                  <descriptorRef>jar-with-dependencies</descriptorRef>
               </descriptorRefs>
               <archive>
                  <manifest>
                     <mainClass>${mainClass}</mainClass>
                  </manifest>
               </archive>
            </configuration>
            <executions>
               <execution>
                  <id>make-assembly</id>
                  <phase>package</phase>
                  <goals>
                     <goal>single</goal>
                  </goals>
               </execution>
            </executions>
         </plugin>
      </plugins>
   </build>
</project>

Inne artykuły z tej serii: