Casting and Type vs. Set theory

A few days ago I saw an awesome movie where Brian Beckaman talks about monads on channel9:

In this movie he explains that one can reason about “Types” just like a “Set”

Brian never goes into deeper details about this in the movie, so this post will deal with my own thought on this matter only.
So don’t hold him responsible for anything crazy that I might write :-)

I found this topic quite interesting, I have never thought about it this way, but it does makes perfect sense.

e.g. Imagine the Type “Byte”, it represents an integer number from 0 to 255.
And thus, all the valid forms of a byte would fit in a set with 256 elements.

The type “Int32” also represents an integer number, but with a larger precision.
But it still models the exact same concept, the concept of an integer value.
Every valid form of an Int32 will also fit into a set, however much larger than the byte set.

Since both types models the same concept, but with different precision, the smaller set can be seen as a subset of the larger set.
That is; the byte set is a sub set of the Int32 set.

Type set diagram:
One intereting thing that this brings to the table, is that it allows us to reason about type casts.
e.g. Since the byte set is a subset of Int32, we can know that any element found in the byte set, will also exist in the Int32 set.
So we can assume that we can pick any element from a bag of Bytes and put it into a bag of Int32s.

And this is exactly what we can do when we write programs (at least in most languages), we can make an implicit type cast from byte to Int32.
Simply because bytes belongs to a subset of Int32, even though the byte is not a sub type of Int32.

The inheritance graph for these types looks quite different than the Set diagram:


The types that represent integer values in the inheritance diagram shows that they do not have a parent / child relation.
They are unrelated except for shared base of ValueType, but you can still do implicit casts from one type to another when the source type belongs to a subset of the destination type.

This is quite obvious facts when dealing with integers, and I guess that most developers already knew when it is possible to do implicit casts from one type to another.
But if we ignore the über obvious for a second and think about what this can be used for:

This does allow us to reason about our OWN types, when and where it makes sense to allow implicit or explicit casts and not.

I have never really had any good approach for this before, I pretty much only threw in implicit cast operators here and there without much thought.
But by thinking of types as sets, it is easy to see if your custom types are a sub/super set of another type, and then allow implicit or explicit casting based on that.
And it might even show you that your types are not overlapping sets at all, and in such case you might want to create transformer / factory methods instead of allowing any type of casting.

e.g. a type that is a string representation of a week day might look like should allow implicit casts to string.
But since they model different concepts; weekday vs. string, those sets are not overlapping.
And thus, you should not allow any sort of casting, but rather supply a “WeekDay.Parse” method or something similar.

While if you were to invent your own Nullable of T type, you could easily see that any instance of T would also fit into the set of Nullable T.
And thus you should allow implicit casts from T to Nullable of T.

Well, that’s all..
I hope this wasn’t far too crazy :-)


Good cop, Bad cop, Stylecop?

So what do I mean with this title?

….I have no clue at all  ;-)

Anyway, a few days ago Andreas Håkansson told me to check out MS StyleCop.
StyleCop is a tool that ensures that you follow a certain code standard, such as naming conventions and general code structure.

Andreas also directed me to a nice Resharper plugin on CodePlex:

This plug in allows you to see the StyleCop warnings directly in your code.

Confident that I was writing at least somewhat decent code, I thought; “OK, I wonder if StyleCop will find any problems with my code?”

And yes, apparently it could do that..


It was a bit depressing to see how badly my code sucked, but I still decided to make my code conform to the standard that MS uses.
Most of the problems in there are quite easy to fix, but even if they are easy to fix, its a pain to add things like “this.” in front of all class members in an entire code base.

Luckily, I found this blog post today: 
Jordan Dimitrov at Telerik shows how to make a Resharper settings file that enables Resharper to format code the way StyleCop wants.

So by using these tools together, you can now use the Resharper “Cleanup code” and format the entire code base to be almost StyleCop compatible.
There are a few things that you still need to do manually, e.g. add comments and add parenthesis for operator priority inside expressions.

So if you own a Resharper 4.1 license, I think you should try these tools together, it’s an awesome way to get a code base that completely follows a style guideline.
Both StyleCop and the add in are free.


Where do you find the best developers?

I’ve always been fascinated with the different schools of software development.
Some make games, some make 3D tools, some make web portal development and some do software for fighter jets etc.

So, in what branch of software development do you think we find the absolutely brightest developers?

I think the bloggosphere might contribute to some sort of blindness in this area, we only notice those who make the most noise, usually the consultant / trainer type of guys.
At the top of this hierarchy are the “senior software architect” guys, they blog about domain models using O/R mappers and how to create nice web pages using MVC pattern and that type of things.

Ooh, so you want an WCF service in the middle? and Hibernate at the bottom?
And maybe some domain specific language for configuring your favorite dependency injection framework?

Spice that up with some talks about unit tests and friction less development and you will be king of the hill in this sphere.

No offence to any of those guys, but how hard is that stuff really?
Just to be clear; I have no delusions of knowing everything or being better than anyone in this area, there are of course really tough problems here too.

But what about those developers that write software for fighter jets?
Or write games like World of Warcraft where you have to deal with thousands and thousands of concurrent users interacting at a very high transaction rate.
Or maybe those who write 3D tools that are able to reduce the polygon count in a highres 3D mesh.

That is some seriously hardcore stuff.
I feel like some soon to go extinct cave man when I think about how those things work.

So what branch of software development holds the best and the brightest?

I thought I knew C#

I honestly thought I had a pretty fair grasp on C# for the last few years.

But apparently there are features that I haven’t known about.

The first one is covariance on arrays in C#

string[] strings = new[]{"Hello","Covariance"};

//assign the string array to an object array
object[] objects = strings; 

objects[0] = "Hi"; //OK
objects[1] = 123; //runtime exception

I know that true covariance and contravariance will come in C# 4.

But I really didn’t know it was already implemented for arrays, I found this out maybe two months ago.

Also note the last line, we got dynamic type checks in C# , ewwww ;-)

Another feature I didn’t know about is this:

this = new Foo();

Think I’m kidding with you?

Assignments to “this” ??

This is actually possible inside structs, which makes sense when you think about it, since you only overwrite the memory for the struct.

But I honestly didn’t know this was possible until I saw the Tuple struct in MEF a few days ago.

Maybe this is common knowledge, but if someone had told me that you could assign values to “this” in C# before I saw that, I would have slapped him.


Scaling Clustered Evolution: 1 + 1 = 4

This is a follow up on:

Yesterday I got the chance to test run the cluster version of EvoLisa on a 64 bit 4 core machine.
(Thanks to my collegue Ulf Axelsson for the help on this one)

The results from the cluster version are quite interesting.
One could expect that you would get a maximum of 200% performance by using two nodes instead of one.
However, this is not the case, we are getting 400% performance by doing this.

Doubling the CPU capacity and get 4 times as much work done.

How is this possible?

This really confused me for a while.
But the reason is quite obvious once you figure it out.

Let’s assume the following:

* We use one core.
* We are running 1000 generations with 50 polygons over 10 seconds.
* 1 out of 10 mutations are positive.

This gives us approx 100 positive mutations over 10 seconds.

If we add one more core we would get:

* We use two cores in parallel.
* We are running a total of 2000 generations, with 50 polygons per node over 10 seconds.
* 1 out of 10 mutations are positive.

This would give us approx 200 positive mutations over 10 seconds. 
Thus, this would give the expected 200% performance.


We are NOT rendering 50 polygons per core in this case.
Each core is only rendering 25 polygons each.

During those 10 seconds, we are actually able to run 2000 generations instead of 1000 per core, thus, running a total of 4000 generations over 10 sec.
Which in turn results in approx 400 positive mutations during the same time span.

We have doubled the CPU capacity and halved the work that needs to be done per node.
Thus, we get a * 2 * 2 perf boost.

Pretty slick :-)

The 4 core machine was able to render the Mona Lisa image with the same quality as the last image in the evolution series in: 1 min 34 sec!


Clustering Evolution – We have lift-off

After some horrible failures trying to cluster EvoLisa, I finally succeeded!
(And some creds goes out to Fredrik Hendeberg on this solution too)

All of my other attempts failed because of the overhead in the communication.
I was trying to synchronize things too often, simply because I didn’t see how it would be possible to solve the original Mona Lisa problem w/o doing so.

The key to successful clustering is to communicate as little as possible and run jobs in isolation as much as possible.

And this is what I’ve done now.
Each node gets ” 50 / NodeCount ” polygons.
If I have 2 nodes, they get 25 each.

So how do I get those two nodes to paint one and the same image with their 25 polygons each?

The solution is quite simple;
Each node runs in isolation for e.g. 1000 generations.
Then they pass their own DNA over to all the other nodes.
The receiving nodes then construct a “foreground image” and a “background image” based on the DNA from the sending nodes, depending on their ordinal/rank/index in the cluster.
Once that process is complete, each node goes back to running another 1000 generations, but now using the static fore and background while rendering.


So each node is sort of rendering the entire image, but where all the polygons except for its own are static for X generations.

This works because the longer the simulation runs, the less changes there are to all the polygons.
So each node can fine-tune it’s own polygons together with the static fore and background since we know that the fore and background will not change that much until the next sync.

There will be a bit of a ping-pong effect in the beginning before all of the polygons on all the nodes start to make sense together.
But that doesn’t matter because it is only for a short period before everything start to stabilize.

So we are actually co-evolving one organism per node, where all of the organisms needs to harmonize with each other in order to get a good fitness level.
There is a sort of symbiosis going on now.

As a result of this, the new algorithm is no longer “greedy” and can in some cases result in a worse fitness level than the previous X generations, but the positive effect by far out-weights this.

The effect was quite dramatic on my 2 core laptop.
With a single core, it takes about 12-20 minutes to reach the fitness level that I use for my tests (The same fitness level as the last image as the original Mona Lisa evolution series).

With two cores, I reach the same fitness in 3-5 minutes.
That’s a pretty nice speedup.

The performance gain is actually more than 100%, and my best guess is that the OS is eating some of the power of the first core, the one that is used when running in single core mode.

Now I just need to find a multi core computer to see how it works on more than two cores.