Shooting Fish in a Barrel

Back at Linuxworld Boston Michael

mentioned a teensy performance problem
with an internal spreadsheet (sorry,
it’s confidential and can’t be posted).

OOo Pivot Sample

This partially autogenerated 50M xls monster has been chock full of useful
compatibility tests for OOo. Unfortunately, one of my recent patches was
forcing the pivot tables to regenerate on load, rather than only on demand
later, and drove load time up
into the 3 hour range. MS Excel could load it < 1 minute.

The first step was to throw speedprof (properly patched for OOo) at it. Why
not use a sexier tool like cachegrind or oprofile you wonder ? The short
answer is simplicity. For a rough first cut speedprof is good enough and
doesn’t have much time/space overhead. The result showed a hotspot in the xls
importer itself with lots of code of the form

  long nCount = aMemberList.Count();
  for (i=0; i<nCount; i++) {
    const ScDPSaveMember* pMember = (const ScDPSaveMember*)aMemberList.GetObject(i);
    if ( pMember->GetName() == rName )
      return pMember;

A quick check showed that ‘aMemberList’ really was a list. Once I’d bandaged
my forhead and checked the monitor for damage the first patch was obvious.
This code was wrong on several levels. Let’s count the complexity.

1) List::Count : Why not just iterate on the list directly and save the lookup ?

2) List::GetObject(i) : Again, why start from the begining of the list each time when you just what to iterate through each element ?

3) if (pMember->GetName() == rName) : Why look things up in order when what you want to look them up by name ?

The first patch was conceptually simple, get a hash in place of that list.
It took some spelunking into the data structures to make that possible but in
the end
brought us down to 45 minutes without bloating the memory usage much.

The next speedprof run seemed as if the construction of the datapilots was uniformly
slow, but a bit of digging showed that one particular pivot tables was dominating.
It had a field with 30,000 unique strings. The code used similar idioms previous block.

  ScDPItemData aMemberData;
  long nCount = aMembers.Count();
  for (long i=0; i<nCount; i++) {
    ScDPResultMember* pMember = aMembers[(USHORT)i];
    target->FillItemData( aMemberData );
    if ( bIsDataLayout || aMemberData->IsNamedItem( target ) )

Thankfully it used an array in place of a list, but it threw an extra object
copy in the heart of the loop to keep things comfortably inefficient. One more
and we were down to 10 minutes. Still not good, but it’s an improvement. The
next steps will be to see why OOo is using 900M vs 90M for XL (and that’s
with wine), and to see about using a set of indicies for the pivot data,
rather than a set of strings.

OOo Pivot Performance

Leave a Reply