🚀 go-pugleaf

> 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

In article <8910251101.AA29989@g.oswego.edu> dl@oswego.oswego.edu writes:
>
>> I'm finding that I pay a real price in speed when I use some of the
>> libg++ library-derived classes.
>
>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.

I encountered this very early in the process of writing my Connection
Machine library.

>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.

In a sense, this was my solution.  If -O is specified, I do lots of
inlining, without it, I do little or none.  Each class in my library has
two files, a .h and a .cc.  They look something like this:

foo.cc:
	#define _FOO_CC_
	#include "foo.h"
	<code>

foo.h:
	class foo {
	};

	#if defined(_FOO_CC_)
	#define inline
	#endif

	#if defined(__OPTIMIZE__) || defined(_FOO_CC_)
	<the inline function definitions>
	#endif

	#if defined(_FOO_CC_)
	#define inline inline
	#endif

When compiling the library, a non-inline version gets put in foo.o, but
the parts of the library that use class foo can use inline versions (if
the library is compiled with -O).  When the user of the library is compiling,
they can compile some files with and others without -O.

When I get in a sitution where I want hundreds, or in some cases thousands
of inline functions, I will put them in a separate .h file.

foo.cc:
	#define _FOO_CC_
	#include "foo.h"
	<code>

foo.h:
	class foo {
	};

	#if defined(_FOO_CC_)
	#define inline
	#endif

	#if defined(__OPTIMIZE__) || defined(_FOO_CC_)
	#include "foo2.h"
	#endif

	#if defined(_FOO_CC_)
	#define inline inline
	#endif

foo2.h:
	<define oodles of inline functions>

This way, the huge number of function definitions is not scanned unless
it is necessary.

This simple scheme has helped a whole lot.  I still have a big problem
deciding which functions to inline.  In a number of cases, g++ tells
me that a function is too large to inline.  Retorical question:  if
I say inline, why doesn't it inline?  Who knows better, me or the compiler?
(I know, the answer is "compiler", but humor me, ok?).  But seriously,
it would be nice to be able to force the inlining of what the compiler
thinks are very large functions.  At least in my code, there are lots
of places where the compiler can evaluate a conditional at compile time,
eliminating lots of code as unreachable (if the function is expanded
inline).

The problem with all these inline functions (besides compile time) is that
I suffer from a serious case of "executable bloat".  I mean I get these
HUGE multi-meg executables.  This problem can be alieviated somewhat by better
optimization in the compiler and by better choice in which functions to 
expand inline.

More on my optimization complaints coming soon to a mailing list near
you...

rob collins
rjc@cs.ucla.edu

PS  For those who are interested in the C++/CM interface, it is about 75%
done.  It has stalled, due to other commitments and massive computer
system changes/problems (latest weirdness: I left town for a couple of days,
and when I came back this morning, all of the machine names had been
changed--strange).

-------------------------------------------------------------------------------
rjc@cs.ucla.edu	                    C++/Paris on the CM2:  The only way to fly.
-------------------------------------------------------------------------------

Another solution to coding around the cost of function calls is to use
a RISC workstantion where that cost is negligible.

Michael