Fastest way to clear group with a lot of shapes / multithreading

Question

In my JavaFX project I'm using a lot of shapes(for example 1 000 000) to represent geographic data (such as plot outlines, streets, etc.). They are stored in a group and sometimes I have to clear them (for example when I'm loading a new file with new geographic data). The problem: clearing / removing them takes a lot of time. So my idea was to remove the shapes in a separate thread which obviously doesn't work because of the JavaFX singlethread.

Here is a simplified code of what I'm trying to do:

HelloApplication.java

package com.example.javafxmultithreading;

import javafx.application.Application;
import javafx.fxml.FXMLLoader;
import javafx.scene.Group;
import javafx.scene.Scene;
import javafx.scene.shape.Line;
import javafx.stage.Stage;

import java.io.IOException;

public class HelloApplication extends Application {

    public static Group group = new Group();

    @Override
    public void start(Stage stage) throws IOException {
        FXMLLoader fxmlLoader = new FXMLLoader(HelloApplication.class.getResource("hello-view.fxml"));
        Scene scene = new Scene(fxmlLoader.load());
        stage.setTitle("Hello!");
        stage.setScene(scene);
        stage.show();

        for (int i = 0; i < 1000000; i++) {
            group.getChildren().add(new Line(100, 200, 200, 300));
        }
        HelloController.helloController = fxmlLoader.getController();
        HelloController.helloController.pane.getChildren().addAll(group);
    }

    public static void main(String[] args) {
        launch();
    }
}

HelloController.java

public class HelloController {

    public static HelloController helloController;
    @FXML
    public Pane pane;
    public VBox vbox;

    @FXML
    public void onClearShapes() throws InterruptedException {
        double start = System.currentTimeMillis();
        HelloApplication.group.getChildren().clear();
        System.out.println(System.currentTimeMillis() - start);

        Service<Boolean> service = new Service<>() {
            @Override
            protected Task<Boolean> createTask() {
                return new Task<>() {
                    @Override
                    protected Boolean call() {
                        // Try to clear the children of the group in this thread
                        return true;
                    }
                };
            }
        };
        service.setOnSucceeded(event -> {
            System.out.println("Success");
        });
        service.start();
    }
}

hello-view.fxml

<?xml version="1.0" encoding="UTF-8"?>

<?import javafx.geometry.*?>
<?import javafx.scene.control.*?>
<?import javafx.scene.layout.*?>

<VBox fx:id="vbox" alignment="CENTER" prefHeight="465.0" prefWidth="711.0" spacing="20.0"
      xmlns="http://javafx.com/javafx/11.0.2" xmlns:fx="http://javafx.com/fxml/1"
      fx:controller="com.example.javafxmultithreading.HelloController">
    <padding>
        <Insets bottom="20.0" left="20.0" right="20.0" top="20.0"/>
    </padding>
    <Pane fx:id="pane" prefHeight="200.0" prefWidth="200.0"/>
    <Button mnemonicParsing="false" onAction="#onClearShapes" text="Clear shapes"/>
</VBox>

I measured the time it took to remove different amounts of children from the group with group.getChildren().clear():

amount of children    |   time
100                       2ms = 0,002s
1 000                     4ms = 0,004s
10 000                    38ms = 0,038s
100 000                   1273ms = 1,2s
1 000 000                 149896ms = 149,896s = ~2,5min

As you can see, the time required increases exponentially.. And now imagine you have to clear the children in an UI and the user has to wait 2,5min for the application while it's freezing. Additionally, in this simplified example it's just a simple line, in the "real" application it's a more complicated geometry -> needs more time.

So another idea was to 'unbind' the group from it's parent, the pane. Because when it's unbind, I can remove it in another thread. That means 1. the ui doesn't freeze and 2. it will be faster. This was the try:

pane.getChildren().remove(group); // or clear()
// and then clear the group in another thread like above

The problem: this 'unbinding' takes also a lot of time. Not 2,5min, but like 0,5min, which is still to much.

Another idea was to create multiple groups, because as you can see, a group with 10 000 or 100 000 elements is cleared faster. That also failed because several groups suddenly take longer and are deleted exponentially faster. For example, the first takes 20 seconds, the second 10, the third 5, etc.

Long story short

Is there any chance to remove the children of the group in a seperate thread or faster than with group.getChildren().clear()? I tried everything that comes to my mind...

And if I could only show a loading bar while deleting, it would be better than just freezing the surface and waiting 2min...

I appreciate every idea / help.

EDIT, see comments Simple example without FXML:

import javafx.scene.Group;
import javafx.scene.shape.Line;

public class Test {

    public static void main(String[] args) {
        Group group = new Group();
        System.out.println("adding lines");
        for (int i = 0; i < 1000000; i++) {
            group.getChildren().add(new Line(100, 200, 200, 300));
        }
        System.out.println("adding done");

        System.out.println("removing starts");
        double start = System.currentTimeMillis();
        group.getChildren().clear();
        System.out.println("removing done, needed time: " + (System.currentTimeMillis() - start));
    }
}

Answer 1

The long execution time comes from the fact that each child of a Parent registers a listener with the disabled and treeVisible properties of that Parent. The way JavaFX is currently implemented, these listeners are stored in an array (i.e. a list structure). Adding the listeners is relatively low cost because the new listener is simply inserted at the end of the array, with an occasional resize of the array. However, when you remove a child from its Parent and the listeners are removed, the array needs to be linearly searched so that the correct listener is found and removed. This happens for each removed child individually.

So, when you clear the children list of the Group you are triggering 1,000,000 linear searches for both properties, resulting in a total of 2,000,000 linear searches. And to make things worse, the listener to be removed is either--depending on the order the children are removed--always at the end of the array, in which case there's 2,000,000 worst case linear searches, or always at the start of the array, in which case there's 2,000,000 best case linear searches, but where each individual removal results in all remaining elements having to be shifted over by one.

There are at least two solutions/workarounds:

1. Don't display 1,000,000 nodes. If you can, try to only display nodes for the data that can actually be seen by the user. For example, the virtualized controls such as ListView and TableView only display about 1-20 cells at any given time.

2. Don't clear the children of the Group. Instead, just replace the old Group with a new Group. If needed, you can prepare the new Group in a background thread.

   Doing it that way, it took 3.5 seconds on my computer to create another Group with 1,000,000 children and then replace the old Group with the new Group. However, there was still a bit of a lag spike due to all the new nodes that needed to be rendered at once.

   If you don't need to populate the new Group then you don't even need a thread. In that case, the swap took about 0.27 seconds on my computer.