Introducing CloneExtensions .NET cloning library

Blog has been moved to new address: marcinjuraszek.com. You'll be redirected to new site in few seconds. If you don't want to wait click here: Introducing CloneExtensions .NET cloning library

I've spent last two days working on my first open source .NET library named CloneExtensions. It gives you a smart way to clone your object instances without implementing any interface writing any additional Clone method at all. It uses Expression Tree to compile that Clone method for you right before you're trying to use GetClone<T> for given type T for the first time.

Project is in early phase but even now you can use it to clone plenty of different types:

• Primitive (int, uint, byte, double, char, etc.), known immutable types (DateTime, TimeSpan, String) and delegates (including Action<T>, Func<T1, TResult>, etc)
• Nullable<T>
• T[] arrays
• Custom classes and structs, including generic classes and structs.

Following class/struct members are cloned internally:

• Values of public, not readonly fields
• Values of public properties with both get and set accessors
• Collection items for types implementing ICollection<T>

If you're interested in how it works internally look at documentation, where Expression Tree creation logic is described with additional samples.

Because Expression once generated and compiled is used like it was written by you, starting from the second time method is used with the same T, it has the same performance as if you'd write the logic by yourself. That's why CloneExtensions is definitely faster then reflection-based solutions and is faster then serialization-based solutions when you clone more then just a couple instances of the same time.

Take a look at CloneExtensions and feel free to provide feedback to both existing solution and plans for future developments.

Partitioning the collection using LINQ: different approaches, different performance, the same result

Blog has been moved to new address: marcinjuraszek.com. You'll be redirected to new site in few seconds. If you don't want to wait click here: Partitioning the collection using LINQ: different approaches, different performance, the same result



Another blog post inspired by StackOverflow question. This time it's all about LINQ, performance and a tiny little detail, that really matters. The question itself is about yield keyword in VB.NET, but there is another, much more interesting part I'd like to examine. The algorithm quoted in the question is the key.

The idea is simple. How to partition a collection into parts with given number of elements in ever part? Algorithm presented in the question is as easy as the questions seems to be:

public IEnumerable<IEnumerable<T>> Partition<T>(IEnumerable<T> source, int size)
{
    if (source == null)
        throw new ArgumentNullException("list");

    if (size < 1)
        throw new ArgumentOutOfRangeException("size");

    int index = 1;
    IEnumerable<T> partition = source.Take(size).AsEnumerable();

    while (partition.Any())
    {
        yield return partition;
        partition = source.Skip(index++ * size).Take(size).AsEnumerable();
    }
}

Question is, it the algorithm good and efficient? It returns correct results, that's for sure. But that's not the only important part of every algorithm. Unfortunately, I must say that the algorithm is no good. To answer why it's no a good algorithm? I'd like to show you another approach on solving the same problem:

public IEnumerable<IEnumerable<T>> Partition<T>(IEnumerable<T> source, int size)
{
    var partition = new List<T>(size);
    var counter = 0;

    using (var enumerator = source.GetEnumerator())
    {
        while (enumerator.MoveNext())
        {
            partition.Add(enumerator.Current);
            counter++;
            if (counter % size == 0)
            {
                yield return partition.ToList();
                partition.Clear();
                counter = 0;
            }
        }

        if (counter != 0)
            yield return partition;
    }
}

Is has exactly the same signature and returns exactly the same results. Why is it better then? There are couple possible answers:

• because it does no use Skip/Take methods
• because it has O(n) complexity, when the other one is O(n*log(n))
• because it iterate over entire collection only once, and the other one does it multiple times

If you look closer, all these actually means the same: the second method is much faster! How much? Really much :) Look at the charts. They show execution time depending on number of partitions that need to be created. Source collections have 1000000 elements and they are created using following code:

var enumSource = Enumerable.Range(0, size);
var arraySource = enumSource.ToArray();
var listSource = arraySource.ToList();

You may wonder why I tried the same algorithm on three different collections. That's because of how Skip/Take solution works: it iterates from that beginning of collection every time new partition is requested. It may not be important if your source is static collection (like Array or List), but it will cause Enumerable.Range to generate the collection every time again and again. That's really not necessary, is it?

Y-axis shows execution time and X-axis shows number of partitions that are being generated. The difference is huge, isn't it? It takes about 6 second to generate 1000 partitions using Skip/Take algorithm and about 40ms to do that with the other one!

I'm writing this post to highlight that if LINQ seems to be really great solution for nearly every collection-related problem and you can get working solution really easily using it, it's not always really a good and fast solution.

Playing around with List<T>, part three: Ensuring underlying array capacity

Blog has been moved to new address: marcinjuraszek.com. You'll be redirected to new site in few seconds. If you don't want to wait click here: Playing around with List, part three: Ensuring underlying array capacity



This time on the series I'm gonna examine how List<T> ensures the underlying array capacity. But because it's quite interesting topic I decided to focus on adding new elements to the list only, leaving deleting/clearing for the next part.

First of all, we have to list all ways to add new elements into the list. There are four of them available:

public void Add(T item)
public void AddRange(IEnumerable<T> collection)
public void Insert(int index, T item)
public void InsertRange(int index, IEnumerable<T> collection)

I've already written a little bit about InsertRange when writing about constructors, but they all should be quite easy to understand. Both Add and AddRange insert new data (one or more items) at the end of the list while Insert and InsertRange inserts data starting from given index. In both cases List<T> class has to take care of ensuring, that underlying array can handle existing and new elements. Because that logic has to be used from couple different methods it was separated into separated private helper method called EnsureCapacity.

private void EnsureCapacity(int min)

Looks easy, but before we'll check what the method actually does let's focus on another question: what is passed as min parameter value when the method is called? The answer can be easily found. Both Add and Insert call it following given pattern:

this.EnsureCapacity(this._size + 1);

Case is even easier with AddRange and InsertRange, because the first one uses the second internally

public void AddRange(IEnumerable<T> collection)
{
    this.InsertRange(this._size, collection);
}

At the end, EnsureCapacity is called using number of elements found in the source collection (if it can be determined without enumeration):

int count = collection2.Count;
if (count > 0)
{
    this.EnsureCapacity(this._size + count);

Otherwise, to source collection is enumerated with Insert method call on every element.

But moving back to EnsureCapacity logic. We now know that the method gets one parameter which determines minimal capacity for underlying array. So someone could say, just use it not as minimum but as direct array size. It would have a great advantage: no unused memory space used. However, because changing array size is quite time consuming it would be really inefficient. We should make sure that underlying array reallocation happens as rarely as possible. But on the other hand we want the structure to not allocate big amount of unused memory. Quite difficult war between time and memory efficiency. How did List<T> solve that problem?

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num > 2146435071)
        {
            num = 2146435071;
        }
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

It follows exponential function by multiplying current array size by 2 whenever it's possible.

Following graph represents size of unused allocated memory in correlation to number of element stored within a list in case they were all added one after another.

The graph has two really important properties:

• Always over 50% of underlying array size is really used by the list
• The bigger the list is, the less often it is necessary to reallocate underlying array

The second one is really important, because reallocating small array is much less expensive then reallocating array with hundreds or thousands of elements.

I remember a really nice StackOveflow question titled How is the internal array of a List<T> increased when using AddRange. Author asked if the underlying array size is always changed to just match current list size + number of elements added. Answer is: it's not. That's because even when collection implements ICollection it's possible that EnsureCapacity will just multiply underlying array size by 2 instead of setting it to strict number. The correct new size of array can be described as Max(old_size * 2, old_size + count) and it will vary depending on current List<T> size.

Why (or when) you should/shouldn't use Descendants() method

Blog has been moved to new address: marcinjuraszek.com. You'll be redirected to new site in few seconds. If you don't want to wait click here: Why (or when) you should/shouldn’t use Descendants() method




A lot of LINQ to XML questions on StackOverflow are being answered using Descendants() method calls. It looks like most of people think it's the best way to handle and query XML document: it's easy to use, you don't have to worry about whole tree structure. It just works. But are these solutions really good ones? Is Descendants method really that good as it seems to be? I would say: NO! I think common LINQ to XML queries should not use Descendants(). I'll try to answer it shouldn't be used in this blog post.

But before I'll answer the question we have to say how does Descendants() really works and how it differs from Elements() method. Let's start with MSDN description of both methods:

XContainer.Elements Method (XName):
Returns a filtered collection of the child elements of this element or document, in document order. Only elements that have a matching XName are included in the collection.

XContainer.Descendants Method (XName)

Returns a filtered collection of the descendant elements for this document or element, in document order. Only elements that have a matching XName are included in the collection.

They differ by only one word: child in Elements() and descendants in Descendants(). What does it actually mean? Consider following XML document:

<?xml version="1.0"?>
<PurchaseOrder PurchaseOrderNumber="99503" OrderDate="1999-10-20">
  <Address Type="Shipping">
    <Name>Ellen Adams</Name>
    <Street>123 Maple Street</Street>
    <City>Mill Valley</City>
    <State>CA</State>
    <Zip>10999</Zip>
    <Country>USA</Country>
  </Address>
</PurchaseOrder>

And a simple method:

Console.WriteLine("Descendants:");
Console.WriteLine();
foreach (var item in doc.Descendants())
    Console.WriteLine(item.Name);

Console.WriteLine();
Console.WriteLine("Elements:");
Console.WriteLine();
foreach (var item in doc.Elements())
    Console.WriteLine(item.Name);

I think the results are predictable:

Descendants:

PurchaseOrder
Address
Name
Street
City
State
Zip
Country

Elements:

PurchaseOrder

The difference is clear: Descendants() returns all descendant element, no matter how deep in XML tree they are. Elements() returns only direct children of current XML node. It looks simple, but it's really a huge difference and every LINQ to XML user has to be aware of that difference! Why it is so important? Because it affects queries performance and can cause incorrect results when used wrong.

OK, get back to the main questions:

Why shouldn't you use Descendants() method?

1. Because it may have poor performance:

Descendants() always traverses down whole document tree starting from current element. It results in a set of unnecessary items being checked. As long as you're able to precisely specify location of elements you're looking for you should do that and use Element()/Elements() instead.

<?xml version="1.0"?>
<PurchaseOrder PurchaseOrderNumber="99503" OrderDate="1999-10-20">
  <Address Type="Shipping">
    <Name>Ellen Adams</Name>
    <Street>123 Maple Street</Street>
    <City>Mill Valley</City>
    <State>CA</State>
    <Zip>10999</Zip>
    <Country>USA</Country>
  </Address>
  <Address Type="Billing">
    <Name>Tai Yee</Name>
    <Street>8 Oak Avenue</Street>
    <City>Old Town</City>
    <State>PA</State>
    <Zip>95819</Zip>
    <Country>USA</Country>
  </Address>
  <DeliveryNotes>Please leave packages in shed by driveway.</DeliveryNotes>
  <Items>
    <Item PartNumber="872-AA">
      <ProductName>Lawnmower</ProductName>
      <Quantity>1</Quantity>
      <USPrice>148.95</USPrice>
      <Comment>Confirm this is electric</Comment>
    </Item>
    <Item PartNumber="926-AA">
      <ProductName>Baby Monitor</ProductName>
      <Quantity>2</Quantity>
      <USPrice>39.98</USPrice>
      <ShipDate>1999-05-21</ShipDate>
    </Item>
  </Items>
</PurchaseOrder>

Let's query the document for all item comments. It can be easily done using Descendants():

var comments = doc.Descendants("Comment")
                    .Select(c => (string)c)
                    .ToList();

It produces expected results and returns a list with just one element. However, it is highly inefficient! It will go through every XML node within whole document (they are 27 nodes in that document) and check, if the node name matches "Comment". Are all these checks necessary? No, they aren't. Because we know how the document is structured, we can do following:

var comments = doc.Root.Element("Items")
                        .Elements("Item")
                        .Elements("Comment")
                        .Select(c => (string)c)
                        .ToList();

It returns the same results, but it will perform much better, because e.g. it won't even look for comments within addresses. The bigger the file, the bigger performance gain you get by using that approach!

2. Because it may produce incorrect results:

Using Descendants() may be risky when you're not aware how it really works or your document structure can change in time. Consider situation, when another <Comment> nodes are added into document from previous examples. But they are not item comments. They are added into addresses, e.g. to indicate preferred time of delivery:

<?xml version="1.0"?>
<PurchaseOrder PurchaseOrderNumber="99503" OrderDate="1999-10-20">
  <Address Type="Shipping">
    <Name>Ellen Adams</Name>
    <Street>123 Maple Street</Street>
    <City>Mill Valley</City>
    <State>CA</State>
    <Zip>10999</Zip>
    <Country>USA</Country>
    <Comment>After 5 P.M. only</Comment>
  </Address>
  <Address Type="Billing">
    <Name>Tai Yee</Name>
    <Street>8 Oak Avenue</Street>
    <City>Old Town</City>
    <State>PA</State>
    <Zip>95819</Zip>
    <Country>USA</Country>
  </Address>
  <DeliveryNotes>Please leave packages in shed by driveway.</DeliveryNotes>
  <Items>
    <Item PartNumber="872-AA">
      <ProductName>Lawnmower</ProductName>
      <Quantity>1</Quantity>
      <USPrice>148.95</USPrice>
      <Comment>Confirm this is electric</Comment>
    </Item>
    <Item PartNumber="926-AA">
      <ProductName>Baby Monitor</ProductName>
      <Quantity>2</Quantity>
      <USPrice>39.98</USPrice>
      <ShipDate>1999-05-21</ShipDate>
    </Item>
  </Items>
</PurchaseOrder>

The first query from previous example will not return correct results any more! You really should specify what you're trying to get from XML document as precisely as possible. Using Descendants() is not precise at all here.

And as an opposite: when should Descendants() be used?

1. When querying document with tree-like data:

I think it's the case that Descendants() is design to be used for. File system content XML file is a great example of XML document you should definitely query using Descendants method: 

<Dir Name="Tmp">
  <Dir Name="ConsoleApplication1">
    <Dir Name="bin">
      <Dir Name="Debug">
        <File>
          <Name>ConsoleApplication1.exe</Name>
          <Length>4608</Length>
        </File>
        <File>
          <Name>ConsoleApplication1.pdb</Name>
          <Length>11776</Length>
        </File>
        <File>
          <Name>ConsoleApplication1.vshost.exe</Name>
          <Length>9568</Length>
        </File>
        <File>
          <Name>ConsoleApplication1.vshost.exe.manifest</Name>
          <Length>473</Length>
        </File>
      </Dir>
    </Dir>
    <Dir Name="obj">
      <Dir Name="Debug">
        <Dir Name="TempPE" />
        <File>
          <Name>ConsoleApplication1.csproj.FileListAbsolute.txt</Name>
          <Length>322</Length>
        </File>
        <File>
          <Name>ConsoleApplication1.exe</Name>
          <Length>4608</Length>
        </File>
        <File>
          <Name>ConsoleApplication1.pdb</Name>
          <Length>11776</Length>
        </File>
      </Dir>
    </Dir>
    <Dir Name="Properties">
      <File>
        <Name>AssemblyInfo.cs</Name>
        <Length>1454</Length>
      </File>
    </Dir>
    <File>
      <Name>ConsoleApplication1.csproj</Name>
      <Length>2546</Length>
    </File>
    <File>
      <Name>ConsoleApplication1.sln</Name>
      <Length>937</Length>
    </File>
    <File>
      <Name>ConsoleApplication1.suo</Name>
      <Length>10752</Length>
    </File>
    <File>
      <Name>Program.cs</Name>
      <Length>269</Length>
    </File>
  </Dir>
</Dir>

Looking for all files with cs extension? Nothing easier than that!

var csFiles = doc.Descendants("File")
                 .Select(f => (string)f.Element("Name"))
                 .Where(n => n.EndsWith(".cs"))
                 .ToList();

It would be a pain to get the same results using Elements() method.

To sum up, Descendants() is really powerful tool, and should be used with a great caution. Instead of using it everywhere you should consider changing it to Element()/Elements() calls and leave Descendants() for cases it's really made for.

Do you have any other examples when Descendants should/shouldn't be used? Use comments to give your samples!