Threading is a Poor Concurrency Programming Model

June 3, 2015 Leave a comment

Here’s why I try to avoid thread-based programming models for expressing concurrency:

The opponents of thread-based systems line up several drawbacks. For Ousterhout, who probably published the most well-known rant against threads [Ous96], the extreme difficulty of developing correct concurrent code–even for programming experts–is the most harmful trait of threads. As soon as a multi-threaded system shares a single state between multiple threads, coordination and synchronization becomes an imperative. Coordination and synchronization requires locking primitives, which in turn brings along additional issues. Erroneous locking introduces deadlocks or livelocks, and threatens the liveness of the application. Choosing the right locking granularity is also source of trouble. Too coarse locks slow down concurrent code and lead to degraded sequential execution. By contrast, too fine locks increase the danger of deadlocks/livelocks and increase locking overhead. Concurrent components based on threads and locks are not composable. Given two different components that are thread-safe, a composition of them is not thread-safe per se. For instance, placing circular dependencies between multi-threaded components unknowingly can introduce severe deadlocks.

Lee [Lee06] focuses on the lack of understandability and predictability of multi-threaded code, due to nondeterminism and preemptive scheduling. Multithreading appears to be error-prone, and very difficult to debug. The state explosion as a result from all possible interleavings of multiple threads renders a reasonable execution analysis of concurrent code virtually impossible. This is primarily caused by the unpredictability of preemptive scheduling. So, contrary to von Behren [vB03a], Lee argues that threads are precisely not a good abstraction for concurrent flows of execution. Quite the opposite, the oversimplifying abstraction of threads appears to be misleading, as it pretends a continuous execution of code that may not match any real runtime behavior.

Read the complete web page — it’s quite good.

Categories: Programming

Exploring the .NET CoreFX Part 17: Videotaped API Review

March 4, 2015 Leave a comment

This is part 17 of my Exploring the .NET CoreFX Series.

Microsoft’s .NET Core team has posted a videotaped API review session where they show how they review API enhancement suggestions. I thought the video was quite educational.

Categories: Programming Tags: ,

Exploring the .NET CoreFX Part 16: Platform-Specific Builds Using Compile-Time Polymorphism

March 1, 2015 Leave a comment

This is part 16 of my Exploring the .NET CoreFX Series.

While .NET has historically been limited to Windows machines, Mono notwithstanding, the introduction of the cross-platform .NET Core runtime has introduced the possibility of running .NET Core applications on Unix machines. With this possibility, developers may have the need of writing platform-specific code.

One way to write platform-specific code is:

  1. Define a conceptual base class which will have an identical name and methods across all platforms. This does not need to be a C# interface, as we will be using compile-time rather than run-time polymorphism.
  2. Provide an implementation of this class for each target platform.
  3. Use build-time conditions to include the platform-specific class based on target compilation platform.

An example from the .NET Core is the System.Console.ConsolePal class from the System.Console library. The library includes two implementations of this class:

  1. ConsolePal.Unix.cs, which provides a Unix-compatible implementation of the ConsolePal class
  2. ConsolePal.Windows.cs, which provides a Windows-compatible implementation of the ConsolePal class

The project file for this library, System.Console.csproj, then selects the appropriate file to build based on the target platform at compile time:

<!-- System.Console.csproj -->
...
<ItemGroup Condition=" '$(OS)' == 'Windows_NT' ">
  <Compile Include="System\ConsolePal.Windows.cs" />
  ...
</ItemGroup>
<ItemGroup Condition=" '$(OS)' == 'Unix' ">
  <Compile Include="System\ConsolePal.Unix.cs" />
  ...
</ItemGroup>

The advantage of this approach is that it has no run-time polymorphism overhead and thus provides maximum performance. The disadvantage of this approach is that the resulting binaries are platform-specific.

Recommendations

  • Avoid writing platform-specific .NET code unless it is completely unavoidable.
  • Consider using compile-time polymorphism to implement platform-specific code.
Categories: Programming Tags: ,

Exploring the .NET CoreFX Part 15: Using Non-Generic Factory Classes to Enable Type Inference

February 18, 2015 Leave a comment

This is part 15 of my Exploring the .NET CoreFX Series.

While C# supports type inference for generic methods, it does not support type inference for constructors. In other words, while this code works:

public class FooFactory
{
   public static Foo<T> Create<T>(T value)
   {
      return new Foo<T>(value);
   }
}
var myObj = FooFactory.Create(212);

This code does not:

public class Foo<T>
{
   private readonly T field;
   public Foo(T value) { field = value; }
}

var obj = new Foo(212); // DOES NOT WORK

For more background on why this is, see this StackOverflow post.

Because of this, every generic type in System.Collections.Immutable includes a factory class of the same name which makes construction more convenient. For example:

// Using the generic class which requires explicitly-specified types
var l = ImmutableList<int>.Empty.Add(1);
// Using the factory class to use inferred types
var l = ImmutableList.Create(1);

The same trick is also used with System.Tuple.

Recommendations

  • If you author a generic class, consider also providing a factory class with generic methods to enable type inference.

Exploring the .NET CoreFX Part 14: Inside Immutable Collections

February 13, 2015 Leave a comment

This is part 14 of my Exploring the .NET CoreFX Series.

Back in 2013, Immo Landwerth and Andrew Arnott recorded a Going Deep video called Inside Immutable Collections which describes how and why System.Collections.Immutable is built the way it is. It’s great background material to understand System.Collections.Immutable.

Exploring the .NET CoreFX Part 13: ImmutableList is an AVL Tree

January 13, 2015 Leave a comment

This is part 13 of my Exploring the .NET CoreFX Series.

Most implementations of IList, including System.Collections.Generic.List, are dynamic arrays. System.Collections.Immutable.ImmutableList is different — it is an AVL tree. This results in significantly different performance characteristics:

  List ImmutableList
Indexing O(1) O(log n)
Append O(1) average, O(n) worst-case O(log n)
Insert at arbitrary index O(n) O(log n)
Remove O(n) O(log n)
Memory layout Contiguous for value types Non-contiguous

The data structure behind ImmutableList was likely chosen so that modifications to the list are non-destructive and require minimal data copying.

Here’s a visual representation of what List and ImmutableList look like behind the scenes:

List ImmutableList
List l = new List();
Array0
ImmutableList l = ImmutableList.Create();
Empty
l.Add(1);
Array1
l = l.Add(1);
1
l.Add(2);
Array2
l = l.Add(2);
2
l.Add(3);
Array3
l = l.Add(3);
3
l.Add(4);
Array4
l = l.Add(4);
4

Exploring the .NET CoreFX Part 12: Aggressive Inlining

January 5, 2015 Leave a comment

This is part 12 of my Exploring the .NET CoreFX Series.

In C++, the inline keyword allows a developer to provide a hint to the compiler that a particular method should be inlined. C# has the identical ability but uses an attribute instead:

internal class SecurePooledObject<T>
{
    ....

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    internal bool IsOwned<TCaller>(ref TCaller caller)
        where TCaller : struct, ISecurePooledObjectUser
    {
        return caller.PoolUserId == _owner;
    }
}

In System.Collections.Immutable, this attribute is used highly selectively — only once, in fact.

Recommendations

  • In rare cases, consider using MethodImpl(MethodImplOptions.AggressiveInlining) to suggest to the .NET runtime that a particular method should be inlined.
Follow

Get every new post delivered to your Inbox.

Join 40 other followers