Stack allocated closures make it into C#

Back in the days when I worked on Lisp compilers, I remember adding stack allocation of the closure records when calling local functions. In C# 7, we now have local functions and it is interesting to look at the optimisations that are applied for these.

Just for a base line let’s have a quick look at the implementation of lambda expressions which close over variables the current method. The implementation, which has been around for a long time, re-homes the locals into a heap allocated (Display) class. This extends the lifetime of the variables allowing the reference from the lambda expression to govern their lifetime.

        static Func<int,int,int> Check(int a, int b)
        {
            return (x, y) => (x + y + a + b);
        }

This is converted into code that as the following form. “a” and “b” have been re-homed into the heap allocated instance.

private static Func<int, int, int> Check(int a, int b)
{
    <>c__DisplayClass1_0 class_ = new <>c__DisplayClass1_0();
    class_.a = a;
    class_.b = b;
    return new Func<int, int, int>(class_.b__0);
}

The DisplayClas has the following definition, where we see the fields corresponding the captured variable, the definition of the lambda method is encoded into this class too.

[CompilerGenerated]
private sealed class <>c__DisplayClass1_0
{
    public int a;
    public int b;

    internal int b__0(int x, int y)
    {
        return (((x + y) + this.a) + this.b);
    }
}

Local functions take us to code that has the following form.

        static Func<int, int, int> Check2(int a, int b)
        {
            return Local;
            
            int Local(int x, int y)
            {
                return (x + y + a + b);
            }
        }

This is code generated slightly differently,

private static Func<int, int, int> Check2(int a, int b)
{
    <>c__DisplayClass2_0 class_ = new <>c__DisplayClass2_0();
    class_.a = a;
    class_.b = b;
    return new Func<int, int, int>(class_.g__Local|0);
}

We have the same style of DisplayClass, with the body of the local added as a method (as expected).

[CompilerGenerated]
private sealed class <>c__DisplayClass2_0
{
    public int a;
    public int b;

    internal int g__Local|0(int x, int y)
    {
        return (((x + y) + this.a) + this.b);
    }
}

However, there are now more optimisation possibilities. First, if the local function is scoped to the method in which it is defined, then it would be good to avoid the heap allocation.

        static int Check3(int a, int b)
        {
            return Local(1,2) + Local(3,4);

            int Local(int x, int y)
            {
                return (x + y + a + b);
            }
        }

This is indeed what happens.

private static int Check3(int a, int b)
{
    <>c__DisplayClass3_0 class_;
    class_.a = a;
    class_.b = b;
    return (g__Local|3_0(1, 2, ref class_) + g__Local|3_0(3, 4, ref class_));
}

The DisplayClass has been optimised to a struct

[CompilerGenerated]
private struct <>c__DisplayClass3_0
{
    public int a;
    public int b;
}

and the body has been added as a method into the class in which contains the method containing the local

[CompilerGenerated]
internal static int g__Local|3_0(int x, int y, ref <>c__DisplayClass3_0 class_Ref1)
{
    return (((x + y) + class_Ref1.a) + class_Ref1.b);
}

The compiler has essentially noticed that the local method cannot escape from the method that uses it, and hence we can try to avoid the heap allocation.

We should also quickly look at the case where the local method doesn’t capture any locals.

        static int Check4(int a, int b)
        {
            return Local(1, 2) + Local(3, 4);

            int Local(int x, int y)
            {
                return (x + y);
            }
        }

In this case, the method compiles to the following

private static int Check4(int a, int b)
{
    return (g__Local|4_0(1, 2) + g__Local|4_0(3, 4));
}

and the local method is simply defined as a static method int he defining class

[CompilerGenerated]
internal static int g__Local|4_0(int x, int y)
{
    return (x + y);
}

While we are here we could quickly cover one memory management gotcha around closures and their implementation.

        static (Func<int,int,int>, Func<int,int,int>) Check(int a, int b)
        {
            return ((x, y) => (x + y + a), (x, y) => (x + y + b));
        }

The implementation decides to put the local variables into a single DisplayCLass

private static ValueTuple<Func<int, int, int>, Func<int, int, int>> Check(int a, int b)
{
    <>c__DisplayClass1_0 class_ = new <>c__DisplayClass1_0();
    class_.a = a;
    class_.b = b;
    return new ValueTuple<Func<int, int, int>, Func<int, int, int>>(new Func<int, int, int>(class_.b__0), new Func<int, int, int>(class_.b__1));
}

This means that if either of the returned lambda expressions is alive (from the pint of the view of the GC), then the variables “a” and “b” are still alive. This might not seem to matter too much, but if “a” and “b” were large objects (for example), it does mean that their lifetime can be extended further than you might expect.

Advertisements
Posted in Uncategorized | Leave a comment

Progressive Web Applications

Building Progressive Web Apps: Bringing The Power of Native to the Web by Tal Ater

I was interested in reading this book because I’d been hearing a lot about service workers and wanted to understand what they were about. The whole Progressive Web Application has been something that Google has been pushing, and it has taken a while for other browser vendors like Microsoft and Apple to declare their support. However, with Microsoft’s recent inclusion of service workers in the latest developer release of Edge, this seems to be a technology that is going to be big – there will be talks on PWAs at //BUILD, and there are rumours that PWAs may replace UWP as one of the implementation mechanisms behind applications in the Windows Store.

The book is a really good introduction to PWAs.

The author’s github repository contains a lot of related material, but for the book he has chapter oriented versions of a web application, Gotham Imperial Hotel, which he converts into a progressive web application  (see the branches corresponding to the various chapters). This is a really good learning mechanism, and it is nice to be able to try and step through the code to see what is happening. Google Chrome, for example, lets you fake internet disconnection so that you can try out the service worker code that handles the offline state.

After a brief introduction to service workers, the first chapter of the book takes us through service workers as a proxy and how they can intercept HTTP requests and hence act as a caching mechanism. Most importantly, the service worker still runs even if the browser is offline, and given that the service can determine that it is running offline, it can return different HTML and hence give the user an experience even in this case.

The next chapter deals with the installation of a service worker. Service workers are queued for installation, and are only actually installed when there are no tabs in the browser visiting the target site  – it would obviously be confusing if different versions of a service worker were running in the different tabs targeting a particular site.  The chapter explains the lifecycle, which includes a state where the service worker can cache resources without it being expected to handle any request interception. If the worker can’t get the data it needs, it can set its state to say that it shouldn’t be used, and we should continue with the existing worker. All of this state transition code is asynchronous, and will use Promises to avoid blocking.

The next chapter demonstrates how service workers let us write offline first applications. It this model we are really using PWAs as a deployment model. The chapter covers various patterns of caching – for example, you might try to pre-cache pages, or might instead cache on first access, but then you might also check for updates when the cache is hit and refresh the cache with the new version of the page. The author talks through the various patterns.

The next chapter looks at IndexDB. This is a local database, implemented in the browser, that allows you to store JSON objects, and offers a cursor to walk through the various tables and indexes. There are various patterns you may use to update the database between versions of the service worker.

The service worker isn’t just a proxy for intercepting web requests. The next chapter covers background sync. If our application has been working offline, when we next go back online we’d like to resync with the application’s web site. The service worker is able to receive callbacks from a sync manager, implemented in the browser, which can take care of tracking the synchronisation steps that need to be carried out and maintain the list of pending synchronisations. This service will take care of starting up our service worker if it isn’t running, and will do so at a time where we are online.

The service is acting as a proxy between a site and the many possible tabs in the browser talking to that site.  You might therefore expect there to be a mechanism for the various tabs to talk to each other (so that they can coordinate between themselves over state), and this is what the next chapter covers. Messages can be posted, and message handlers can be registered.

Installation of a PWA, to give it a more permanent presence in the browser, is covered in the next chapter. Many web sites these days, nag you to install the mobile application version of their web site via interstitials, and this chapter talks about the heuristic driven way a browser allows you to install a PWA. In Chrome, for example, there are a number of things that trigger installation – regular use of the site for example.

Once your PWA is installed as an application, you might need a way for the site to notify you of interesting things that have happened. The next chapter covers the two different push notification mechanisms that you can can use. There appears to be more standardisation work required in this area,

The book finishes with a couple of chapters of UX for Progressive Web Applications and where PWAs are going in the future.

The author has done a good job of breaking down the material into the various chapter sized chunks, and having a github application that can show you the changes related to each chapter is a really good learning mechanism. PWAs seem to have many uses, from pseudo-applications that are easy to install, to a richer way to allow web applications to run offline.

Posted in Uncategorized | Leave a comment

Modern JavaScript for the win

Practical Modern Javascript by Nicolas Bevacqua

I needed a book to get up to speed with ECMAScript 6, a book that would assume some knowledge of JavaScript and would take me through the new features. This book meets those requirements exactly. As we work though the sections, it takes its time to describe what problems the new features are trying to fix, and puts it all together in a really informative 300 page book.

The introduction discusses the various themes behind the added features, and then tells you how to configure Babel so that you can see how some of the new features can be transpiled down into code that will run on a large number of browsers. There’s an online REP for Babel here. ES6 has a large amount of new syntactic sugar, and it is great to be able to play around and see how such additions are converted into the old language – it really aids the understanding.

It was impressive to me how much JavaScript has moved forwards as a language. I remember going to a talk by Mark Miller many years ago where he discussed using revocable proxies to enable mashups, and it is impressive to see how the proxy mechanism can be used for this kind of thing, as well as many other types of meta-programming. I also remember reading articles that described the various patterns to define object-oriented class like entities, and it’s great to see that one standard pattern has now been put into the language.

Promises, generators and iterators (which should really be ordered the other way to describe how the features build on one another) bring really useful higher level programming to the language, and the inclusion of proper maps and sets give us a proper language at last. There’s also a new module system to make programming in the large much easier, and also a number of  new built-ins as well as additional methods on existing types.

What features do I think are really useful?

The extensions to the property syntax – method definitions, shorthands and computed property names

  var x = "hello"
  var y = { x, [x]:29, test(x) {return x+2}}

Argument destructuring and the spread operator.

  var f = x => x + 1
  var x = [1,2,3,4]
  var y = [...x, ...x]
  var [p, ...q] = x

Arrow functions and let and const together with temporal dead zone

  const x = 20
  let y = 40
  let f = a => a * x + y

The class statement which expands to one of the old class patterns where you define a constructor function and set the relevant prototype.

class MyPoint {
    constructor(x,y) {
        this.x = x
        this.y = y
    }
    sum() {
      return this.x + this.y
    }
}
class NextPoint extends MyPoint {
    constructor(x,y,z) {
        super(x,y) 
        this.z = z
    }
}

var p = new NextPoint(1,2,3)

ES6 adds a new extensibility mechanism, the Symbol, which allows you to add items to an object that won’t be found by the standard for..in, Object.keys and Object.getOwnPropertyNames. This gives a way to add methods to make an object iterable, for example, without old code finding that it is being returned new keys in its iterations of an object’s properties.

There are some new utility methods on Object, such as assign which allows you to take a default object and modify the properties,

Object.assign({}, defaults, options);

Also “is” which is a modified form of the === operator where

Object.is(NaN, NaN); // is true
Object.is(+0, -0); // is false

and Object.setPrototypeOf for setting the prototype (if you don’t want to set it when using Object.create).

There is also the concept of decorators which allow you to add additional functionality to classes and statically defined properties. This post offers a few examples.

The most interesting part of the book was the chapter on Promises, which also covers  iterators and the implementation of async. The book works through the design of promises, starting with a description of callback hell and describing how promises help with this issue.

    var reject, resolve
    var p = new Promise((a,b) => { resolve = a; reject = b })
    p.then(() => console.log("ok1"));
    p.catch(() => console.log("fail")).then(() => console.log("ok2"));
    reject(new Error("testing"))

It builds up nicely, with the author spending time talking about Promise.all and Promise.race, before moving on to the Iterable protocol.

const mySequence = {
    [Symbol.iterator]() {
        let i = 0
        return { next() { i++; var value = i; var done = i > 5; return {value,done} } } } }

for (var x of mySequence) { console.log(x); }

The book that talks about generators,

function* test() {
  yield 1;
  yield 2;
}

for (var x of test()) { console.log(x); }

and then async/await

var resolve;

var p = new Promise(r => resolve=r)

async function play() {
  console.log("start")
  await p
  console.log("end")
}

play()  // prints "start"

resolve(20)  // prints "end"

The author spends time describing the transformation that happens when translating the async function into a generator, and how the steps of the generator are forced.

Chapter 5 looks at the new Map/WeakMap/Set/WeakSet datatypes and this is followed by a chapter on the new proxies, which allow controlled access to objects. This part of the language allows you to provide objects to foreign libraries, without having to give that foreign library full control of the object. There is a lot of discussion about the various traps that can be set up and handled, and how you can use the Reflect object to carry on with the default action after intercepting the call.

Chapter 7 of the book discusses a whole load of built-in improvements in ES6, including much better handling of Unicode characters that aren’t on the BMP, and this is followed by a great chapter on the new module system.

In the last, short chapter of the book, the author discusses the language changes, and which parts of the language he considers to be important.

All considered this is a very good book, showing the numerous changes to the language and discussing the reasons behind the changes.

Posted in Uncategorized | Leave a comment

Dependent Types

I’ve been doing a fair amount of reading about dependent types recently, mainly because we have been working through the Idris book as a weekly lunchtime activity at work.

For a good article on the current state of play in Haskell, Richard Eisenberg’s thesis is very good – chapter 2 discusses a load of extensions of Haskell to enable type level programming. He also has a good series of blog posts on various Dependent Types aspects. There are a number of interesting YouTube videos too, including this one of using dependent types in a RegExp library.

At some level, the type checking becomes theorem proving. For the Idris language, there are slides from a talk on how this process happens, and there’s another phd thesis on type checking Haskell which discusses some of the trade offs.

While we are talking about type checking, there is a repository where the author is writing variants on Hindley-Milner type checking in F#. It’s a very interesting learning resource, as the examples are small enough to step in the debugger, so you can watch what happens when a let bound function is generalised by the system.

There’s always that interesting point between type checking and proof, and this github repository uses Idris to generate proofs about various Minesweeper boards.

Posted in Uncategorized | Leave a comment

C# fun with structs

I’ve just spent a while trying to catch up with all the changes to valuetypes in C# 7.x. As someone who doesn’t use the struct keyword in C# very often at all, it is quite amazing all of the changes to C# around this area. This talk is a very good summary.

The key point about structs is that they allow you to avoid some of the heap allocation that can be very bad for certain types of application. In the recent versions of C# the language has changed to allow the user to maintain a pointer to a struct, and hence use that rather than a copy of the original struct.

The classic example is something like the following (where we use a local function to make the example easier to read).

  var data = new[] {1, 2, 3, 4, 5};
  ref int second = ref GetItem(data);
  second = 5;

  ref int GetItem(int[] incoming)
  {
    ref int x = ref incoming[2];
    return ref x;
  }

In the example, the local variable, second, is an alias to the item in the data array, and so any change to either can be seen when viewing the data via the other item. The first thing one notices is the addition of a lot of “ref” keywords to make it clear that the local variable is holding an alias, and that the result of the method call is an alias to something else. It’s a shame that there was a better syntax for this.

There are two other things that have happened in this area. The use of the “in” modifier and the ability to define a struct as readonly.

In the classic struct as a parameter case, the struct is copied on the way in to the method. Hence, for the example struct,

struct A
{
  public int _x;
  public void Increment() => _x++;
}

we get the behaviour.

  A a = new A();
  Increment(a);

  void Increment(A x)
  {
    x.Increment();
    x.Increment();
    Debug.Assert(x._x == 2);
  }

  Debug.Assert(a._x == 0);

We can avoid the copy using ref, but this then affects the caller.

  A a = new A();
  Increment(ref a);

  void Increment(ref A x)
  {
    x.Increment();
    x.Increment();
    Debug.Assert(x._x == 2);
  }

  Debug.Assert(a._x == 2);

We can pass the argument as an “in” parameter, which stops it being copied on entry to the method.

  A a = new A();
  Increment(in a);

  void Increment(in A x)
  {
    x.Increment();
    x.Increment();
    Debug.Assert(x._x == 0);
  }

  Debug.Assert(a._x == 0);

Now, of course, we have to answer the question: how is it that we don’t see the parameter x being changed after the call to x.Increment. The answer is that the compiler takes a defensive copy when it makes the call. You can see this in the IL that is generated (and this is all covered really well by this blog post).

In the above code, the IL for the invocation of Increment is

    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: ldobj ConsoleApp15.Program/A
    L_0007: stloc.0 
    L_0008: ldloca.s a
    L_000a: call instance void ConsoleApp15.Program/A::Increment()
    L_000f: nop 
    L_0010: ldarg.0 
    L_0011: ldobj ConsoleApp15.Program/A
    L_0016: stloc.0 
    L_0017: ldloca.s a
    L_0019: call instance void ConsoleApp15.Program/A::Increment()
    L_001e: nop 

Changing the definition of A to

readonly struct A
{
  public readonly int _x;
  public void Increment() => Console.WriteLine(_x);
}

the compiler notices that the copy can be avoided and hence the IL changes to the more expected

    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: call instance void ConsoleApp15.Program/A::Increment()

It all goes to show that valuetypes are a bit confusing in C#, and it is really hard to know whether you need to optimise them. You really need to do performance measurements to tell whether extra copying is really going to make a difference to the performance of your application.

I got interested in the struct related changes after looking into the implementation of Span, which is implemented as a “ref struct”. Span is a powerful new abstraction over data types such as arrays, and allows you to slice them without copying, and without performance sapping view types. To implement such a thing, the view, the Span instance, needs to be stack allocated and guaranteed to have a dynamic scope that causes it to be de-allocated before the stack frame is unwound – this is a new idea for the CLR which has never really guaranteed that stack allocated things were different before.

You can play with Span using the pre-release System.Memory Nuget package.

            var data = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            var subdata = data.AsSpan().Slice(3, 4);

The subdata item is a Span, and looking at that in the debugger’s raw view, shows you that it has the fields:

   _byteOffset 0x00000010 System.IntPtr
   _length 4 int 
   _pinnable {int[9]} System.Pinnable 

This efficient implementation, means that we require the Span object is confined to the stack, which is all covered in this proposal document. Span (and the heap allocated version, Memory) are likely to make their way into many framework classes in the coming releases because of the amount that they can reduce allocation in cases where data is pulled from a buffer. The System.Memory package is .NET Standard and so is already available to run on a large number of platforms.

Posted in Uncategorized | Leave a comment

Not sure I love it, but I do understand it better

There was a recent talk at NDC entitled How to stop worrying and love msbuild by Daniel Plaisted. It was an interesting talk that discussed the history of the change to the csproj file to make it a lot smaller and tidier. The new format makes the project file look like the following, which is a massive contrast to the old multi-line mess.

  
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>netcoreapp2.0</TargetFramework>
  </PropertyGroup>
</Project>

Of course, we have to ask where all of the existing XML has gone. The build system needs to get it from somewhere, and in the other parts of the talk the speaker discusses various debugging tools that give you a better idea of what is going on.

In the past I’ve always found it really hard to debug msbuild proj files. There seem to be masses of files that get imported and the trick has always seemed to be to pick a suitable target and then work from that. Using verbose logging you can track the actions of the build system as it does its work, and then work from that.

The first trick that the talk mentions is to use the pre-processor to get all of the content into a single text file.

msbuild /pp:out.txt

That works really well. Our small project file above expands to around 10000 lines of text, which is commented so that you can see the various imports and what those imports contain. It’s really interesting looking through it to see what the build system defines.

To understand the dynamic side of things, there is a new binary logging format that the build system can dump. You can then load this into a tool to search through the execution of the build.

msbuild /bl

The structured log viewer tool makes it really easy to find your way around the build. You can search for a text string, which makes it really easy to find tasks and properties, and there is a timeline that tells you went and how long the various targets took to execute. It is fascinating to see how much work the system does before it actually calls the CSC task to compile a single file of C#.

I also notice that the documentation about msbuild has got better. A good starting point is the page that talks about the difference between Items and Properties.

msbuild has always felt like the kind of technology I would love. I like programming systems with a small core language (so msbuild has items/properties and targets and tasks) and which then add abstractions on this small core. This kind of approach leaves you needing to understand only the small core language and allows you to explore into the abstractions that have been built up around it. For many Lisp and Smalltalk systems it is this exploration phase that it made easy by the tooling (the development environment) and this has always felt like the part that the msbuild ecosystem was missing. Maybe, these new tools are going to take this pain away at long last, though it still seems to be missing a way to actually single step though the execution of a build in some kind of build debugger which would allow the user to dynamically change things to see the effects. [Apparently you could at one point debug the build scripts using Visual Studio though the debug flag doesn’t seem to be available any more]

Posted in Uncategorized | Leave a comment

Some recent C# learnings

There are a couple of C# related things that I’ve come across recently, and also some interesting C# related talks from NDC which I’ll detail below.

The first interesting thing I came across is that the names of your method parameters are semantically meaningful. I should probably have realised this in the past, but didn’t until someone at work showed me how to stop an ambiguous reference.

The example was something like:

interface IA { }
interface IB { }
class C : IA, IB { }

static void Method(IA a) { }  // set up some methods are equally good
static void Method(IB b) { }

static void Main()
{
   Method(new C());
}

The call to Method in Main cannot be resolved to either of the possible overloads. However, if you change it to

Method(a: new C());

or

Method(b: new C());

then the call is no longer ambiguous.

I’d obviously realised in the past that you had to be careful with optionals as they are inlined, potentially across assemblies, but I had never seen overload resolution changed by naming the parameters.

The second observation is to do with inlining in a Parallel.ForEach. I had some code that simplifies to roughly the following.

static void Main(string[] args)
{
  void Recurse(int x) =>
    Parallel.ForEach(new int[] { x}, Recurse);
  Recurse(1);
}

In the real code I’d added some code to try to check that we didn’t end up calling a Parallel.ForEach in the context of another Parallel.ForEach using a ThreadStatic variable to record the context on the thread.

If you run the above code with a breakpoint on the Recurse method, you’ll see it using the stack of where you first run it, due to the system trying to run the call inline [see TaskScheduler.TryRunInline]. However, rather than eventually getting a StackOverflowException, the computation is eventually moved to a different thread.

Poking around in Reflector you can find the class System.Threading.Tasks.StackGuard which has a method named CheckForSufficientStack which uses Win32 methods to see how much stack space is left on the current thread. If there isn’t enough stack space then we don’t inline the recursive call, but instead move to another thread.

I’ve also seen some good C# talks: C# 7.1 and 7.2 from NDC, high performance C# code from experience working on Bing, msbuild, which is a great introduction and covers the history of the transition to json project files and back,
what is .NET Standard?, more C# 7 related performance changes
and there is also a discussion of the future of Rx and the associated Reactor project
Continue reading

Posted in Uncategorized | Leave a comment