pondělí 10. června 2019

Cancellation in .NET

.NET 4.0 introduced support for cancelling asynchronous operations using CancellationToken. It is a cooperative pattern, where one operation has a means to trigger cancellation of another operation by sending a cancellation request to it. In order for this to work, the receiver must listen for such requests and react appropriately. In other words, an operation can only be cancelled when the code is written with cancellation support in mind.

This article will explain how to properly implement this pattern.


There are the following two sides of  cancellation:

Allows the sender to trigger cancellation.

Allows the receiver to receive cancellation request.

In general the approach works as follows:

// the sender:
  // the sender operation creates a source ...
  var cts = new CancellationTokenSource();

  // ... and links it to a token
  var token = cts.Token;

  // the token is pased to the receiver
  var task = LongRunningOperation(token);


  // at some later point in time
  // the source is used to issue a cancellation request
// the receiver:
async Task LongRunningOperation(
  CancellationToken token = default(CancellationToken))
  while (...)
    // the receiver periodically checks for cancellation request
    // when triggered, the operation is cancelled
    // by throwing OperationCanceledException

    // do work

An Example

Let me now illustrate this concept with an example.  We will use a simple Windows Forms application, because it allows a straightforward demonstration of the concept, although the approach is universally applicable and can be used with any asynchronous code.

Our application allows to calculate highest prime number lower than a given max value. It contains an input field and two buttons - the Calculate button to start the calculation and the Cancel button to cancel it.

Efficient algorithms exist for this problem, however I have chosen a naive quadratic iteration so that the cancellation code stands out.

The application contains a single Form class:

public partial class Form1 : Form
  CancellationTokenSource cts;
There is a CancellationTokenSource stored as a class field. This is needed so that we can share it between the two button clicked handlers (see below).

  private long FindLargestPrimeNumber(
    long max, CancellationToken token = default(CancellationToken))
    var result = 1;
    for (int i = 2; i <= max; i++)
      if (IsPrime(i, token))
        result = i;
    return result;

  private bool IsPrime(
    int num, CancellationToken token = default(CancellationToken))
    for (int i = 2; i < num; i++)
      if (num % i == 0)
        return false;

    return true;
These two methods implement the computation algorithm. Note how the token is used for periodic cancellation checks.

Also note how the token is propagated through the whole call chain. This is a common practice as in general code which doesn't accept a cancellation token is impossible to cancel.

  private void calculateBtn_Click(object sender, EventArgs e)
    cts = new CancellationTokenSource();
    var token = cts.Token;

    Task.Run(() =>
      long max = -1;
      this.Invoke((Action)(() => 
        calculateBtn.Enabled = false;
        cancelBtn.Enabled = true;
        calculatingLbl.Visible = true;
        max = long.Parse(this.maxValueTxt.Text);

      long prime = -1;
        prime = FindLargestPrimeNumber(max, token);
      catch (OperationCanceledException)
      { }
      this.Invoke((Action) (() =>
        calculateBtn.Enabled = true;
        cancelBtn.Enabled = false;
        calculatingLbl.Visible = false;

        if (prime != -1)
          largestPrimeTxt.Text = prime.ToString();

    }, token);
This is the handler to start the computation. Note how a new CancellationTokenSource is created and CancellationToken retrieved. The token is then accessed in the asynchronously executed lambda function.

As explained above, upon cancellation an OperationCanceledException gets thrown deep within the computation algorithm, which then propagates all the way up the call stack. Note the catch block which interrupts the propagation and allows us to make sure the UI gets properly updated.

Since CancellationTokenSource is IDisposable, the Dispose call on the bottom is necessary so that allocated OS resources get freed up.

  private void cancelBtn_Click(object sender, EventArgs e)
The last piece is the handler to cancel the computation.

Linked Tokens and Timeouts

In addition to cancellations triggered by user actions, it is also possible to set up automatic cancellations based on timeouts. Since .NET 4.5 there is a convenient way to express this.

The timeout can be passed into the CancellationTokenSource constructor:

// create a token which will automatically get cancelled
// after a given time
var timespan = ...;
var cts = new CancellationTokenSource(timespan);
var token = cts.Token;
For existing sources, a timeout can be set through the CancelAfter method:

// set up cancellation for an existing token after a given time
var cts = new CancellationTokenSource();
var token = cts.Token;
var timespan = ...;
It is also possible to combine multiple sources of cancellation together. .NET allows to link a CancellationTokenSource to one or multiple existing cancellation tokens. The resulting token is cancelled when any of the linked sources is cancelled.

var token = ...; // original cancellation token
using (var cts = 
  var combinedToken = cts.Token;

An Example

We can use these features to modify the prime number calculation to get automatically cancelled when it isn't finished in 30 seconds. 

In this case it's only needed to specify the timeout in CancellationTokenSource constructor:

cts = new CancellationTokenSource(TimeSpan.FromSeconds(30));

Sample Code

You can download the full sample code from prime number calculator at GitHub.


In this article I have shown you how to properly implement cancellation in .NET, including timeouts and linked tokens.

čtvrtek 29. prosince 2016

Binary Heap - Top N Elements

Suppose we have a very large collection of items and need to select the first N, according to some criterion. In this article I will show you an efficient algorithm based on the heap data-structure and explain how to implement it using standard Java features.

An Example

As an example, suppose we created a very popular on-line game, such as Tetris. Over the few months since the game was published we've gathered a list of achieved scores with the following structure:

1 Jose Rodriguez 2016/10/01 14:55:02 154
2 Nefart 2016/12/15 03:12:21 12
3 SUF4N 2016/06/03 22:00:01 10280
4 EtnaVolcano 2016/12/24 18:56:15 1342
5 Guido 2016/09/09 07:15:00 280
Now we'd like to find the highest 10 achieved scores.

As our game has become quite popular, this list is very long. Let's say we've gathered a few millions of records.

Binary Heap

This is a task most suited for a heap data-structure. There are many variants of heap, of which the most basic and commonly known is binary (or 2-regular) heap.

According to Wikipedia:

Binary heap is a complete binary tree which satisfies the heap property - the key stored in each node is greater than or equal to the keys in the node's children, according to some total order function.

A complete binary tree is, put informally, a binary tree for which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

An Example Binary Heap

From the heap property follows an important observation - the greatest element is always located in the root of the tree. Also, given heap is a complete binary tree, it has logarithmic height. Therefore the following convenient time complexities:

  1. Insert O(log(N))
  2. FindMax O(1)
  3. DeleteMax O(log(N))

You can find a more detailed explanation and implementation details on the Internet.

Min vs. Max Heap

The above description holds for a so-called max-heap. Additionally, there also is
a min-heap, where the heap property is inverted and root node contains the minimum element.

It is useful to observe that a min-heap is just a max-heap with inverted ordering
function. Specifically:

x <fmax y <=> x >fmin y 
Therefore the distinction between max-heap and min-heap lies purely in what ordering function it takes. It is, however, a useful abstraction that simplifies communication and reasoning about heap behaviour.

The Algorithm

So how can we use a heap to solve the problem at hand?

A sequence of M elements, an appropriate ordering function and 
a positive number N. Supposing M >> N.

1. Build a min-heap of size N by inserting the first N elements.
2. For each remaining element:
      a) Insert the element.
      b) Delete the current minimum.
3. While heap is non-empty:
      a) Find and collect minimum.
      b) Delete minimum.
4. Return collected elements, in reversed order.

A sequence of top N elements of the input sequence.
A key observation here is that after i-th iteration in Step 2 the heap will contain
the top N elements of the N+i-th prefix of the input sequence. Therefore, at the end of step 2, after all items have been processed, it will contain the top N elements of the whole sequence.

Note that we've used a min-heap, even though we're interested in the N largest elements. This is an important trick that allows us to easily drop the smallest of the current N+1 largest elements in step 2b. Conversely, at the end in Step 4, we need to reverse the order of output, because the heap will give out the N largest elements sorted from the smallest.

Time And Space Complexity

The total time complexity of the algorithm is O(M log(N)), where M is the size of the input sequence and N is the size of the output sequence. Note that M >> N and so this bound is much better than for e.g. sorting the whole input sequence. Often N is very small, such as 10. In that case the time complexity is essentially O(M).

The heap can be implemented using an underlying array of size N. Therefore the space complexity of this algorithm is O(N), which is also very good.


Now that the algorithm is clear, let's look at how we can implement it in Java. The standard library provides a binary heap implementation under a class named PriorityQueue.

It has the following interface:

public PriorityQueue(int initialCapacity, Comparator<E> comparator)


The initialCapacity determines the initial size of the underlying 
array. This is just a technical detail. PriorityQueue is an 
unbounded queue and the array will grow as needed.

The comparator implements the ordering function. PriorityQueue is 
a min-heap - root note will contain the record which the comparator
deems smallest. If you need a max-heap, just give it a reversed 
(see java.util.Collections#reverseOrder(Comparator<T> cmp)).
public boolean add(E element)

public int size()

public E poll()

Retrieve and delete min.

The Implementation

Using PriorityQueue the algorithm can be expressed in a straight-forward way.

public class TopN {
  public static <T> List<T> getTopN(Stream<T> entries, Comparator<T> comparator, int count) {

    PriorityQueue<T> queue = new PriorityQueue<>(count + 1, comparator);
    entries.forEach(entry -> {
      if (queue.size() > count) {

    List<T> result = new ArrayList<>(queue.size());
    while (!queue.isEmpty()) {

    return result;

Back to our Example

Now that we have the algorithm implemented we just need to provide the representation of a record and the ordering function for our specific use-case.

public class Score {
  int id;
  String player;
  Date date;
  int score;
The @Value annotation comes from Project Lombok and denotes a value-object. It is just some syntactic sugar that allows to make our class definitions clearer. The compiler will augment the AST - make all those fields private and final, generate a corresponding getter for each of them plus an all-arguments constructor.

The comparator will look as follows:

public class ScoreComparator implements Comparator {
  public int compare(Score first, Score second) {
    return Integer.compare(first.getScore(), second.getScore());
With all the pieces in place we can now use them this way:

Stream<Score> scores = ...; // obtain a stream of all scores
List<Score> top10 = TopN.getTopN(scores, new ScoreComparator(), 10);
This will give us the 10 greatest scores achieved in our game.


In this article we've seen a brief overview of the heap data-structure and demonstrated, based on a use-case, one type of applications it is very useful for.

You can find the complete code on GitHub under dusan-rychnovsky/top-n.

sobota 21. února 2015

A Proper Visitor Implementation

As you probably know, Visitor is a design pattern originally defined by Gamma, Helm, Johnson and Vlissides in their book called Design Patterns - Elements of Reusable Object-Oriented Software. There, the intent of this pattern was described as:

Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.
Today, the Internet is flooded with web pages describing individual patterns, including Visitor. However, these pages only include trivial examples, which provide little help when implementing Visitor in a real-world application. Unfortunately, the Design Patterns book does not include any more advanced examples either.

The Problem

In my experience, a typical usage of this pattern is as follows: You've got a tree-like data structure on which you need to implement multiple different operations. For example:
  1. calculate certain properties (tree depth, average number of child nodes, etc),
  2. convert the tree to a different format (serialize it to a string, etc),
  3. etc.
Because a tree is inherently a recursive data structure, it is a good idea to follow the Divide and conquer principle when implementing these operations - to assemble the result for a given node based on the results for it's child nodes. This is where the simple implementations fall short.

A Solution

In this article I'd like to present a slightly modified implementation that supports easy and efficient access to sub-results.

As an example, suppose that we need to store and evaluate boolean expressions. A boolean expression can be represented as a tree-like structure, with atomic propositions as leaf nodes and boolean operations as intermediary nodes. The evaluation of such an expression is a great case for Visitor.

To represent such functions, we'll need to build a hierarchy consisting of the following classes:
  1. Expression - a generic boolean expression,
  2. Atom - an atomic proposition,
  3. Negation - a negation of an expression,
  4. Conjunction - a conjunction of two expression,
  5. Disjunction - a disjunction of two expression.
Let's first focus on the Visitor implementation. The following is a generic Visitor interface. For every operation (such as evaluating an expression), we'll create a separate implementation.

public interface Visitor<T> {
    public T visit(Atom atom);
    public T visit(Negation neg);
    public T visit(Conjunction con);
    public T visit(Disjunction dis);

It is important to note that this interface is parametrized - here T stands for the type of result of the represented operation. Every method accepts an expression of some kind as an argument and returns the result of applying the represented operation on that expression. This allows us to implement these methods using recursive calls according to the expression structure, as we'll see below. This is where this approach differs from those presented in existing articles.

In our case, T is going to be Boolean, as evaluating a boolean expression results into a single boolean value. For other operations this could be different.

Let's now take a look at the implementation.

public class Evaluate implements Visitor<Boolean> {
    private final Map<Atom, Boolean> valuation;

    public Evaluate(Map<Atom, Boolean> valuation) {
        this.valuation = new HashMap<>(valuation);

    public Boolean visit(Atom atom) {
        Boolean result = valuation.get(atom);
        if (result == null) {
            throw new IllegalArgumentException(
                "Missing valuation for atom [" + atom + "]."
        return result;

    public Boolean visit(Negation neg) {
        Boolean subResult = neg.getExpr().accept(this);
        return !subResult;

    public Boolean visit(Conjunction con) {
        Boolean leftSubResult = con.getLeftExpr().accept(this);
        Boolean rightSubResult = con.getRightExpr().accept(this);
        return leftSubResult && rightSubResult;

    public Boolean visit(Disjunction dis) {
        Boolean leftSubResult = dis.getLeftExpr().accept(this);
        Boolean rightSubResult = dis.getRightExpr().accept(this);
        return leftSubResult || rightSubResult;

Please note again how applying the Divide and conquer principle resulted into a very clear and concise implementation.

The last piece of puzzle is the Expression interface. It looks as follows.

public interface Expression {
    public <T> T accept(Visitor<T> visitor);

The important part is the accept method declaration. It is generic, which allows to use it together with a Visitor of any result type.

For the sake of completeness, let's now look at the rest of the Expression hierarchy.

public class Atom implements Expression {
    public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);

public class Negation implements Expression {
    private final Expression expr;

    public Negation(Expression expr) {
        this.expr = expr;

    public Expression getExpr() {
        return expr;

    public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);

public class Disjunction implements Expression {
    private final Expression leftExpr;
    private final Expression rightExpr;

    public Disjunction(Expression leftExpr, Expression rightExpr) {
        this.leftExpr = leftExpr;
        this.rightExpr = rightExpr;

    public Expression getLeftExpr() {
        return leftExpr;

    public Expression getRightExpr() {
        return rightExpr;

    public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);

Lastly, the following snippet shows how to put all the pieces together to evaluate a sample boolean expression.

Atom a = new Atom();
Atom b = new Atom();
Atom c = new Atom();

Expression expr = new Disjunction(
    new Conjunction(
        new Negation(

Map<Atom, Boolean> valuation = new HashMap<>();
valuation.put(a, true);
valuation.put(b, true);
valuation.put(c, false);

Visitor<Boolean> evaluate = new Evaluate(valuation);


Compared to traditionaly presented Visitor implementations, the one described in this article offers greater flexibility and allows to take advantage of the Divide and conquer principle, which is very convenient when dealing with recursive data-structures. The cost is a certain complexity increase due to the introduction of generic types.

If you have any questions and/or comments, please don't hesitate to contact me. I'll appreciate any feedback!