Tonight, I was writing some code that made use of transactional WCF bindings. I wanted to do some experimentation with all the bindings available to see which ones support flowing transactions. The pre-built bindings that do this will create a TransactionFlowBindingElement when you ask them to call CreateBindingElements(). The types I’m interested are concrete (no abstract methods) and have a zero-argument constructor. A few years ago, I would have done a bunch of looping constructs to look at each element. However, I’ve been doing a lot more work with F#. While doing this experiment in C# for a project, I wound up writing the following instead:

static void Main(string[] args)
{
    var bindings = from bindingType in typeof (MessageContractAttribute).
                       Assembly.GetTypes()
                   where typeof (Binding).IsAssignableFrom(bindingType) &&
                   !bindingType.IsAbstract &&
                   (from constructorInfo in bindingType.GetConstructors()
                           where constructorInfo.GetParameters().Length == 0
                           select constructorInfo).Count() > 0
                   select bindingType;

    var txBindings = from bindingType in bindings
                     where
                         (from bindingElement in
                              ((Binding) Activator.CreateInstance(
                                bindingType)).CreateBindingElements()
                          where bindingElement.GetType() ==
                            typeof (TransactionFlowBindingElement)
                          select bindingElement).Count() > 0
                     select bindingType;
    foreach (var txBinding in txBindings)
        Console.WriteLine(txBinding.FullName);
}

I would’ve loved a Seq.iter for the last 2 lines of the function. I think this is a good reason to learn F# or another functional language. It’ll change how you write code elsewhere. I’m not saying that this code is more readable, but it is interesting.

So, what does the code write out as the transaction supporting bindings?

System.ServiceModel.NetTcpBinding

System.ServiceModel.NetTcpContextBinding

System.ServiceModel.WSHttpBinding

System.ServiceModel.WSHttpContextBinding

System.ServiceModel.NetNamedPipeBinding

System.ServiceModel.WSFederationHttpBinding

System.ServiceModel.WS2007FederationHttpBinding

System.ServiceModel.WS2007HttpBinding

System.ServiceModel.WSDualHttpBinding

There is a problem on the Euler project, www.projecteuler.net, which asks to find the sum of all values under a given number. Problems on the Euler project have a range of solutions, where at least one solution has a runtime of under 1 minute. A popular, time efficient algorithm that finds all primes in a given range is the Sieve of Eratosthenes. The basic algorithm is:

1. Create an array that contains all values from 2 up to the final maximum value
2. Starting at 2, For each value in the array, mark all items that have indices of the current value that are multiples and NOT equivalent to the current index as 0 (eg. index mod [current value] == 0).
3. March forward until you hit a non-zero value in the array, then mark all multiples as 0.
4. Halt condition: stop when you cross the midpoint of the array (anything remaining that is non-zero is a prime since you already all multiples of 2).

In practice, this gives successive iterations of an array from 2 .. 10 as:

1. [2, 3, 4, 5, 6, 7, 8, 9, 10]
2. [2, 3, 0, 5, 0, 7, 0, 9, 0]
3. [2, 3, 0, 5, 0, 7, 0, 0, 0]
4. At this point, we reach 5, which is greater than the length of the array (9) divided by 2 (4.5). Any non-zero values in the array are prime.

In C#, one possible implementation is:

private static long SieveOfErastosthenes(long maxvalue)
{
    long[] values = new long[maxvalue];
    // Populate the list for (long i = 0; i < values.LongLength; ++i)
    {
        values[i] = i;
    }
    values[0] = 0;
    values[1] = 0;
    for (long i = 2; i < values.LongLength; ++i)
    {
        if (values[i] != 0)
        {
            for (long j = i * 2; j < values.LongLength; j += i)
            {
                values[j] = 0;
            }
        }
    }

    long retval = 0;
    foreach (long k in values)
    {
        retval += k;
    }
    return retval;
}

Overall computational complexity is O(n). If you aren’t familiar with big O notation, the overall complexity is bound by the size of the dataset times a constant-in this case 3, since we iterate through the complete dataset 3 times:

1. Populate the dataset
2. Mark all non primes as 0
3. Sum the primes

And yes, this works quite well, even for large values of n. My challenge was to get the sieve to work with performance equal to C#, only in F#. At the start of this, I had my first pass of the C# code running in ~600 ms for a value of 5 million. The challenge I set for myself was to achieve a similar timing in F#. The first few passes left me with runtimes of over 15 minutes (I killed the runs prior to completion). The reason why was simple: I wrote an O(n^3) algorithm. My challenge was to get this faster without using mutable values. My first pass looked like this:

let rec sieveofErastosthenes values filterout maxval =
    if (filterout >= (maxval/2)) then values
    else let shouldFilter =
            try let a = values |> List.find(fun x -> x = filterout)
                a <> 0 with | _ as ex -> false if (shouldFilter) then sieveofErastosthenes (values
                |> List.filter(fun x -> (x = filterout) || ((x % filterout) <> 0))) (filterout + 1) maxval
        else sieveofErastosthenes values (values |> List.find(fun x -> x > filterout)) maxval

let max = 5000000let sumofprimes =  sieveofErastosthenes [2 .. max] 2 max |> List.map( fun x -> int64 x) |> List.sum

This code is correct-pass in 10 for the max and the value returned is 17. But the answer just never returned for larger values within reasonable time. Next, I tried using a mutable type: System.Collections.Generic.List<T>. This got the time down to a measureable 4s. That’s still 6.5x longer than the C# version. That next attempt looks like this:

let sieveOfEratosthenes x =
    let retval = new List<int32>()
    retval.AddRange([0 .. x])
    retval.Item(0) <- 0 retval.Item(1) <- 0 for i in 2 .. x do if retval.Item(i) <> 0 then for j in 2 * i .. i .. x do retval.Item(j) <- 0 retval.ToArray()

let max = 5000000let sumofprimes =  sieveOfEratosthenes max |> Seq.map( fun x -> int64 x) |> Seq.sum
printfn "%An" sumofprimes

Notice that this latest iteration executes a lot less code and, frankly, looks pretty close to the C# code. Through some investigation, I found that the call to preload the array consumed 2.6 s. I then switched to a sequence and shrank the execution time to 2300 ms. I was closing in on my goal and learning some stuff about the performance of various F# constructs. Loading using a sequence changed the AddRange call to this:

retval.AddRange([|0 .. x|])

The reason this takes less time is simple. When allocating a List, F# allocates and initializes all values up front. The Seq is created with an iterator and only allocates enough space to store the iterator and not much else. So far, so good. At this point, I did a search on F# implementations of the Sieve of Eratosthenes and found that Chris Smith had one. His implementation keeps track of which numbers AREN’T prime. Performance on his algorithm hits 8600 ms. That wound up being a step in the wrong direction.

Next, I tried, explicitly initializing the list of integers and cut the time down to 1450 ms. The strategy was getting me closer to optimal timing and showed that, for 5 million int32s, I was filling in the list in 46 ms.

let sieveOfEratosthenes x =
    let retval = new List<int32>(x + 1)
    for i in 0 .. x do retval.Add(i)

    retval.Item(0) <- 0 retval.Item(1) <- 0 for i in 2 .. x do if retval.Item(i) <> 0 then for j in 2 * i .. i .. x do retval.Item(j) <- 0 retval |> Seq.filter(fun x -> x <> 0)

This was better, but I’d like to get closer to the C# version. The last thing I tried was moving to Array from System.Collections.Generic.List. This last change cut 250 ms, bringing my times down to 1200 ms. It looks like using lighter weight objects really will speed things up! That version is:

let sieveOfEratosthenes x =
    let retval = Array.zeroCreate(x + 1)
    for i in 0 .. x do retval.[i] <- i
    retval.[0] <- 0 retval.[1] <- 0 for i in 2 .. x do if (i % 2 <> 0) && retval.[i] <> 0 then for j in 2 * i .. i .. x do retval.[j] <- 0 retval |> Seq.filter(fun x -> x <> 0)

let max = 5000000let sumofprimes =  sieveOfEratosthenes max |> Seq.map( fun x -> int64 x) |> Seq.sum

Today I was reading an article in The Onion, Conquerors You May Have Missed,  and noticed that the number for the ant looked like it might be a big old prime, or at least have a large prime divisor. (For reference, the ant is # 43,168,974,563,247.) There are a number of algorithms for finding this answer, but my favorite is a little brute force algorithm that keeps dividing the big number by some other value until the two numbers are equal. Yes, I know I can short circuit a bunch of testing via a square root function, but BigInteger doesn’t have a sqrt function (yet.).

Anyhow, I cobbled this together and it worked right out of the gate:

let rec largestFactor x y =
    if (x = y) then y
    else
        let z = x % y
        if z = 0I then largestFactor (x/y) y
        else largestFactor x (y + 1I)

let LargestPrime x = largestFactor x 2I

let a = LargestPrime 43168974563247I

printf "%A" a

Answer: 84,826,177

So, the number isn’t prime, but the largest prime factor is pretty big! And, writing up the code to figure out the answer itself was pretty simple.

I was unusually quiet over the last couple of weeks. Why? My former host apparently packed too many sites on one machine and caused this page to experience OutOfMemoryExceptions galore. I run a number of sites for various purposes and decided it was time to move up to a VM host. I’m currently on MaximumASP and am using a MaxV server. Setup was pretty simple, support was helpful for a few of my questions, and I’m happy to have my blog engine up and running again.

I want to say thanks to everyone who came out to watch me speak about OpenSocial at the Chicago Alt.NET meeting. Thanks for inviting me to present and for making the time so enjoyable. I’ve posted the slides and the code for the Canvas page here.

This month, I’ll be speaking at the Chicago Alt.Net user group meeting. Please check out the details here and register here. And, here is the blurb on the talk:

November 2009 Meeting

Building OpenSocial Applications

6:00 pm
Pizza and networking time

6:30 pm

From its official web site:

Friends are fun, but they’re only on some websites. OpenSocial helps these sites share their social data with the web. Applications that use the OpenSocial APIs can be embedded within a social network itself, or access a site’s social data from anywhere on the web.

OpenSocial is the platform that MySpace, Orkut, Ning, LinkedIn, Hi5, and pretty much every social network but Facebook supports for creating games and other applications that run on these social network sites.

In this talk, we focus on the MySpace platform and how one builds a MySpace application. This involves interacting with the OpenSocial JavaScript as well as receiving and sending OpenSocial requests on your own servers.

I want to send out a big thank you to the team who put together the Iowa Code Camp. You people did an awesome job!!! I had a great time giving my talks and really enjoyed hanging out with the crowd in Iowa.

For those of you who attended my talks, or just want to see the materials, I’ve posted things.

WCF Diagnostics Talk and Materials

WinDBG Talk and Materials

See you next year.

On December 7, I’ll be speaking at the nPlus1 ArcSummit for the optional morning session. I’d love to see the place packed! Here are the details:

https://www.clicktoattend.com/invitation.aspx?code=142763

About nPlus1.org

nPlus1.org is a site dedicated to helping Architects, aspiring Architects and Lead Developers learn, connect and contribute. On this site you’ll have access to great first party content written by some of the most skilled and experienced Architects working today. You’ll also have access to, and be able to contribute to a nexus of content from around the Internet aimed at keeping Architects up to date on all the new developments in their fields of interest.

When

Monday December 7, 2009 – 10:00PM to 5:00PM

Where

Microsoft MTC – Aon Center

200 E. Randolph

Suite 200

Chicago, IL 60601

driving directions

Free Lunch Provided

Agenda

Morning Session (Optional): An Introduction to Object Oriented Programming

10:00 AM – 12:00 PM

Are you new to OOP? Do you want a refresher on the benefits of Interfaces and the differences between implements and extends? The morning session is a two hour introductory course of Object Oriented Programming. If you are new to OOP the lessons in this session will prepare you for the more advanced topics in the afternoon.

If you are already well versed in OOP then feel free to come have a refresher, or simply join us for lunch and the advanced sessions in the afternoon. The morning session is completely optional.

Afternoon sessions:

Session One: Software Patterns

Patterns are an important tool to use as architects and developers. They provide a common vocabulary for us to design with, as well as a common approach to a common problem. Come learn about useful patterns, and how to use them in your everyday code.

Session Two: How I Learned To Love Dependency Injection

Dependency Injection is one of those scary topics that most developers avoid. It sounds all ‘high-falootin’ and complex. It’s not. Really. We wouldn’t lie. It’s a great way to manage complexity in your system, and a great way to make your system so much more testable. And isn’t that what we all want?

Each session will be followed by open discussions periods.

A catered lunch will be provided starting at noon. This will divide the morning introductory sessions from the advanced sessions. Register once for all session and choose to attend the morning, the afternoon or both! Lunch is provided for attendees for any of the sessions.

A long time ago, I was a C++ developer. I actually thought of myself as a pretty darn good C++ developer and got way too excited when I finally got to meet folks like Scott Meyers and actually landed a job working with Bobby Schmidt-same team on MSDN. (If you know Bobby’s name, well, you were pretty deep into C++ circa 1999.) Then, like many C++ devs, I moved over to a garbage collected language. I’ve done more than my fair share of professional .NET and Java development. C++ has been left by the wayside. Today, I finally downloaded and installed Visual Studio 2010 Beta 2. I dug into the “What’s New” and, out of curiosity, decided to look at C++ first (I already know about many of the C# and VB changes). I saw two cool things:

1. C++ now has an auto keyword. For you C# devs, it is pretty much the same as the C# var keyword.

2. C++ has lambdas.

Now, I’m only a little ways into understanding C++ lambdas, so some of my information here may be suspect. The C++ lambda is just an anonymous function. You can pass variables into the function so that the variable is visible within the function. The syntax is:

[ list of variables from current scope to pass into lambda scope ] return-type( function signature ) { code }

The canonical example appears to be std::for_each from <algorithm>.

In this example, I have two values: number and numSquared. I make references of the value visible to the lambda, which prints out each value as it comes through and then sums the numbers and their squares. Once the function completes, the code emits the values to the console window. If you don’t want to pass anything to the lambda, you still need to state this. If I didn’t want number or numSquared visible, the lambda signature would be:

At some point, I’ll dig in and see what else this is good for, including how to build my own Functor signatures. Anyhow, just thought I’d share this little nugget with you.

My article on programming REST services with F# and WCF went up at InformIT. Please go read it! http://www.informit.com/articles/article.aspx?p=1394625