Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!G.OSWEGO.EDU!dl
From: dl@G.OSWEGO.EDU (Doug Lea)
Newsgroups: gnu.g++.lib.bug
Subject: lack of inline functions in libg++
Message-ID: <8910251101.AA29989@g.oswego.edu>
Date: 25 Oct 89 11:01:31 GMT
References: <32147@ucbvax.BERKELEY.EDU>
Sender: daemon@tut.cis.ohio-state.edu
Reply-To: dl@oswego.oswego.edu
Distribution: gnu
Organization: GNUs Not Usenet
Lines: 45


> I'm finding that I pay a real price in speed when I use some of the
> libg++ library-derived classes.  For example, SplaySets are used
> extensively in my code, and in a particularly crucial loop, elements
> are retrieved from two SplaySets and multiplied -- my goal is to get
> around that loop as many times as possible.
> 
> Unfortunately, functions like __SplaySet::next() cannot be inlined, as
> they are not in the class header file -- they end up in another object
> file.  This function call (and other accesses of different classes in
> the same loop) costs me a significant constant in the speed around
> that loop.  A lot of simple functions (even basic accesses like
> class::operator[] and class::operator()) suffer from this same
> problem, and they are precisely the functions that are called
> thousands/millions of times in typical code.
> 

Decisions about what to inline in a library are hard, and sometimes
arbitrary. I usually have to guess about which things are both short
enough and well-used enough to be worth declaring as inline. These
decisions never please everyone -- I get just about as many complaints
that there are too many inlines in libg++, making compiles unbearable
slow, as complaints that there are not enough inlines, hurting
performance.

Michael and I are toying with employing a numerical INLINE_LEVEL
compiler switch, with levels that correspond to more or less inlining
(thus, faster or slower compilation). A bunch of compilation and
linkage details have to be worked out before we can implement this.

The specific case at hand (SplaySets) is tougher. The succ() function
called by next() is inherently a loop that is not very amenable to
inlining -- inlining it might only give you a couple of percent
speedup, depending, in part, on the kind of machine you are using. In
your case, it might make sense to use SplaySets for the dynamic
aspects of your application, and then to transfer things to something
like an OSLSet, which supports a faster next() method, for traversal.
You might even transfer things (or, more likely, the corresponding
pointers) into a simple local array and step through it.

About your previous note requesting libg++ Graph classes. These are on
my (much too long) list of things to do. If anyone would like to
donate something before then, or collaborate on them, please do!

-Doug