Evaluate Functions and Formulas fun: How to make Excel’s Evaluate method twice as fast

Prompted by a comment from Sam on Match vs Find I thought I would take a look at Excel’s rather quirky Evaluate method with Excel 2010 to see how it performed.

The Evaluate method internally uses Excel’s formula parser and calculator, and this makes it surprisingly powerful. You can use it on virtually any kind of formula, range reference or Defined Name. But, as we will see, it does have a number of strange “quirks” that you have to navigate around.

Depending on the context Evaluate will either return an object (for example a Range) or values.

I will be using exactly the same test setup of 100000 rows of randomly generated XY pairs and timing routine as in Match vs Find, so you can directly compare the results.

Using the square brackets [ ] shortcut for Evaluate

Sam’s comment suggested using [COUNTIFS] to see how the timing compared with MATCH and FIND. Of course its not quite the same thing because the loop on Match and Find allows the VBA to do something for each XY pair found. Sam’s VBA looks like this:

Sub FindXY_COUNTIFS1()
Dim j As Long
Dim dTime As Double
dTime = Microtimer
j = [COUNTIFS(A1:A100000,"x",B1:B100000,"y")]
Debug.Print "COUNTIFS1 " & j & " " & (Microtimer - dTime) * 1000
End Sub

It takes 11.6 millisecs to find the 25135 XY pairs generated using a constant of 0.5 in the test data generator.

[ ] is a shortcut for Application.Evaluate. The advantage of using the [ ] brackets is that it is concise and the formula inside the [ ] is exactly the same as when used in a worksheet cell. The disadvantage is that you cannot generate the formula as a string. I tend to only use this notation when evaluating my hidden workbook-scoped defined names, because they are not likely to change. (Of course sometimes I get lazy …)

Using Application.Evaluate instead of [ ]

You can use Evaluate or Application.Evaluate with a string instead of the [ ]

j = Evaluate("COUNTIFS(A1:A100000," & Chr(34) & "x" & Chr(34) & ",B1:B100000," & Chr(34) & "y" & Chr(34) & ")")
The timing is virtually identical to the [ ] shortcut method.

Application.Evaluate and the Activesheet

One trap for the unwary with [ ] , Evaluate and Application.Evaluate is that all references that do not contain a worksheet (unqualified references like A1:A100000) are assumed to refer to whatever the Active sheet currently happens to be.
So if you are going to use Application.Evaluate you should always use a qualified reference (Sheet1!A1:A100000) unless you like your code to live dangerously.

Worksheet.Evaluate

Worksheets and Charts also have an Evaluate Method. When you use these methods unqualified references are assumed to refer to the worksheet or chart.

Sub FindXY_COUNTIFS3()
Dim j As Long
Dim dTime As Double
dTime = Microtimer
j = Worksheets("Sheet1").Evaluate("COUNTIFS(A1:A100000," & Chr(34) & "x" & Chr(34) & ",B1:B100000," & Chr(34) & "y" & Chr(34) & ")")
Debug.Print "COUNTIFS3 " & j & " " & (Microtimer - dTime) * 1000
End Sub

Now for the surprise: Worksheet.Evaluate is twice as fast as Application.Evaluate!
(actually 6.1 millisecs as opposed to 11.6 millisecs)

I am fairly sure that there is a bug in Application.Evaluate that actually does the evaluation twice.
Certainly if you use Application.evaluate on a UDF the UDF will be executed twice.

Chart.Evaluate

In the real world I have never actually used Chart.Evaluate (probably because I hate programming Chart objects), but according to Help it seems you can do interesting things with it:

“Chart Objects. You can specify any chart object name, such as “Legend”, “Plot Area”, or “Series 1″, to access the properties and methods of that object. For example, Charts("Chart1").Evaluate("Legend").Font.Name returns the name of the font used in the legend.”

Evaluating Array Formulas

Amazingly if you give Evaluate an array formula it evaluates it as an array formula:

Sub FindXY_COUNTIFS4()
Dim j As Long
Dim dTime As Double
dTime = Microtimer
j = ActiveSheet.Evaluate("SUM((A1:A100000=" & Chr(34) & "x" & Chr(34) & ")*(B1:B100000=" & Chr(34) & "y" & Chr(34) & "))")
Debug.Print "COUNTIFS4 " & j & " " & (Microtimer - dTime) * 1000
End Sub

This is quite a lot slower than COUNTIFS: it takes nearly 19 milliseconds.
If you are a SUMPRODUCT fan you could use

j = ActiveSheet.Evaluate("SUMPRODUCT(--(A1:A100000=" & Chr(34) & "x" & Chr(34) & "),--(B1:B100000=" & Chr(34) & "y" & Chr(34) & "))")
But its not significantly faster.

Evaluate speed compared to a formula in a cell

You would expect Evaluate to be slower than Excel natively calculating the formula in a cell. And indeed it is, but its quite close for a single formula;

Countifs Formula 6.0
Evaluate Countifs 6.1

Array Sum Formula 16.9
Evaluate Array Sum 18.9

Evaluate speed compared to using Application.Worksheetfunction

It looks like there is a higher overhead to using Evaluate, which is what you would expect.
Here is a version of the FindXY sub using Evaluate with MATCH instead of Worksheetfunction.Match.

Sub FindXYEval()
Dim oRng As Range
Dim oLastRng As Range
Dim j As Long
Dim jRow As Long
Dim n As Long
Dim Rw As Long
Dim dTime As Double
dTime = Microtimer
Set oRng = Range("a1:A100000")
Set oLastRng = oRng(oRng.Rows.Count)
Rw = oLastRng.Row
On Error GoTo finish
With Application.WorksheetFunction
Do
Set oRng = Range(oRng(j + 1), oLastRng) '<<< Rw
End With
finish:
Debug.Print "MatchEval " & n & " " & (Microtimer - dTime) * 1000
End Sub

This takes 3720 milliseconds compared to 478 milliseconds using Worksheetfunction.Match. There are just over 50000 calls to Evaluate or Match so I reckon the additional overhead of using Evaluate is about 65 Microseconds per call.

More Evaluate Limitations: Updated

• The string being evaluated must be less than 256 characters, even in Excel 2010.
• A1 style references can be evaluated in both A1 and R1C1 reference mode (Application.ReferenceStyle), but R1C1 style references can only be evaluated in R1C1 mode.
• Relative references in the string are treated as absolute, unless they are contained in defined names in which case the defined name is evaluated with respect to cell A1.
• Dates should be in USA format (Month-Day-Year).
• Evaluate will return an error value if the string formulae contains external references to closed workbooks or XLM functions.
• Using Evaluate INDEX(rng,rownum,COLUMN()) gives incorrect answers except for the first column. Evaluate 0+INDEX(rng,rownum,COLUMN()) works
• If the string formula contains a reference to both a UDF and a name it will fail with an error 2029 if the name reference occurs AFTER the UDF reference:

• If fred is a named range and xyz() is a user defined VBA function then this statement returns error 2029: application.Evaluate(“=xyz(b1)+fred”)
• This statement returns the correct value: application.Evaluate(“=fred+xyz(b1)”)
• Microsoft KB article 823604 identifies this problem but does not correctly diagnose the circumstances that cause it.

You can bypass many of these limitations (at the cost of performance) by inserting the formula string into a worksheet cell and then reading the resulting cell value back into a VBA variable.

Error Handling

If Evalaute cannot evaluate the formula string it returns an error rather than raising an error, so the result of Evaluate should always be assigned to a Variant.

Conclusion

• The Evaluate method adds a lot of power to VBA
• Always use Worksheet.Evaluate rather than Application.Evaluate: its twice as fast and less error-prone
• Using Worksheet.Evaluate has comparable speed to a cell formula but a higher overhead
• Worksheetfunction has a lower overhead than Evaluate
• Beware the Quirks of Evaluate!

So whats your experience of Evaluate?

MATCH vs FIND vs Variant Array VBA Performance Shootout in Excel 2010

When searching unsorted data in VBA I have always tended to use MATCH rather than FIND, mainly because early versions of Excel before Excel 2003 did not allow you to use FIND in UDFs.

But prompted by a discussion in one of the Excel forums I thought it was about time I revisited Find and Match to see which performs better in Excel 2010, and for good measure lets compare them to getting the data into a variant array and looping through the array.

Generating Test Data

Andreas Killer came up with a nice routine for generating test data:

Sub Init()
Dim Data(1 To 100000, 1 To 2)
Dim i As Long
Rnd -5
For i = 1 To UBound(Data)
If Rnd > 0.5 Then Data(i, 1) = "X"
If Rnd > 0.5 Then Data(i, 2) = "Y"
Next
Cells.ClearContents
Range("A1").Resize(UBound(Data), UBound(Data, 2)) = Data
End Sub

This code randomly generates X in column 1 and Y in column 2 in a range of 100 thousand rows, with the number of Xs and Ys controlled by the constant 0.5
Changing the 0.5 to 0.9 will give few Xs and Ys, and changing it to 0.001 will give lots.

Since the X and the Y are using different random numbers there will be rows with X but no Y and Y but no X, as well as rows with both X and Y.

This makes it easy to test how the various methods compare with different densities of data.

Timing

I am using the MicroTimer high-resolution timer API to give timing accuracy at the microsecond (millionths of a second) level, but the timing results will all be in milliseconds.

#If VBA7 Then
Private Declare PtrSafe Function getFrequency Lib "kernel32" Alias _
"QueryPerformanceFrequency" (cyFrequency As Currency) As Long
Private Declare PtrSafe Function getTickCount Lib "kernel32" Alias _
"QueryPerformanceCounter" (cyTickCount As Currency) As Long
#Else
Private Declare Function getFrequency Lib "kernel32" Alias _
"QueryPerformanceFrequency" (cyFrequency As Currency) As Long
Private Declare Function getTickCount Lib "kernel32" Alias _
"QueryPerformanceCounter" (cyTickCount As Currency) As Long
#End If
Public Function MicroTimer() As Double
'
' returns seconds
' uses Windows API calls to the high resolution timer
'
Dim cyTicks1 As Currency
Dim cyTicks2 As Currency
Static cyFrequency As Currency
'
MicroTimer = 0
'
' get frequency
'
If cyFrequency = 0 Then getFrequency cyFrequency
'
' get ticks
'
getTickCount cyTicks1
getTickCount cyTicks2
If cyTicks2 < cyTicks1 Then cyTicks2 = cyTicks1
'
' calc seconds
'
If cyFrequency Then MicroTimer = cyTicks2 / cyFrequency
End Function

The code uses conditional compilation for the Windows API calls so that it will work for both Excel 2010 32-bit and 64-bit Excel.

Using FIND

Here is the test code using Range.Find

Sub FindXY1()
Dim oRng As Range
Dim n As Long
Dim dTime As Double
Dim FirstAddress As String
dTime = MicroTimer
'
With Range("a1:A100000")
Set oRng = .Find("X", , xlValues, , , xlNext, False)
If Not oRng Is Nothing Then
FirstAddress = oRng.Address
If oRng.Offset(0, 1) = "Y" Then n = n + 1
Do
Set oRng = .FindNext(oRng)
If Not oRng Is Nothing Then
If oRng.Offset(0, 1) = "Y" And oRng.Address <> FirstAddress Then
n = n + 1
End If
End If
Loop While Not oRng Is Nothing And oRng.Address <> FirstAddress
End If
End With
'
Debug.Print "Find " & n & " " & (MicroTimer - dTime) * 1000
End Sub

The Sub does a Range.Find on the 100 thousand rows looking for X, and then checks if column 2 for that cell also contains Y.
Then this is repeated using FindNext until we have looped back to the first range address.
When completed the number of rows with both X and Y (this is less than the number of times an X was found) and the time in milliseconds is shown in the Immmediate window.

Using Match

Here is the code using WorksheetFunction.MATCH

Sub FindXY2()
Dim oRng As Range
Dim j As Long
Dim n As Long
Dim dTime As Double
dTime = MicroTimer
Set oRng = Range("a1:A100000")
On Error GoTo Finish
With Application.WorksheetFunction
Do
j = .Match("X", oRng, 0)
If oRng(j, 2).Value2 = "Y" Then n = n + 1
Set oRng = oRng.Resize(oRng.Rows.Count - j, 1).Offset(j, 0)
Loop
End With
Finish:
Debug.Print "Match " & n & " " & (MicroTimer - dTime) * 1000
End Sub

This Sub works by using Worksheetfunction.Match to find the first occurrence of X within the Range object oRng.
After each X is found oRng is resized to exclude the range already searched.

The loop terminates either when nothing is found (Worksheetfunction.Match raises an error)  or the Resize fails, also raising an error.

Using a Variant Array

Sub FindXY3()
Dim vArr As Variant
Dim j As Long
Dim n As Long
Dim dTime As Double
dTime = MicroTimer
vArr = Range("a1:B100000").Value2
For j = LBound(vArr) To UBound(vArr)
If vArr(j, 1) = "X" Then
If vArr(j, 2) = "Y" Then
n = n + 1
End If
End If
Next j
Debug.Print "Var array " & n & " " & (MicroTimer - dTime) * 1000
End Sub

The code gets the Range into a Variant, creating a 2-dimensional array, and then loops down the array looking for X and Y.

Timing Results

I ran each sub 4 times using different densities of data.

The first is with a single XY pair at row number 100000. This tests the scanning speed per row rather than the calling overhead.

Then I used the Test data generator with constant values of 0.9, 0.5 and 0.001.

Here are the results giving timings in Milliseconds with counts of the XY pairs:

 
 
 
 
 

And here are the ratios of the times:

 
 
 
 
 

• You can see that Find is significantly slower than Match or using a Variant array, regardless of the number of XY pairs found.
• The timings for Match increase fast with the number of XY pairs, whereas the Variant array increases much more slowly.
• This is because there is a much higher overhead for each call to Match than looping from row to row of the array.
• For small numbers of XY pairs Match is faster than the Variant array.

Conclusions

• Don’t use Range.Find unless you want to search a large number of columns for the same thing (you would have to do a Match for each column).
• The Variant array approach is surprisingly effective, particularly when you expect a large number of hits.
• Match wins easily for a small number of hits.

OK, so who is going to admit to using Range.Find?

Writing efficient VBA UDFs (Part 6) – Faster string handling and Byte arrays

None of  the previous posts on writing efficient VBA UDfs (Part1,Part2,Part3,Part4,Part5) talked about handling strings in VBA.
This could be a major omission since string-handling is one of VBAs slowest “features”.

Suppose you want to find the position of the first capital letter in a string.

Array Formula

You could use an array formula like this:

{=MATCH(TRUE,ISERR(FIND(MID(A5,ROW($1:$255),1),
LOWER(A5))),0)}

My test data is 2000 rows, each containing 25 lower-case characters and one randomly placed upper-case character.

2000 calls to this array formula takes 250 milliseconds.

So lets try some VBA UDFs.

Using LIKE

One way is to use the VBA LIKE statement:

Function FirstCap2(Cell As Range)
For FirstCap2 = 1 To Len(Cell.Value)
If Mid(Cell.Value, FirstCap2, 1) Like "[A-Z]" Then
Exit For
End If
Next FirstCap2
End Function

The code loops across the string using Mid to look at each character in turn, and then uses LIKE to see if the character is one of upper-case A to upper-case Z.
2000 calls to this UDF takes 50 milliseconds – a factor of 5 faster, but we can make it faster (of course).


Function FirstCap3(Rng As Range) As Long
Dim theString As String
theString = Rng.Value2
For FirstCap3 = 1 To Len(theString)
If Mid$(theString, FirstCap3, 1) Like "[A-Z]" Then
Exit For
End If
Next FirstCap3
End Function

I changed the code to only get the string out of the cell once, and to use Mid$ rather than Mid. All the VBA string handling functions have 2 versions: versions without the $ work with variant arguments, whereas versions with the $ suffix only work on string arguments, but are slightly faster.
2000 calls to this version of the UDF takes 17 milliseconds, nearly 3 times faster.

Using MID$

But maybe using LIKE is slow? Lets try comparing a lower-case version of the string and stopping when the characters don’t match:

Function FirstCap4(strInp As String) As Long
Dim tmp As String
Dim i As Long
Dim pos As Long
tmp = LCase$(strInp)
pos = -1
For i = 1 To Len(tmp)
If Mid$(tmp, i, 1) <> Mid$(strInp, i, 1) Then
pos = i
Exit For
End If
Next
FirstCap4 = pos
End Function

Well surprisingly this is slower than the optimised version using LIKE:
2000 calls to this version of the UDF takes 36 milliseconds.

Using Byte Arrays

Using Byte arrays with strings is one of VBAs less well known secrets, but its often an efficient way of handling strings when you need to inspect each character in turn.


Public Function FirstCap5(theRange As Range) As Long
Dim aByte() As Byte
Dim j As Long
FirstCap5 = -1
aByte = theRange.Value2
For j = 0 To UBound(aByte, 1) Step 2
If aByte(j) < 91 Then
If aByte(j) > 64 Then
FirstCap5 = (j + 2) / 2
Exit For
End If
End If
Next j
End Function

This version of the UDF is slightly faster: 2000 calls takes 15 milliseconds.

So how does this work?

First create an undimensioned array of Bytes : Dim aByte() as Byte
Then assign a string to it: aByte=”abEfg”
You can use the Locals window to see what the resulting Byte array looks like:

Each character in the string has resulted in 2 bytes which are the Unicode code points for the character. Since I am working in a UK English Locale using the Windows Latin-1 codepage the first byte is the ANSI number for the character and the second byte is always zero.

Unaccented english upper-case characters are ANSI numbers 65 to 90, so I can loop down the byte array, looking at every other byte, and do a numeric test directly on the character to see if it is upper-case. You can see that only the third character is upper-case.

Another surprising feature of  this kind of Byte array is that you can assign a byte array directly back to a string:

Dim str1 as string
str1=aByte


Str1 now contains “abEfg”

Array version of the Byte UDF

As discussed in Part 5 of writing efficient UDFs, Array Formulae go faster. So here is an array formula version of the Byte UDF.

Public Function AFirstCap(theRange As Range) As Variant
Dim aByte() As Byte
Dim j As Long
Dim L As Long
Dim vRange As Variant
Dim jAnsa() As Long
Dim NumCells As Long
vRange = theRange.Value2
NumCells = UBound(vRange, 1)
ReDim jAnsa(NumCells - 1, 0)
For L = 0 To NumCells - 1
jAnsa(L, 0) = -1
aByte = vRange(L + 1, 1)
For j = 0 To UBound(aByte, 1) Step 2
If aByte(j) < 91 Then
If aByte(j) > 64 Then
jAnsa(L, 0) = (j + 2) / 2
Exit For
End If
End If
Next j
Next L
AFirstCap = jAnsa
End Function


This version, entered into 2000 rows as an array formula using Control/Shift/Enter, takes just 4.8 milliseconds.

Conclusion

Here is a table comparing the speed of these different approaches.

Method	Milliseconds
Array Formula	250
LIKE UDF	50
Optimised LIKE UDF	17
MID$ UDF	36
Byte Array UDF	15
Array Formula version of Byte Array UDF	4.8

So the fastest VBA is just over 10 times faster than the slowest VBA solution, and a whopping 52 times faster than the array formula solution.

Using Byte arrays for strings can be a good solution for string handling where you need to inspect or manipulate many individual characters.

So what do you use Byte arrays for?


Does MATCH handle mixed alphabetic and numeric data when sorted?

I was doing some testing on my new XLL advanced LOOKUP and MATCH functions, comparing them to MATCH when I came across some quirks (actually I think some of them are bugs).

Mixed Characters and Numbers

So suppose we have data in M3:M8, consisting of 3 numbers and 3 alphabetic characters.
The data is sorted ascending and there are no duplicates.
Note that the characters are all sorted higher than the numbers: thats the standard result with SORT.
Using MATCH with the sorted ascending option to lookup each element in the data in turn: you can see the results in column O:
so far so good – it all looks correct.

But what happens if you try looking up values that don’t exist in the data?

Since we have told MATCH that the data is sorted ascending it will use approximate match and should return the position of the largest value that is less than or equal to the lookup value.

So we can try using a set of lookup values, none of which exist in the data, which range from 0.5 (smaller than the first value in the table) through 3.5 (larger than the largest numeric value) and from a to e for the alphabetic values.

The first value 0.5 returns #N/A because there is no value in the lookup table that is smaller than or equal to 0.5.
The next value is 1.5 which lies between the first and second value so MATCH returns 1.
Now look at 3.5. since text is sorted as being larger than numbers it comes between 3 and b in the lookup table, so MATCH correctly returns 3.

Next up is a: this should also come between the 3 and the b in the lookup table, so should return 3: but it returns #N/A instead (a definite FAIL!) Similarly aa fails, but b through d work correctly.

Next up is trying larger values: dd and e are both larger than the largest value (d) in the data, so MATCH says that the largest value that is less than or equal to them is the last value.
Looking up a large number (99999) returns 3 because any text value is sorted as larger than all numbers.

Mixed Numbers and Textual Numbers

So if that does not always workl, what happens if you data contains numbers and numbers which are textual representations of numbers. (You can usually see these because they are by default left-adjusted and the numbers are right-adjusted).

When you sort this kind of data Excel asks you if you want to treat numbers that look like text as numbers.

Column F (Data 2)  is sorted this way and column D (Data 1) is sorted numbers and text separately.

So the first check is to lookup the values in the table using themselves: we should get a nice sequence from 1 to 20.
That works OK when the data is sorted numbers and text separately, but fails for the value 10 when textual numbers are sorted as numbers.

If you use lookup values as numbers from 0.5 to 10.5 incrementing by 1, you get correct answers on both tables.

But if you use lookup values entered as text by entering them as ’5.5 you get different answers to entering the numbers and then formatting them as text!

In the same way as above, column H is looking up Data 1 and column I is looking up Data 2.

Lots of weird answers: I can’t work out what Excel thinks its doing!

Conclusion

I suppose if you were extremely careful you could make this work most of the time, But for me its another good reason to avoid mixing data types within a column of a table.

Of course if all you want is an exact match you can use the unsorted option, which I think works OK because its only ever looking for equality rather than less than/greater than.

Is ‘Can of Worms’ the right description?

False Volatility – Is this a bug?

There was an interesting discussion here about using Application.Volatile False in a VBA UDF.

It seems that if you create a VBA UDF like this one:

Function functest2(x As Double) As Double
Application.Volatile (False)
Dim Z As Double
Z = x + 2
functest2 = Z
End Function

and call it from a cell when x refers to another cell that contains a volatile function or has a precedent cell with a volatile function, then the function is not recalculated when the volatile precedent cell changes because of a recalc. But of course it should!

If you change the function by either:

• Changing x as double to x as variant
• Removing the Application Volatile False statement

then the function is recalculated as expected. It also works as expected if the precedent cell is not volatile, or is changed, or a full calculation (ctrl-alt-F9) is done.

I have to admit that I had never seen the point of using Application.Volatile False since thats supposed to be what you get if you omit the Application.Volatile statement altogether. But this unexpected behaviour started me digging.

In the old XLM Macro language it turns out there was a use for Volatile False. If you created an XLM UDF using ARGUMENT(8) to make the argument remain as a reference rather than be coerced to a value the UDF was made Volatile, so you could use Volatile False if you did not want this behaviour.

Also (and probably more relevant) in a similar way when creating XLL functions if you register the function as a macro-equivalent function by adding a # to the end of the registration type string, and you are using type R or U arguments (reference) then the function will be made volatile, (the usual way is to add ! to the end of the type string). And in a similar way to the XLM macros you can use the C API function xlfVolatile to switch this volatility to False.
If you have not flagged the XLL UDF as a macro-equivalent function then using xlfVolatile has no effect
Macro-equivalent XLL functions can be useful because they have increased permissions compared to normal UDFs:

• They can get the previous value of an uncalculated cell
• They can use information functions that ordinary functions cannot

But these macro-equivalent XLL functions using R or U with Volatile set to False also do not recalculate when they have a volatile precedent.

It seems to me that this is definitely a bug with the VBA UDF, and that there is no reason to use Application.Volatile False with VBA (maybe unless you want to have a conditionally volatile function?).

With an XLL function (and an XLM function) at least there is a use for Volatile False, but the XLL behaviour with Volatile precedents also looks buggy to me.

So what do you think? Bug or by design?

Can you see another use for explicitly setting Volatile to False?

Anyone want to see if the same bug exists with an XLM function?

For more information on Volatile Functions and Actions see my Volatility page.

Developing Faster Lookups – Part 3 – A Binary Search UDF – Updated

In part 1 and part 2 of Developing Faster Lookups I sidestepped the question of whether its faster to use your own VBA Binary Search routine than to use Excel’s Worksheet Functions.

In this post I will look at 2 Binary Search UDFs. Both UDFs are the equivalent of MATCH with sorted ascending data, except that when there are multiple identical values that could be the answer:

• MATCH returns the LAST of the identical values
• BSearchFirstV and BSearchFirstR return the FIRST of the identical values

Binary search works by looking at the midpoint of the range of lookup values and comparing it to the value being looked up.
If the lookup value is less than the midpoint then the upper half of the range is discarded and Binary search looks at the midpoint of the lower half of the range. So on each successive iteration half the data gets discarded. This makes the Binary Search algorithm extremely efficient with anything more than 10-20 rows of data.

To find the first of multiple sorted matches we want to find the consecutive pair of values where the first is less than the lookupvalue and the second is >= the lookupvalue.

When the pair has been found we have to check whether its the first value we want or the second. And then we have to handle the boundary conditions:

• The lookup value is less than the first value in the lookup table
• The lookup value is equal to the first value in the lookup table
• The lookup value is greater then the last value in the lookup table

The algorithm is very simple and concise, but surprisingly difficult to program correctly. Many variations exist and its often useful to create your own variation  for particular circumstances.

I have coded 2 variations: (these are revised versions – the first versions I posted had bugs!)

BSearchFirstR only works when you pass the LookupTable as a Range. BSearchFirstV is designed to work withe the LookupTable being passed as a 2-Dimensional 1 column N rows variant array (although if you give it a Range it converts it to a variant array anyway).

Here is the code:


Option Explicit
Option Base 1
'
' COPYRIGHT © DECISION MODELS LIMITED 2006, 2007, 2011. All rights reserved
' May be redistributed for free but
' may not be sold without the author's explicit permission.
'
Public Function BSearchFirstR(LookupValue As Variant, LookupArray As Range) As Variant
'
' find the position of the largest value in LookupArray 1
middle = (low + high) \ 2
varMiddle = .Cells(middle, 1).Value2
If varMiddle >= LookupValue Then
high = middle
Else
low = middle
End If
Loop
If (low > 0 And high LookupValue Then
BSearchFirstR = low
Else
BSearchFirstR = high
End If
ElseIf low = 0 Then
If .Cells(1, 1).Value2 BSearchFirstR = 1
End If
End If
End With
End Function
Public Function BSearchFirstV(LookupValue As Variant, LookupArray As Variant) As Variant
'
' find the position of the largest value in LookupArray 1
middle = (low + high) \ 2
varMiddle = LookupArray(middle, 1)
If varMiddle >= LookupValue Then
high = middle
Else
low = middle
End If
Loop
If (low > 0 And high LookupValue Then
BSearchFirstV = low
Else
BSearchFirstV = high
End If
ElseIf low = 0 Then
If LookupArray(1, 1).Value2 BSearchFirstV = 1
End If
End If
End Function

Notes:

• Most error checking has been omitted to simplify the code
• There is no checking for uncalculated cells
• There is no allowance for whole-column references or ranges containing empty cells.
• The UDFs assume the data is sorted ascending
• The UDFs do not allow for wild-card text matching

Timing Results

• BSearchFirst V is faster than BSearchFirstR when the Lookup Table contains less than about 500 rows.
• For large ranges BSearchFirstR is considerable faster because the whole of the Lookup Table data is not transferred to VBA.
• Both variations are slower than using approximate MATCH, but are faster than using Linear Search (unsorted) MATCH to find the first exact match for large ranges, and are faster than Array formulae for finding the first of multiple matches

Conclusion

Using  a VBA coded Binary Search routine will not improve the speed of the FLOOKUP UDF.

However when you want a variation of MATCH that is not in the built-in Excel MATCH VBA Binary Search is a useful tool.

Developing Faster Lookups – Part 2 – How to build a faster VBA Lookup

In part 1 I looked at some of the difficulties with making efficient use of Excel’s built-in Lookup and Match functions:

• Lookups are often recalculated unecessarily even when all data actually relevant to the Lookup is unchanged.
• Binary Search Lookup requires a double lookup to handle missing data
• Linear Search requires either a double lookup or IFERROR to handle the #N/A from missing data
• Excel’s Lookup and Match functions are not designed to handle multiple results
• Whole-column arguments are handled well as long as the used-range is OK

An ideal Lookup/Match function would handle these problems and also

• Allow Named column headers as well as numbers
• Allow more than one column as the Lookup Value
• Allow alternative sets of Lookup Values
• VLOOKUP would handle both ascending and descending sorted data

And of course it has to be faster than Excel’s functions in most circumstances!
What I finally developed was the AVLOOKUP/AMATCH/AVLOOKUPS/AMATCHS series of UDFs in FastExcel Version2
This post describes the design approach and shows some sample code from these UDFs.

The Design Approach

Solution for No Relevant Data Changed

The solution I chose was to store the row number in the TableRange where the answer was last found, and then before doing the actual lookup check whether that row number still gives the right answer. If it does then short-circuit the UDF by returning the answer, else go do the full lookup.

There is a small problem with this approach in that a VBA UDF is not supposed to be able to alter anything except by returning values to its calling cells, so how do you store the Row number? The solution I chose is to to use the Range.ID property for the calling cell. This works well (althought it only persists for the duration of the Excel workbook session).

The great thing about this approach is that it is fail-safe and avoids having to handle some tricky situations: if there are 2 UDF calls using this technique within a formula the first call will get the row number stored by the second call, decide that this gives the wrong answer and then do the full lookup to get the right answer.

Binary Search with Missing Data

Part 1 showed how to make this work by making a lookup lookup itself to see if it has found an approximate or an exact match. So you need to have 2 arguments for the function (Data_Is_Sorted and Do_Exact_Match) instead of just one (Data_Is_Sorted). Then if the data is sorted and an Exact Match is requested the UDF can do the Binary Search exact match trick.

Handling the #N/A from Missing Data

This also requires another optional parameter for the UDF, giving the Value to return if an exact match has been requested but not found (defaults to #N/A).

Optimizing Data Transfer

To minimise data transfer time if the Lookup_Table is a range then the UDF keeps it as a range and passes the range object to Application.WorksheetFunction.MATCH, instead of transferring all the data to a Variant array and then either searching that using VBA or passing the variant array to MATCH. If the input is a calculated range or array constant rather than a Range then the UDF passes that directly to MATCH.
When checking if the stored row number gives the right answer the UDF does need to get a value, but it only gets a single cell.

Handling Whole Column arguments

Because the UDF is passing Range Objects rather than Variant arrays to Excel worksheet functions it does not really need to bother about this. In other cases the trick would be to use Application.Intersect(UsedRange,InpurRange).

Handling Multiple Results & Alternative sets of Lookup Values

This is handled by writing the UDF so that it loops on the inputs and lookups and returns an array of results rather than a single value.

Named Column Headers

If the Answer Column parameter is passed as a string then the UDF searches for it in the first row of the data, but if its passed as a number then that is used as the column index.

Ascending and descending Sorted data

Internally the UDF uses Excel’s MATCH function which handles both sort types.

Example code – the FLOOKUP UDF

FLOOKUP is a simplified version of the FastExcel AVLOOKUP function.
FLOOKUP does not contain these AVLOOKUP features:

• Calculated columns/ranges or constant array arguments
• Named Column headers
• Multiple Answers
• More than one column as the Lookup Value
• Alternative sets of Lookup Values
• Function Wizard Help

FLOOKUP VBA Code


Option Explicit
Option Base 1
Option Compare Text
'
' COPYRIGHT © DECISION MODELS LIMITED 2006, 2007, 2011. All rights reserved
' May be redistributed for free but
' may not be sold without the author's explicit permission.
'
Public Function FLOOKUP(lookup_value As Variant, _
Lookup_Range As Range, _
Answer_ColNum As Variant, _
Optional Sort_Type As Variant, _
Optional Exact_Match As Variant)
'
' FLOOKUP UDF: Fast Lookup
'
' find the Lookup_Value in the first column of Lookup_Range
' and return the corresponding row value from Answer_Colnum
'
' Sort_Type may be:
' -1 = sorted descending
' 1 = sorted ascending
' 0 = not sorted
'
' Exact_Match may be: True or False or any Non-Boolean value or string
' Exact_Match is returned if there is no exact match
'
' Sort_Type is optional and defaults to 1
' Exact_Match is optional and defaults to False if sorted, or #N/A if unsorted
'
Dim vAnsa As Variant ''' output to be assigned to function
Dim vRow As Variant ''' the row number found in Lookup_Range else error
Dim vNoMatch As Variant ''' the value to return if no exact match found
Dim lSorted As Long ''' -1 =descending, 0= not sorted, 1=ascending
Dim jAnswerColumn As Long ''' the answer column number in Lookup_Range
Dim blExact As Boolean ''' exact match flag
Dim blFound As Boolean ''' true if a match found
'
' setup error handler
'
On Error GoTo FuncFail
'
' skip execution if empty or uncalculated inputs
'
If IsEmpty(lookup_value) Or IsEmpty(Lookup_Range(1, 1)) Or IsEmpty(Answer_ColNum) Then
Exit Function
End If
'
' convert defaults etc
'
SetDefaults Sort_Type, lSorted, Exact_Match, vNoMatch, blExact, _
Answer_ColNum, jAnswerColumn
'
' now try to find the lookup_value
'
blFound = False
If Not blExact Then
'
' approx match sorted requested
'
On Error Resume Next
vRow = Application.WorksheetFunction.Match(lookup_value, Lookup_Range.Columns(1), lSorted)
If Err = 0 Then blFound = True
On Error GoTo FuncFail
Err.Clear
Else
'
' exact match requested
'
' first check memory, If matches then done
'
vRow = lMemoryId(Application.Caller)
If vRow > 0 Then
'
' check value in column 1 against Lookup_Value
'
If vRow < = Lookup_Range.Rows.Count Then
If Lookup_Range(vRow, 1) = lookup_value Then
blFound = True
End If
End If
End If
'
' no memory or memory does not match
'
If Not blFound Then
'
' look for the row
'
vRow = Application.Match(lookup_value, Lookup_Range.Columns(1), lSorted)
'
' if unsorted and nomatch vRow contains error
'
If Not IsError(vRow) Then
If lSorted = 0 Then
blFound = True
Else
'
' we have a potential row: check against Lookup_Value
'
If Lookup_Range(vRow, 1) = lookup_value Then blFound = True
End If
End If
End If
End If
'
' return the value
'
If Not blFound Then
'
' unsuccessful Exact Match: return the given error value
'
FLOOKUP = vNoMatch
Else
'
' successful: get answer from column
'
FLOOKUP = Lookup_Range(vRow, jAnswerColumn)
End If
'
' store memory
'
If blExact Then
Call StoreID(Application.Caller, vRow)
End If
Exit Function
FuncFail:
FLOOKUP = CVErr(xlErrValue)
Exit Function
End Function
Private Sub SetDefaults(Sort_Type As Variant, lSorted As Long, Exact_Match As Variant, _
vNoMatch As Variant, blExact As Boolean, _
Answer_ColNum As Variant, jAnswerColumn As Long)
'
' sorted defaults to sort ascending : 1
'
lSorted = 1
If Not IsMissing(Sort_Type) Then lSorted = CLng(Sort_Type)
'
' set blExact and vNoMatch
'
vNoMatch = CVErr(xlErrNA)
blExact = True
'
If IsMissing(Exact_Match) Then
'
' Exact_Match defaults to False if Sorted, #N/A if unsorted
'
If lSorted <> 0 Then blExact = False
Else
'
' do exact match unless sorted and exact match=false
'
vNoMatch = Exact_Match
If VarType(vNoMatch) = vbBoolean And lSorted <> 0 Then
If Not vNoMatch Then blExact = False
End If
End If
'
' answer column must be convertible to long
'
jAnswerColumn = CLng(Answer_ColNum)
End Sub
Private Function lMemoryId(oCaller As Range) As Long
'
' get the ID from the calling cell and convert to long
'
Dim vID As Variant
lMemoryId = 0
On Error GoTo FuncFail
'
' ID property not available in Excel 97
'
If Val(Left(Application.Version, 2)) > 8 And Not oCaller Is Nothing Then
vID = oCaller.ID
If vID <> "" And IsNumeric(vID) Then
lMemoryId = CLng(vID)
End If
End If
FuncFail:
End Function
Private Sub StoreID(oCaller As Range, vRowNum As Variant)
'
' store the id in the calling cell
'
If Not oCaller Is Nothing And Val(Left(Application.Version, 2)) > 8 Then
oCaller.ID = CStr(vRowNum)
End If
End Sub


Performance Comparison of FLOOKUP and VLOOKUP

These comparisons are done using Excel 2010 32-bit, but with multi-threading  calculation switched off.
The data range is 32000 rows and timings are for 10 function calls.
Vlookup Error handling is using the double lookup method rather than IFERROR.

Case 1: Approx Match on sorted data

• VLOOKUP 0.53 Millisecs
• FLOOKUP 1.01 Millisecs

Case 2: Exact Match on Unsorted Data (Midpoint)

• VLOOKUP 2.65 Millisecs
• FLOOKUP 1.28 Millisecs (second call)

Case 3: Exact Match – Unsorted Data – No Match found – return #N/A

• VLOOKUP 4.64 Millisecs
• FLOOKUP 5.43 Millisecs

Case 4: Exact Match – Unsorted Data – with Error Handling (Midpoint)

• VLOOKUP 4.5 Millisecs
• FLOOKUP 1.29 Millisecs (second call)

Case 5: Exact Match – Unsorted Data – with Error Handling (No Match found)

• VLOOKUP 4.66 Millisecs
• FLOOKUP 5.48 Millisecs

Case 6: Exact Match – Sorted Data – With Error Handling (Midpoint)

• VLOOKUP 4.56 millisecs (Double Exact Lookup)
• VLOOKUP 0.6 Millisecs (Double Sorted Lookup trick)
• FLOOKUP 1.35 Millisecs

Case 6: Exact Match – Sorted Data – With Error Handling (No Match Found)

• VLOOKUP 4.63 Millisecs (Double Exact Lookup)
• VLOOKUP 0.58 Millisecs (Double Sorted Lookup trick)
• FLOOKUP 1.49 Millisecs

Summary

• Although VBA UDFs have a higher overhead than Excel’s native functions carefully written functions can perform well.
• Using memory with unsorted exact matches can significantly improve LOOKUP performance.
• The double sorted lookup trick is significantly faster than Linear search on sorted data with missing values.
• FLOOKUP and the double sorted lookup trick win 4 out of the 6 tests!

So now all I have to do is rewrite the AVLOOKUP family of functions into C++ to exploit multi-threading, improved performance and the lower UDF overhead of the XLL.

Developing Faster Lookups – Part 1 – Using Excel’s functions efficiently – updated

When profiling Excel workbook calculation time I often find that Lookups are one of the main causes of performance problems.
So this is the first of 2 posts looking at how to do Lookups faster.

This post concentrates on the difficulties in using Excel’s built-in functions efficiently, and the next post will look at how to develop UDFs that address some of these difficulties and do Lookups faster than the Excel built-in functions.

There are 2 basic search strategies for Lookups:

• Linear Search for unsorted data – Exact Match
• Binary Search for sorted data – Approximate Match

Uusually if your data is unsorted or your data may not contain the value you want to find you will use Exact Match:

Linear Search Lookup Difficulties

VLOOKUP(lookup_value, table_range, col_index, False)
MATCH(lookup_value, column_range, 0)

Using False as the last parameter in Vlookup, and 0 as the last parameter in Match tells these functions to do a Linear Exact Match. The function will start at the first row and look at all the rows in turn until it finds a value that matches the lookup value.

For large data ranges all these comparisons take a lot of calculation time.

Linear Search with missing data: Lookup Value not found

If all the rows have been searched and no value has been found the function returns #N/A.
If the lookup value exists the function will, on average, have to look at half the rows, but if the lookup value does not exist the function will have to look at all the rows.
If you are using Excel 2003 or earlier and you want to avoid the #N/A you can use 2 Lookups and ISERROR(), but that doubles the amount of rows to be looked at if the value exists.

IF(ISERROR(VLOOKUP(lookup_value, table_range, col_index, False),”not found”,VLOOKUP(lookup_value, table_range, col_index, False))

In Excel 2007 and later you can use IFERROR(), which avoids the double lookup.

IFERROR(VLOOKUP(lookup_value, table_range, col_index, False),”not found”)

Whole Column Lookups and the Used Range

If the size of the data you are looking up keeps changing/expanding its convenient to use a whole column as the table range. Excel’s Lookup functions are smart enough not to look in all the extra empty rows, but you have to be careful because they will scan down to the last row in the Used Range. So If you have excess formatting causing a large used range your whole-column Lookups will be super slow with missing data.

Large dependency ranges trigger unnecessary Lookups

Suppose your Lookup range is 10000 rows by 5 columns and you have 500 Vlookups of different values. If nothing changes in the Lookup Range then the 500 Lookups don’t get recalculated. But as soon as 1 single value in the 50000 cells of the Lookup Range changes, every single one of the 500 Lookups will be flagged as needing recalculation, even if 499 or 500 of them don’t need recalculating because they will give exactly the same answer as before.
And by the way this effect will ripple down to all the other formulas that are dependent on the 500 Lookups, because Excel does not stop the calculation dependency chain just because a formula result has not actually changed after a recalc.

Multiple Matching Values

Linear search always returns the first matching value found. There are other ways than LOOKUP of finding the nth or last matching value, but they are all slow.

Binary Search Difficulties: Lookups on Sorted Data

If you tell the Excel functions that your data is sorted (VLOOKUP(,,,TRUE) or -1 or 1 as the last parameter for MATCH) they will use a binary search algorithm.

The good news is that binary search is really fast compared to linear search (LOG2(N) compared to N/2)
The bad news is that the particular implementation of binary search used by Excel does not tell you if the value you are looking for cannot be found, instead it returns the highest value that is less than the lookup value.

Binary Search with missing data: the solution

Fortunately its easy to check for missing data using VLOOKUP or MATCH with sorted data: the trick is to use the Lookup_Value to lookup itself.

IF(VLOOKUP(Lookup_Value, Table_Range,1,TRUE)<>Lookup_Value,”Not Found”, VLOOKUP(Lookup_Value, Table_Range,Col_Index,TRUE))

The first VLOOKUP looks up the Lookup_Value in column 1 and returns the value from column 1.
If this does not equal the Lookup_Value then return “Not Found”, otherwise do another VLOOKUP but this time using the answer Column Index.
Doing 2 Binary Search lookups is faster than doing one Linear Search lookup with anything more than about 20 rows of data.

Whole Column Lookups and the Used Range

In the same way as Linear Search, Binary Search lookup also only searches the used rows when given whole columns. But because binary search is so efficient even searching 1 million rows is fast.

Large Dependency Ranges

Binary search Lookups and their dependents will also be recalculated unnecessarily, but since the actual Lookups are so fast it does not matter so much.

Multiple Matching Values

Excel’s binary search functions return the Last matching value with ascending sort, and the First with descending sort (Match(… -1)).

Using Excel’s Lookup functions efficiently

Here are some additional tips for using Excel’s functions efficiently:

VLOOKUP versus INDEX and MATCH or OFFSET.

I recommend using INDEX and MATCH.

VLOOKUP is slightly faster (approx. 5%), simpler and uses less memory than a combination of MATCH and INDEX or OFFSET.

However the additional flexibility offered by MATCH and INDEX often allows you to make significant timesaving compared to VLOOKUP.

INDEX is very fast and from Excel 97 onwards is a non-volatile function (speeds up recalculation).

OFFSET is also very fast, but it’s a volatile function.

Converting VLOOKUP to INDEX and MATCH.

These statements return the same answer:

VLOOKUP(A1, Data!$A$2:$F$1000,3,False)
INDEX(Data!$A$2:$F$1000,MATCH(A1,$A$1:$A$1000,0),3)

Exact Match Lookups returning values from Multiple Columns.

You can often reuse a stored exact MATCH many times.

If you are doing exact lookups on multiple columns you can save a lot of time using one MATCH and many INDEX statements rather than many VLOOKUPs.

Add an extra column for the MATCH to store the result (stored_row).

For each column use:
INDEX(Lookup_Range,stored_row,column_number)Alternatively you can use VLOOKUP in an array formula: this example returns the value from the 2nd and 4th column in the lookup range.

{VLOOKUP(lookupvalue,Lookup_Range,{4,2},FALSE)}

Looking Up a Set of Contiguous Rows or Columns.

You can also return many cells from one Lookup operation.

If you want to lookup a number of contiguous columns then you can use INDEX in an array formula to return multiple columns at once (use 0 as the column number). You can also use INDEX to return multiple rows at once.

{INDEX($A$1:$J$1000,stored_row,0)}
This returns columns A to J in the stored row created by a previous MATCH

Looking Up a Rectangular Block of Cells.

You can use MATCH and OFFSET to return a rectangular block of cells as a range.

Two-Dimensional Lookup

Multi-dimensional lookup can also be done efficiently.

Two-dimensional table lookup using separate lookup’s on the rows and columns of a table can be efficiently done using an INDEX with two embedded MATCH functions.This example assumes a table in A1:Z1000 with column A containing the row identifier and row 1 containing the column identifier. Both the row and column identifiers are sorted ascending.

INDEX($B$2:$Z$1000,MATCH(RowLookup_Value,$A$2:$A$1000),MATCH(colLookup_value,$B$1:$Z$1))

Multiple-Index Lookup

In large spreadsheets you often need to lookup using multiple indexes, such as looking up product volumes in a country.

The simple way to do this is to concatenate the indexes and lookup using concatenated lookup values. This is inefficient when the data is sorted for two reasons:

• Concatenating strings is a calculation-intensive operation.
• The lookup will cover a large range.

It is often more efficient to calculate a subset range for the lookup: for example by using COUNTIF to count the number of rows for each country and then calculating the first and last row for each country from the counts, and then looking up the product within that range. See SUMIF Example or the FastExcel sample problem for an example of using this technique.

Three-dimensional lookup.

If you need to lookup the table to use as well as the row and the column here are some techniques you can use, focussing on how to make Excel lookup/choose the table.

If each table you want to lookup (the third dimension) is stored as a set of range names, or as a table of text strings that represent ranges, then you may be able to use INDIRECT or CHOOSE.

Using CHOOSE and range names can be a very efficient method, and it is not volatile, but it is best suited to only a small number of tables:

INDEX(CHOOSE(TableLookup_Value,TableName1,TableName2,TableName3,TableName4),MATCH(RowLookup_Value,$A$2:$A$1000),MATCH(colLookup_value,$B$1:$Z$1))

The example above dynamically uses TableLookup_Value to choose which range name (TableName1, TableName2, …) to use for the lookup table.

INDEX(INDIRECT(“Sheet” & TableLookup_Value & “!$B$2:$Z$1000″),MATCH(RowLookup_Value,$A$2:$A$1000),MATCH(colLookup_value,$B$1:$Z$1))

This example uses INDIRECT and TableLookup_Value to dynamically create the sheet name to use for the lookup table. This method has the advantage of being simple and can handle a large number of tables, but because INDIRECT is a volatile function the lookup will be calculated at every calculation even if none of the data has changed.
You could also use VLOOKUP to find the name of the sheet or the text string to use for the table, and then use INDIRECT to convert the resulting text into a range:

INDEX(INDIRECT(VLOOKUP(TableLookup_Value,TableOfTAbles,1)),MATCH(RowLookup_Value,$A$2:$A$1000),MATCH(colLookup_value,$B$1:$Z$1))

Another technique is to aggregate all your tables into one giant table, but with an additional column which identifies the individual tables. You can then use the techniques for multiple-index lookup above.

Wildcard Lookup

AVLOOKUP, AMATCH, MATCH,VLOOKUP and HLOOKUP allow you to use the wildcard characters ? (Any single character) and * (no character or any number of characters) on alphabetic exact matches. Sometimes this can avoid multiple matches.

Conclusion

• Linear Search Lookups are slow.
• Sorting your data and using the Binary Search options on VLOOKUP and MATCH is very fast.
• It’s easy and fast to detect missing values using Binary Search on sorted data.
• Lookups with large Table_Ranges often get recalculated unnecessarily.
• Lookups on whole columns are inefficient with large excess used range, but this does not matter with Binary Search.
• Excel’s Lookup functions do not provide good solutions with data containing multiple matching values.

For more information on speeding up Lookups see my Lookups Page

The next post will look at ways of bypassing and simplifying these difficulties by developing a UDF.

Excel UDF Technology Choices – Snakes & ladders with VBA, VB6, .NET, C++, COM, XLL, Interop …

I develop a commercial Excel addin product, FastExcel, one component of which contains a number of UDFs. I have been planning and developing the next version of FastExcel for some time, and it probably won’t surprise you to hear that it will contain even more UDFs designed to help you make Excel calculate faster.

Currently the product supports Excel 97 through Excel 2010 32-bit and uses VBA with a lot of Windows API Calls. But the not-so-simple question was:

What technology to use for the UDFs?

Having got bored waiting for MicroSoft to fix the UDF VBE refresh bug I wanted to use a technology that solved that problem. It would also be nice if I did not have to rewrite the existing 8000 lines of VBA code. And faster performance would of course be good.

I had just about decided to use VB6 Automation addins, with a VBA wrapper for Excel 97 and Excel 2000, and had an initial Beta version which demonstrated that the technology worked well.

Then came the news of Excel 2010 64-bit, and guess what – VB6 does not produce 64-bit DLLs (and by the way Excel 2010 still does not fix the UDF VBE refresh bug).
So VB6 was a snake and not a ladder.
It was time for a rethink and a more thorough evaluation of the alternatives, including some performance benchmarking.

Some preliminary research narrowed my choices to:

• Continue to use VBA
• Use VB6 and ignore the 64-bit market
• Take the .NET plunge and rewrite using one of
  • VSTO
  • .NET Interop Automation Addin
  • Excel DNA
  • Addin Express
  • Managed XLL
  • …
• Go for broke with C++ using XLL Plus or equivalent

VSTO was rapidly ruled out when I discovered that it did not support Automation Addin UDFs or XLLs and was not good for version independence.

UDF Technology Benchmarks

The UDFs in FastExcel are mostly general purpose UDFs and so have to handle all the Excel data types with reasonably large sets of data. I decided to benchmark a do-nothing UDF to see what the overhead per UDF call was, and a UDF whose performance was dominated by data transfer. I used the AverageTol UDF shown in Writing Efficient VBA UDFs Part 1 for the data transfer UDF.

The performance results looked like this:

Timings in Milliseconds	AvTol 10K datacells x 10 calls	10K Calls    Do Nothing
VBA Worst	7704	7030
SUMPRODUCT	277	4
VB.Net Automation Addin	170	101
Addin Express VB.Net Auto	170	101
VBA Best	109	26
Addin Express VB.Net XLL	100	112
XLDNA Vb.Net XLL	81	77
VB6 Automation Addin	63	25
XLL+ C XLL	37	13

VBA appears twice in the table:

• The first VBA times are the least efficient version of the AverageTol UDF and using the Do-Nothing UDF without bypassing the VBE Refresh bug.
• The second VBA times are the most efficient (non-array) version of the AverageTolUDF and using the Do-Nothing UDF but bypassing the VBE refresh bug.

Addin Express also appears twice because it supports both XLL and COM-Interop technologies.

Technologies:

There are basically three underlying technologies that can be used by UDFs:

• COM (VBA and VB6)
• XLL (C++, Excel DNA and Addin Express)
• COM-Interop (.Net Automation, Excel DNa and Addin Express)

The COM and COM-Interop interface exposes all the Excel object model, whereas the XLL interface is more limited but much faster.
COM-Interop is generally slow because of the additional Interop overhead.

So .NET products such as Excel DNa and Addin Express offer both the XLL and COM interfaces, and thats why I benchmarked both technologies.
From a performance point of view the XLL interface is clearly unbeatable, particularly with C++.

Tools Technology Support

Performance is important, but there are many other factors that could influence your choice of technology. In fact all of these solutions can be a good choice in different circumstances.
I was particularly interested in 64-bit support, Multi-threading, code/intellectual property security and Function wizard support:

	64Bit      Multithread	Security	Func Wizard
VBA Worst	Y                      N	None	Limited
SUMPRODUCT	Y                      Y	Excellent	Excellent
VB.Net Auto	Y                      Y	Good (Obfusc)	Limited
ADX VB.Net	Y                      Y	Good (Obfusc)	Good
VBA Best	Y                      N	Poor	Good (Hack)
ADX VB.XLL	Y                      Y	Good (Obfusc)	Good
XLDNA Vb.Net	Y                      Y	Good (Obfusc)	Good
VB6 Auto	N                      N	Excellent	Good (Hack)
XLL+ C	Y                      Y	Excellent	Good

I reckon it will be some time before 64-bit Excel is in widespread use, but I have already had several requests to support it from high-end users.
Multi-Threaded UDFs are moving into the mainstream as all new PCs have multiple cores and Excel 2007 and Excel 2010 penetration ramps up.
The security column is not about ant-virus security but protection of intellectual property and licensing. Obfusc refers to the need to obfuscate .Net code because it is easy to reverse compile it.
The function wizard support is about how easy it is to provide argument descriptions and help for your UDFs from within the Function wizard.
There is a good description here of the technique used for VBA and VB6 to provide enhanced Function Wizard support for UDFs (regarded by some as a bit of a hack), but even in Excel 2010 there is no way of implementing the argument intellisense that Excel’s native functions provide.

The Decision

It became clear that the easiest solution, using VB6 automation addins, was not the right choice because of lack of 64-bit and multi-threading support.
So I would have to rewrite, either to .NET or to C++.

Its easier to rewrite to .NET than to C++, and both Addin Express and Excel DNA provide excellent support. Excel DNA seems to have slightly better performance but Addin Express has better installability with .Net version independence.

XLL Plus shields you from a lot of the pain of working with the XLL SDK and I found it very easy to develop simple UDFs. But it was clear that some of the things I wanted to do would be challenging in C++, and the learning curve would be even steeper than .NET.

Looking longer term its hard to see which of these technologies (if any) provides a better long-term strategy. You would think that if MicroSoft were serious about .NET programmability in Office they would provide something better than VSTO, but so far there is no sign of that. They continue to support VBA, even if a bit weakly, and the XLL interface has continued to lead the way in performance support.

So I finally decided to bite the bullet and go the C++ route with XLL Plus. Significant performance and technology advantages, and if you are going to have to rewrite anyway, why not go for it?

So far its working well, but there is a lot to learn as I wade into XLL Plus, VS2010, the STL and BOOST libraries etc etc.

So thats my decision: whats yours?

Making the most of your XIPS (Part 1) – counting XIPS and reducing them to make Excel calculate faster

In the previous post The Xips challenge – How fast does Excel Calculate I managed to make Excel calculate 6.6 million simple formulae in under a second, and promised to come back in future posts to try to answer my question:
If Excel can calculate formulae this fast how come my spreadsheet takes several seconds to calculate?

And of course the follow-up to that is:
And how do I make it go faster?

So this is the first in what will hopefully be a series of posts trying to answer both these questions.
Lets start with a simple example:

Calculating cumulative sums.

Suppose you have a series of dated payments and you want to calculate the cumulative sum of all the prior payments for each date.

The formula in D6 is =SUM($B$6:$B6) and this is then copied down for all the 10000 rows, so the formula in row 5000 is =SUM($B$6:$B5000), and the formula in row 10005 is =SUM($B$6:$B10005): so each formula sums all the previous rows.

So how do you count the XIPS?

There are only 10000 formulas, but they take 1.2 seconds to calculate (just over 8000 formulas per second: thats a long way off the potential of 6.6 million XIPS).

Well of course the reason this is so slow is that each formula refers, on average, to a large number of cells.

On average each formula sums 5000 cells, so thats a total of 10000 x 5000 = 50 million operations Excel has to do. Its probably time to change the terminology here: lets call this 50 MXOPS (Millions of eXcel Operations per Second). This is much faster than the 6.6 Million XIPS in the previous post, because we only have 10000 formulas instead of 6.6 million formulas and the overhead of interpreting the formulas is making the difference.

Counting the number of operations Excel has to do on cells (XOPS)  (or virtual cells when using array formulae) can be a useful proxy predictor of calculation time, and one that should make you start thinking about how you might improve things.

OK, but do you make Excel calculate this faster?

If you look at what the formula are doing you soon discover that the cells near the beginning of column B are each being summed thousands of times. So if you can avoid this duplication of XOPS things should go faster. This is easy, just make each formula add the value from this row to the cumulative sum result from the previous row:

The formula in F6 becomes =B6, and the formula in F7 becomes =F6+B7. The F7 formula is then copied down the remaining rows.

Now each formula references just 2 cells, so thats 2 x 10000 = 20000 operations. And now the calculation takes just 0.011 seconds, an improvement factor of 110. Notice that the XOPS went from 50 million to 20 thousand, and improvement factor of 2500, but the calculation time only improved by a facor of 110. So there are other things besides XOPS that consume calculation time, such as:

• interpreting the formulae
• calling the SUM function
• returning the results to the cells
• reformatting the results
• repainting the screen

but counting the cell operations is still a good way of thinking about calculation time.

Conclusion

If you have got slow formulae its usually because the formulas are making Excel do a lot of work.
A useful way of quantifying that is to estimate the the number of real or virtual cell operations Excel has to do (XOPS).
Because Excel formulas are so flexible there is usually a different way of achieveing the same result, but using much fewer XOPS.

You just have to think creatively!