JDK-8223376 : Selection of multiple items in ListView hung UI
  • Type: Bug
  • Component: javafx
  • Sub-Component: controls
  • Affected Version: openjfx13
  • Priority: P3
  • Status: Closed
  • Resolution: Duplicate
  • OS: os_x
  • CPU: x86
  • Submitted: 2019-05-04
  • Updated: 2019-05-08
  • Resolved: 2019-05-08
Related Reports
Duplicate :  
Description
ADDITIONAL SYSTEM INFORMATION :
OpenJFX EAP: 13-ea+6

OpenJDK:
openjdk version "13-internal" 2019-09-17
OpenJDK Runtime Environment (build 13-internal+0-jdk13-jpackage.49)
OpenJDK 64-Bit Server VM (build 13-internal+0-jdk13-jpackage.49, mixed mode, sharing)


A DESCRIPTION OF THE PROBLEM :
I have ListView with several thousands items and enabled multi-select. When I try to select many items in ListView it hung whole application.

This functionality works fine in JDK 8 (I could select millions of item without any delays) but looks like was broken after this release.

REGRESSION : Last worked in version 8u192

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run test application (here Maven project for any case: https://github.com/maxd/listview_multiselect_performance ) or from code below.

Manual steps to reproduce:

1. Select first item in ListView
2. Scroll down to last item in ListView
3. Press `SHIFT` key and select last item

Steps to reproduce from code:

1. Click `Select %d items and measure selection time`

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Selected items must be selected without delay
ACTUAL -
Selection of multiple items hung application and macOS show mac rainbow wheel (it's mean that application doesn't respond).

---------- BEGIN SOURCE ----------
import javafx.application.Application;
import javafx.collections.FXCollections;
import javafx.collections.ObservableList;
import javafx.scene.Scene;
import javafx.scene.control.Alert;
import javafx.scene.control.Button;
import javafx.scene.control.ListView;
import javafx.scene.control.SelectionMode;
import javafx.scene.layout.VBox;
import javafx.stage.Stage;

public class App extends Application {
    @Override
    public void start(Stage stage) {
        int itemsCount = 20_000;

        ObservableList<String> list = FXCollections.observableArrayList();

        for (int i = 0; i < itemsCount; i++) {
            list.add(String.format("%07d", i));
        }

        ListView<String> listView = new ListView<>(list);
        listView.getSelectionModel().setSelectionMode(SelectionMode.MULTIPLE);

        Button button = new Button(String.format("Select %d items and measure selection time", itemsCount));
        button.setOnAction(actionEvent -> {
            long timestamp = System.currentTimeMillis();

            listView.getSelectionModel().selectRange(0, itemsCount - 1); // <== Here `selectRange` take a lot of time to select items

            String message = String.format("Selection time: %d seconds", (System.currentTimeMillis() - timestamp) / 1000);
            Alert alert = new Alert(Alert.AlertType.INFORMATION, message);
            alert.initOwner(stage);
            alert.showAndWait();
        });

        stage.setScene(new Scene(new VBox(listView, button)));
        stage.show();
    }
}

---------- END SOURCE ----------

FREQUENCY : always



Comments
Additional Information from submitter: I have found a place which cause this problem. Look at [this](https://github.com/javafxports/openjdk-jfx/blob/6d027bf6019b91723d7c88a48d1be8ad370db69e/modules/javafx.controls/src/main/java/javafx/scene/control/MultipleSelectionModelBase.java#L744) line at `MultipleSelectionModelBase.java`: ``` startAtomic(); List<Integer> sortedNewIndices = IntStream.concat(IntStream.of(index), IntStream.of(indices)) .distinct() .filter(this::isValidIndex) .filter(this::isNotSelected) .sorted() .boxed() .peek(this::set) // we also set here, but it's atomic! //!!!!! <== The `set` method is call a lot of times .collect(Collectors.toList()); stopAtomic(); ``` As you can see the `set` method is calling a lot of time inside `atomic` block. Let's look at [this method](https://github.com/javafxports/openjdk-jfx/blob/6d027bf6019b91723d7c88a48d1be8ad370db69e/modules/javafx.controls/src/main/java/javafx/scene/control/MultipleSelectionModelBase.java#L691-L701): ``` public void set(int index) { if (!isValidIndex(index) || isSelected(index)) { return; } _beginChange(); bitset.set(index); int indicesIndex = indexOf(index); _nextAdd(indicesIndex, indicesIndex + 1); _endChange(); } ``` As you can see it call `indexOf` method. Yes, it has `O(N)` complexity and together with stream-loop above this give `O(N^2)` complexity (may be even more because inside of `indexOf` it call `cardinality` method of `BitSet`). BUT this call of `indexOf` in this context in useless. Look at implementation of `_nextAdd`. If it's calling inside `atomic` context it do nothing. So, I suppose to fix this problem need to check `atomic` context inside `set` method and don't call `indexOf`: ``` public void set(int index) { if (!isValidIndex(index) || isSelected(index)) { return; } bitset.set(index); if (!isAtomic()) { _beginChange(); int indicesIndex = indexOf(index); _nextAdd(indicesIndex, indicesIndex + 1); _endChange(); } } ``` BUT this is fix this problem in one place. Looks like other methods can have the same problem i.e. nobody use computation of `indexOf` if they call from `atomic` context. I suppose need to check them too and fix if possible.
08-05-2019