FULL PRODUCT VERSION :
java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Windows 10

A DESCRIPTION OF THE PROBLEM :
Calling selectAll on a tableview's selection model is fast when you call it the first time, but noticeably slower when you call it the second time.

For example, with a 5000 row table with 3 columns, selectAll when only one row is selected takes:

setCellSelectionEnabled(false) : 5-10ms
setCellSelectionEnabled(true) : 13-30ms

and when all the rows are selected and selectAll is run:

setCellSelectionEnabled(false) : 350-600ms
setCellSelectionEnabled(true) : 3500-5000ms

This happens even when you use ctrl+A twice in a row, but is hard to detect visually. In the 5000 row example, if you hit ctrl+A twice, you won't be able to interact with the UI for at least 3 seconds. If you add a context menu with a select all option, it's much more obvious because the context menu freezes and stays open while the selection is occurring.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Click Select All

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The time taken for the first selection should be more than the time taken for the second selection, or at least close.
ACTUAL -
SelectAll from a state where everything is already selected takes significantly longer.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
package tabletestproject;

import javafx.application.Application;
import static javafx.application.Application.launch;
import javafx.beans.property.SimpleStringProperty;
import javafx.beans.property.StringProperty;
import javafx.collections.FXCollections;
import javafx.collections.ObservableList;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.SelectionMode;
import javafx.scene.control.TableColumn;
import javafx.scene.control.TableView;
import javafx.scene.layout.StackPane;
import javafx.scene.layout.VBox;
import javafx.stage.Stage;

public class SelectAllTwice extends Application {

    @Override
    public void start(Stage primaryStage) {
        StackPane root = new StackPane();
        Scene scene = new Scene(root, 300, 250);

        final ObservableList<StringProperty[]> data = FXCollections.observableArrayList();

        int numRows = 5000;
        for (int i = 0; i < numRows; i++) {
            data.add(new StringProperty[]{new SimpleStringProperty(String.format("Row %d", i)), new SimpleStringProperty("Col 2"), new SimpleStringProperty("Col 3")});
        }

        TableView<StringProperty[]> table = new TableView<>();
        table.getSelectionModel().setSelectionMode(SelectionMode.MULTIPLE);
        table.getSelectionModel().setCellSelectionEnabled(true);

        for (int i = 0; i < 3; i++) {
            TableColumn<StringProperty[], String> col = new TableColumn("Col " + (i + 1));
            col.setMinWidth(100);
            final int j = i;
            col.setCellValueFactory(row -> {
                return row.getValue()[j];
            });
            table.getColumns().add(col);
        }

        table.setItems(data);
        Button b = new Button("Select All");
        b.setOnAction((e) -> {
            long start = System.currentTimeMillis();
            table.getSelectionModel().selectAll();
            System.out.println(System.currentTimeMillis() - start);
            start = System.currentTimeMillis();
            table.getSelectionModel().selectAll();
            System.out.println(System.currentTimeMillis() - start);
        });

        root.getChildren().add(new VBox(b, table));

        primaryStage.setTitle("Selection Test");
        primaryStage.setScene(scene);
        primaryStage.show();
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        launch(args);
    }
}

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

CUSTOMER SUBMITTED WORKAROUND :
You can call clearSelection() on the selection model before calling selectAll. This dramatically improves performance.

If you want to improve the performance of the built in select all triggered by keyboard shortcuts, you can add your own listener which calls clearSelection() followed by selectAll() and then consumes the event.