morzel.net

.net, js, html, arduino, java... no rants or clickbaits.

[OoB] Sonar with Arduino, C#, JavaScript and HTML5 (Part 2)

Part 1 described the general idea behind Sonar project, hardware components used and Arduino sketch... This second post in "Out of Boredom" series is about C# and JavaScript programs that make it possible to display ultrasonic range sensor data in web browsers. The role of .NET application is to receive messages from Arduino over serial port and broadcast it to clients using SignalR library. JS/HTML5 clients use jquery.signalR lib to obtain information about servo position with distance to obstacles and use this data to render sonar image on canvas:

Sonar client image... Click to enlarge...

These links are in previous post, but just to remind you:

 

1. SonarServer 

SonarServer is a .NET 4.5 console app created in Visual Studio Express 2013 for Windows Desktop. It uses Microsoft.AspNet.SignalR.SelfHost and Microsoft.Owin.Cors NuGet packages to create self-hosted SignalR server. ASP.NET SignalR is a library designed to make it easy to create applications that are able to push data to clients running in web browsers. This is in contrast to normal web pages/apps behavior where the client (browser) asks server for action by issuing a request (such as GET or POST). SignalR allows clients to listen for messages send by a server... If possible SignalR will use WebSockets to enable efficient bi-directorial connection. If that option is not available due to either browser or server limitations, it will automatically switch to other push techniques like long polling or Server-Sent Events. When I tested the code on my laptop with Windows 7 Home Premium SP1, long polling was used on IE 11 and SSE in Chrome 37. Server was sending about 20 messages per second and clients didn't have any problems with handling that load (communication was on localhost). Self-hosting means that SignalR server doesn't have to be run on a web server such as IIS - it can exist in plain old console project! If you are completely new to SignalR check this tutorial... 

This is SonarServer project structure:

SonarServer solution...

SonarData.cs file contains such struct:

namespace SonarServer
{
    public struct SonarData
    {
        public byte Angle { get; set; }
        public byte Distance { get; set; }
    }
}

Server will send a list of such objects to clients.

SonarHub.cs contains a class derived form Hub. It doesn't declare any methods but is nonetheless useful. Library will use it to generate JavaScript proxy objects...

using Microsoft.AspNet.SignalR;

namespace SonarServer
{
    public class SonarHub : Hub
    {

    }
}

Startup.cs file looks like this:

using Microsoft.Owin.Cors;
using Owin;

namespace SonarServer
{
    class Startup
    {
        public void Configuration(IAppBuilder app)
        {
            app.UseCors(CorsOptions.AllowAll);
            app.MapSignalR();
        }
    }
}

It configures the SignalR server, letting it support cross-domain connection thanks to UseCors call.

Below are the most important bits of Program.cs file. This code:

using (SerialPort sp = new SerialPort())
 {
     sp.PortName = "COM3";
     sp.ReceivedBytesThreshold = 3;
     sp.DataReceived += new SerialDataReceivedEventHandler(DataReceivedHandler);

     sp.Open();

     Console.WriteLine("Serial port opened!");

     using (WebApp.Start<Startup>("http://localhost:8080/"))
     {
         Console.WriteLine("Server running!");
         Console.ReadKey();
     }
 }

is responsible for opening a connection with Arduino over serial port named "COM3" and starting SignalR server on localhost:8080ReceivedBytesThreshold property allows us to control the amount of bytes received from Arduino before DataReceivedHandler is called. You can increase this value if you want bigger packages of data to be broadcasted by server and rendered by clients. This is the part of DataReceivedHandler method that loads serial port data into a byte array:

int count = sp.BytesToRead;
[] data = new byte[count];
sp.Read(data, 0, count);

Such array of bytes is latter on added to custom buffer and processed to create a list of SonarData objects sent to SignalR clients. Part 1 mentioned that Arduino sends data to PC in bytes (array) packages containing three elements: [255, angle, distance]. The purpose of special 255 value is to separate angle-distance pairs of values which are used to create sonar image. We can't just send [angle, distance] stream from Arduino to PC, because the Server could easily loose track of which value is angle and which is distance. This might happen due to delays, buffering etc. Sure it's not a bulletproof protocol but it work well when I tested it. Lot's not get crazy with that - it's a hobby project, remember? :) Check ProcessSonarData method in repository if you want to see how an array of bytes is turned into SonarData list (with buffering taken into account)... 

The last missing piece of SonarServer puzzle is SendSonarDataToClients method:

private static void SendSonarDataToClients(List<SonarData> sonarDataForClients)
{
    var hub = GlobalHost.ConnectionManager.GetHubContext<SonarHub>();
    hub.Clients.All.sonarData(sonarDataForClients);

    Console.WriteLine("Sonar data items sent to clients. Samples count=" + sonarDataForClients.Count);
}

This is the thing that actually broadcasts data to clients running in web browsers. You may be wondering why SonarHub instance is not created directly with new operator and instead GetHubContext method is used. This is because SignalR is responsible for its hubs life cycle. Such code:

SonarHub sonarHub = new SonarHub();
sonarHub.Clients.All.sonarData(sonarDataForClients);

would result in the exception: System.InvalidOperationException: Using a Hub instance not created by the HubPipeline is unsupported." .

 

2. SonarClient

SonarClient is the subproject responsible for drawing sonar image. It's not a Visual Studio solution - just a few files:

SonarClient files...

I've tested SonarClient code in IE 11 and Chrome 37 and it worked really well. The assumption is that you run modern browser too. I didn't bother with any feature detection, it's enough for me that I have to write for IE9 at work - well, at least it's not IE 6, huh? ;) But if you want to do such thing I can recommend Modernizr library...

This is content of index.html file (with some boring parts removed for brevity):

<!DOCTYPE html>
<html>
<head>
    <title>Sonar - sample code from morzel.net blog post</title>
    <style>
        /* more */
    </style>
</head>
<body>
    <div>
        <canvas id="sonarImage" width="410" height="210"></canvas>

        <table>
              <!-- more -->            
        </table>
    </div>

    <a href="http://morzel.net" target="_blank">morzel.net</a>

    <script src="lib/jquery-1.6.4.js"></script>
    <script src="lib/jquery.signalR-2.1.1.js"></script>
    <script src="http://localhost:8080/signalr/hubs"></script>
    <script src="sonarStats.js"></script>
    <script src="sonarImage.js"></script>
    <script src="sonarConnection.js"></script>

    <script>
        $(function () {          
            sonarImage.init('sonarImage');
            sonarConnection.init('http://localhost:8080/signalr');
        });
    </script>
</body>
</html>

Most important bit of this HTML5 markup is the canvas element used to create sonar image. The page imports jquery and jquery.signalR libraries that make it possible to communicate with the Server. That line is particularly interesting:

 <script src="http://localhost:8080/signalr/hubs"></script>

SingalR automatically creates JavaScript proxy objects for server-client messaging, that line lets us load them into page. Last three script references are for JS modules responsible for: displaying info about data received from SonarServer, rendering sonar image and communication with server, respectively. Later there's a short script which initializes the modules after pages DOM is ready.

I will skip the description of sonarStats.js file (nothing fancy there - just filling some table cells). But sonarConnection.js should be interesting for you. This is the whole content:

var sonarConnection = (function () {
    'use strict';

    var sonarHub, startTime, numberOfMessages, numberOfSamples;

    var processSonarData = function (sonarData) {
        numberOfMessages++;
        $.each(sonarData, function (index, item) {
            numberOfSamples++;
            sonarImage.draw(item.Angle, item.Distance);
            sonarStats.fillTable(item.Angle, item.Distance, startTime, numberOfMessages, numberOfSamples);
        });
    };

    return {
        init: function (url) {
            $.connection.hub.url = url;

            sonarHub = $.connection.sonarHub;

            if (sonarHub) {
                sonarHub.client.sonarData = processSonarData;
                               
                startTime = new Date();
                numberOfMessages = 0;
                numberOfSamples = 0;

                $.connection.hub.start();
            } else {
                alert('Sonar hub not found! Are you sure the server is working and URL is set correctly?');
            }
        }
    };
}());

The init method sets SignalR hub URL along with sonarData handler and starts a connection with the .NET app. There is also some very basic hub availability check (jquery.signalR library has extensive support for connection related events but lets keep things simple here). processSonarData is invoked in response to Server calling hub.Clients.All.sonarData(sonarDataForClients). The processSonarData function receives an array of objects containing information about servo angle and distance to obstacles. SignalR takes care of proper serialization/deserialization of data - you don't have to play with JSON yourself. $.each function (part of jQuery) is used to invoke sonarImage.draw and sonarStats.fillTable methods for every item in sonarData array...

And here comes the module that changes pairs of angle-distance values into o nice sonar image (whole code of sonarImage.js):

var sonarImage = (function () {
    'use strict';

    var maxDistance = 100;
    var canvas, context;

    var fadeSonarLines = function () {
        var imageData = context.getImageData(0, 0, canvas.width, canvas.height),
            pixels = imageData.data,
            fadeStep = 1,
            green,
            fadedGreen;

        for (var i = 0; i < pixels.length; i += 4) {
            green = pixels[i + 1];

            fadedGreen = green - fadeStep;
            pixels[i + 1] = fadedGreen;
        }

        context.putImageData(imageData, 0, 0);
    };

    return {
        init: function (canvasId) {
            canvas = document.getElementById(canvasId);
            context = canvas.getContext('2d');

            context.lineWidth = 2;
            context.strokeStyle = '#00FF00';
            context.fillStyle = "#000000";

            context.fillRect(0, 0, canvas.width, canvas.height);

            context.translate(canvas.width / 2, 0);
            context.scale(2, 2);
        },

        draw: function (angle, distance) {
            context.save();

            context.rotate((90 - angle) * Math.PI / 180);
            context.beginPath();
            context.moveTo(0, 0);
            context.lineTo(0, distance || maxDistance); // Treat 0 as above range
            context.stroke();

            context.restore();

            fadeSonarLines();
        }
    };
}());

Again we have an init method. It obtains 2d drawing context from canvas and uses it to set line width and color (green). It also sets inner color (black) and fills the whole canvas with it. context.translate call is used to move origin of coordinate system to the middle of canvas (horizontally). By default it sits in upper left corner. context.scale is used to make image two times bigger than it would be drawn in default settings. Read this post if you want to know more about canvas coordinates.

The draw method is invoked for each data sample (angle-distance pair) produced by Arduino and broadcasted with SonarServer. The distance to obstacles measured by HC-SR04 sensor is represented as a line. The bigger the distance the longer the line. This happens thanks to beginPath, moveTo, lineTo, and stroke calls. context.rotate method is responsible for showing the angle in which the sensor was pointing while measuring distance (angle of servo arm). As the servo moves around we want to change the direction in which distance line is drawn. Notice that code responsible for drawing the line is surrounded by context.save and context.restore calls. These two ensure that rotation transformation doesn't accumulate between draw method calls...

fadeSonarLines function is responsible for creating the effect of older sonar lines disappearing in a nice gradual way. context.getImageData method returns an array of RGBA values representing the pixels that create current canvas image. The function loops through image data and progressively reduces the intensity of green color component. This way sonar lines fade to black.

And viola - sonar image can be rendered in a browser :)

Isn't it amazing what is now possible on the web platform? I'm not exactly a dinosaur but I remember when displaying a div overlay on a page required use of hidden iframe (because select elements were otherwise rendered above the overlay)... Crazy times ;)

[OoB] Sonar with Arduino, C#, JavaScript and HTML5

This post marks the beginning of "Out of Boredom" series. It will be about creating stuff with my recently purchased Arduino Uno. Let's have a break from chores of professional programming and create something just for fun :)

My first Arduino based project is Sonar. It utilizes ultrasonic range sensor, servo, SignalR and canvas to create sonar image:

Sonar at work... Click to enlarge...

I am splitting the description into two posts. First post will focus on hardware components and Arduino sketch and the second will be about .NET and JavaScript applications. You can get complete code in this GitHub repository. You can also click here to see short video of the whole thing working.

Here are hardware elements used:

Element Role
Arduino Uno R3 Handling HC-SR04, controlling servo and communicating with PC
HC-SR04 Ultrasonic Ranging Module Measuring time it takes sound to bounce back from objects
9g Tower Pro Micro Servo Moving sensor to get 180 degree view
Red LED Signalling ready state
330 Ohm resistor Limiting current going through diode
Breadboard and few jumper wires Connecting components without soldering 

That's it, just a few cheap components! Virtually no electronics skills are required to complete this project. I assume, however, that you have basic Arduino knowledge and you know a bit about C# and JavaScript.

Here is the software stack:

Element Role
Arduino sketch (firmware) Measuring distance, moving servo and sending data to PC over serial port 
.NET/C# 4.5 console application with SignalR library  Receiving data from Arduino using SerialPort class and broadcasting angle and distance information to clients
HTML5 page with JavaScript SignalR library Receives data from server and creates sonar image using canvas element

Above might sound a bit overwhelming but I assure you that the code is short and not that complicated.

The basic idea goes like this: HC-SR04 sensor measures time it takes an ultrasonic signal to bounce from obstacles and this gives as a chance to calculate distance to these obstacles. Position of the sensor is controlled by servo. Information about distance to objects and direction in which the sensor is pointing is sent to PC that is running console application with SignalR sever. PC receives the data and sends it to JavaScript clients that are capable of presenting sonar data in nice visual way using HTML5 canvas element...

More details!

The main component (except for the Arduino of course) is the HC-SR04 Ultrasonic Ranging Module. This sensor works by sending sound signal at 40 kHz (so above human perception limits) and detecting the echo. That's why this project is called "Sonar" and not "Radar" - it uses sound waves (not radio waves) do detect objects. The sensor should work in ranges from 2cm up to 400cm at accuracy of few millimetres. But keep in mind that the shape an material of objects might affect performance. I tested it at maximum distance of about 2 meters and was happy with the results. You can use this sensor without any libraries. That requires doing things like putting HIGH value on Trig pin for 10uS to emit ultrasonic signal, measuring duration of HIGH pulse on Echo pin and calculating distance knowing that speed of sound in the air is around 340m/s... But there's a better way: you can use NewPing lib (link) to get the distance. If you don't know how to include new library in your Arduino sketch click here.

The second important component is the servo. HC-SR04 sensor has measuring angle of about 15 degrees. But if we move it around by attaching it to servo's arm we can easily get 180 degree view. I won't get into details on how servo works and how it is controlled in this post. I plan to make another post about shooting paintball marker with Arduino+laptop and I will describe it then. For now all you need to know is that Arduino comes with Servo library which makes it very easy to move servo into desired position (angle)... I utilized 9g Tower Pro Micro Servo in this project. It's powerful enough to move the sensor yet can be powered directly from Arduino's +5V pin.

Last physical components are LED used to signal the ready state (that is when setup function had completed) with its accompanying resistor. Making a diode shine is electronics equivalent of "Hello World!" so I'm sure you know how to handle LED. Even if not, you can always use the tiny built-in LED connected to pin 13 of Arduino Uno...

This diagram shows how hardware components should be connected:

Fritzing breadboard diagram

Here's the whole code that should be uploaded to Arduino:  

#include <NewPing.h>
#include <Servo.h>  

const byte setupReadyLedPin = 8;
const byte triggerPin = 10;
const byte echoPin = 11;
const byte servoPin = 12;

const byte maxDistanceInCm = 100;

byte angle;
byte angleStep;
byte angleStepDelayInMs = 50;

NewPing sonar(triggerPin, echoPin, maxDistanceInCm); 
Servo servo; 

void setup() {  
    pinMode(setupReadyLedPin, OUTPUT);
    
    angle = 0;
    angleStep = 1;
    
    servo.attach(servoPin);   
    servo.write(angle); 
    
    Serial.begin(9600); // Open connection with PC
    
    digitalWrite(setupReadyLedPin, HIGH);
}

void loop() {      
    alterServoMoveDirection();    
    
    measureAndSendDistance();
    
    angle += angleStep;
    servo.write(angle); // Move servo
    
    delay(angleStepDelayInMs);   
}

void alterServoMoveDirection() {
    if (angle == 180) {
       angleStep = -1; 
    } else if (angle == 0) {
       angleStep = 1;
    }
}

void measureAndSendDistance() {
    byte distanceInCm = sonar.ping_cm(); // Use ultrasound to measure distance   
      
    byte sonarData[] = {255, angle, distanceInCm};
    Serial.write(sonarData, 3); // Send data to PC
}

As stated before, I assume that you know something about Arduino programming and things like const, pinMode, delay, setup and loop don't require explanation...

First lines which should capture your attention are:

#include <NewPing.h>
#include <Servo.h>  

NewPing sonar(triggerPin, echoPin, maxDistanceInCm); 
Servo servo;

Above lines let us use NewPing and Servo classes to measure distance and move the sensor. Notice also that setup function has such lines:

servo.attach(servoPin);   
servo.write(angle);

These exist to set the pin used to control the servo and to move the servo into initial position at 0 degrees.

This line:

Serial.begin(9600);

allowes Arduino to talk to PC (in my case a laptop with Windows 7) over serial port. That's right, even though Arduino Uno is connected to computer via USB cable it actually uses COM port to communicate. On my machine its called "COM3" (screen shown below comes from Device Manager - my Windows is in Polish):

COM port for Arduino... Click to enlarge...

The value passed to begin method determinates baud rate (communication speed). It's important to have the same value used in software that communicats with Arduino.

The loop function moves servo and invokes measureAndSendDistance function which uses NewPing to calculate distance and Serial to send data to PC. This is how easy it is to get distance in cm thanks to NewPing lib:

byte distanceInCm = sonar.ping_cm()

If measured distance exceeds the maximum value specified as last parameter to NewPing constructor the value of 0 is returned. Check NewPing docs to see other useful functions of this lib.

And finally this is how Arduino sends data to PC:

byte sonarData[] = {255, angle, distanceInCm};
Serial.write(sonarData, 3); // Send data to PC

The first array element (255) is used as a marker/separator to easily distinguish pairs of angle-distance values. Its role will become clear in the second post which will describe SignalR server and clients... I assume that maxDistanceInCm const will never be set above 200 so distanceInCm will never have value of 255. 255 will never be sent as an angle too because our servo moves in 0..180 degrees range. Sure it might be a good idea to create const and avoid 255 magic number. Some validation would be useful too... But screw it, this project is just for fun! :)

Ok, you survived to the end of the first post about Arduino/.NET/JS/HTML sonar. The second post should be ready in about a week.

Update 2014-09-29: Here's the Part 2.

How fast is .NET Garbage Collector? Part 2.

Read the first part of the article if you haven’t done so already. Part 1 has a brief overview of what GC is and how it performs its magic. It contains a test of GC performance with regards to large array of bytes. You can also find there a detailed information about my test environment…

This part will focus on scenarios which put a lot more pressure on GC and appear more commonly in real world applications. You will see that even a tree of more than 100 million objects can be handled quickly… But first let’s see how GC responds to big array of type object:

static void TestSpeedForLargeObjectArray()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before creating array: {0:N0}. Press key any to create array...", GC.GetTotalMemory(true)));
    Console.Read();
    object[] array = new object[100 * 1000 * 1000]; // About 800 MB (3.2 GB when filled with object instances)
             
    sw.Start();
    for (int i = 0; i < array.Length; i++)
    {
        array[i] = new object();
    }
    Console.WriteLine("Setup time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after creating array: {0:N0}. Press Enter to set array to null...", GC.GetTotalMemory(true)));

    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting array to null");
        array = null;
    }
    
    sw.Restart();
    GC.Collect();
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));

    Console.WriteLine(array); // To avoid compiler optimization...
    Console.ReadKey();
}

Above test creates and array of 100 million items. Initially such array takes about 800 megabytes of memory (on x64 platform). This part is allocated on LOH. When object instances are created total heap allocation jumps to 3.2 GB. Array items are tiny so they are part of Small Object Heap and initially belong to Gen 0.

Here are the test results for situation when array is set to null:

GC.GetTotalMemory before creating array: 41,736. Press key any to create array...
Press any key to fill array...
Setup time: 00:00:07.7910574
GC.GetTotalMemory after creating array: 3,200,057,616. Press Enter to set array to null...
Setting array to null
Collection time: 00:00:00.7481998
GC.GetTotalMemory after GC.Collect: 57,624. Press any key to finish...

It took only about 700 ms to reclaim over 3 GB of memory!

Take a look at this graph from Performance Monitor:

Managed memory counters for large object[] array; setting array to null... Click to enlarge...

You can see that while program was filling the array, Gen 0 and Gen 1 changed size (notice though that the scale for these is 100x bigger than scale for other counters). This means that GC cycles were triggered while items were created - this is expected behavior. Notice how Gen 2 and LOH size adds up to total bytes on managed heap.

What if instead of setting array reference to null we set array items to null?

Let’s see. Here’s the graph:

Managed memory counters for large object[] array; setting array items to null... Click to enlarge...

Notice that after GC.Collect is done 800 MB are still allocated - this is LOH memory held by array itself…

Here are the results:

GC.GetTotalMemory before creating array: 41,752. Press key any to create array...
Press any key to fill array...
Setup time: 00:00:07.7707024
GC.GetTotalMemory after creating array: 3,200,057,632. Press Enter to set array elements to null...
Setting array elements to null
Collection time: 00:00:01.0926220
GC.GetTotalMemory after GC.Collect: 800,057,672. Press any key to finish...

Ok, enough with arrays. One can argue that as continues blocks of memory they are easier to handle then complex objects structures that are abundant in real word programs.

Let’s create a very big tree of small reference types:

static int _itemsCount = 0;

class Item
{
    public Item ChildA { get; set; }
    public Item ChildB { get; set; }
    
    public Item()
    {
        _itemsCount++;
    }           
}

static void AddChildren(Item parent, int depth) 
{
    if (depth == 0)
    {
        return;
    }
    else
    {
        parent.ChildA = new Item();
        parent.ChildB = new Item();

        AddChildren(parent.ChildA, depth - 1);
        AddChildren(parent.ChildB, depth - 1);                
    }
}

static void TestSpeedForLargeTreeOfSmallObjects()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before building object tree: {0:N0}. Press any key to build tree...", GC.GetTotalMemory(true)));
    Console.ReadKey();

    sw.Start();
    _itemsCount = 0;       
    Item root = new Item();            
    AddChildren(root, 26);
    Console.WriteLine("Setup time: " + sw.Elapsed);
    Console.WriteLine("Number of items: " + _itemsCount.ToString("N0"));

    Console.WriteLine(string.Format("GC.GetTotalMemory after building object tree: {0:N0}. Press Enter to set root to null...", GC.GetTotalMemory(true)));

    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting tree root to null");
        root = null;                
    }
    
    sw.Restart();
    GC.Collect();
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));
                
    Console.WriteLine(root); // To avoid compiler optimization...            
    Console.ReadKey();
}

The test presented above creates a tree with over 130 million nodes which take almost 4.3 GB of memory.

Here’s what happens when tree root is set to null:

GC.GetTotalMemory before building object tree: 41,616. Press any key to build tree...
Setup time: 00:00:14.3355583
Number of items: 134,217,727
GC.GetTotalMemory after building object tree: 4,295,021,160. Press Enter to set root to null...
Setting tree root to null
Collection time: 00:00:01.1069927
GC.GetTotalMemory after GC.Collect: 53,856. Press any key to finish...

Managed memory counters for large tree of small objects; setting tree root to null... Click to enlarge...

It took only 1.1 second to clear all the garbage! When root reference was set to null all nodes below it became useless as defined by mark and sweep algorithm… Notice that this time LOH is not utilized as no single object instance is over 85 KB threshold.

Now let’s see what happens when the root is not set to null and all the objects survive GC cycle:

GC.GetTotalMemory before building object tree: 41,680. Press any key to build tree...
Setup time: 00:00:14.3915412
Number of items: 134,217,727
GC.GetTotalMemory after building object tree: 4,295,021,224. Press Enter to set root to null...
Collection time: 00:00:03.7172580
GC.GetTotalMemory after GC.Collect: 4,295,021,184. Press any key to finish...

This time it took 3.7 sec (less than 28 nanoseconds per reference) for GC.Collect to run – remember that reachable references put more work on GC then dead one!

There is one more scenario we should test. Instead of setting root = null let's set root.ChildA = null. This way half of the tree would became unreachable. GC will have a chance to reclaim memory and compact it to avoid fragmentation. Check the results:

GC.GetTotalMemory before building object tree: 41,696. Press any key to build tree...
Setup time: 00:00:15.1326459
Number of items: 134,217,727
GC.GetTotalMemory after creating array: 4,295,021,240. Press Enter to set root.ChildA to null...
Setting tree root.ChildA to null
Collection time: 00:00:02.5062596
GC.GetTotalMemory after GC.Collect: 2,147,537,584. Press any key to finish...

Time for final test. Let’s create a tree of over 2 million complex nodes that contain some object references, small array and unique string. Additionally lets fill some of the MixedItem instances with byte array big enough to be put on Large Object Heap.

static int _itemsCount = 0;

class MixedItem
{
    byte[] _smallArray;
    byte[] _bigArray;
    string _uniqueString;

    public MixedItem ChildA { get; set; }
    public MixedItem ChildB { get; set; }

    public MixedItem()
    {
        _itemsCount++;

        _smallArray = new byte[1000];
        if (_itemsCount % 1000 == 0)
        {
            _bigArray = new byte[1000 * 1000];
        }

        _uniqueString = DateTime.Now.Ticks.ToString();
    }
}

static void AddChildren(MixedItem parent, int depth)
{
    if (depth == 0)
    {
        return;
    }
    else
    {
        parent.ChildA = new MixedItem();
        parent.ChildB = new MixedItem();

        AddChildren(parent.ChildA, depth - 1);
        AddChildren(parent.ChildB, depth - 1);
    }
}

static void TestSpeedForLargeTreeOfMixedObjects()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before building object tree: {0:N0}. Press any key to build tree...", GC.GetTotalMemory(true)));
    Console.ReadKey();

    sw.Start();
    _itemsCount = 0;
    MixedItem root = new MixedItem();
    AddChildren(root, 20);
    Console.WriteLine("Setup time: " + sw.Elapsed);
    Console.WriteLine("Number of items: " + _itemsCount.ToString("N0"));

    Console.WriteLine(string.Format("GC.GetTotalMemory after building object tree: {0:N0}. Press Enter to set root to null...", GC.GetTotalMemory(true)));

    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting tree root to null");
        root = null;
    }

    sw.Restart();
    GC.Collect();
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));

    Console.WriteLine(root); // To avoid compiler optimization...
    Console.ReadKey();
}

How will GC perform when subjected to almost 4.5 GB of managed heap memory with such complex structure? Test results for setting root to null

GC.GetTotalMemory before building object tree: 41,680. Press any key to build tree...
Setup time: 00:00:11.5479202
Number of items: 2,097,151
GC.GetTotalMemory after building object tree: 4,496,245,632. Press Enter to set root to null...
Setting tree root to null
Collection time: 00:00:00.5055634
GC.GetTotalMemory after GC.Collect: 54,520. Press any key to finish...

Managed memory counters for large tree of mixed objects; setting tree root to null... Click to enlarge...

And in case you wonder, here's what happens when root is not set to null:

GC.GetTotalMemory before building object tree: 41,680. Press any key to build tree...
Setup time: 00:00:11.6676969
Number of items: 2,097,151
GC.GetTotalMemory after building object tree: 4,496,245,632. Press Enter to set root to null...
Collection time: 00:00:00.5617486
GC.GetTotalMemory after GC.Collect: 4,496,245,592. Press any key to finish...

So what it all means? The conclusion is that unless you are writing applications which require extreme efficiency or total guarantee of uninterrupted execution, you should be really glad that .NET uses automatic memory management. GC is a great piece of software that frees you from mundane and error prone memory handling. It lets you focus on what really matters: providing features for application users. I’ve been professionally writing .NET applications for past 8 years (enterprise stuff, mainly web apps and Windows services) and I’m yet to witness1 a situation when GC cost would be a major factor. Usually performance bottleneck lays in things like: bad DB configuration, inefficient SQL/ORM queries, slow remote services, bad network utilization, lack of parallelism, poor caching, sluggish client side rendering etc. If you avoid basic mistakes like creating to many strings you probably won’t even notice that there is a Garbage Collector :)

Update 31.08.2014: I've just run the most demanding test (big tree of small reference types with all objects surviving GC cycle) on my new laptop. The result is 3.3s compared to 3.7s result presented in the post. Test program: .NET 4.5 console app in Release mode run without debugger attached. Hardware: i7-4700HQ 2.4-3.4GHz 4 Core CPU, 8GB DDR3/1600MHz RAM. System: Windows 7 Home Premium x64.

1. I’ve met some out of memory exceptions related to LOH fragmentation. The good thing is that LOH algorithms are improving and x86 platform, which is especially susceptible to such errors, is becoming a thing of the past…

How fast is .NET Garbage Collector? Part 1.

.NET GC is very fast! Well... I hope you need more than this reassuring statement, if so, read on :) I will show you some test results to prove that I’m not lying but first I will give you a quick reminder about what GC is:

Garbage Collector is fundamental component of .NET CLR. It takes care of freeing managed heap memory so a programmer doesn’t have to think about deallocation. Contrary to popular belief, GC handles memory occupied for both reference and value types. Why? Because quite often space for things like structures or integers is allocated on the heap. It happens for example when value type is an item of array or is a field in a class instance.

GC in .NET uses mark and sweep algorithm: it walks through objects graph starting from root elements (such us statics, references on stack or registers) and marks every object it can reach. When the walk is done, GC knows it can safely free the memory of objects that have not been marked – because as unreachable they are useless for the application.

For efficiency purposes GC supports notion of generations. When the object is created it belongs to Gen 0 (except for so called large objects). If Gen 0 object survives GC cycle it’s moved to Gen 1. If it survives one more cycle it goes to Gen 2 and stays there (there’s no Gen 31). Most objects are short lived – they don’t get pass Gen 0 or Gen 1 so .NET GC tries to free memory from lower generations first. It does Gen 2 (aka full collection) far less often then Gen 0 collection. If the object is big – above 850002 bytes it is allocated in Large Object Heap (LOH) and goes straight to Gen 2. Treating big objects the same way as small objects would have negative impact on heap defragmentation3 algorithms because moving such objects is time-consuming.

GC supports different modes for workstation and server configurations, is able to do some work in background threads, has to consider special cases like finalizers or pined memory buffers, its settings vary between platforms (e. g. CLR on PC is not the same as the one on Xbox)… well let’s stop here – I’ve promised a “quick reminder”! 

Ok, time for the test! 

In this first post I will show you how fast .NET GC can handle large arrays of value (non-reference) types. The test will involve an array of bytes that occupies about two gigabytes of memory. Despite its large size, such object does not put much pressure on the Garbage Collector. This is because the only reference GC has to check is the one for the array itself. If array becomes unreachable all memory occupied by its elements can be safely reused. Additionally, such array, being part of LOH, is not copied (to avoid heap fragmentation) when it survives collection cycle… In the second installment of this article I will show you how GC can handle more complex scenarios. We will examine performance for object array, and more importantly, a tree of objects with thousands of references… 

Note about test environment: I’ve run the test code on desktop PC with Intel i-5 2400 3.1 GHz 4 Core CPU, 12 GB of DDR 3/1333 RAM, running Windows 7 Ultimate x64. The program was a .NET 4.0 console application compiled in Release mode and run without debugger attached.

Here’s the test code:

static void TestSpeedForLargeByteArray()
{
    Stopwatch sw = new Stopwatch();

    Console.Write(string.Format("GC.GetTotalMemory before creating array: {0:N0}. Press any key to create array...", GC.GetTotalMemory(true)));
    Console.ReadKey();
    byte[] array = new byte[2000 * 1000 * 1000]; // About 2 GB
   
    sw.Start();
    for (int i = 0; i < array.Length; i++)
    {
        array[i] = 1; // Touch array elements to fill working set              
    }          
    Console.WriteLine("Setup time: " + sw.Elapsed);

    Console.WriteLine(string.Format("GC.GetTotalMemory after creating array: {0:N0}. Press Enter to set array to null...", GC.GetTotalMemory(true)));
    if (Console.ReadKey().Key == ConsoleKey.Enter)
    {
        Console.WriteLine("Setting array to null");
        array = null;
    }
               
    sw.Restart();
    GC.Collect();                 
    Console.WriteLine("Collection time: " + sw.Elapsed);
    Console.WriteLine(string.Format("GC.GetTotalMemory after GC.Collect: {0:N0}. Press any key to finish...", GC.GetTotalMemory(true)));

    Console.WriteLine(array); // To avoid compiler optimization...
    Console.ReadKey();
}

As you can see test is very simple. The code uses two methods of static GC class: GC.GetTotalMemory and GC.Collect. The former returns the amount of allocated managed memory and the latter forces Garbage Collector to do its job and free unused memory. The only thing that might be surprising is the loop that touches array items. Without it you will witness “strange” phenomenon: after array is defined GC.GetTotalMemory would report about 2 GB but you will not see memory usage increase in Task Manager! This is because taskmgr.exe shows Working Set data. You can run more advanced tool: Resource Monitor (resmon.exe) to see what’s happening: 

This is the screenshot before the “touch”:

Memory usage before access to array items. Click to enlarge...

And this is the one after the loop is executed:

Memory usage after access to array items. Click to enlarge...

Here are the test results (yeah, finally):

GC.GetTotalMemory before creating array: 41,568. Press any key to create array...
Setup time: 00:00:01.0633903
GC.GetTotalMemory after creating array: 2,000,053,864. Press Enter to set array to null...
Setting array to null
Collection time: 00:00:00.1443391
GC.GetTotalMemory after GC.Collect: 53,800. Press any key to finish...

What you can see here is that it took GC just around 150 milliseconds to free about 2 GB of memory. Nice, huh? You can appreciate the speed especially if you compare it with 1 second it took to just iterate over the array!

Below is a screenshot from Performance Monitor (perfmon.exe) running couple of .NET memory counters:

Performance Monitor with managed memory counters. Click to enlarge...

Our array is a big object (well over LOH threshold) – hence after it is defined memory of LOH increases yet Gen 0 heap size remains flat. 

Below are the results for GC.Collect run when reference to the array was not set to null:

GC.GetTotalMemory before creating array: 41,568. Press any key to create array..
Setup time: 00:00:01.0385779
GC.GetTotalMemory after creating array: 2,000,053,864. Press Enter to set array to null...
Collection time: 00:00:00.0001287
GC.GetTotalMemory after GC.Collect: 2,000,053,824. Press any key to finish...

Fraction of a millisecond. Totally negligible! Why I’m even mentioning a test for situation when memory is not collected? Well, in part two you will see that GC usually has more work to do when heap items survive collection cycle…

I hope to post the second part of the article in about a week or two. No promises though – you know, life… ;)

Update 26.07.2014: I've changed the screenshot from perfmon (Gen 0 and Gen 1 scale is bigger now).

Update 24.06.2014: I wrote the second part of this article few days ago. Click here to read it.

1. You can use GC.GC.MaxGeneration method to check it.

2. LOH threshold is an implementation detail. Most sources mention 85KB as the limit but it's not always the case - array of doubles with as little as 1000 items goes on LOH (on x86)...

3. .NET 4.5 introduces LOH improvements for better fragmentation prevention through balancing and enhanced free list usage. Future releases will probably have compaction option too.

Html Agility Pack - massive information extraction from WWW pages

Recently I needed to acquire some database. Unfortunately it was published only as a website that presented 50 records per single page. Whole database had more than 150 thousand records. What to do in such situation? Click through 3000 pages, manually collecting data in a text file? One week and it's done! ;) Better to write a program (so called scraper) which will do the work for you. The program has to do three things:

  • generated a list of addresses from which data should be collected;
  • visit pages sequentially and extract information from HTML code;
  • dump data to local database and log work progress.

Address generation should be quite easy. For most sites pagination is built with plain links in which page number is clearly visible in the main part of URL (http://example.com/somedb/page/1) or in the query string (http://example.com/somedb?page=1). If pagination is done via ajax calls situation is a bit more complex, but let's not bother with that in this post... When you know the pattern for page number parameter, all it's needed is a simple loop with something like:

string url = string.Format("http://example.com/somedb?page={0}", pageNumber)

Now it's time for something more interesting. How to extract data from a webpage? You can use WebRequest/WebResponse or WebClient classes from System.Net namespace to get page content. After that you can obtain information via regular expressions. You can also try to treat downloaded content as XML and scrutinize it with XPath or LINQ to XML. These are not good approaches, however. For complicated page structure writing correct expression might be difficult, one should also remember that in most cases webpages are not valid XML documents. Fortunately Html Agility Pack library was created. It allows convenient parsing of HTML pages, even these with malformed code (i.e. lacking proper closing tags). HAP goes through page content and builds document object model that can be later processed with LINQ to Objects or XPath.

To start working with HAP you should install NuGet package named HtmlAgilityPack (I was using version 1.4.6) and import namespace with the same name. If you don't want to use NuGet (why?) download zip file from project's website and add reference to HtmlAgilityPack.dll file suitable for your platform (zip contains separate versions for .NET 4.5 and Silverlight 5 for example). Documentation in .chm file might be useful too. Attention! When I opened downloaded file (in Windows 7), the documentation looked empty. "Unlock" option from file's properties screen helped to solve the problem.

Retrieving webpage content with HAP is very easy. You have to create HtmlWeb object and use its Load method with page address:

HtmlWeb htmlWeb = new HtmlWeb();
HtmlDocument htmlDocument = htmlWeb.Load("http://en.wikipedia.org/wiki/Paintball");

In return, you will receive object of HtmlDocument class which is the core of HAP library.

HtmlWeb contains a bunch of properties that control how document is retrieved. For example, it is possible to indicate whether cookies should be used (UseCookies) and what should be the value of User Agent header included in HTTP request (UserAgent). For me AutoDetectEncoding and OverrideEncoding properties were especially useful as they let me correctly read document with Polish characters.

HtmlWeb htmlWeb = new HtmlWeb() { AutoDetectEncoding = false, OverrideEncoding = Encoding.GetEncoding("iso-8859-2") };

StatusCode (typeSystem.Net.HttpStatusCode) is another very useful property of HttpWeb. With it you can check the result of latest request processing.

Having HtmlDocument object ready, you can start to extract data. Here's an example of how to obtain links addresses and texts from previously downloaded webpage (add using System.Linq):

IEnumerable<HtmlNode> links = htmlDocument.DocumentNode.Descendants("a").Where(x => x.Attributes.Contains("href"));
foreach (var link in links)
{
    Console.WriteLine(string.Format("Link href={0}, link text={1}", link.Attributes["href"].Value, link.InnerText));       
}

Property DocumentNode of type HtmlNode points to page's root. Method Descendants is used to retrieve all links (a tag) that contain href attribute. After that texts and address are printed on the console. Quite easy, huh? Few other examples:

Getting HTML code of the whole page:

string html = htmlDocument.DocumentNode.OuterHtml;

Getting element with "footer" id:

HtmlNode footer = htmlDocument.DocumentNode.Descendants().SingleOrDefault(x => x.Id == "footer");

Getting children of div with "toc" id and displaying names of child nodes which have type different than Text:

IEnumerable<HtmlNode> tocChildren = htmlDocument.DocumentNode.Descendants().Single(x => x.Id == "toc").ChildNodes;
foreach (HtmlNode child in tocChildren)
{
    if (child.NodeType != HtmlNodeType.Text)
    {
        Console.WriteLine(child.Name);
    }
}

Getting list elements (li tag) that have toclevel-1 class:

IEnumerable<HtmlNode> tocLiLevel1 = htmlDocument.DocumentNode.Descendants()
    .Where(x => x.Name == "li" && x.Attributes.Contains("class")
    && x.Attributes["class"].Value.Split().Contains("toclevel-1"));

Notice that Where filter is quite complex. Simple condition:

Where(x => x.Name == "li" && x.Attributes["class"].Value == "toclevel-1")

is not correct! Firstly there is no guarantee that each li tag will have class attribute set so we need to check if attribute exist to avoid NullReferenceException exception. Secondly the check for toclevel-1 is flawed. HTML element might have many classes, so instead of using == it's worthwhile to use Contains(). Plain Value.Contains is not enough though. What if we are looking for "sec" class and element has "secret" class? Such element will be matched too! Rather than Value.Contains you should use Value.Split().Contains. This way an array of strings will be checked via equals operator (instead of searching a single string for substring).

Getting texts of all li elements which are nested in minimum one li element:

var h1Texts = from node in htmlDocument.DocumentNode.Descendants()
              where node.Name == "li" && node.Ancestors("li").Count() > 0
              select node.InnerText;

Beyond LINQ to Objects, XPath might also be used to extract information. For example:

Getting a tags that have href attribute value starting with # and longer than 15 characters:

IEnumerable<HtmlNode> links = htmlDocument.DocumentNode.SelectNodes("//a[starts-with(@href, '#') and string-length(@href) > 15]");

Finding li elements inside div with id "toc" which are third child in their parent element:

IEnumerable<HtmlNode> listItems = htmlDocument.DocumentNode.SelectNodes("//div[@id='toc']//li[3]");

XPath is a complex tool and it's impossible to show all its great capabilities in this post...

HAP lets you explore page structure and content but it also allows page modification and save. It has helper methods good for detecting document encoding (DetectEncoding), removing HTML entities (DeEntitize) and more... It is also possible to gather validation information (i.e. check if original document had proper closing tags). These topics are beyond the scope of this post.

While processing consecutive pages, dump useful information to local database most suitable for your needs, Maybe .csv file will be enough for you, maybe SQL database will be required? For me plain text file was sufficient.

Last thing worth doing is ensuring that scraper properly logs information about its work progress (for sure you want to know how far your program went and if it encountered any errors). For logging it is best to use specialized library such as log4net. There's a lot of tutorials on how to use log4net so I will not write about it. But I will show you a sample configuration which you can use in console application:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
    <configSections>
        <section name="log4net" type="log4net.Config.Log4NetConfigurationSectionHandler, log4net"/>          
    </configSections>
    <log4net>        
        <root>
            <level value="DEBUG"/>            
            <appender-ref ref="ConsoleAppender" />
            <appender-ref ref="RollingFileAppender"/>
        </root>
        <appender name="ConsoleAppender" type="log4net.Appender.ColoredConsoleAppender">
            <layout type="log4net.Layout.PatternLayout">
                <conversionPattern value="%date{ISO8601} %level [%thread] %logger - %message%newline" />
            </layout>
            <mapping>
                <level value="ERROR" />
                <foreColor value="White" />
                <backColor value="Red" />
            </mapping>
            <filter type="log4net.Filter.LevelRangeFilter">
                <levelMin value="INFO" />                
            </filter>
        </appender>         
        <appender name="RollingFileAppender" type="log4net.Appender.RollingFileAppender">
            <file value="Log.txt" />
            <appendToFile value="true" />
            <rollingStyle value="Size" />
            <maxSizeRollBackups value="10" />
            <maximumFileSize value="50MB" />
            <staticLogFileName value="true" />
            <layout type="log4net.Layout.PatternLayout">
                <conversionPattern value="%date{ISO8601} %level [%thread] %logger - %message%newline%exception" />
            </layout>
        </appender>
    </log4net>    
</configuration>

Above config contains two appenders: ConsoleAppender and RollingFileAppender. The first logs text to console window, ensuring that errors are clearly distinguished by color. To reduce amount of information LevelRangeFilter is set so only entries with INFO or higher level are presented. The second appender logs to text file (even entries with DEBUG level go there). Maximum size of singe file is set to 50MB and total files number limit is set to 10. Current log is always in Log.txt file...

And that's all, scraper is ready! Run it and let it labor for you. No dull, long hour work - leave it for people who don't know how to program :)

Additionally you can try a little exercise: instead of creating a list of all pages to visit, determine only the first page and find a link to next page in currently processed one...

P.S. Keep in mind that HAP works on HTML code that was sent by the server (this code is used by HAP to build document model). DOM which you can observe in browser's developer tools is often a result of scripts execution and might differ greatly form the one build directly from HTTP response.

Update 08.12.2013: As requested, I created simple demo (Visual Studio 2010 solution) of how to use Html Agility Pack and log4net. The app extracts some links from wiki page and dumps them to text file. Wiki page is saved to htm file to avoid dependency on web resource that might change. Download