Multi-threaded UDFs – Technology, Locking, Race conditions and Deadlocks

One of the major disadvantages of VBA (and VB6) UDFs is that they cannot be multi-threaded. And since everyone now has PCs with multiple cores and Excel 2007 or Excel 2010 (well except for my better half Jane who is currently struggling with a rather ancient laptop) this is starting to be a problem for us Excel speed freaks/geeks.

Thats one of the reasons why I decided to rewrite my next generation of fast UDFs as C++ XLLs.
I am using XLL+ Version 7 and VS 2010: using these tools to make a UDF multithreaded is easy: just tick the multi-threaded option and away you go.

I am now about 6 months into learning how to write these C++ UDFs things and its mostly going OK. Of course there are minor hiccups along the way: like when it took me half a day to figure out why this numeric parameter always arrived in the UDF as 1 regardless of whatever value was passed in! (If you really want to know its because Excel and the Oper data structure don’t really know about integers: they insist on thinking they are primitive booleans. I knew that happened on output – always use doubles – but stupidly had not considered that it would also happen on input …).

Anyway I have now written most of my simple functions: they all work OK and calculate fast, so obviously its now time to get overconfident and go for a real challenge.

Multi-threaded UDFs sharing a global resource.

One of the tricks involved in writing faster Lookup and Matches is to be able to store the row number in the input range where the answer was found and use it the next time the Lookup or Match is executed. This technique is fast with unsorted data.

For unthreaded UDFs this is conceptually straightforward: just store the row number in a global container of some kind. But for multithreaded UDFs its not so simple because you can have multiple instances of the UDF being executed on different threads and all trying to update or read the container at the same time – a definite no-no for multi-threading. The answer is to be able to set a lock on the global container.

After a lot of Googling I decided to use a shared lock from the Boost library and either a Map container from the Standard Template Library (STL), or an unordered Map from Boost. (Both of these libraries contain an enormous framework of containers and algorithms and other excellent stuff). The shared lock allows only 1 thread to update but multiple threads to read.

There were a few glitches getting VS2010 to acknowledge the Boost libraries, but once I had figured that out it all works and seems quite efficient (half a million updates and half a million reads in about 1 second using 8 cores). The unordered Map using integer keys is fastest.

The next thing to get my head around is how to handle multiple global containers at the same time. Simples! I thought, you just have a separate Lock for each container. But I suspect this could lead to the dreaded “race condition”  “deadlock” where one thread holds one lock and is waiting for another lock, and another thread holds that lock and is waiting for the first thread: the corresponding image is 2 meerkats chasing each other’s tails.
(Mike Woodhouse points out that a “race condition” is having 2 threads trying to update the same thing at the same time.)

Time for a cold towel wrapped round my head, swiftly followed by a large glass of Central Otago Pinot Noir (fantastic stuff).


Having slept on it I think I need a timeout on the locks as well (I wondered why there was a timeout parameter on the shared lock). The problem is that even if all MY udfs depend on a single lock the user could be using someone elses UDFs at the same time that could have their own lock:


  • MyXLL creates MyLockUDF and OtherXLL creates OtherLockUDF
  • Formula1 =MyLockUDF()+OtherLockUDF()
  • Formula2 =OtherLockUDF()+MyLockUDF()
  • Formula1 and Formula2 are on separate threads being calculated at the same time

then there could be a deadlock.

This entry was posted in UDF, Wine, XLL. Bookmark the permalink.

8 Responses to Multi-threaded UDFs – Technology, Locking, Race conditions and Deadlocks

  1. mikewoodhouse says:

    I think the particular nastiness described is actually a “deadlock” – a race condition is … er … well this seems to explain:

  2. jeff Weir says:

    Glad you enjoy our Pinot from up there as much as I enjoy your blog from down here! Suggest you also try Epic Lager or TuaTara the next time you’ve got time on your hands while Excel is recalculating.
    Jeff Weir, Wellington, New Zealand.

    • fastexcel says:

      When we were in Wellington we had a great meal at Monsoon Poon (accompanied by some NZ Pinot of course)

      • Jeff Weir says:

        What brought you down here (apart from an airplane)? Heading back our way?

      • fastexcel says:

        Damon Longworth organised a 3 day XL conference in Sydney 2008 and Dick Kusleika & I were speakers. So I extended the trip to NZ , Melbourne and western australia. It was great – we (Jane & I) will definitely be back sometime in the next few years …

  3. jeff Weir says:

    Speaking of our Pinot, you might guffaw at this:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s