Subject: Optimization Opportunities 1 [long]
From: Sam TH (sam@uchicago.edu)
Date: Mon Feb 05 2001 - 02:02:48 CST
Well, I've been playing with the wonderful gcov program (which has now
tripled the size of my source tree), and I have some interesting
data. This is just on startup time, one of the key measures that
users will judge the speed of AbiWord by. More on other aspects
later.
First, basically all startup time is spent in the following functions:
linit (only with ispell)
EV_EditMethod::getName(void) const
EV_EditBindingMap::getShortcutFor(EV_EditMethod const *) const
EV_UnixMenu::synthesizeMenu(_GtkWidget *)
EV_EditBinding::getType(void) const
1) linit - in src/other/spell/lookup.c
The gcov data tells us that there are only two sections of code, both
in for looks, that are executed a significant number of times. Each
of these loops ends up iterating about 30,000 times. For comparison,
I didn't see any other line in this function over 65 times. We
consider the second for loop first. [line 283]
31084 for (i = hashsize, dp = hashtbl; --i >= 0; dp++)
{
31083 if (dp->word == (char *) -1)
12 dp->word = NULL;
else
31071 dp->word = &hashstrings [ (int)(dp->word) ];
31083 if (dp->next == (struct dent *) -1)
19594 dp->next = NULL;
else
11489 dp->next = &hashtbl [ (int)(dp->next) ];
31083 }
Basically, this loop is non-optimizeable. These are all just
assignments, and can't really be sped up. On to the first for loop.
[line 259]
31084 for( x=0; x<hashheader.tblsize; x++ )
{
31083 if( fread ( (char*)(hashtbl+x),
sizeof( struct dent)-sizeof( MASKTYPE ),
1, fpHash)
!= 1)
{
###### (void) fprintf (stderr, LOOKUP_C_BAD_FORMAT);
###### return (-1);
31083 }
31083 } /*for*/
so, basically, this for loop consists of just one call, that to
fread. So, since we can't optimize fread, the problem boils down to
what we could use instead. Suggestions? Might read() be faster here?
Note also that this is not originally our code. The offending for
loop was actually written by Darren Benham, our illustrious Debian
maintainer, whom I've cc'ed on this mail. So we should investigate the
possibility that upstream has dealt with this issue [1].
[1] Does ispell upstream still exist?
2) EV_EditMethod::getName
Here's the definiton of this function:
inline const char * EV_EditMethod::getName(void) const
{
return m_szName;
}
Enough said.
3) EV_EditBindingMap::getShortcutFor
This is a rather large function, but again we have two for loops. For
loop 1 [line 352]
34873 for (j=0; j < EV_COUNT_EMS_NoShift; j++)
139330 if (m_pebChar->m_peb[i][j])
32906 {
// only check non-null entries
32906 pEB = m_pebChar->m_peb[i][j];
32906 if ((pEB->getType() == EV_EBT_METHOD) &&
32906 (pEB->getMethod() == pEM))
81 {
// bingo
81 bChar = UT_TRUE;
81 ems = EV_EMS_FromNumberNoShift(j);
81 break;
}
}
For loop 2 [line 375]
112 for (i=0; (i < EV_COUNT_NVK) && !bNVK; i++)
6981 for (j=0; j < EV_COUNT_EMS; j++)
55797 if (m_pebNVK->m_peb[i][j])
9350 {
// only check non-null entries
9350 pEB = m_pebNVK->m_peb[i][j];
9350 if ((pEB->getType() == EV_EBT_METHOD) &&
9350 (pEB->getMethod() == pEM))
9 {
// bingo
9 bNVK = UT_TRUE;
9 ems = EV_EMS_FromNumber(j);
9 break;
}
}
Whee, it's a nested for loop.
Ok, I have to admit that I don't have good suggestions for optimizing
these loops, since they mostly all involve assignments, macro calls
(EV_EMS_FromNumber) and calls to inlined accessor functions.
But the real question here is why we need to run these loops 60,000
times on start up. Ideas? Suggestions?
4) EV_UnixMenu::synthesizeMenu
This is unix specific, but I wouldn't be surprised if the same
function took a while on other platforms.
This function, however, is likely to be very hard to optimize. It's
really long, consists of *lots* of GTK calls, and has no loops at
all. Significant investigation would be required to discover what
parts of this function, if any, take a long time. I may
instrumentalize it later this evening, if I get bored.
5) EV_EditBinding::getType
EV_EditBindingType EV_EditBinding::getType(void) const
{
return m_ebt;
}
Any objections to inlining this? That's all we can really do.
If anyone want more gcov data (I have it for every file in the tree)
just let me know.
Motto: start faster than vi (we're already faster than emacs).
sam th
sam@uchicago.edu
http://www.abisource.com/~sam/
GnuPG Key:
http://www.abisource.com/~sam/key
This archive was generated by hypermail 2b25 : Mon Feb 05 2001 - 02:02:23 CST