A Quantum of Time – measuring time accurately.

If you want to do work on Excel performance stuff you need a method of timing things so that you can see whether one way of doing things is faster than another.

Typically this requires 2 things:

• A method for reading some kind of clock.
• A method of executing the thing you want to time.

There are several clocks you can use with VBA.

• the built-in Time() function
• the timeGetTime Windows API
• the QueryPerformanceCounter and QueryPerformanceFrequency Windows APIs

But each clock has different sized “ticks” (the clock’s Quantum of Time, more usually called its resolution), and the size of the tick is the smallest amount of time you can measure.

The VBA built-in Time() function has a very large tick: about half a second on my system which makes it fairly useless for anything except long-running macros.
timeGetTime is much better: the tick is about a millisecond (one thousandth of a second).
But the winner is QueryPerformanceCounter and QueryPerformanceFrequency: I get about 0.3 microseconds (millionths of a second).

You can download VBA code using these 2 timers from here.

So now we need a method of executing the thing we want to time, which in my case is usually the calculation of a block of Excel formulas or UDFs. The most convenient method for this is to use Range.Calculate. This method has some peculiarities that need handling, and the actual calculation method used varies somewhat depending on the Excel version you are using. I have packaged all this together into a small Excel addin file RangeCalc, which gives you a button to click which shows you the time taken to calculate the currently selected formulas.

The RangeCalc times are not completely consistent, because Windows is a multi-tasking operating system, tends to move stuff in and out of the high-speed caches and also because Excel itself will try to cache recently used stuff. So its best to do several successive clicks on RangeCalc and take an average of the times.

Some more things to bear in mind when timing formula calculation are:

• Multi-threaded Recalculation
• Excel’s smart Recalculation engine
• Volatile Functions

Excel 2007 introduced Multi-threaded recalculation. This allows Excel to split the calculation into multiple calculation chains and execute each of them simultaneously if you have a multi-core PC. But Range.Calculate does not use Multi-Threading, so will be misleading if you compare a multi-threaded Function with a non-multithreaded Function. (All VBA UDFs are non multi-threaded).

Excel’s smart Recalculation engine minimises the number of formulae that it recalculates by tracking changes to cells and formulae. Only changed cells, cells containing Volatile functions such as Rand() or Now(), and the cells that are dependent on these cells will be calculated in a normal Recalculation (F9). But RangeCalc calculates ALL the selected cells rather than just the ones that need recalculating. So it measures the speed of a Full Calculation of all the selected formulas rather than telling you the time for only the cells that need calculation.

The RangeCalc addin gives you an excellent starting tool for measuring and comparing the calculation time of a formula or a block of formulas. You can extend the approach to measure the time taked to Calculate a worksheet or a workbook. And once you can measure calculation time accurately you can start comparing the alternatives so that you can find faster solutions.

The XIPS Challenge – how fast does Excel calculate?

It used to be fashionable to measure computer speed in MIPS (millions of instructions per second).
So I thought it would be interesting to:

• Find out how many XIPS (Excel Calculations per second) Excel could do on a modern PC.
• Then challenge people to guess how many calculations per second they thought Excel could do.

For my test I used Excel 2010 on my desktop PC, which is currently an Intel I7 870 2.93 GHz. This PC has 4 cores each of which can run 2 threads, so Excel 2010 could run 8 calculation threads in parallel if I set up the test properly.

In row 1 I entered =RAND() and copied the formula across to column Z.
Then I entered =A1+1 into A2 and copied the formula across to column Z, and then down to row 256000.
this gave me 6656000 formulae (6.6 million) in 26 independent calculation chains.

Then I switched to Manual Calculation mode and pressed F9 or Ctrl/AltF9 a few times to time the calculation (I was using FastExcel to time the calculations, if you don’t own FastExcel you can find the code for a simple calculation timer in my MSDN article on finding and prioritizing Excel Calculation Bottlenecks ).

OK, so how many XIPS do YOU think Excel can do?

• 1000 per second?
• 10000 per second?
• 100000 per second?
• 1000000 per second?
• More than 1000000 per second?

My PC calculated the 6.6 million formulae in under a second (the average was about 0.96), so my PC is rated at 6.9 MXIPS (millions of Excel calculations per second).

Well I know its very simple formulae but WOW!!!

I was giving a talk a couple of years ago at the London Excel Users Conference on Improving Excel Performance, and I asked the audience the XIPS question: most of them thought the answer was in the tens or hundreds of thousands: nobody thought it was over a million.

So here is a question for future posts:

If Excel can calculate formulae this fast how come my spreadsheet takes several seconds to calculate?

Writing efficient VBA UDFs (Part 1) – It ain’t what you do it’s the way that you do it

Its fairly easy to write a User Defined Excel function using VBA:

Suppose you want to write a function that calculates the average of a range of cells, but exclude from the average anything that is not a number or is less than a tolerance.
Lets call the Function AverageTol

Start Excel
Alt-F11 gets you to the Visual Basic Editor (VBE)
Insert–>Module
Enter the following VBA Code
Function AverageTol(theRange, dTol)
For Each Thing In theRange
If IsNumeric(Thing) Then
If Abs(Thing) > dTol Then
AverageTol = AverageTol + Thing
lCount = lCount + 1
End If
End If
Next Thing
AverageTol = AverageTol / lCount
End Function

The function loops through every cell in the range and, if the cell is a number greater than the tolerance, adds it to the total and increments a count. Finally it divides the total by the count and returns the result.
Now go back to the Excel worksheet, enter some data in cells A1:A10 and in B1 enter

=AverageTol(A1:A10 , 5)

That was pretty easy, and works well for 10 cells.
But if you have a lot of data, say 32000 cells, then 10 formulas using this UDF takes over 5 seconds to calculate on my fast PC (Intel I7 870 2.9 GHZ).

One major reason this is so slow is that I used all the defaults: I was lazy and did not declare any of the variables so they all defaulted to Variants.
Thats SLOW … but I can easily improve it: here is version A of AverageTol:
Function AverageTolA(theRange As Range, dTol As Double)
Dim oCell As Range
Dim lCount As Long
For Each oCell In theRange
If IsNumeric(oCell) Then
If Abs(oCell) > dTol Then
AverageTolA = AverageTolA + oCell
lCount = lCount + 1
End If
End If
Next oCell
AverageTolA = AverageTolA / lCount
End Function

This is the same function but with each variable declared as a sensible Type. This is good programming practice, and considerably faster.
10 formulas using this UDF on 32000 cells now calculates in 1.4 seconds, thats an improvement factor of 3.5 but still SLOW.
One reason its slow is that there is a large overhead each time a VBA program transfers data from an Excel cell to a VBA variable
And this function does that lots of times (3 times 32000).
If you transfer the data in one large block you can avoid much of this overhead:
Function AverageTolC(theRange As Range, dTol As Double)
Dim vArr As Variant
Dim v As Variant
Dim lCount As Long
'
On Error GoTo FuncFail
'
' get Range into a variant array
'
vArr = theRange
'
For Each v In vArr
If IsNumeric(v) Then
If Abs(v) > dTol Then
AverageTolC = AverageTolC + v
lCount = lCount + 1
End If
End If
Next v
AverageTolC = AverageTolC / lCount
Exit Function
FuncFail:
AverageTolC = CVErr(xlErrNA)
End Function

The statement vArr = theRange takes the values from all the cells in the Range and transfers it to a 2-dimensional Array of Variants. Then the UDF loops on each element of the Variant array. I also added an error handling trap that makes the UDF return #N/A if any unexpected error occurs.

Now the 10 formulas calculate in less than 0.1 seconds: thats an additional improvement factor of 14.

But we have’nt finished yet! Another speedup trick is to replace

vArr = theRange
with
vArr = theRange.Value2

That reduces the calculation time from 98 milliseconds (thousandths of a second) to 62 milliseconds. Using .Value2 rather than the default property (.Value) makes Excel do less processing (.Value checks to see if cells are formatted as Currency or Date, whereas .Value2 just treats all numbers including dates and currency as Doubles).

We can also make another small speedup by using Doubles rather than Variants wherever possible. Change the For Each v … Next v loop to:
Dim d as Double
Dim r as Double
On Error GoTo skip
For Each v In vArr
d = CDbl(v)
If Abs(d) > dTol Then
r = r + d
lCount = lCount + 1
End If
skip:
Next v

Now the calculation time has come down to 47 milliseconds.

So a series of small changes has improved the calculation speed of this simple UDF from 5.4 seconds to 0.047 seconds, 115 times faster!

Fast Gini – calculating Gini coefficients in Excel efficiently

“The Spirit Level” is a very interesting book about the effects of inequality on health and wellbeing. It introduced me to the Gini coefficient, which is a number ranging from 0 to 1 that measures the degree of inequality in a set of data.

Of course as an Excel Geek I immediately wanted to know how to calculate Gini Coefficients in Excel …

And then I wanted to see how an array formula compared to  a VBA UDF and a C++ XLL UDF …

What are Gini Coefficients?
Gini Coefficients are a frequently-used method of measuring inequalities such as income distribution in a population.
They can be calculated as “the relative mean difference” – the mean of the difference between every possible pair of datapoints, divided by the mean of all the datapoints. A Gini Coefficient ranges from 0 (everyone has the same income) to 1 (one person has all the income).

Some Gini Income coefficients are:

• Sweden     0.23
• France      0.28
• UK            0.34
• USA          0.45
• Brazil        0.57
• Zimbabwe  0.57

(Source: http://en.wikipedia.org/wiki/List_of_countries_by_income_equality)

The Gini formula is often written as:
G=SUM(i=1 to n) SUM(j=1 to n) ABS(Datapoints(i)-Datapoints(j)) / (n*n*Average(Datapoints))

where Datapoints is the range of data and n is the number of points in Datapoints.

A Bias Correction factor of n/(n-1) is usually applied.

Calculating Gini Coefficients using Excel.
The Gini Formula can be written as an Excel array formula (Array1, credited to Harlan Grove) (ignoring the Bias correction Factor):
{=AVERAGE(ABS(DataPoints-TRANSPOSE(Datapoints)))/AVERAGE(Datapoints)/2}

You need to enter this formula without the { } using Control-Shift-Enter to make Excel handle it as an array formula.

This array formula works well for small amounts of data, but because it creates and calculates a square array of n rows by n columns it is slow, and does not work for n> approx 4000.

The 4000 limit can be bypassed by programming a VBA UDF (DaGini, credited to Dana DeLouis), and this UDF calculates very slightly faster than the array formula (in Excel 2003).

Function DaGini(v)
Dim r As Long
Dim c As Long
Dim n As Long
Dim t, M
With WorksheetFunction
M = .Transpose(v.Cells.Value)
n = v.Cells.Count
For r = 2 To n
For c = 1 To (r - 1)
t = t + Abs(M(r) - M(c))
Next c
Next r
DaGini = t / (CDbl(n) * .Average(M) * CDbl(n))
End With
End Function

For large data volumes the performance of this UDF is horrible (317 seconds for 64000 datapoints)

A more efficient formula was developed by Angus Deaton (Princeton):
G=(n+1)/(n-1)-2 /(n*(n-1)* Average(Datapoints))*SUM(i=1 to n) Datapoints(i)*Rank(i)
Where Rank is 1 for the largest value and n for the smallest value.
This formula has the bias correction factor built-in.

This can be translated into an Array formula (Array2):
{=(ROWS(Datapoints)+1)/(ROWS(datapoints)-1)-2/(ROWS(Datapoints)*(ROWS(Datapoints)-1)*AVERAGE(Datapoints)) *SUM(RANK(Datapoints,Datapoints)*Datapoints)}

Don’t forget to enter this formula without the { } using Control-Shift-Enter to make Excel handle it as an array formula.
This array formula is considerably more efficient than the previous array formula, with most of the calculation time being used in the RANK function, but its still quite slow with large amounts of data (72 seconds for 64000 datapoints)

Rewriting this formula as a VBA UDF (GiniCoefA) using an internal Quicksort to sort the data once instead of using the RANK function results in an extremely efficient function that is useable with very large numbers of datapoints: (0.4 secs to calculate 64000 datapoints).

The GiniCoefA function has options for the data to be already sorted and to include/exclude the Bias correction factor.

Public Function GINICOEFA(InputData As Variant, _
Optional Sorted As Long = 0, Optional BiasCorrect As Boolean = True) As Variant
Dim InputValues As Variant
Dim j As Long
Dim jRank As Long
Dim dObs As Double
Dim dGini As Double
Dim dSum As Double
Dim oRng1 As Range
Dim oRng2 As Range
On Error GoTo Fail
If IsObject(InputData) Then
If InputData.Rows.Count > 10000 Then
Set oRng1 = InputData.Parent.UsedRange
Set oRng2 = Application.Intersect(oRng1, InputData)
Else
Set oRng2 = InputData
End If
If Application.WorksheetFunction.CountA(oRng2) = 0 Then Exit Function
InputValues = oRng2.Value2
ElseIf VarType(InputData) >= vbArray Then
InputValues = InputData
ElseIf IsEmpty(InputData) Or IsError(InputData) Then
GoTo Finish
ElseIf Len(CStr(InputData)) = 0 Then
GoTo Finish
Else
GINICOEFA = 1
GoTo Finish
End If
dObs = UBound(InputValues)
If Sorted = 0 Then QSortVar InputValues, 1, CLng(dObs)
For j = 1 To dObs
If Sorted = 1 Then
jRank = j
Else
jRank = dObs - j + 1
End If
dGini = dGini + InputValues(j, 1) * jRank
dSum = dSum + InputValues(j, 1)
Next j
GINICOEFA = (dObs + 1) / (dObs - 1) - dGini * 2# / (dObs * (dObs - 1) * _
(dSum / dObs))
If Not BiasCorrect Then GINICOEFA = GINICOEFA * (dObs - 1) / dObs
Finish:
Set oRng1 = Nothing
Set oRng2 = Nothing
Exit Function
Fail:
GINICOEFA = CVErr(xlErrValue)
GoTo Finish
End Function

Update: added the Quicksort VBA Sub

Sub QSortVar(InputValues As Variant, jStart As Long, jEnd As Long)
Dim jStart2 As Long
Dim jEnd2 As Long
Dim v1 As Variant
Dim v2 As Variant
jStart2 = jStart
jEnd2 = jEnd
'
' choose random pivot
'
v1 = InputValues((jStart + (jEnd - jStart) * Rnd()), 1)
While jStart2 < jEnd2
While InputValues(jStart2, 1) < v1 And jStart2 < jEnd
jStart2 = jStart2 + 1
Wend
While InputValues(jEnd2, 1) > v1 And jEnd2 > jStart
jEnd2 = jEnd2 - 1
Wend
If jStart2 < jEnd2 Then
v2 = InputValues(jStart2, 1)
InputValues(jStart2, 1) = InputValues(jEnd2, 1)
InputValues(jEnd2, 1) = v2
End If
If jStart2 <= jEnd2 Then
jStart2 = jStart2 + 1
jEnd2 = jEnd2 - 1
End If
Wend
If jStart2 > jStart Then QSortVar InputValues, jStart, jEnd2
If jStart2 < jEnd Then QSortVar InputValues, jStart2, jEnd
End Sub

Rewriting the VBA UDF in C++ using STL Vector and XLL Plus Version 7 gives further significant speed improvements (0.01 secs to calculate 64000 datapoints).

CXlOper* GINICOEFF_Impl(CXlOper& xloResult, const CXlOper* InputValues_op, const
CXlOper* Sorted_op, const CXlOper* BiasCorrect_op)
{
// Input buffers
std::vector InputValues;
long Sorted;
bool BiasCorrect;
// Validate and translate inputs
XlReadVector(*InputValues_op, InputValues, L"InputValues", XLA_TRUNC_ONEMPTY
|XLA_TRUNC_ONBLANK|XLA_FLAG_REJECT_NULL_ARRAY);
static CScalarConvertParams Sorted__params(L"Sorted", XLA_DEFAULT_ZERO
|XLA_DEFAULT_EMPTY|XLA_DEFAULT_NONNUMERIC|XLA_DEFAULT_BLANK, 0, -1, (
long)0);
XlReadScalar(*Sorted_op, Sorted, Sorted__params);
static CScalarConvertParams BiasCorrect__params(L"BiasCorrect",
XLA_DEFAULT_EMPTY|XLA_DEFAULT_BLANK, 0, -1, true);
XlReadScalar(*BiasCorrect_op, BiasCorrect, BiasCorrect__params);
// End of generated code
long nObs=0;
long jRank=0;
double dGini=0.0,dSum=0.0,dObs=0.0,dVal=0.0;
nObs=InputValues.size();
dObs=nObs;
if (nObs==0) throw CXlErrorException(xlerrValue);
// single value result is 1
if (nObs==1)
{xloResult=1.0; return xloResult.Ret();}
// sort data if required
if (Sorted==0) sort(InputValues.begin(),InputValues.end());
// calc values * rank, and sum
for (long j=0;j<nObs;j++)
{
if (Sorted==1)
{jRank=j + 1;}
else
{jRank=nObs - j ;}
;
dVal=InputValues[j];
// values not allowed to be negative
if (dVal<0.0) throw CXlErrorException(xlerrNum);
{dGini=(dObs + 1.0) / (dObs - 1.0) - dGini * 2.0 / (dObs * (dObs - 1.0) * (dSum / dObs));}
if (!BiasCorrect) dGini = dGini * (dObs-1.0) / dObs;
xloResult=dGini;
return xloResult.Ret();
}


Comparison Timings in Milliseconds using Excel 2003 on an Intel i7 870 2.9GHz

 500 Data Rows – Milliseconds

Array 1	22
DaGini VBA UDF	20
Array 2	5
GiniCoefA VBA UDF	1
GiniCoeff XLL	0.2

 64000 Data Rows – Milliseconds

DaGini VBA UDF	318000
Array 2	72000
GiniCoefA VBA UDF	394
GiniCoeff XLL	12

Conclusions:

• For small amounts of data there is no point in optimising the calculation: any method is fast enough.
• Finding the best algorithm is often more important that using faster technology.
• An efficient UDF is much faster than Array formulae for this calculation.
• C++ XLL can be a lot faster than VBA.

More:

If you want an efficient ready-made Excel Gini Coefficient solution try SpeedTools Extras, a library of Excel functions including GINICOEFF

http://www.decisionmodels.com/FastExcelV3SpeedTools_buy.htm

For more information on Gini Coefficients see:

http://en.wikipedia.org/wiki/Gini_coefficient

http://mathworld.wolfram.com/GiniCoefficient.html