It happens more often than not when working with spatial data I have at least a reference to NetTopologySuite (NTS). NTS has a very useful implementation of an r-tree which is the STRtree. This object allows insertion of 2D spatial data (shapes and points), and allows querying those. My use-case is to store all kinds of polygons in the STRtree object and to retrieve some of them based on a single point. I want to retrieve polygons that overlap a single point.

After googling for a while I think I’m looking for something like a Bounding Volume Hierarchy (BVH). I do think the STRtree is a type of a BVH. I did not dig any deeper into it, especially since I’m too lazy to write a decent data type myself, so we’re stuck with an STRtree for now.

Why I don’t think it works as intended

The STRtree object has a Query method which accepts an Envelope object. This Envelope object also accepts a Coordinate object in it’s constructor, and therefore only representing a single point.

When using this method I expect to be returned with all polygons that overlap the specified point. While it does not do this, it’ll probably return points, if, provided at that position.

What I can do to make it work ‘as intended’

As the STRtree seems to do intersections, we’re going to deal with this. The idea is that we draw a line from the edge of the bounding box to the point where we’re at in order to retrieve all polygons that could potentially be related. I’m executing the following steps:

  1. Determine what side of the bounding box is closest to the point you want to find.
  2. Draw a line from the side of the box to the single point.
  3. Add an additional filter on the retrieved objects to determine whether the point is actually inside any of the polygons.

For the circumstances I do think this is a fairly elegant way of retrieving this data. It’s not too performant though. I only manage to do 20,000 lookups a second this way. I want it to be faster, and I do think it can be a lot faster. Turned out I am right, but more on that later.

Let’s get some code going. First we need to populate the STRtree object. Just the same as usual.

STRtree<object> _tree = new STRtree<object>();

// Do something like this a few times, just hook your own data.
var polygon = new Polygon();
_tree.Insert(polygon.EnvelopeInternal, polygon);

// And build the tree to start using it.
// Note that you cannot modify the contents of the tree after this.
_tree.Build();

Now in order to retrieve some useful data from the tree I’m using the following helper method. I highly recommend you to modify this code to your specific needs!

public IEnumerable<object> GetPolygons(Coordinate point)
{
    // Figure out which boundary is closest.
    var xBoundary = point.X.Closest(
        _tree.Root.Bounds.MinX,
        _tree.Root.Bounds.MaxX);

    var yBoundary = point.Y.Closest(
        _tree.Root.Bounds.MinY,
        _tree.Root.Bounds.MaxY);

    var dX = point.X.Difference(xBoundary);
    var dY = point.Y.Difference(yBoundary);

    Envelope envelope;

    if (dX < dY)
        envelope = new Envelope(xBoundary, point.X, point.Y, point.Y);
    else
        envelope = new Envelope(point.X, point.X, yBoundary, point.Y);

    // Note that my object has a Polygon property which contains the polygon itself.
    return _tree.Query(envelope).Where(q => q.Polygon.Contains(point));
}

Note that this code only manages to execute 20,000 lookups each second. If that’s good enough for you, well, go use it! If not, read on.

Bonus: More bang for your bucks 🎉

Now if you need to squeeze a little more performance out of it I have good news for you: that’s totally possible. By the usual wizardy with the Visual Studio profiler you can see the Contains() method takes the biggest chunk of CPU time. I’m not sure at all what takes so much processing time, but I have a gut feeling it can be a lot faster.

As I went googling a bit I stumbled upon this answer on StackOverflow which suggested checking whether a point is on a single side of a polygon. I have slightly adapted the code to my use-case:

public static bool IsPointInPolygon(Coordinate[] polygon, Coordinate testPoint)
{
    bool result = false;
    int j = polygon.Count() - 1;
    for (int i = 0; i < polygon.Count(); i++)
    {
        if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
        {
            if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
            {
                result = !result;
            }
        }
        j = i;
    }
    return result;
}

Which you can use as follows:

_tree.Query(envelope).Where(q => Extensions.IsPointInPolygon(q.Polygon.Coordinates, point));

Using the code above I can manage to do about 260,000 lookups each second. While these measurements are far but scientific it shows roughly a 13x increase in performance, which is great!



Given my background with .NET technology, and me being stupid enough to store the DateTime struct’s Ticks value in a SQL database I found the need to convert these Ticks to a DateTime again, in order to visualize the stuff going on in the database.

Let me just drop the code here. It’s not mine, but I’m having trouble finding it on the internet every time I need it.

The script to convert ticks (long value) to datetime2:

SET ANSI_NULLS ON
GO
CREATE FUNCTION dbo.ToDateTime2 ( @Ticks bigint )
    RETURNS datetime2
AS
BEGIN
    DECLARE @DateTime datetime2 = '00010101';
    SET @DateTime = DATEADD( DAY, @Ticks / 864000000000, @DateTime );
    SET @DateTime = DATEADD( SECOND, ( @Ticks % 864000000000) / 10000000, @DateTime );
    RETURN DATEADD( NANOSECOND, ( @Ticks % 10000000 ) * 100, @DateTime );
END
GO

After you created the function you can use it as:

SELECT dbo.ToDateTime2(`Table`.`Ticks`) AS `TimeStamp` FROM `Table`

The script to convert a datetime2 value to ticks again:

SET ANSI_NULLS ON
GO

CREATE FUNCTION [dbo].[Ticks] (@dt DATETIME)
    RETURNS BIGINT
WITH SCHEMABINDING
AS
BEGIN
    DECLARE @year INT = DATEPART(yyyy, @dt)
    DECLARE @month INT = DATEPART(mm, @dt)
    DECLARE @day INT = DATEPART(dd, @dt)
    DECLARE @hour INT = DATEPART(hh, @dt)
    DECLARE @min INT = DATEPART(mi, @dt)
    DECLARE @sec INT = DATEPART(ss, @dt)

    DECLARE @days INT =
        CASE @month - 1
            WHEN 0 THEN 0
            WHEN 1 THEN 31
            WHEN 2 THEN 59
            WHEN 3 THEN 90
            WHEN 4 THEN 120
            WHEN 5 THEN 151
            WHEN 6 THEN 181
            WHEN 7 THEN 212
            WHEN 8 THEN 243
            WHEN 9 THEN 273
            WHEN 10 THEN 304
            WHEN 11 THEN 334
            WHEN 12 THEN 365
        END

    IF  @year % 4 = 0 AND (@year % 100  != 0 OR (@year % 100 = 0 AND @year % 400 = 0)) AND @month > 2 BEGIN
        SET @days = @days + 1
    END
    RETURN CONVERT(bigint,
        ((((((((@year - 1) * 365) + ((@year - 1) / 4)) - ((@year - 1) / 100)) + ((@year - 1) / 400)) + @days) + @day) - 1) * 864000000000) +
        ((((@hour * 3600) + CONVERT(bigint, @min) * 60) + CONVERT(bigint, @sec)) * 10000000) + (CONVERT(bigint, DATEPART(ms, @dt)) * CONVERT(bigint,10000));

END
GO

Which can be used in the following way again:

SELECT dbo.Ticks(`Table`.`TimeStamp`) AS `Ticks` FROM `Table`

 

In case you figure out the source of these scripts, please pass me a message and I’ll give proper credit



This post is a short note of the important takeaways from the talk given by Fons Sonnemans with the .NET Zuid usergroup on the topic of writing performant .NET code. I am not the expert on the topics described below. I’m only recollecting what I learned last night. It’s one of the talks I was super excited about attending, because well, I do have my own performance problem of sorts.

Fons showed this screenshot of the diagnostic tools to the audience. When I heard someone from the back say “oh shit” I lost it for a brief moment :)

The Garbage Collector

The first and in my humble opinion most interesting part of the talk was about the garbage collector. I know what it is, and what it does, but I did not know about some of the intricate details which are really important. Also, I did not know about the relationship of the garbage collector with the stack and the heap. Heck, I could not even properly explain the difference between the stack and the heap myself.

My understanding is currently still limited to a general overview, and I would love to learn a lot more about it in the future, but note that I could be completely wrong on these topics!

Each time the garbage collector runs, data existing in gen 0 and gen 1 is being promoted to the next generation. Copying information like this is definitely expensive. It’s only after last night that I understand what the flyweight pattern is actually useful for.

Running a little code sample (for example in LinqPad) shows how the variables are promoted to following generations:

void Main()
{
	int i = 1;

	var c1 = new C();
	GC.Collect();
	var c2 = new C();
	GC.Collect();
	var c3 = new C();

	string s = "";

	GC.GetGeneration(i).Dump();
	GC.GetGeneration(c1).Dump();
	GC.GetGeneration(c2).Dump();
	GC.GetGeneration(c3).Dump();
	GC.GetGeneration(s).Dump();
}

class C {
	public int I { get; set; }
}

While the output is as follows:

0
2
1
0
2

Obviosuly the int stays on the stack (gen 0). The class instances are all being promoted to the next generation with each collection, and the string is immediately promoted to gen 2.

Lists

Everybody loves lists, right? The List<T> object is amazing. It’s flexible, and fast enough for everyday use. Who doesn’t use the .ToList() extension method? It’s safe, right? For developers working a lot with Entity Framework it means that the result set is retrieved and any further processing will be done locally. For others it might mean that the IEnumerable is not enumerated multiple times (which might be a huge performance killer as well).

Apparently the .ToList() (LINQ) extension method is also a huge performance killer. Let me explain.

By default a list is initialized with a capacity of 0. Lists tend to automatically resize, based on whatever is required. Everytime the list is resized this means it is copied around memory, and that is expensive.

Let us time something. What if we create a list with 10 million integers?

var sw = new Stopwatch();
sw.Start();

List<int> ints = new List<int>();

for (var i = 0; i < 10_000_000; i++)
{
    ints.Add(i);
}

sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());

Now the execution time of the code is about 0.11 seconds on my machine, while the tool uses 153MB of memory, and during this time about 3 garbage collections have occurred.

If we only could do something to prevent these lists from resizing? Actually we can. The List<T> class has a constructor where you can provide the initial capacity. We’re running the same code now, but we’ve provided the list with a capacity.

Stopwatch sw = new Stopwatch();
sw.Start();

List<int> ints = new List<int>(10_000_000);

for (var i = 0; i < 10_000_000; i++)
{
    ints1.Add(i);
}

sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());

Running this snippet takes about 0.05 seconds, with a memory usage of 51MB, without GC collections!

The most difficult thing about this is knowing how many elements will be in the list. To indicate the amount of performance there is to gain, lets assume the capacity would be 16,777,216, while we’re only adding 10 million items. Execution time stays the same, and even seems to be a bit faster (?). Memory footprint is 79MB, and no GC collections have occurred. The while the estimate of the data size is at least 50% off, we’re still only using half the size we would’ve been using if we did not set the initial size explicitly.

Classes vs Structs

Now it gets interesting. From my experience I can tell structs aren’t used so often at all. While extremely beneficial for application performance, developers usually go with classes. Mostly from lack of proper understanding of the differences between these two. The main differences:

  • Structs are considered value types, and therefore live (generally) on the stack. Classes are considered reference types and live on the heap.
  • Structs do not have inheritance.
  • Structs are not nullable.
  • Structs have a fixed memory footprint.

Structs usually do live in the stack. That is, until the stack size grows too big and some of it is moved to the heap. Testing this makes that quite clear.

void Main()
{
	var s1 = new S();
	GC.Collect();
	var s2 = new S();
	GC.Collect();
	var s3 = new S();
	GC.Collect();

	GC.GetGeneration(s1).Dump();
	GC.GetGeneration(s2).Dump();
	GC.GetGeneration(s3).Dump();
}

struct S {
	int I1 { get; set; }
	int I2 { get; set; }
}

Ther resulting output shows that all objects still live in gen 0.

One of the cool things a struct can do which a class can’t is replace itself, due to it’s fixed size.

void Main()
{
	var s = new S(1 ,2);

	s.I1.Dump();
	s.I2.Dump();

	s.Switch();

	s.I1.Dump();
	s.I2.Dump();
}

struct S {
	public S(int i1, int i2) {
		I1 = i1;
		I2 = i2;
	}

	public int I1 { get; set; }
	public int I2 { get; set; }

	public void Switch() {
		this = new S(I2, I1);
	}
}

Upon showing this someone made the comment “Hey, we’re not talking about JavaScript here, right?”.

In the following section the sizes of objects have been determined by using the System.Runtime.InteropServices.Marshal.SizeOf() method. This method returns the size of an object when it would’ve been marshaled (converted to an unmanaged representation).

Talking about the fixed size of structs, you might be able to shave a few bytes off structs. The following struct will take 8 bytes. Makes sense. 2x 4 bytes.

struct S {
	int I1 { get; set; }
	int I2 { get; set; }
}

Compare that with the reported size of the following struct (which is 16 bytes).

struct S {
	long L1 { get; set; }
	int I2 { get; set; }
}

Now it gets fun as the reported data size of the following struct is also 16 bytes!

struct S {
	long L1 { get; set; }
	int I1 { get; set; }
	string S1 { get; set; }
}

But wait! A string is a class right? And besides that, a string can store an amount of data certainly larger than the amount of RAM in your workhorse, right? The trickery that is going on here is that the string is stored as a reference (in the heap), which, because the program runs in 32 bit mode, is 4 bytes long.

Long story short, structs are padded by their biggest data type, which can be observed in awe by checking the size (24 bytes) of the following struct:

struct S {
	int I1 { get; set; }    // 4 bytes for the int, + 4 bytes for the padding
	long L1 { get; set; }   // 8 bytes for the long
	int I2 { get; set; }    // 4 bytes for the int, + 4 bytes of padding
}

The fix is fairly easy. There’s a StructLayoutAttribute which you can use on a struct in the form of [StructLayout(LayoutKind.Auto)] (which doesn’t only work on structs but also on classes). Apparently, due to backwards compatibility, this isn’t being applied by default.

Buffers

With .NET Core (and in Framework through NuGet packages) the [System.Buffers](https://docs.microsoft.com/en-us/dotnet/api/system.buffers) namespace has been introduced. This namespace contains the ArrayPool<T> class which gives you the ability to reserve a section of memory and do all kinds of array/list operations in it. While the array resizing operations stay the same (you should use an initial size where possible anyway) the memory pressure on the garbage collector is significantly smaller, resulting in less collections.

Note that garbage collection can be a blocking operation, and therefore slow the overall performance of your application. See https://docs.microsoft.com/en-us/dotnet/standard/garbage-collection/induced#background-or-blocking-collections for more information about whether garbage collection is blocking or not.

Visual Studio

The speed with which Fons managed to navigate through and work with Visual Studio was (at least for me) astonishing. The takeaways from this:

  • VS managed to catch up with ReSharper. I kind of immediately uninstalled ReSharper and so far it’s not like I’m missing anything at all! (Huge performance increase)
  • By using ctrl+F5 you can start your program without attaching the debugger. It is so much faster than hitting F5, and having to wait for the debugger to attach. The debugger is truly amazing, but not always required.
  • Visual Studio can be an incredible help with generating code. (ctrl+. on a class in order to automagically implement IEquatable and GetHashCode!)
  • Visual Studio currently supports so called ‘Analyzers’. These analyzers are tools which can inspect your code in some way and give you hints about what stuff to improve. I have no further knowledge about how they work, but they can help you not to shoot of your feet, or your leg. And oh, a cool thing is that they can be installed on a per-project basis through NuGet packages! ErrorProne.NET (on GitHub) seems like a decent set of analyzers to start with.

Benchmarking

Now, last but not least, know what things cost! For quick experiments you’re most certainly fine with using the StopWatch class and LinqPad. For more thorough tests you might use something more advanced like https://benchmarkdotnet.org/. Again, I’ve heard it exists, and I think it looked nice so I might be interested in using it in the future. For now it’s just important you know it exists.



This is definitely more of a note to myself, and my fellow Surface Book 2 users;

Lately mostly after installing Windows updates, the book is plagued by strange behavior.

A few things include:

  • Difficulties to start up. When the power button has been pressed, it won’t quickly start up after hibernation. Most of the times you have to press a few times in a row to get the Surface to wake up. Pressing the detach button mostly is the quickest way to wake up in this situation.
  • After a sleep the NVIDIA GTX 1050/1060 isn’t recognized after sleep. Detaching and then attaching may work to detect it again. A restart also works fine. So now and then a warning would pop up that there is a hardware problem with the base.
  • Bad performance for detaching. It’d be easily possible to have to wait about 20 or 30 seconds for the base to detach. If at all. A restart mostly fixed these issues.

There is an old Reddit post I stumbled upon with people experiencing the same problem, and few fixes have been shared.

Go here for the Reddit post: https://www.reddit.com/r/Surface/comments/81qvp1/my_surface_book_2_having_issues_with_waking_up/

The top comment seemed to fix my problems. With the most recent updates I figured out that booting in UEFI mode (by pressing the power button and the volume up button) and exiting again solved my problems.



Please note before reading: this post flows over from implementation details of the graphql-dotnet project. If you’re like me, stuck on authorization for subscriptions, and want to know how I worked around it, read the post. If you just want authorization with subscriptions to work, copy past the code blocks.

The folks working on the graphql-dotnet library have done some amazing work on bringing the GraphQL specification to the .NET ecosystem. While the library is definitely not easy to implement, the resulting GraphQL API can be a delight to work with.

By now several additional libraries have been developed. Notoriously the authorization library. This library brings policies and permissions to your GraphQL API. This authorization library is not dependent on any specific authorization mechanism, as long as you can provide an implementation for the IProvideClaimsPrincipal interface which sole responsibility is providing GraphQL with a ClaimsPrincipal instance. Validation logic is provided by implementing the IValidationRule interface.

While this works fine for queries and mutations, at the time of writing the following issues with regards to making bearer authorization work on subscriptions:

  • HTTP headers are provided in the payload of the first frame that goes over the WebSocket connection. This first frame has the type of connection_init. As the subscription subscriber is only invoked at the start frame, it might seem difficult at first sight to retrieve the JWT token from the payload of the connection_init frame.

If you want to know what is going on within a websocket connection, the developer tools inside browsers can show the individual frames on websocket connections these days, which is a nice way of getting to know some about the protocols flowing through :)

  • Subscriptions hijack the UserContext property on the ResolveEventStream object to pass a MessageHandlingContext instance. Therefore, generic auth validation logic provided with an IValidationRule implementation cannot access the ClaimsPrincipal object on the UserContext, therefore failing verification.

Retrieving the bearer token

While the GraphQL library looks pretty daunting at first sight, it also happens to be incredibly extensible at all points through the use of interfaces. One of these extension points happens to be the IOperationMessageListener, which acts on different messages received via the websocket connections, and therefore, indirectly on subscriptions. I have implemented the IOperationMessageListener in a way that the bearer token can be extracted from the connection_init frame.

public class SubscriptionInitializer : IOperationMessageListener
{
    private IHttpContextAccessor _contextAccessor;
    public SubscriptionInitializer(IHttpContextAccessor httpContextAccessor)
    {
        _contextAccessor = httpContextAccessor;
    }

    public async Task BeforeHandleAsync(MessageHandlingContext context)
    {
        if (context.Terminated) return;

        var message = context.Message;

        if (message.Type == MessageType.GQL_CONNECTION_INIT)
        {
            JwtSecurityTokenHandler handler = new JwtSecurityTokenHandler();
            var user = handler.ValidateToken(message.Payload.GetValue("Authorization").ToString().Replace("Bearer ", ""),
                new TokenValidationParameters
                {
                    ValidIssuer = "TODO: Enter your issuer",
                    ValidAudience = "TODO: Enter your audience",
                    IssuerSigningKey = new JsonWebKey(@"TODO: Load your JWKS")
                },
                out SecurityToken token);

            if (!user.Identity.IsAuthenticated) await context.Terminate();

            _contextAccessor.HttpContext.User = user;
        }
    }

    public Task HandleAsync(MessageHandlingContext context)
    {
        return Task.CompletedTask;
    }

    public Task AfterHandleAsync(MessageHandlingContext context)
    {
        return Task.CompletedTask;
    }
}

Passing on the IPrincipal

As seen in the code above it is not too difficult to validate a JWT for a subscription, but what if we’re using the authorization library and want our existing IValidationRule implementations also to apply for subscriptions?

To understand one of the possible ways we can pass this data to the IValidationRule implementations we have to dig into the DI system. The GraphQL library heavily relies on the DI mechanics, and the only thing we want to know is how IValidationRule objects are passed, or in this case, injected.

You don’t have to figure that out yourself. A type of IEnumerable<IValidationRule> is injected into the constructor of the DefaultGraphQLExecuter<TSchema> which is being registered in the DI as transient, therefore meaning that it is instantiated every time it is requested. Thankfully the IGraphQLExecuter<TSchema> is requested in the GraphQLHttpMiddleware<TSchema> middleware, so with every request we get a new executer. Great!

Because of these properties we can create our own object which is injected through the constructors both in the IOperationMessageListener and IValidationRule implementations. We will transfer the principal by means of this transport object. We can then populate the ClaimsPrincipal in the UserContext with the value we passed in this terrible, awefull, and just plain ugly way, but at least it’s better than duplicating code multiple times.

Now here comes the exciting part (As inspired by this commented out class, which I only discovered after I figured everything else out…). We can inject the IHttpContextAccessor into our class to have the ability to get the current HttpContext instance into our SubscriptionInitializer. Even more beautifull is the way we can pass the ClaimsPrincipal to the IValidationRule: We set the HttpContext.User property with our ClaimsPrincipal, after which it is available on the current HttpContext. How easy can life be sometimes.

Also, don’t forget to inject the IHttpContextAccessor into your IValidationRule in order to be able to access the IPrincipal.