by ·4 Comments

Let’s say that you’ve been working hard on this really awesome data structure. Its fast, its space efficient, its immutable, its everything anyone could dream of in a data structure. But you only have time to implement one function for processing the data in your new miracle structure, so what would it be?

Ok, not a terribly realistic scenario, but bare with me here, there is a point to this. The answer to this question, of course, is that you would implement fold. Why you might ask? Because if you have a fold implementation then it is possible to implement just about any other function you want in terms of fold. Don’t believe me? Well, I’ll show you, and in showing you I’ll also demonstrate how finding the right abstraction in a functional language can reduce the size and complexity of your codebase in amazing ways.

Now, to get started, let’s take a look at what exactly the fold function is:

val fold:folder('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

In simple terms it iterates over the items in the structure, and applies a function to each element which in some way processes the element and returns some kind of accumulator. Ok, maybe that didn’t come through quite as simply as I would have hoped. So how about start with a pretty straight-forward example: sum.

 
let sum (list:int list)= List.fold (fun s i -> s + i) 0 list

Here we are folding over a list of integers, but in theory the data structure could be just about anything. Each item in the list gets added to the previous total. The first item is added with the value passed in to the fold, so for items [1;2;3] we start by adding 1 to 0, then 2 to 1, then 3 to 3, the result is 6. We could even get kinda crazy with the point-free style and use the fact that the + operator is a function which takes two arguments, and returns a third…which happens to exactly match our folding function.

let sum (list:int list) = List.fold (+) 0 list

So that’s pretty cool right? Now it seem like you could also very easily create a Max function for your structure by using the built in max operator, or a Min function using the min operator.

let max (list:int list) = List.fold (max) (Int32.MinValue) list 
let min (list:int list) = List.fold (min) (Int32.MaxValue) list

But I did say that you could create any other processing function right? So how about something a little trickier, like Map? It may not be quite as obvious, but the implementation is actually equally simplistic. First let’s take a quick look at the signature of the map function to refresh our memories:

val map: mapping ('T –> 'U) –> list:'T list –> 'U list

So how do we implement that in terms of fold? Again, we’ll use List because its simple enough to see what goes on internally:

let map (mapping:'a -> 'b) (list:'a list) = List.fold (fun l i –> mapping i::l) [] list

Pretty cool right? Use the Cons operator (::) and a mapping function with an initial value of an empty list. So that’s pretty fun, how about another classic like filter? Also, pretty similar

let filter (pred:'a -> bool) (list:'a list) = List.fold (fun l i –> if pred I then i::l else l) [] list

Now we’re on a roll, so how about the choose function (like map, only returns an Option and any None value gets left out)? No problem.

let choose (chooser:'a –> 'b option) (list:'a list) = List.fold (fun l i –> match chooser i with | Some i –> i::l | _ –> l) [] list

Ok, so now how about toMap?

let toMap (list:'a*'b list) = List.fold (fun m (k,v) –> Map.add k v) Map.empty list

And collect (collapsing a list of lists into a single list)?

list collect (list:'a list list) = List.fold (fun l li –> List.fold (fun l' i' –> i'::l') l li) [] list

In this case we’re nesting a fold inside a fold, but it still works. And now, just for fun, list exists, tryFind, findIndex, etc

let exists (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i || b) false list
let tryFind (pred:'a -> bool) (list:'a list) = List.fold (fun o i -> if pred i then Some i else o) None list
let findIndex (pred:'a -> bool) (list:'a list) = List.fold (fun (idx,o) i -> if pred i then (idx + i,Some idx) else (idx + 1,o)) (-1,None) list |> snd |> Option.get
let forall (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i && b) true list
let iter (f:'a -> unit) (list:'a list) = List.fold (fun _ i -> f i) () list
let length (list:'a list) = List.fold (fun c _ -> c + 1) 0 list
let partition (pred:'a -> bool) (list:'a list) = List.fold (fun (t,f) i -> if pred i then i::t,f else t,i::f) ([],[]) list

Its worth pointing out that some of these aren’t the most efficient implementations. For example, exists, tryFind and findIndex ideally would have some short-circuit behavior so that when the item is found the list isn’t traversed any more. And then there are things like rev, sort, etc which could be built in terms of fold, I guess, but the simpler and more efficient implementations would be done using simpler recursive processing. I can’t help but find the simplicity of the fold abstraction very appealing, it makes me ever so slightly giddy (strange, I know).

by ·0 Comments

Tentatively subtitled: “How scale can make fools of us all”

This is going to be a real life war story…cause I haven’t done one of those in a while, and this particular case really ticked me off.  Here’s the scoop:  I’ve got a “service” which is called by other parts of the system.  And by “service” I don’t mean something running in its own process and waiting for SOAP/REST requests or messages, I simply mean something that has a defined entry point (a static method in this case), where you pass in some data, and get something back.

Like many others, I’m sure, I’m using an IoC container to wire up bits so that I can have a big ball of interfaces “to make testing easier” (one of these days I’ll break that rather nasty habit and figure out a better way to do thing, but I’m getting off topic).  Specifically, I’m using Windsor for my dependency injection because it seems to have become the Container de jure among the devs that actually are using containers at work (StructureMap was in there for a while too, but it seems to have faded).  As many of you may know, Windsor is one of those containers that tracks instances for you so that it can use a Lifecycle rule to decide whether to give you an already existing instance of an object, or create a new one for you. It will also automatically call Dispose() on IDisposable objects that it may be tracking, thus helping ensure proper cleanup of resources.

In my case I had everything set up using the Transient lifestyle, because each request was essentially stateless, and there really wasn’t a lot of expense involved in creating a new instance of the objects.  Because I’ve done my homework, I know that if you’re using Transient objects in Windsor, you should explicitly call Release on the container to release the object when you’re done with it, otherwise you’re likely to get a memory leak, since the container would be holding on to an instance of the object, not letting the GC do its thing.  So, I made sure I did that, and my code looked something like this:

var myService = _container.GetService<IMyService>();
try
{
    myService.DoWork();
}
finally
{
    _container.Release(myService);
}

The one thing to point out here, is that my reference to _container was a singleton, so I would get it set up the first time and then use the pre-configured container after that. So, where is the problem? Anyone? Well, I didn’t see anything wrong with it. And neither did the person doing the code review.  But, as you might guess from the fact that I’m writing about this, there was a problem, and here’s how it manifested itself:

Approximately 6 days after this went to production, one particular set of servers in one of our data centers (lets say for the sake of this post we have 2) started kicking out OutOfMemoryExceptions during calls to the service.  My first thought was, “strange, but I’m doing the right thing here and releasing, so its probably just something else eating up memory and my code is suffering”.  To help demonstrate this I even set up a test running 1000 calls to the service in a while loop and watching the memory…nothing unusual, hovered around 33MB.  So I fired up the most excellent dotTrace memory profiler, and it confirmed.

4 more days go by and our operations folks come and beat the crap out of me because they have had to reboot production servers every couple of hours.  Ok, they didn’t beat the crap out of me, but they wanted to, and they did send along a dump, which one of the other devs who is a wiz with windbg was able to translate into something meaningful for me.  The dump showed thread contention in ReaderWriterLockSlim.WaitOnEvent(), and about 200MB worth of an object called Castle.Microkernel.Burden.  And here are some other interesting details:  The service is called by all kinds of different servers; Web servers, SOAP servers, REST servers, but none of these were showing problems.  The only one that was having issues was a server that was set up to process asynchronous SOAP requests (don’t ask).  And each server could process up to 20 at a time.

Armed with this information I did some googling, and discovered that the Burden object is the thing you leak when you don’t call Release() on the container in Windsor….But I was calling release!  I found a blog post by Davy Brion that talked about getting leaks when using your own Windsor container with NServiceBus, and how to deal with it….seemed interesting, but it also seemed like something that didn’t apply, since the problem there was that NServiceBus didn’t know about calling Release() since it was written with a container that didn’t keep references.  It did lead me to the source code for the release policy, which showed me something very interesting.

The Windsor object tracking is basically doing some reference counting.  The ReaderWriterLockSlim is being used to manage the count of instance references, so when you create a new instance it is incremented, and when you release an instance it is decremented.  In either case you’re doing a write, so you’re calling a ForWriting() method on a lock wrapper, which is effectively trying to do a write lock (at some point down the call stack)….very interesting.  At this point I decided to see if I could reproduce the problem, and so I took my earlier test running 1000 calls in a loop, and kicked it up a few notches on the concurrency scale, and set it up to run calls in a while loop until the thread was canceled. I fired up 25 threads to do this, launched the little console app and waited.  Sure enough I was able to see in process monitor that memory was rising….there were some spots where a large collection was taking place, but it wouldn’t release everything, and so soon my little app which started at around 40 MB was using 50 MB, then 60 MB.  It was the concurrency!  The multiple requests were stacking up new instances of object, and new instances of the Burden object faster than they could be collected because the whole thing was bottle-necked by the ReaderWriterLockSlim!

So I plugged in a version of Davy’s code to fix the NServiceBus issue, only I decided since I was managing this container local to my service, and I was also dealing with any Disposables myself, that I would not let it track anything (there is actually a built-in policy object for not tracking anything…just realized that).  Plugged it in, fired up the test, and I had a little console app that ran for about an hour and hovered at about 40MB of memory in use.

We actually did an emergency deployment to push this to the effected set of servers in production, and I’m happy to say that so far I’ve not seen an issue….of course our logs stopped showing the OutOfMemory exceptions about 24 hours before we pushed the fix, so we have that to help out our feeling of doubt that the issue is resolved.  And even though I could create something suspicious locally, we were never able to recreate the production issue in QA.  One of the interesting things about our environment is that we have a lot of customers who do things that we don’t exactly expect, or want, them to do.  It looks like in this case we had some customers who were doing a lot of asynchronous calls and they just managed to stack up in a way where things got ugly.

by ·0 Comments

If you happen to be one of the many people in the unfortunate situation to be stuck working with TFS source control on a daily basis and gaze longingly at the folks using Git or Mercurial wishing you could have some of that distributed goodness for your very own self, I am here to tell you that all is not lost.  There are a couple ways you can work with a distributed version control system along side TFS and try and reduce the pain associated with TFS.  One way I wrote about here as an answer to a question on StackOverflow.  This technique worked fairly well for me dealing with a small codebase with only a few branches.  However, it became unmanageable once I started working in an environment which had a large TFS repo with several different branches that I needed to switch between on a regular basis.  You can read about some of the issues I ran into within the updated section of the answer, but overall things got messy quickly.

The solution I have arrived at, and one which seems to be working out reasonably well so far, is to use Git and git-tfs rather than Mercurial.  This could actually apply equally to Mercurial if such a thing as hg-tfs existed, but alas no such animal can be found.

Quick introduction to git-tfs

The git-tfs project can be found out on Github (of course), and is based on the also very awesome git-svn project.  It takes advantage of the fact that git allows for custom commands by looking for anything on the path that has the form git-<command> and executing it when you type in git <command>.  The project is a C# project that compiles into an EXE named git-tfs.exe.  You drop this in your path and you’re off to the races.

Under the covers git-tfs will tag commits that come from TFS with the repository information and changeset ID, and then when you want to put your changes into TFS (as a shelfset or a commit) it creates a new workspace, adds changes not associated with a changeset from your git repo, and then when it is all done the workspace gets deleted.

Rather than go through the details of getting git-tfs installed and your repository set up I’m going to refer you to the documentation, which is not too bad, and get to the more involved scenario that this post is all about.

TFS Branches and Remotes

If you take a look at the config information on your git-tfs repo you are likely to see a section that looks something like

[tfs-remote "default"]
    url = http://mytfsserver:8080/tfs
    repository = $/TFS/repo
    fetch = refs/remotes/default/master

As you might expect this defines your TFS server and branch information. You can edit your configuration and add as many of these as you want, as long as they have unique fetch paths. The problem is that there really isn’t any documentation that talks about how this works, and so that is what I’m hoping to illuminate. For starters, I’m going to assume you have just the “default” tfs-remote configured.

Working with a new branch

The first thing to do is to create a new remote in your git config.  As you might guess that simply means creating a new tfs-remote section with a unique name.  Lets add something like:

[tfs-remote "release"]
    url = http://mytfsserver:8080/tfs
    repository = $/TFS/release
    fetch = refs/remotes/release/master

This creates a new remote name “release”. The next step is to set up a git branch for this TFS branch. To do that simply create the branch the way you would any git branch:

git checkout -b release

Now comes the good part, we want to pull in the changes from our TFS branch into this git branch.   Git-tfs includes a “pull” command, but it has a fairly big limitation when working in this particular scenario.  It does not allow you to specify a merge strategy.  That means that there is no way to say “pull in everything and use the versions of the files on TFS if there is a conflict”, which is what we want to do.  To accomplish this, we’ll want to deconstruct the “pull” command into it’s discrete steps.  The first step is to do a get-tfs fetch against the new remote.  You do that using this command:

git tfs fetch -i release

This will pull in all of the changesets from the TFS branch and apply them to the object tree that sits under the covers in git. Once that is done we’ll want to merge those changes into our git branch by doing:

git merge -X theirs refs/remotes/tfs/release

You can actually specify whichever merge strategy you want, but this is the one I generally choose (merge recursive, take the remote changes for any conflicts). Pay special attention to where we are merging from. This is the remote location that points to the HEAD of the commit tree that we just pulled from TFS. The general format of this is: refs/remotes/tfs/<tfs-remote name> Once you have done the initial fetch/merge you will have better luck using the get-tfs pull command, though you can still run into merge conflicts if there are a lot of changes between pulls.

The way I have been working, and a way that seems to work well, is to have a primary branch that mirrors each of your TFS branches that you may be working in, with topic branches created from there. That gives you at least one git branch for every TFS branch that is “pure”, and that you can potentially mess up without feeling too bad, since you can always fetch everything from TFS again (this assumes you have some time to kill, since fetching a lot of changes from TFS takes a while).

By the way, when you’re working with multiple TFS branches in git-tfs, the –i <remote-name> switch will become your constant companion.  You will need to use it on any command which may have an ambiguous parent….meaning when git-tfs goes through you’re history to find out which TFS remote to use, it’s going to look at those git-tfs-id tags on the commits, and if there is more than one source it will ask you which one you want.  When you have several branches you’ve created that represent different TFS branches, you are most likely going to have the history of the original branch lurking somewhere, so you will be needing the switch.

 

Committing your work back to TFS

Now that you have branches in git you can work with, you can use whatever topic-branching strategy makes sense when your doing your day-to-day work.  Once you are ready to commit things back to TFS, the simplest way to do that is to check your changes into git, and then issue a git-tfs check-in command (There are three, “checkin”, ‘”rcheckin” and “ct”.  I personally like the “ct” command, which brings up the TFS dialog that lists changes and allows you to specify commit messages).  When you do this, git-tfs will look through your commit history, and find the last commit with a git-tfs-id tag, and then take every commit from that point and apply it to a workspace that it creates behind the scenes. Once you check-in git-tfs then does a pull/merge from TFS (to get any changes since your last fetch), and leaves your branch with your commit on top.

Notice I said that it goes through the commit history, and looks for the first commit with a git-tfs-id tag?  This is important if your working in a scenario where you have a reasonably large change you’re working on, and you are doing periodic tfs fetches and merges into your topic branch to keep up to date with what your colleges are doing. 

Lets say you’ve been working on something for 5 hours, doing periodic commits as your go, and one of your teammates tells you they’ve made a change to one of the common libraries that you are using.  At this point you’ll want to switch back to your TFS tracking branch, get the latest changes, and them merge those in to your working branch.  Doing this, though, means that git-tfs is not going to see the changes you made over the last 5 hours.  So what do you do?

You remember that you’re using git :).  Lets continue with our scenario and say you work for another two hours and complete your feature making commits along the way.  Now, you’re ready to check in to TFS.  What I’ve found works best for me is to go back to my TFS tracking branch, make sure it’s up to date, and then create a new branch for my pending check-in.  Then I do a merge into the new branch from the topic branch I had been working in, and throw a –squash on there (this is not strictly necessary, but in my environment it’s handy to have a change in a single changeset that is associated with a single change request, that way roll-back is easier).  Once the merge is done, I can issue my git tfs ct –i release command and all is good.  I’ve got all of my changes in a nice neat little package.

Another option available is to use the git-tfs rcheckin command, which essentially does a rebase against your TFS branch.  I’ve actually not done this, since it doesn’t fit in with how changes are handled in my organization.

What about Shelf-Sets?

I’m glad you asked.  We actually use shelf-sets for code-reviews (which are required before code goes to production).  Fortunately git-tfs has nice support for shelfsets. For starters un-shelving changes puts them in a topic branch, which is exactly what I would hope for.  To do this use the following command:

git tfs unshelve -i <remote> [-u <username>] <shelfset name> <branch>

(Just a quick note, the master branch of the git-tfs github repo does not contain support for the –I argument at this point.  I’ve got a pull-request in place to add it, since it was just a one-liner.  You can track it here if you need to.  You can also grab my fork of the git-tfs project here (there is a branch called UnshelveTweak that has the change) Looks like the pull request has been merged into the main git-tfs project.  If you clone/fork and do a build you should be good to go)

Hopefully this is pretty self-explanatory. The -u option is not required if your pulling from one of your own shelfsets. If you’re shelfset has a name with spaces in it, you should surround it with double quotes.

Shelving changes is equally easy, you just issue the shelve command:

git tfs shelve -i <remote> <shelfset name>

Again, if you’ve got a shelfset name with spaces be sure to put quotes around it.

 

A few more tips

I’ve found on occasion that things get a little out of whack when shelving or committing changes back to TFS, and some files are included that shouldn’t be.  This usually happens when things are not merged 100% after a git tfs fetch, and there are some files that need to be committed separately.  So how do you deal with this?  Well, you rely on our friend the get-tfs-id tag.  The simplest process is to do a git log to see your list of changes, and copy the line that starts with git-tfs-id:. Then, if you’ve not committed your changes yet, add that to a new line at the end of your commit message. If you have committed you can use the git commit --amend command to update the last commit. Once you’ve done this you will only get new changes checked in or shelved to TFS

Another useful bit of kit is a script I whipped together that sets up a git bash shell with all of the .Net/Visual Studio 2010 tools on the path, so I can build my projects from within the git-tfs bash shell. The script looks like (I’m running a 64-bit OS, so you may need to adjust the paths):

@echo off
call "C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat" x86
"C:\Program Files (x86)\Git\bin\sh.exe" --login -i

I use the most excellent Console2 project, so I can just save that script to a .bat or .cmd file and add a new tab that has that file as the shell.  Now I can see which branch I’m working in while on the command line, and still build everything.

So there you have it.  It’s not 100% hassle free, but it is a lot less hassle than dealing with TFS all of the time.  I probably save several hours a week simply by not needing to wait on TFS fetches and branch changes.

by ·0 Comments

I ran into this odd problem recently working with some Linq2SQL based persistence code.  There is some code someone put together to commit a list of changed entities to the database as part of a single transaction, which simply iterates through the list and performs the appropriate action.  The problem I was having was that I had an object referenced by another object that needed to be persisted first, otherwise there was a foreign key violation.  To add to the strangeness there seemed to be some magic going on (most likely utilizing the INotifyPropertyChanged goodness), so that even if I tried to persist just my dependent object first, both were still showing up in the list, and always in exactly the wrong order.  Now, I’m okay with magic.  Magic makes a lot of things a lot easier.  The problem arises whenever the magic is incomplete, and doesn’t follow through to take care of all of the operation.  Its like someone comming up to you and saying “Pick A Card”, at which point you do, and put the card back, and they say “I know what your card was” and walking away.  Not real convincing.  This is what was going on here.  There was the smarts to know that changes were being made to more than one entity, and there were even attributes to define what properties contained dependent objects, but no smarts to actually deal with a case when you would want to save more than one object in an object graph at a time.

So it occued to me I should be able to do some linqy magic and create some sort of iterator that would return dependent objects in the appropriate order, so the lest dependent of the objects get move to the beginning of the list.  My first step, since I wasn’t really sure how to do this, was to write a test.  And I made it more or less mirror the issue I was facing, a list of two items, one of which is a dependency of the other.  I don’t know if there is a lot of value in posting all of the test cases here, but the end result was rather nice.  Sure it took several iterations, and there was plenty of infinite looping and stack overflows (which does some fun things to studio when your running your tests with TestDriven.Net), but I think this is a reasonable solution to the problem:

public static IEnumerable<T> EnsureDependenciesFirst<T>(this IEnumerable<T> items, Func<T ,IEnumerable> selector)
{
    if(items.Count() < 2)
        return;
    var firstPass = items.SkipWhile(t => items.Intersect(selector(t)).Count() > 0);
    var remainingItems = items.Except(firstPass);
    if(items.Count() == remainingItems.Count())
        return remainingItems;
    return firstPass.Concat(remainingItems.EnsureDependenciesFirst(selector));
}

Ok, so what do we have here?  Well to start out I’m checking the item list to see if there are at least two items in it, if not I just return the list.  This provides a means to avoid an infinate loop due to the recursive call, and provides a shortcut for a scenario with only one item.  Next off I use the SkipWhile() method, combined with the user-supplied selector function to iterate through each item, retrieve it’s list of dependencies (which is what the selector function does), and checks to see if the current list contains any of the dependencies for the object.  The results of this first pass are the objects which have no dependencies at all, so therefore they need to be first in the list.  The next logical step is to run the operation again for a list that does not contains the items filtered out by the first pass.  This is done via a recursive call back to the EnsureDependenciesFirst extension.  You will notice we’re checking the count of the remaining items against the current list, and returning the list if they are the same.  This is another safety precaution for dealing with infinite loops.  If we have a circular dependency, this bit will just return the items that are interdependent.

You will note that this is a generic function that has really noting at all to do with the entities that I am dealing with.  This was largely due to the fact that this was built TDD, so I just used a simple class which had a property that could take another instance of itself.  To use this to overcome my entity committing problem, I would have to write a not too small function to retrieve the list of dependent objects from the entity (since there would need to be some reflection magic to look at attributes on the properties to determine which properties contain dependencies), but it pretty much will drop in to the foreach statement that is currently being used to persist the entities.

Incidently, I learned from my dev team what the “official” way of dealing with this is a “ReorderChanges” method, which takes two entities, in the order in which they should be persisted.  I think I like my solution better, mostly because it should mean I don’t have to worry about it again.