Thread Safe Collection Iteration Techniques

Under multithreaded environment every operation should be tested and analyzed from the viewpoint of thread-safety. That is check every data structure what will happen if it is accessed/changed from multiple threads

Imagine, we need to iterate over a collection of items and perform some actions over each item of the collection. Since we're talking about threading - iteration should be done in a thread safe way. That is while we are iterating over collection no other thread is allowed to add or remove items from it.
No problemo! you may think - do the iteration under a lock.

But it is not that simple.

Code sample below illustrates two approaches how to do the iteration. Both have pros and cons. More on that after the code sample.

int initialItems = 5;
ICollection<string> coll = new List<string>(initialItems);

for(int i = 1; i <= initialItems; i++)
 coll.Add("item" + i.ToString());
   
//#1 iterating with lock approach
lock(coll)
{
 foreach(string item in coll)
 {
  PerformWorkWithItem(item);    
 }
}
//

//#2 iteration over a copy 
ICollection<string> copyColl = null;
lock(coll)
{
 copyColl = new List<string>(coll);
}

foreach(string item in copyColl)
{
 PerformWorkWithItem(item);    
}
//    

void PerformWorkWithItem(string item)
{
 //
 // perform operations that can take some 
 // considereable amount of time     
 //
}

Welcome back.

Approach #1 uses global lock for iteration. That means that while iterating collection is protected by the lock.
The pros are:

• simplicity (just put the lock and do the job)
• Memory efficiency - no new object are constructed

The cons are:

• if PerformWorkWithItem takes long time to complete or is blocking (i.e. reading data from the network) access to collection is blocked for considerable amount of time
• action with a collection item is also protected by the lock

Approach #2 uses different technique. It locks access to the collection only to perform a copy (snapshot) of the original collection. Iteration and PerformWorkWithItem action is made over a snapshot and is not protected by the lock.
The pros are:

• Operations on collection items are done without locking the collection. If PerformWorkWithItem takes long time to complete original collection is not locked as in #1
• Allows to schedule actions on collection items using separate thread

The cons are

• If original collection is large enough performing data copy can become inefficient
• Add complexity. While performing actions on snapshot items of the original collection may have been already changed.

Now that we know pros and cons of these two approaches we can deduce some hints that can help choose appropriate technique.

For instance, if PerformWorkWithItem action is relatively fast and there is no problem for the rest of the application to wait for iteration process then approach #1 is the best.

On the other hand if PerformWorkWithItem can take considerable amount of time and other parts of the application frequently access the collection (i.e. it is not desirable to block access to the collection for a long time) then #2 can do.

P.S. There also exists an approach #3. It utilizes lock-free data structures. But it is a whole new story and a topic for separate post.

AesManaged class Key and KeySize properties issue

Today when working with AesManaged class I've encountered very strange behavior.
If you have a code like this - you're in trouble:

AesManaged aes = new AesManaged();
aes.Key = key;
aes.KeySize = key.Length; //the problem

The problem with this code is setting KeySize after setting Key value.
When you set KeySize after Key - the previously specified key is discarded and a brand new key value is generated and put into Key property

I find this behavior rather strange, especially that there is no information describing what will happen after setting KeySize.

I would expect that when Key value is set setting KeySize will throw exception if specified key's size is bigger or smaller than the new one.

The Big Bang Theory sitcom scientific background

Usually I do not write about TV. But the serial in the subject is one of my favorite.

Recently I've found blog of the guy who does scientific background for that sitcom.
There are a lot of interesting scientific facts on that blog in the context of the TV show.

I totally recommend reading it even if you do not watch The Big Bang Theory
The url of the blog is http://thebigblogtheory.wordpress.com/

Refactoring code with lambda expressions

Without much ado lets go straight to the code that needs to be refactored:

bool SomeMethod(long param)
{
   //
   // some prefix code
   //
   try
   {
      //do specific job here
      return DoSpecificJob(param);
   }
   finally
   {
      //
      // some suffix code
      //
   }
}

Result SomeOtherMethod(string name, int count)
{
   //
   // some prefix code
   //
   try
   {
      return DoOtherSpecificJob(name, count);
   }
   finally
   {
      //
      // some suffix code
      //
   }
}

The question is how we can bring prefix and suffix code from the example above in one place (method) without changing code logic.
The goal is to have these two methods rewritten like this:

bool SomeMethod(long param)
{
   return DoSpecificJob(param);
}

Result SomeOtherMethod(string name, int count)
{
   return DoOtherSpecificJob(name, count);
}

While another method will be created that executes prefix and suffix code.

There are several ways how to do that:
1. Create method that contains prefix and suffix code, accepts Delegate object and params object[] array

object ExecuteCommon(Delegate d, params object[] args)
{
   //
   // prefix code
   //
   try { return d.DynamicInvoke(args); }
   finally
   {
      //
      // suffix code
      //
   }
}

bool SomeMethod_First(long param)
{
   Delegate d = new Func<long, bool>((b) => SomeMethod(b));
   return (bool)ExecuteCommon(d, new object[] {param});
}

Result SomeOtherMethod_First(string name, int count)
{
   Delegate d = new Func<string, int, Result>((n, c) => SomeOtherMethod(n, c));
   return (Result)ExecuteCommon(d, new object[] { name, count });
}

The approach looks nice but has several caveats. The problems here are: boxing (wrapping value types into reference types) and casting.
2. Move repeated code up on the call stack
This approach is possible if SomeMethod and SomeOtherMethod are on the same call stack level or called from the same method.

3. Create a generic method that accepts generic delegate and defines several parameters

TResult ExecuteCommon<T1,TResult>(Func<T1, TResult> func, T1 param1)
{
   //
   // some prefix code
   //
   try { return func(param1); }
   finally
   {
      //
      // some suffix code
      //
   }
}

TResult ExecuteCommon<T1, T2, TResult>(Func<T1, T2, TResult> func, T1 param1, T2 param2)
{
   //
   // some prefix code
   //
   try { return func(param1, param2); }
   finally
   {
      //
      // some suffix code
      //
   }
}

bool SomeMethod_Third(long param)
{
   return ExecuteCommon<long, bool>((p) => SomeMethod(param), param);
}

Result SomeOtherMethod_Third(string name, int count)
{
   return ExecuteCommon<string, int, Result>(
      (n, c) => SomeOtherMethod(n, c), name, count);
}

This method does not use casting and there is no boxing present when value type parameters are specified. However, the caveat is that you need to define multiple methods with variable type parameters count. In my opinion the third approach is the best although we have to define two methods that execute prefix/suffix code.

P.S. Another way of refactoring here is code generation: emitting code on the fly or using template tools like T4 templates in Visual Studio.

Mono: C# compiler bug with property inheritance

The bug appeared quite unexpectedly.
In Visual Studio code sample below compiled fine. But doing the same with Mono C# compiler results in error: Compiler Error CS0546: 'Derived2.Accessor.set': cannot override because 'Base.Accessor' does not have an overridable set accessor.
It must've been a bug with the compiler I thought to myself. Mono bugzilla search confirmed that bug was there.

Here is the code sample that produces error report (workaround is described under it):

abstract class Base
    {
        public virtual string Accessor
        {
            get { return "base"; }
            set { }
        }
    }

    class Derived1 : Base
    {
        public override string Accessor
        {
            get { return base.Accessor; }
        }
    }

    class Derived2 : Derived1
    {
        public override string Accessor
        {
            set { }
        }
    }

Workaround for this error is to add set property to Derived1 class:

public override string Accessor
        {
            get { return base.Accessor; }
            set { base.Accessor = value; }
        }

Happy coding :)

MSSQL DATEDIFF Equivalent in MySQL

Recently I was porting T-SQL (MSSQL) code into SQL dialect used by MySQL.
Process went smoothly until I have stuck with dates. Especially intervals between two dates. In T-SQL datediff function is used to get interval between to datetime values.

Let us consider this T-SQL sample:

declare @d1 datetime;
declare @d2 datetime;
set @d1 = '2009-01-18 15:22:01'
set @d2 = '2009-01-19 14:22:01'
select datediff(hour, @d1, @d2) as hour, 
       datediff(day, @d1, @d2) as day,
       datediff(second, @d1, @d2) as second

Query results are:

hour	day	second
23	1	82800

After doing some searching I found out that MySQL equivalent is:

set @d1 = '2009-01-18 15:22:01';
set @d2 = '2009-01-19 14:22:01';
select timestampdiff(hour, @d1, @d2) as hour,
       timestampdiff(day, @d1, @d2) as day,
       timestampdiff(second, @d1, @d2) as second;

Query results are:

hour	day	second
23	0	82800

Query results are nearly the same except day difference. Somehow, MSSQL treats 23 hours as one day.

In general we can think of timestampdiff (MySQL) as 1-to-1 equivalent of datediff (MSSQL). To make them truly equal it is better to get difference in seconds and then convert (calculate) required interval (hours, days).

String Compare Performance in D

A while ago I was measuring performance of string comparison in .NET. Today I played with string type in D programming language and decided to make similar tests.

D is relatively new language with some good perspectives (by the way Andrei Alexandrescu is engaged in D development).

Here is relatively simple code, that I have used to make the tests:

import std.string;
import std.date;
import std.stdio;

string cmp1 = "SomeString";
string cmp2 = "Someotherstring";
auto iters = 100000;

void test_f()
{
    for(int i = 0; i < iters; i++) { auto res = icmp(cmp1, cmp2); }
}

void test_equal()
{
    for(int i = 0; i < iters; i++) { auto res = cmp1 == cmp2; }
}

void main()
{
    ulong[] results;
    int mean1 = 0;
    int mean2 = 0;
 
    for(int i = 0; i < 5; i++)
    {
        results = benchmark!(test_f, test_equal)(1, results);
 mean1 += results[0];
 mean2 += results[1];
 writefln("Test_f: %d", results[0]);
 writefln("Test_equal: %d", results[1]);
    }
 
    mean1 = mean1 / 5;
    mean2 = mean2 / 5;
 
    writefln("Mean Test_f: %d", mean1);
    writefln("Mean Test_equal %d", mean2);
}

Test results where interesting:

Test_f: 21
Test_equal: 2
Test_f: 21
Test_equal: 2
Test_f: 22
Test_equal: 2
Test_f: 14
Test_equal: 1
Test_f: 12
Test_equal: 1
Mean Test_f: 18
Mean Test_equal 1

18 millis for 100000 iterations looks pretty nice. It is faster then .NET string case insensitive ordinal string comparison. If you remember: .NET version completed in about 26 milliseconds. Second test function just compares two values for equality, I assume that mere pointer compare is made.

I have decided to give this relatively new language a try, it is highly possible that there will be more posts about D in this blog :).

Local Computer Connection Failure When Using ActiveSync

Not so long ago I have encountered strange problem with Windows Mobile device connectivity when using ActiveSync.

Here is long story cut short and the solution I came up with.

Server software was located on the Host1. Windows Mobile device was supposed to connect to that server software.

When device was cradled and connected to Host1's ActiveSync it was unable to open connection to server software. However, it could connect perfectly well to the same server software located on Host2. Strange?

It turned out that for local connections (connections to the host where ActiveSync is located) ActiveSync substitutes remote address device wants to connect to with 127.0.0.1. It is loopback address.
Server software was listening on particular IP address (at that time this was by design).
I discovered this by using netstat command and connecting with Windows Mobile browser to local IIS web server.
The command I have used was: netstat -anbp tcp

Obvious fix: listen on 0.0.0.0 (in .NET it is IpAddress.Any).
Any time when connection to local computer from cradled device fails - check if software you are connecting to listens on all IP addresses or is configured to listen on loopback (127.0.0.1) too.

Performance Issues When Comparing .NET Strings

Every time when you want to use string.Compare("str1", "str2", true) for case insensitive string comparison - think twice.

To illustrate my point I am bringing this example:

int iters = 100000;
string cmp1 = "SomeString";
string cmp2 = "Someotherstring";

Stopwatch sw = Stopwatch.StartNew();
for(int i =0 ;i < iters;i++)
{
    int res = string.Compare(cmp1, cmp2, true);
}
sw.Stop();

Console.WriteLine("First:" + sw.ElapsedMilliseconds);
            
sw = Stopwatch.StartNew();

for (int i = 0; i < iters; i++)
{
    int res = string.Compare(cmp1, cmp2, StringComparison.OrdinalIgnoreCase);
}
sw.Stop();

Console.WriteLine("Second:" + sw.ElapsedMilliseconds);

Quick question which method is faster, first or second?

...
...

Here is my result in milliseconds:
First:77
Second:26

Wow, second sample nearly 3 times faster!!!
This is because first method uses culture-specific information to perform comparison, while the second uses ordinal compare method (compares numeric values of each char of the string).

Knowing the above we can deduce general rule of thumb: when culture-specific string comparison is not required we should use second way otherwise first one.

Howto: C++ Class Conversion Operator in .CPP file

In case someone did not know how to do this. It took me some time to figure out the right syntax for writing conversion operator implementation in the CPP file. Here is the definition of the conversion operator.

In a header (.h) file we have TestCase class declared.

class TestCase
{
public:
    operator std::string ();
};

While in .CPP we should have declaration written in the form TestCase::.
The declaration of the "to std::string" conversion operator will look like this

TestCase::operator std::string()
{
   std::string msg("TestCase internals");
   return msg;
}

Now we can use this operator in the code

TestCase testClass;
std::string msg = testClass;

msg variable will be equal to "TestCase internals" string.