# Wie kann ich eine kleine Stelle in meinem Code mit multiplen Threads abarbeiten..?



## sirbender (17. Mai 2017)

Hallo,
ich habe ein recht komplexes Programm, bei dem ich einen kleinen Bereich mit mehreren Threads ausfuehren will.

Ich habe mal ein minimales Beispiel geschrieben, damit man ungefaehr sieht was ich nebenlaeufig ausfuehren will.

Ich hab den Bereich der durch mehrere Threads ausgefuehrt werden soll mit // mehrere Threads markiert. Im Beispiel werden zufaellig 1000 Quadrate erzeugt mit der Kantenlaenge 10. Die Position x,y der Quadrate ist zufaellig. Einige Quadrate ueberlappen und dies ist nicht erlaubt. Im Rechenschritt der parallelisiert werden soll, werden die Quadrate durchlaufen und geschaut ob sie mit einem Quadrat in der "output" Liste ueberlappen. Wenn ja, bekommt das Quadrat eine neue Position bis keinen Konflikt mehr gibt und es dann der "output" Liste hinzugefuegt wird.


```
public class MultiThreadedAccess {

    public static void main(String[] args) {
        int n = 1000;
        Random ran = new Random();
        int w = 10, h = w;
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++) {
            input.add(new Rectangle(ran.nextInt(n), ran.nextInt(n), w, h));
        }

        List<Rectangle> output = new ArrayList<Rectangle>(n);

        // mehrere Threads
        for (Rectangle r : input) {
            expensiveCalc(r);
            while (conflicts(r, output)) {
                Point p = expensiveCalc(r);
                r.setLocation(p.x, p.y);
            }
            output.add(r);
        }
        // mehrere Threads
    }

    private static boolean conflicts(Rectangle r, List<Rectangle> output) {
        for (Rectangle fixed : output) {
            if (r.intersects(fixed)) {
                // System.out.println(r + " conflicts " + fixed);
                return true;
            }
        }
        return false;
    }
}
```


----------



## Thallius (17. Mai 2017)

Eine parallelisierung wird hier wenig Sinn machen denn die Threads müssten sich ja gegenseitig blockieren. Sonst könnten ja zwei Threads gleichzeitig die gleiche Position testen und für leer befinden und dann das rechteck dort platzieren. Schon hast du zwei Rechtecke übereinander. 

Gruß

Claus


----------



## sirbender (17. Mai 2017)

Das ist leider nur ein Minimalbeispiel. Der conflicts() Test dauert nur sehr kurz und davor gibt es immer einen Aufruf von "expensiveCalc()".

Ich hab mal das Beispiel gefixt. Der "conflicts()" Test haengt von den anderen Quadraten ab, die "expensiveCalc()" nicht.

D.h. es ist sehr wahrscheinlich, dass einige Threads gerade mit der expensiveCalc() beschaeftigt sind waehrend nur 1-2 Threads den conflicts() Test machen wollen.


----------



## mrBrown (17. Mai 2017)

Das dürfte eigentlich recht simple sein, im Wesentlichen musst du nur das innere der forEach parallel, laufen lassen, zB mit Streams oder händisch mit ExecutorService, und die Aufrufe von conflicts und add synchronisieren.


----------



## JCODA (17. Mai 2017)

Wäre das folgende eine "richtige" Lösung? 


```
import java.awt.Point;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class MultiThreadedAccess {
   
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int n = 100;
        Random ran = new Random();
        int w = 10, h = w;
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++) {
            input.add(new Rectangle(ran.nextInt(n), ran.nextInt(n), w, h));
        }

        List<Rectangle> output = new ArrayList<Rectangle>(n);
        input.stream().parallel().forEach(r -> loopFor(r,output));       
        long mid = System.currentTimeMillis();       
        System.out.println("finished parallel: "+ (start-mid));
       
       
        List<Rectangle> output2 = new ArrayList<Rectangle>(n);
        input.stream().forEach(r -> loopFor(r,output2));
        long end = System.currentTimeMillis();       
        System.out.println("finished non-parallel: "+ (mid-end));
       
    }

    private static void loopFor(Rectangle r, List<Rectangle> output){
        expensiveCalc(r);
        while (conflicts(r, output)) {
            Point p = expensiveCalc(r);
            r.setLocation(p.x, p.y);
        }
        synchronized(output){
            output.add(r);
        }           
    }
   
    private static Point expensiveCalc(Rectangle r) {
        try {
            Thread.sleep(50);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }       
        return new Point((int)(Math.random()*10000),(int)(Math.random()*10000));
    }

    private static boolean conflicts(Rectangle r, List<Rectangle> output) {
        synchronized(output){
            for (Rectangle fixed : output) {
                if (r.intersects(fixed)) {
                    // System.out.println(r + " conflicts " + fixed);
                    return true;
                }
            }
       
            return false;
        }
    }
}
```


----------



## sirbender (18. Mai 2017)

Vielen Dank. Puhhh...ich glaube ich muss mich erstmal in Streams einlesen bevor ich es wirklich kapiere. Normalerweise parallelisiere ich mit ExecutorService


----------



## sirbender (22. Mai 2017)

Hi,
ich hab mir noch ein paar mehr Gedanken gemacht. Anbei der Code. Irgendwie passiert es manchmal, dass "output" nicht alle alle "Rectangles" aus Input hinzugefuegt bekommen hat. Und ich kann mir beim besten Willen nicht erklaeren woran das liegen kann. Hat irgendwer eine Idee?

Meistens rechnet das Programm richtig, aber manchmal eben nicht, dann spuckt es sowas aus: WTF! Only: 997. In output sind also 997 und nicht 1000 wie erwartet.

Ich habe den Code so abgeaendert, dass er alle Rectangle-Intersections durchgefuehrt hat und den "synchronized" Block erst betritt wenn er sich relativ sicher ist, dass er jetzt das Rechteck hinzufuegen darf. Klappt auch meistens.



```
public class MultiThreadedAccess4 {

    final static boolean DEBUG = false;
    final static int n = 1000;
    final static int w = 10, h = w;
    final static Random ran = new Random();
    static Lock lock = new ReentrantLock();
    static int syncCount = 0;
    static int intersectCount = 0;

    public static void main(String[] args) throws Exception {
        final int repeats = 100;
        for (int i = 0; i < repeats ; i++) {
            final List<Rectangle> input = getRandomInput();
            final List<Rectangle> output = new CopyOnWriteArrayList<Rectangle>();

            final List<Callable<Rectangle>> taskList = new ArrayList<Callable<Rectangle>>();
            for (final Rectangle r : input) {
                taskList.add(new Callable<Rectangle>() {
                    @Override
                    public Rectangle call() throws Exception {
                        return calc(r, output, true);
                    }
                });
            }

            final ExecutorService service = Executors.newFixedThreadPool(4);

            final long start = System.currentTimeMillis();
            service.invokeAll(taskList);
            final long end = System.currentTimeMillis();
            System.out.println("finished parallel: " + (end - start));

            fullConflictsCheck(output);
            System.out.println("SyncCount: " + syncCount);
            System.out.println("intersectCount: " + intersectCount);

            service.shutdown();
            syncCount = 0;

            if (output.size() != input.size()) {
                System.err.println("WTF! Only: " + output.size());
            }
            System.out.println();
        }
    }

    private static Rectangle calc(Rectangle r, List<Rectangle> output, boolean firstRun) {
        int conflictfreeIndex = resolveConflicts(r, output, firstRun);
        while (true) {
            final int newIndex = output.size(); // check if other threads added new rectangles to output
            final int diff = newIndex - conflictfreeIndex;
            if (DEBUG && diff != 0) System.err.println(Thread.currentThread().getName() + " Added after last Check: " + diff + " [" + conflictfreeIndex + "," + newIndex + "]");
            if (diff != 0) {
                // check if the new rectangles in output conflict with the current Rectangle
                for (Rectangle rx : output.subList(conflictfreeIndex, newIndex)) {
                    // System.err.println(r.getLocation() + " -> " + rx.getLocation());
                    if (r.intersects(rx)) return calc(r, output, false); // if yes, start over by calling this method again
                }
            }

            conflictfreeIndex = newIndex;
           
            // last test before entering the costly synchronized to increase chances that r can be added to output
            if (conflictfreeIndex == output.size()) { // check if other threads added new rectangles to output
                synchronized (output) {
                    syncCount++;
                    if (conflictfreeIndex == output.size()) { // last check if other threads added new rectangles to output
                        output.add(r);
                        return r;
                    }
                    if (DEBUG) System.err.println(Thread.currentThread().getName() + " Unsuccessful Sync: " + (output.size()-conflictfreeIndex) + " [" + conflictfreeIndex + "," + output.size() + "]");
                }
            }
            else if (DEBUG) System.err.println(Thread.currentThread().getName() + " Unsuccessful Pre-Sync: " + (output.size()-conflictfreeIndex) + " [" + conflictfreeIndex + "," + output.size() + "]");

        }
    }

    private static int resolveConflicts(Rectangle r, List<Rectangle> output, boolean firstRun) {
        if (firstRun == false) {
            r.setLocation(expensiveCalc(r));
        }
        int size = output.size();
        while (conflicts(r, output)) {
            r.setLocation(expensiveCalc(r));
            size = output.size();
        }
        return size;
    }

    private static boolean conflicts(Rectangle r, List<Rectangle> output) {
        for (Rectangle fixed : output) {
            if (r.intersects(fixed)) {
                intersectCount++;
                return true;
            }
        }
        return false;
    }

    private static Point expensiveCalc(Rectangle r) {
        try {
            Thread.sleep(5);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        return randomPoint();
    }

    private static Point randomPoint() {
        return new Point(ran.nextInt(n), ran.nextInt(n));
    }

    private static List<Rectangle> getRandomInput() {
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++) {
            input.add(new Rectangle(randomPoint(), new Dimension(w, h)));
        }
        return Collections.unmodifiableList(input);
    }

    private static boolean fullConflictsCheck(List<Rectangle> output) {
        int n = output.size();
        int totalCombinations = n * (n - 1) / 2;
        System.out.println("Total Combinations: " + totalCombinations);
        int tests = 0;
        int index = 0;
        for (Rectangle r : output) {
            index++;
            for (int i = index; i < output.size(); i++) {
                tests++;
                if (r.intersects(output.get(i)))
                    return true;
            }
        }
        System.out.println("No. of Conflict Tests: " + tests);
        return false;
    }
}
```


----------



## TheWhiteShadow (22. Mai 2017)

Der Ansatz ist gut, nur...
Du greift ständig auf dein output-array zu, ohne es zu synchronisieren. Dann führt deine calc-Methode eine rekursion innerhalb einer Schleife aus. Entscheide dich mal für eins davon. Beides ist hier überflüssig. Außerdem wartest du nicht, bis dein Executor-Service fertig ist, damit ist das Benchmarking an der Stelle sinnlos.

Ich habs mal ein bischen umgestrickt und so müsste es gehen:


```
public class AlternativResult
{
    final static boolean DEBUG = true;
    final static int n = 1000;
    final static int w = 10, h = w;
    final static Random ran = new Random();
//    static Lock lock = new ReentrantLock();
   
    static volatile int syncCounts = 0;
    static volatile int intersectCount = 0;
    static volatile int outputSize = 0;
    static volatile int doubleChecks;
   
    static final List<Rectangle> output = new ArrayList<Rectangle>(n);
   
    public static void main(String[] args) throws Exception
    {
        final int repeats = 10;
        for (int i = 0; i < repeats; i++)
        {
            output.clear();
            outputSize = 0;
            doubleChecks = 0;
            syncCounts = 0;
            intersectCount = 0;
           
            final List<Rectangle> input = getRandomInput();
           
            final ExecutorService calculator = Executors.newFixedThreadPool(4);
           
            final List<Runnable> taskList = new ArrayList<Runnable>();
            for (final Rectangle r : input)
            {
                taskList.add(new Runnable()
                {
                    @Override
                    public void run()
                    {
                        calc(r);
                    }
                });
            }
   
            final long start = System.currentTimeMillis();
           
            for (Runnable task : taskList)
            {
                calculator.execute(task);
            }
   
            calculator.shutdown();
            if (!calculator.awaitTermination(20, TimeUnit.SECONDS))
            {
                System.out.println("Timeout!!!!!");
            }
            final long end = System.currentTimeMillis();
            System.out.println("finished parallel: " + (end - start));
           
            System.out.println("outputSize:     " + outputSize);
            System.out.println("doubleChecks:   " + doubleChecks);
           
            if (fullConflictsCheck())
            {
                System.out.println("Konflikt!");
            }
           
            System.out.println("syncCounts:     " + syncCounts);
            System.out.println("intersectCount: " + intersectCount);
           
            if (output.size() != input.size())
            {
                System.err.println("WTF! Only: " + output.size());
            }
            System.out.println();
        }
    }
   
    private static void calc(Rectangle r)
    {
        CALC:
        while(true)
        {
            r.setLocation( expensiveCalc(r) );
            final int lastIndex;
            lastIndex = output.size()-1;
           
            for(int i = 0; i <= lastIndex; i++)
            {
                if ( r.intersects(output.get(i)) )
                {
                    continue CALC;
                }
            }
           
            final int newLastIndex;
            newLastIndex = output.size()-1;
           
            if (lastIndex != newLastIndex)
            {
                doubleChecks++;
                for(int i = lastIndex+1; i <= newLastIndex; i++)
                {
                    if ( r.intersects(output.get(i)) )
                    {
                        continue CALC;
                    }
                }
            }
           
            synchronized (output)
            {
                syncCounts++;
                for(int i = newLastIndex+1; i < output.size(); i++)
                {
                    if ( r.intersects(output.get(i)) )
                    {
                        intersectCount++;
                        continue CALC;
                    }
                }
                output.add(r);
                outputSize++;
                return;
            }
        }
    }
   
//    private static boolean conflicts(Rectangle r, List<Rectangle> output)
//    {
//        for (Rectangle fixed : output)
//        {
//            if (r.intersects(fixed))
//            {
//                intersectCount++;
//                return true;
//            }
//        }
//        return false;
//    }
   
    private static Point expensiveCalc(Rectangle r)
    {
        try
        {
            Thread.sleep(5);
        }
        catch (InterruptedException e)
        {
            e.printStackTrace();
        }
        return randomPoint();
    }

    private static Point randomPoint()
    {
        return new Point(ran.nextInt(n), ran.nextInt(n));
    }

    private static List<Rectangle> getRandomInput()
    {
        List<Rectangle> input = new ArrayList<Rectangle>(n);
        for (int i = 0; i < n; i++)
        {
            input.add(new Rectangle(randomPoint(), new Dimension(w, h)));
        }
        return Collections.unmodifiableList(input);
    }
   
    private static boolean fullConflictsCheck()
    {
        int n = output.size();
        int totalCombinations = n * (n - 1) / 2;
        System.out.println("Total Combinations: " + totalCombinations);
        int tests = 0;
        int index = 0;
        for (Rectangle r : output)
        {
            index++;
            for (int i = index; i < output.size(); i++)
            {
                tests++;
                if (r.intersects(output.get(i)))
                    return true;
            }
        }
        System.out.println("No. of Conflict Tests: " + tests);
        return false;
    }
}
```

Die zweite Prüfung in der calc-Methode hab ich eingebaut, um mal zu testen, wie oft die Liste während der ersten Prüfung weiter wächst. <10% der Fälle - Somit überflüssig.
Außerdem hab ich die Callable mal in Runnable umgeändert, weil es mich verwirrt hat, dass der Rückgabewert nirgens benutzt wurde.


----------



## mrBrown (22. Mai 2017)

TheWhiteShadow hat gesagt.:


> Du greift ständig auf dein output-array zu, ohne es zu synchronisieren


In den meisten Fällen ist das egal, da es eine CopyOnWriteArrayList ist (und lernt doch mal den Unterschied zwischen Array und Liste  )

Aber für Nutzung von Labels gehört man gesteinigt


----------



## sirbender (23. Mai 2017)

TheWhiteShadow hat gesagt.:


> Die zweite Prüfung in der calc-Methode hab ich eingebaut, um mal zu testen, wie oft die Liste während der ersten Prüfung weiter wächst. <10% der Fälle - Somit überflüssig.
> Außerdem hab ich die Callable mal in Runnable umgeändert, weil es mich verwirrt hat, dass der Rückgabewert nirgens benutzt wurde.



Vielen Dank. Die Labels sind zwar nicht huebsch, aber es ist ja eh nur Experimentiercode und es bleibt ja recht ueberschaubar.

Ich hab mal spasseshalber die Executor-Thread-Anzahl auf 16, 32, 64 erhoeht und manchmal wirft es dann im ersten Run eine Exception. Je hoeher die Thread-Anzahl desto wahrscheinlicher. Bei 4 oder 8 Threads hab ich die Exception nie gesehen. Auch wird sie wirklich nur im ersten Run geworfen, bis die VM warmgelaufen ist scheinbar.

Passieren sollte sowas aber trotzdem nicht. Irgendwie kapier ich auch immer noch nicht wo mein Sync-Problem war, da ich eben wie erwaehnt CopyOnWriteArrayList nutze und alle Schreibvorgaenge per 'synchronized' auf die CopyOnWriteArrayList-Instanz zusaetzlich beschraenkt habe. Aber vielleicht klaert sich das ja auf, wenn wir rausfinden warum dein Code eine Exception wirft?

Die Exception wird uebrigens beim intersects-Test geworfen. r oder output.get(i) scheinen Null zu sein. Komisch:

```
if (lastIndex != newLastIndex) {
                doubleChecks++;
                for (int i = lastIndex + 1; i <= newLastIndex; i++) {
                    if (r.intersects(output.get(i))) {
                        continue CALC;
                    }
                }
            }
```




> Exception in thread "pool-1-thread-4" java.lang.NullPointerException
> at java.awt.Rectangle.intersects(Rectangle.java:786)
> at exp.AlternativResult.calc(AlternativResult.java:104)
> at exp.AlternativResult.access$0(AlternativResult.java:86)
> ...






mrBrown hat gesagt.:


> und lernt doch mal den Unterschied zwischen Array und Liste



Wie meinst du das genau bezogen auf den Code von TheWhiteShadow oder meinen Code oder bezogen auf CopyOnWriteArrayList?


----------



## sirbender (23. Mai 2017)

Ich hab mal den Debugger angeschmissen und nach 10 Versuchen konnte ich die NullpointerException reproduzieren. Wie zu erwarten ist output.get(i) das Problem.


----------



## sirbender (23. Mai 2017)

Ich denke das Problem bei dir ist ArrayList. Der synchronized-Block verhindert nicht, dass andere Threads die ArrayList lesen, sondern nur, dass sie den Block betreten wenn sich gerade ein Thread darin befindet. Der Thread der gerade schreibt erhoeht den internen index (also die Size der Liste) BEVOR er den Wert von Null auf Rectangle aendert. Ein lesender Thread kann deswegen Null bekommen. Passiert nur sauselten...so selten, dass man extrem viele Threads nutzen muss, damit man es ueberhaupt mal sieht.

```
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
```

Bei CopyOnWirteArrayList wird erst eine Kopie des Arrays gemacht bevor das Rectangle hinzugefuegt wird. Alle lesenden Threads die output.get(i) aufrufen bekommen noch den alten Array zu sehen. Auch ist der array volatile, sodass wenn der schreibende Thread die Arrays mal austauscht die lesenden Threads nun sofort den neuen Array sehen.


```
public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
```


----------



## mrBrown (23. Mai 2017)

sirbender hat gesagt.:


> Wie meinst du das genau bezogen auf den Code von TheWhiteShadow oder meinen Code oder bezogen auf CopyOnWriteArrayList?


Auf seine Erklärung: 





TheWhiteShadow hat gesagt.:


> output-array


 ^^


----------



## sirbender (23. Mai 2017)

Uebrigens finde ich interessant, dass bei vielen Threads (z.B. 32), die doubleChecks eben doch wichtig werden. In dem Output unten sieht man beim zweiten Run, das es 353 doubleChecks gab. Ohne die haette es potentiell zu 353 zusaetzlichen syncCounts kommen koennen.

Finde die Parallelisierungsmethode richtig toll. Ich hab nur Mist beim ExecutorService gebaut indem ich nicht darauf gewartet hab, dass die Threads alle erfolgreich durchlaufen. Glaube das war mein einziger Fehler - werde das aber nochmal checken.



> finished parallel: 237
> syncTime: 77
> outputSize:     1000
> doubleChecks:   234
> ...


----------



## TheWhiteShadow (24. Mai 2017)

sirbender hat gesagt.:


> Der Thread der gerade schreibt erhoeht den internen index (also die Size der Liste) BEVOR er den Wert von Null auf Rectangle aendert.


ok, ich hätte mir die add-methode von der ArrayList mal anschauen sollen.^^
synchronisiert man alle "output.size()"-Zeilen gehts. Verwendet man einfach die Variable outputSize gehts auch.



mrBrown hat gesagt.:


> und lernt doch mal den Unterschied zwischen Array und Liste


output-array ist doch nur die Kurzform von output-array*list* 

Und Labels sind cool.


----------



## mrBrown (24. Mai 2017)

TheWhiteShadow hat gesagt.:


> output-array ist doch nur die Kurzform von output-array*list*


Allerdings ist *array* das Gegenteil von *list
*


TheWhiteShadow hat gesagt.:


> Und Labels sind cool.


Dafür gehört man vor'm steinigen noch geteert und gefedert...
Label zeugen eigentlich nur von einem: unglaublich schlechtem Code, den man am besten mit strg+A & Entf. refactored.


----------



## Meniskusschaden (25. Mai 2017)

Ach, was hätten wir damals für Label gegeben, als wir in alten BASIC-Tagen noch mit `GOTO zeilennummer`arbeiten mussten?


----------



## sirbender (25. Mai 2017)

10 Home
20 Sweet
30 GOTO 10


----------



## Xyz1 (25. Mai 2017)

Hier geht's anscheinend um Bashing.
Labels sind per se nicht evil.
Und "goto" hat man sich auch vorbehalten, wie sicherlich jeder weiß.

Dann zum eigentlichen Thema. Hat das Verfahren einen Namen? Dann wärn wir schonmal Schritt weiter. "Parallelisierung" gibts dann noch einiges zu beachten. Wisst ihr aber auch.


----------



## mrBrown (25. Mai 2017)

DerWissende hat gesagt.:


> Labels sind per se nicht evil.
> Und "goto" hat man sich auch vorbehalten, wie sicherlich jeder weiß.


Man kann sich auch mit der Schrotflinte in den Fuß schießen, ist auch nicht per se evil und hat man nicht verboten.


----------



## DrZoidberg (25. Mai 2017)

Hier mal eine andere Lösung mit Streams. Ohne irgendwelche Locks. Solange die Worker-Threads laufen wird input nicht verändert, daher sollte keine zusätzliche Synchronisierung nötig sein.

```
import java.util.List;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.IntStream;
import java.awt.Rectangle;
import java.awt.Point;

public class RecTest {
  private static Random ran = new Random();

  private static Rectangle randRect(int max) {
    return new Rectangle(ran.nextInt(max), ran.nextInt(max), 10, 10);
  }

  private static Point randPoint(int max) {
    return new Point(ran.nextInt(max), ran.nextInt(max));
  }

  private static BitSet getConflictingRectangleIdxs(List<Rectangle> input) {
    return IntStream.range(0, input.size()).parallel().mapToObj(idx -> {
      BitSet set = new BitSet(input.size());
      Rectangle r = input.get(idx);
      for(int i = idx + 1; i < input.size(); i++) {
        if(r.intersects(input.get(i))) {
          set.set(i);
        }
      }
      return set;
    }).reduce(new BitSet(input.size()), (bs1, bs2) -> {
      bs1.or(bs2);
      return bs1;
    });
  }

  static List<Rectangle> genNewList(List<Rectangle> input, int max, BitSet conflictingRectanglesIdx) {
    return IntStream.range(0, input.size()).parallel().mapToObj(idx -> {
      if(conflictingRectanglesIdx.get(idx)) return randRect(max);
      else return input.get(idx);
    }).collect(Collectors.toList());
  }

  public static void main(String[] args) throws Exception {
    int n = 20000;
    List<Rectangle> input = new ArrayList<Rectangle>(n);
    for(int i = 0; i < n; i++) input.add(randRect(n));

    long start = System.nanoTime();

    BitSet conflictingRectanglesIdx = getConflictingRectangleIdxs(input);

    while(conflictingRectanglesIdx.cardinality() > 0) {
      System.out.println("Anzahl ueberlappender Rechtecke = " + conflictingRectanglesIdx.cardinality());
      input = genNewList(input, n, conflictingRectanglesIdx);
      conflictingRectanglesIdx = getConflictingRectangleIdxs(input);
    }

    long end = System.nanoTime();
    double time = (end - start)/1e9;
    System.out.println("Anzahl ueberlappender Rechtecke = " + conflictingRectanglesIdx.cardinality());
    System.out.println("time = " + time +"s");
  }
}
```


----------

