Showing posts with label Data Structures. Show all posts
Showing posts with label Data Structures. Show all posts

Sunday, 15 January 2023

Working-With-Byte-Arrays

In this post I will show how to read/write different data type values to and from a byte buffer. This should prove useful when working with block data or pages. In this scenario, pages describes database pages or similar block data mechanisms.


Top

In this post...

Top

How To Handle Typed Values

The aim is to read/write different typed values from a byte array. In C++ one can achieve this by using a union. In C# we achieve this by using a struct/class using explicit layout. Explicit layout is the key here as it ensures types are aligned correctly.

The basic idea is to have a number of byte values offset from zero to maximum bytes required. Then add basic types, such as int 16, int 32, int 64, float, etc all at offset zero. Then one can set a float value and read of the four byte values. The same can be done for most basic types, set the value and the read the corresponding byte values. To read typed values, simply populate the byte values accordingly then read the basic type info (int 16, int 32, int float, etc).

For those with a COM background this approach is similar to the VARIANT type.

Top

The Union Value Type


using System;
using System.Runtime.InteropServices;
namespace Blog
{
  [StructLayout(LayoutKind.Explicit)]
  public struct Value
  {
    [FieldOffset(0)] public byte B0;
    [FieldOffset(1)] public byte B1;
    [FieldOffset(2)] public byte B2;
    [FieldOffset(3)] public byte B3;
    [FieldOffset(4)] public byte B4;
    [FieldOffset(5)] public byte B5;
    [FieldOffset(6)] public byte B6;
    [FieldOffset(7)] public byte B7;

    [FieldOffset(0)] public float Float;
    [FieldOffset(0)] public double Double;
    [FieldOffset(0)] public Int16 Int16;
    [FieldOffset(0)] public Int32 Int32;
    [FieldOffset(0)] public Int64 Int64;
  }
}

The above struct declaration shows eight bytes, B0-B7 for data transfer. If using the decimal type this will need to be expanded to include 16 bytes! As can be seen, B0-B7 is byte aligned and offset accordingly.

Note also, that basic types float, double, Int16, etc all start at offset zero. So, if one sets the Float field, the corresponding 4 bytes can be read from B0-B3. To reverse the action, set fields B0-B3, then read the float value.

It is imperative that one knows how many bytes are required for a typed value. The above structure should cover most data types bar decimal. DateTime values can also be stored by first converting to long and using the Int64 field or bytes B0-B7 to recreate.

Top

Testing The Union Value Type

The above can be tested using the following code...

static void RawTest()
{
  Value value = new Value();
  byte[] data = new byte[128];

  int cursor = 0;
  
  // *********************************************************************************************
  // Writing values to the data byte array.
  // *********************************************************************************************
  Int16 v1 = Int16.MaxValue - 1067;
  Int32 v2 = Int32.MaxValue - 10067;
  float v3 = float.MaxValue - 1.07896f;

  // Write an Int16 value to the data byte array.
  // First set the Value's Int16 field, then read two Value bytes.
  value.Int16 = v1;
  data[cursor++] = value.B0;
  data[cursor++] = value.B1;

  // Write an Int32 value to the data byte array.
  // First set the Value's Int32 field, then read four Value bytes.
  value.Int32 = v2;
  data[cursor++] = value.B0;
  data[cursor++] = value.B1;
  data[cursor++] = value.B2;
  data[cursor++] = value.B3;

  // Write a float value to the data byte array.
  // First set the Value's Float field, then read four Value bytes.
  value.Float = v3;
  data[cursor++] = value.B0;
  data[cursor++] = value.B1;
  data[cursor++] = value.B2;
  data[cursor++] = value.B3;

  
  // *********************************************************************************************
  // Reading values from the data byte array.
  // *********************************************************************************************
  cursor = 0;
  
  // Read an Int16 from the data byte array.
  // Set Value's first two byte fields, then read the Value's Int16 field.
  value.B0 = data[cursor++];
  value.B1 = data[cursor++];
  var v1Result = value.Int16;

  // Read an Int32 from the data byte array.
  // Set Value's first four byte fields, then read the Value's Int32 field.
  value.B0 = data[cursor++];
  value.B1 = data[cursor++];
  value.B2 = data[cursor++];
  value.B3 = data[cursor++];
  var v2Result = value.Int32;

  // Read a float from the data byte array.
  // Set Value's first four byte fields, then read the Value's Float field.
  value.B0 = data[cursor++];
  value.B1 = data[cursor++];
  value.B2 = data[cursor++];
  value.B3 = data[cursor++];
  var v3Result = value.Float;

  Console.WriteLine(v1);
  Console.WriteLine(v1Result);
  Console.WriteLine(v2);
  Console.WriteLine(v2Result);
  Console.WriteLine(v3);
  Console.WriteLine(v3Result);
}
Top

Writing Values To A Byte Array

Figure 2 illustrates a byte array filled with values from the previous test code. As the diagram illustrates, data values are byte aligned accordingly. That is, a 16 bit-integer requires 2 bytes, a float or 32-bit integer requires 4 bytes. This approach works well for data blocks comprising of byte arrays. Simply create a byte array, write values and save to disk. Conversely, load a byte array block from disk into memory, then proceed to read actual values.

Top

Improving The Value Interface

The current method of reading/writing values is somewhat verbose. One needs to track the byte array offset (cursor) and the offset to add following a read or write. In addition, explicitly reading and writing to the Value's byte fields (B0...BN) is tiresome and error-prone. The following should help alleviate these problems...

  • Specify the byte array and initial offset.
  • Specify a cursor that is relative to the specified initial offset.
  • Update the cursor accordingly following a read or write operation.
  • Allow the cursor's position to be set manually, the cursor will always be relative to the specified offset.

The following class, ByteBuffer, implements the above features.

using System;

namespace Blog
{
  /// <summary>
  /// Allows values to read/written to/from a byte array.
  /// Specify a byte buffer and initial offset in the constructor.
  /// Data will be read/written at this offset.
  /// The class uses a cursor to indicate current read/write position.
  /// The cursor is always offset by the offset specified in the constructor.
  /// </summary>
  public class ByteBuffer
  {
    private Value _value = new Value();
    private int _internalCursor;
    private int _offset;
    private readonly byte[] _buffer;

    public int Cursor => _internalCursor - _offset;

    public ByteBuffer(byte[] buffer, int offset)
    {
      _buffer = buffer;
      _offset = offset;
      _internalCursor = offset;
    }

    public ByteBuffer SetCursor(int position)
    {
      _internalCursor = _offset + position;
      return this;
    }

    public ByteBuffer Int16(Int16 value)
    {
      _value.Int16 = value;
      _buffer[_internalCursor++] = _value.B0;
      _buffer[_internalCursor++] = _value.B1;
      return this;
    }

    public ByteBuffer Int16(out Int16 result)
    {
      _value.B0 = _buffer[_internalCursor++];
      _value.B1 = _buffer[_internalCursor++];
      result = _value.Int16;
      return this;
    }

    public ByteBuffer Int32(Int32 value)
    {
      _value.Int32 = value;
      _buffer[_internalCursor++] = _value.B0;
      _buffer[_internalCursor++] = _value.B1;
      _buffer[_internalCursor++] = _value.B2;
      _buffer[_internalCursor++] = _value.B3;
      return this;
    }

    public ByteBuffer Int32(out Int32 result)
    {
      _value.B0 = _buffer[_internalCursor++];
      _value.B1 = _buffer[_internalCursor++];
      _value.B2 = _buffer[_internalCursor++];
      _value.B3 = _buffer[_internalCursor++];

      result = _value.Int32;
      return this;
    }

    public ByteBuffer Float(float value)
    {
      _value.Float = value;
      _buffer[_internalCursor++] = _value.B0;
      _buffer[_internalCursor++] = _value.B1;
      _buffer[_internalCursor++] = _value.B2;
      _buffer[_internalCursor++] = _value.B3;
      return this;
    }

    public ByteBuffer Float(out float result)
    {
      _value.B0 = _buffer[_internalCursor++];
      _value.B1 = _buffer[_internalCursor++];
      _value.B2 = _buffer[_internalCursor++];
      _value.B3 = _buffer[_internalCursor++];
      result = _value.Float;
      return this;
    }
  }
}
Top

Using The ByteBuffer Class

Using the ByteBuffer class is fairly straightforward. Simply call the constructor with a byte array and offset. No data can be read or written before the offset.

A sample test/driver program now follows...

static void Main(string[] args)
{
  byte[] data = new byte[128];
  ByteBuffer buffer = new ByteBuffer(data, 5);

  Int16 v1 = Int16.MaxValue - 1067;
  Int32 v2 = Int32.MaxValue - 10067;
  float v3 = float.MaxValue - 1.07896f;

  int bytesWritten = buffer
    .Int16(v1)
    .Int32(v2)
    .Float(v3)
    .Cursor;
  Console.WriteLine($"{bytesWritten} bytes written to buffer.");

  int bytesRead = buffer
    .SetCursor(0)
    .Int16(out var v1Read)
    .Int32(out var v2Read)
    .Float(out var v3Read)
    .Cursor;

  Console.WriteLine($"{bytesRead} bytes read from buffer.");
  Console.WriteLine($"v1Write:{v1} - v1Read:{v1Read}");
  Console.WriteLine($"v2Write:{v2} - v2Read:{v2Read}");
  Console.WriteLine($"v3Write:{v3} - v3Read:{v3Read}");
}

The above code wites the following to the console.

Notice how the test program uses an offset of 5 when constructing the ByteBuffer. The correct bytes read/wrriten of ten is still returned. The first five bytes in this example will be zeroed.

Top

Saturday, 19 November 2022

Performance Testing

Often in software development one needs to determine which algorithm is more performant. The easiest way to do this, in C#, is to use the Stopwatch class. To ensure fairly accurate results, it is best to run each algorithm N times and take the average. Even so, results are not entirely accurate as the first run will be cold. That is, currently, the JIT compiler may not have been enacted. My own test results show that that the first run tends to be slowest. Subsequent runs tend to be much faster (in the same session).

Regardless of the above, timings are useful enough to determine performant algorithms.

In this post...

Goals

With any software project, no matter the size, some planning is always worthwhile. So, for this project I want the following...

  • Easy test specification, e.g. test name and a function pointer to the test.
  • Specify the number of times each test should be run.
  • Obtain the total time for all test runs and the average run time.
  • The ability to obtain test results as a string.
Top

Analysis

Given the above requirements the following can be stated.

  • Each test is named and timed.
  • Each test is run N times, from this one can deduce the total runtime and average runtime.
  • One may run multiple tests and each test may be run N times. From this one can deduce that an array of sorts will be required.
Top

Design

Given the requirements and preliminary analysis we can proceed to perform some basic design.

Let's start with the idea of a test. A test simply consists of a name and a function pointer. Something like...

Test(string name, Func<object> func)

The function pointer expects the function to return an object. This leaves it open-ended and will prove useful to ensure that in release mode functions are not removed. Release mode in most languages will remove functions that appear useless.

Next we need a structure that holds the results of a single test run N times. We might call this TestGroupResult. The structure should maintain the test name, total elapsed time (for the N runs, and the average time per test run). Such a structure might be as follows...

TestGroupResult(string name, TimeSpan totalElapsedTime, TimeSpan averageElapsedTime)

For the next step we need a structure that maintains the entire result set. That is all the group test results. Again, for each test we run said test N times to obtain a total elapsed time and average times. The result is the TestGroupResult. Let's name this new structure BenchmarkResult...

BenchmarkResult(int runsPerTest, GroupResult[] results)

Finally, we need an entry point, where we specify the tests to run and the number of times each test should be run. It makes sense to call this entry point Benchmark.

Benchmark.Run(string name, Func<object> func)

To create an instance we might run the following code.

internal class Program
{
  static void Main(string[] args)
  {
    var result = Benchmark.Run(10,
      ("Test1", () => { Thread.Sleep(500); return 1; }),
      ("Test2", () => { Thread.Sleep(400); return 2; })
    );

    Console.WriteLine(result.GenerateReport());    
  }
}

Using the above code, my console output is as follows..

Top

Source code

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace Fun.Benchmarking
{
  /// <summary>
  /// Encapulates a group of tests.
  /// Maintains the total elapsed time and average elapsed time.
  /// Generate a report as a string.
  /// </summary>
  public class TestGroupResult
  {
    public string Name { get; }
    public TimeSpan TotalElapsedTime { get; }
    public TimeSpan AverageElapsedTime { get; }

    public TestGroupResult(
      string name,
      TimeSpan totalElapsedTime,
      TimeSpan averageElapsedTime)
    {
      this.Name = name;
      this.TotalElapsedTime = totalElapsedTime;
      this.AverageElapsedTime = averageElapsedTime;
    }

    public StringBuilderGenerateReport(StringBuilder sb)
    {
      return sb
        .AppendLine($"Test Name : {Name}")
        .AppendLine($"  Total Elapsed Time: {TotalElapsedTime}")
        .AppendLine($"  Total Average Time: {AverageElapsedTime}");
    }
  }

  /// <summary>
  /// Represents a benchmark result which includes...
  /// The number of runs for each supplied test.
  /// An array of test group results (a group is a single test run N times).
  /// </summary>
  public class BenchmarkResult
  {
    public int RunsPerTest { get; }
    public TestGroupResult[] GroupResults { get; }

    public BenchmarkResult(
      int runsPerTest,
      TestGroupResult[] groupResult)
    {
      this.RunsPerTest = runsPerTest;
      this.GroupResults = groupResult;
    }

    public string GenerateReport()
    {
      StringBuilder sb = new StringBuilder();
      sb.AppendLine($"Runs Per Test: {RunsPerTest}");
      foreach (TestGroupResult groupResult in GroupResults)
        groupResult.GenerateReport(sb);
      return sb.ToString();
    }
  }

  /// <summary>
  /// The Benchmark allows one to determine the performance of an algorithm.
  /// Multiple algorithms may be tested, great for determining which algorithm performs best.
  /// </summary>
  public class Benchmark
  {
    /// <summary>
    /// Run one or more tests and specify how many times each test should be run.
    /// The total and average elapsed time for each test will be calculated.
    /// </summary>
    /// <param name="runsPerTest">How many times each test should be run.</param>
    /// <param name="tests">An array of tests to be run.</param>
    /// <returns></returns>
    public static BenchmarkResult Run(
      int runsPerTest,
      params (string Name, Func<object> Code)[] tests)
    {
      List<TestGroupResult> groups = new List<TestGroupResult>();
      foreach (var test in tests)
      {
        TestGroupResult group = RunTestGroup(runsPerTest, test);
        groups.Add(group);
      }
      return new BenchmarkResult(runsPerTest, groups.ToArray());
    }

    /// <summary>
    /// Run a single test (N runsPerTest) times.
    /// </summary>
    /// <param name="runsPerTest"></param>
    /// <param name="test"></param>
    /// <returns></returns>
    public static TestGroupResult RunTestGroup(
      int runsPerTest,
      (string Name, Func<object> Code) test)
    {
      Stopwatch stopwatch = Stopwatch.StartNew();
      for (int testCount = 0; testCount < runsPerTest; testCount++)
      {
        test.Code();        
      }
      stopwatch.Stop();
      TimeSpan elapsedTime = stopwatch.Elapsed;
      return new TestGroupResult(test.Name, elapsedTime, new TimeSpan>(elapsedTime.Ticks/runsPerTest));
    }
  }
}

Tuesday, 12 July 2022

Tree Data Structures

In this post I will explain an important data structure, "The Tree". Trees are versatile data structures that are used in many algorithms, from abstract syntax trees, to the HTML DOM your Web browser uses.

Top

A Basic Tree Data Structure

Diagram 1 illustrates that a tree is simply a collection of nodes. How the nodes are layed out and, the information a given node contains, is specific to the problem being solved.

Some basic observations about a tree data structure are...

  • A tree always contains a single, top-level node, known as the root.
  • Any given tree node can have zero or more child nodes. (E.g. The root node in diagram 1, contains three child nodes)
  • Any given node has a level. In diagram 1, the root is defined as being at level 1.

Top

A Tree Structure In Code

Given that we know a node may contain zero or more children. How can we represent this in code? One way might be to have each node contain a collection of child nodes. The collection might be an array or list of nodes. A list, of course allows us to add more child nodes without having to resize the collection as with an array. Under the hood, a list will resize itself as nodes are added.

The list approach is commonly used, however, having a list instance for each node can impact the memory footprint.

As always with software, there are tradeoffs and one needs to consider the problem domain and problem size to determine the best fit.

Diagram 2 illustrates how to implement a tree structure, where child nodes are stored within a list. As is often the case in software, adding a level of indirection is key. Here, the indirection is a list that stores child nodes for any given node. As already noted, this approach can prove to be expensive in terms of memory usage. Each node must contain an instance of the list class, even if the node contains no child nodes.

Top

Self-Describing Tree Structure

Most of the time, using data structures provided by your development platform are fine. Other times, however, one needs to rethink, go back to basics and develop a more streamlined solution. Developing custom data structures to fit a niche is not a new idea.

Diagram 3 illustrates a tree structure that is fully described using a node structure. That is, no need for a separate list data structure to store child nodes.

Diagram 3 also illustrates the following...

  • Implements a doubly-linked list, allowing one to forward or reverse traverse sibling nodes.
  • Each node has a pointer to its parent node.
  • A node containing children has a pointer to its first child node and to its last child node. This caters for efficient insertion of removal of nodes.

This particular structure is optimal in the sense that only the node data required is stored. A node does not require a list or array to store child nodes. This does complicate the implementation somewhat, but, I think is worthwhile to ensure minimal memory usage.

Analysis allows us to determine that a node basically consists of a previous and next sibling. This essentially describes a doubly-linked list. The first and last child pointers describe how a node collection might describe a collection of nodes.

Top

Self-Describing Tree Source Code

Analysis of the self-describing tree structure leads to two separate records. The first describes a simple node, that contains pointers to previous and next siblings. The second, describes a node that contains the first and last child nodes, essentially a collection of nodes. The following C# code illustrates how these ideas might be implemented. Records, in C# are best represented using classes or structs.

The following is the code for a Node (C#). Note, all members could just be declared as public fields. Using private members and separate accessor functions allows us to add additional functionality. This might include raising events when the tree structure is modified.


public class Node
{
  private NodeContainer _parent;
  private Node _previousSibling;
  private Node _nextSibling;

  public Node Parent =>
    _parent;

  public Node PreviousSibling =>
    _previousSibling;

  public Node NextSibling =>
    _nextSibling;

  public void SetParent(NodeContainer container)
  {
    _parent = container;
  }

  public void SetPreviousSibling(Node prev)
  {
    _previousSibling = prev;
  }

  public void SetNextSibling(Node next)
  {
    _nextSibling = next;
  }
}
Top

The next code snippet describes a node container. As one might expect, a node container, contains zero or more nodes. Code is included to append a node to an existing node. The code also includes an All method. This method returns all nodes, using a depth-first tree search.


public class NodeContainer : Node
{
  private Node _firstChild;
  private Node _lastChild;

  public IEnumerable<Node> All()
  {
    Stack<Node> stack = new Stack<Node>();
    stack.Push(this);

    while (stack.Count > 0)
    {
      Node cur = stack.Pop();
      yield return cur;

      if (cur is NodeContainer container)
      {
        Node curSib = container._lastChild;

        while (null != curSib)
        {
          stack.Push(curSib);
          curSib = curSib.PreviousSibling;
        }
      }       
    }
  }

  public void Append(Node node)
  {
    node.SetParent(this);

    if (null == _firstChild)
    {
      _firstChild = node;
      _lastChild = node;
      node.SetNextSibling(null);
      node.SetPreviousSibling(null);
    }
    else
    {
      node.SetPreviousSibling(_lastChild);
      node.SetNextSibling(null);
      _lastChild.SetNextSibling(node);
      _lastChild = node;
    }
  }
}
Top

Summary

This post only scratches the surface when discussing tree data structures.

Tree, in software are found in many places. Examples include...
  • Abstract Syntax Trees - the result of parsing program text.
  • Expression trees - the result of parsing an expression.
  • HTML DOM - as used by a web browser.