Goal:
Implement a way to a cancel FastTree training during runtime without impacting the performance too much.

Solution proposal:
Identify code paths that are CPU intensive such as tight loops and place a check in them for cancellation signal.

Below are the performance graphs of FastTree run from this example. The graph will have a function selected and red stripes indicate the position in the graph it is called.

The first checkpoint would be InitializeBins as evident from the below graph. We see before training there is the data prep step that is CPU intensive. In this step transpose of the dataset is created in-memory and binning of features is done.

The second place would be somewhere in the Feature Flock creation. Here we think CreateFlocksCore would be ideal. Based on the below graph.

The third place would be at FeatureHistogram ctr called by CreateSufficientStats. This function is called by constructor of LeastSquaresRegressionTreeLearner within a loop that creates CreateSufficientStats. We will just place a checkpoint in this loop.

The last place would be somewhere we do the splitting of the nodes and partitioning of the data to construct the tree. We see that FindBestThresholdForFlockThreadWorker() seems to be a good place to check for cancellation signal as it seems to consume bulk of CPU cycles as evident from the red stripes in the graph. We can also place the checkpoints into the functions that it calls such as FindBestThresholdFromHistogram, Sumup, SubtractCore, FillSplitCandidates, FindBestSplitForFeature but I think place checks in the inner function could degrade the performance.

CC: @TomFinley , @eerhardt , @shauheen , @glebuk