compile time vs. run time?

[Markus Dehmann]

I have a big class that contains code like this (the code is automatically
generated according to some configuration):

if(str == "name1"){
do;
something;
name1_specific;
}else if(str == "name2"){
do;
something;
name2_specific;
}else...

Now, since I have hundreds of these name1, name2, ... the code takes forever
to compile. Even worse, if only one name changes in the configuration, the
whole code gets re-generated and I have to wait on compilation very long.

Would some amount of separate compilation be a good idea?

// main.cpp
if(str == "name1"){
processName1();
}else if(str == "name2"){
processName2();
}else...

// name1.cpp
void processName1(){...}

// name2.cpp
void processName2(){...}

// ...


Now, if I have to modify name1.cpp, it won't affect the whole code anymore,
and compilation will be quick.

But does it affect runtime? Can these processName1()... functions be inlined
automatically? Or does the separate compilation make that impossible?

Thanks!
Markus

 

[Victor Bazarov]

[...]
But does it affect runtime? Can these processName1()... functions be
inlined
automatically? Or does the separate compilation make that impossible?

Functions can only be inlined if the compiler knows the contents of their
bodies when generating code for a call to that function. If no body is
visible, what would the complier put instead of the call?

V

 

[Siemel Naran]

I have a big class that contains code like this (the code is automatically
generated according to some configuration):

if(str == "name1"){
do;
something;
name1_specific;
}else if(str == "name2"){
do;
something;
name2_specific;
}else...

Now, since I have hundreds of these name1, name2, ... the code takes forever
to compile. Even worse, if only one name changes in the configuration, the
whole code gets re-generated and I have to wait on compilation very long.

Would some amount of separate compilation be a good idea?

Yes. Depending on the body if the if blocks, the cost of a non-inline
function call or even a virtual function is generally negligible. Meausre
the performance impact first, using a profiler if necessary, and only then
should you inline.

// main.cpp
if(str == "name1"){
processName1();
}else if(str == "name2"){
processName2();
}else...

// name1.cpp
void processName1(){...}

// name2.cpp
void processName2(){...}

// ...

They won't be inlined automatically in all the compilers I know of.
However, you can force the compiler do do this in the release build by using
#ifndef _DEBUG. For example,

// main.cpp
#ifdef _DEBUG
#include "name1.h"
#include "name2.h"
#else
#include "name1.inl"
#include "name2.inl"
#endif
int main() {
std::string str;
if(str == tagName1){
processName1();
}else if(str == tagName1){
processName2();
}else...
}

// maybeinline.h
#ifdef _DEBUG
#define maybeinline
#else
#define maybeinline inline
#endif

// name1.h
#ifndef processName1
#define processName1
extern const char *const tagName1;
void processName1();
#endif

// name1.inl
#include "name1.h"
#include "maybeinline.h"
maybeinline void processName1() { ... }
#endif

// name1.cpp
#include "name1.inl"
const char *const tagName1 = "name1";


More importantly, consider using the command pattern. There will be an
asbtract class BaseAction or some name, with a pure virtual function exec or
some name. The function exec will normally take one or more function
arguments. There will be a registry that has a vector<BaseAction*> or the
like. People will define their derived action classes in seperate files.
The registry will provide a way of adding a new derived action or a pointer
to a function that creates a new derived function, to the registry. When
one adds a new derived action to the registry, one also adds the name of the
action (or provides a virtual function that returns the name of the name of
the action). To run an action given a function name, ask the registry to
return the BaseAction* whose function name equals to the name of the
function you want to run, then call the virtual exec function.

Now when you add new functions to the registry, neither do you have to
change main.cpp by adding more if-else blocks, nor do you have to recompile
it. This helps maintainance a lot.

But does it affect runtime? Can these processName1()... functions be inlined
automatically? Or does the separate compilation make that impossible?

Well, there is a way to get inlining, as indicated above. But the cost of a
non-inline virtual function call is usually (but not always) negligible in
my experience. Furthermore, if every function -- processName1, processName2
etc -- is inline, your function int main() will be very large. This could
degrade performance by introducing paging. I don't know the details about
paging as it is OS and CPU and RAM specific, but it's got something to do
with not being able to keep the entire program code in a single chunk of
RAM, so the compiler has to swap program code in and out all the time.

 

[Joseph Turian]

Markus,

You could make your code much simpler by having a lookup table of the
different "processes" (or whatever they are). Each element of the
lookup table array would store a string and a function pointer. Then,
your code could just iterate over the array, and call the appropriate
function pointer when there's a string match.

This is much easier to maintain. It will also speed your compilation,
since you can have your lookup table in a separate file from the
implementation of the process functions.

But does it affect runtime? Can these processName1()... functions be inlined
automatically? Or does the separate compilation make that impossible?

Is this really the bottleneck in your code?
Remember what Knuth said: Premature optimization is the root of all
evil.

Joseph

 

[davidrubin]

Markus,

You could make your code much simpler by having a lookup table of the
different "processes" (or whatever they are). Each element of the
lookup table array would store a string and a function pointer. Then,
your code could just iterate over the array, and call the appropriate
function pointer when there's a string match.

Iteration is no better than if-else clauses. You want an
std::hashmap[*] if possible, otherwise an std::map. You will probably
also want to encapsulate this detail in a class, and provide a typedef
for the function (or functor) type, and appropriate manipulators and
accessors. This allows you to provide thread safety, make use of object
pools, etc. as necessecary.

[*] still non-standard?

This is much easier to maintain. It will also speed your compilation,
since you can have your lookup table in a separate file from the
implementation of the process functions.

It also allows you to test the lookup table and each function
independently.

be

impossible?

The functions are being called through a pointer anyway, so inlining is
a moot point.

Is this really the bottleneck in your code?
Remember what Knuth said: Premature optimization is the root of all
evil.

Obviously, a constant-time algorithm is a better choice than a linear
one. /david

 

[Alan Krueger]

Iteration is no better than if-else clauses.

In maintainability, it's definitely an improvement, though clearly not
any better in runtime performance.

 

[E. Robert Tisdale]

I have a big class that contains code like this
(the code is automatically generated according to some configuration):

if("name1" == str) {
do;
something;
name1_specific;
}
else if("name2" == str) {
do;
something;
name2_specific;
}
else...

Now, since I have hundreds of these name1, name2, ...
the code takes forever to compile.
Even worse, if only one name changes in the configuration,
the whole code gets re-generated and I have to wait on compilation very long.

Would some amount of separate compilation be a good idea?

// main.cpp
if("name1" == str) {
processName1();
}
else if("name2" == str){
processName2();
}
else...

// name1.cpp
void processName1(void) { ... }

// name2.cpp
void processName2(void) { ... }

// ...


Now, if I have to modify name1.cpp,
it won't affect the whole code anymore, and compilation will be quick.

But does it affect runtime?
Perhaps.

Can these processName1()... functions be inlined automatically?
No.

Or does the separate compilation make that impossible?
Yes.

cat file.h

#ifndef GUARD_FILE_H
#define GUARD_FILE_H 1

#ifdef EFINE_INLINE
inline
double dot(const double x[], const double y[], int n) {
double t = 0.0;
for (int j = 0; j < n; ++j)
t += x[j]*y[j];
return t;
}
#else //EFINE_INLINE
double dot(const double x[], const double y[], int n);
#endif//EFINE_INLINE

#endif//GUARD_FILE_H

cat file.cc

#undef EFINE_INLINE
#include "file.h"

double dot(const double x[], const double y[], int n) {
double t = 0.0;
for (int j = 0; j < n; ++j)
t += x[j]*y[j];
return t;
}

cat main.cc

#include "file.h"

int main (int argc, char* argv[]) {
// code to invoke dot
return 0;
}

g++ -Wall -ansi -pedantic -c file.cc

Now, for all of your development, testing and debugging, you invoke

g++ -Wall -ansi -pedantic -o main main.cc file.o

This compiles and links quickly but may run slowly.

Then, just before you are ready to release and distribute your code,
you invoke

g++ -Wall -ansi -pedantic -DEFINE_INLINE -O2 -o main main.cc

This may take much longer to compile
but the optimized inline'd code may run much faster.

 

[Markus Dehmann]

You could make your code much simpler by having a lookup table of the
different "processes" (or whatever they are). Each element of the
lookup table array would store a string and a function pointer. Then,
your code could just iterate over the array, and call the appropriate
function pointer when there's a string match.

Thanks for your and all the other comments!

Instead of a hashtable (or map), could I also call the function directly,
given the function name as a string?

I mean, instead of this:

str = "name1";
// all function pointers have been stored in the map
funcPointer = funcPointers[str];

I would like to convert the string str into a function pointer pointing to a
function whose name equals the string content:

str = "name1";
funcPointer = &((void(*)())str) // whatever the cast syntax would look like

funcPointer would now point to a function void name1(). But I don't if such
a conversion is possible in C/C++. In Perl, it would be certainly
possible...

Remember what Knuth said: Premature optimization is the root of all
evil.

Hehe, I like that one.

Markus

 

[Joseph Turian]

David,

Iteration is no better than if-else clauses.

No better according to what criterion?

Iteration is far clearer and more easily maintained. These are mere
trifles to you?

Obviously, a constant-time algorithm is a better choice than a linear
one.

Let me repeat what I said: Premature optimization is the root of all
evil.
Code that makes your program 0.01% faster is a bad choice if it takes
you more time to implement it and/or you sacrifice clarity.

With that said, I don't think a hashmap is any less clear or more
difficult to implement than iteration.

However, it may be slower. A constant-time algorithm is not better than
a linear one for small N and large constant factors. In particular,
hash performance is typically abysmal. Since N is only about two orders
of magnitude, iteration may well be faster than hashing. And if the
distribution of the queries is non-uniform, he can move the most common
queries to the beginning of the lookup table. This is a huge speed win
that is not possible with hashing.

Joseph

 

[davidrubin]

Please review what you wrote in your previous post: you mention a
lookup table and iteration as part of the same solution. My comment
merely points out that one does not iterate when using a lookup table;
that defeats the purpose (or at least indicates that you have
sub-optimal or non-reusable implementation).

Iteration is no better than if-else clauses in terms of performance.
Obviously, initializing a vector is equivalent to initializing a map
(that is, any implementation of lookup table). However, since OP is
dealing with "hundreds" of different cases, why would you choose a
linear-time algorithm over a constant or logarithmic one?

Furthermore, your academic comments regarding the performance of
hashing versus iteration appear to be made with no consideration for
the problem posed by OP: Can we improve the compile-time of an
application without sacrificing run-time, where the apparant bottleneck
are the "hundreds" of string comparisons that must be done to locate a
particular callback.

Fortunately for OP, we can improve both the run-time and the compile
time with the added bonus of improving the mantainability of the source
code: implement each function (or group of functions) as individual
components (.h/.cpp pairs), and use a map or hashmap to implement a
lookup table based on the key value, which is a string.

Once you've done this, *now* you can consider optimizations that might
fall under the umbrella of "premature" such as cacheing, indexing into
secondary storage, pre-hashing key values, etc.

Lastly, I'm not convinced by your argument that

Since N is only about two orders of magnitude, iteration may well be
faster than hashing.

You will have to scan the entire key value to either compute the hash
value or match the first table element. If your key matches the second,
third, fourth, etc., element, the difference between hashing and
iteration is at most a constant factor. Naturally, we cannot complain
about how this small constant factor affects the run-time of specific
usage cases since we gain genericity and scalability using hashmap
(otherwise, we will make the necessary optimizations). Additionally, if
you want to amortize lookups of frequently-made queries, you cannot
simply use standard components; you will have to implement (and test,
and maintain) your own lookup table.

 

[Joseph Turian]

David,

Please review what you wrote in your previous post: you mention a
lookup table and iteration as part of the same solution. My comment
merely points out that one does not iterate when using a lookup table;
that defeats the purpose (or at least indicates that you have
sub-optimal or non-reusable implementation).

"Lookup table" may be the wrong term. Don't get locked up on it.

Iteration is no better than if-else clauses in terms of performance.

Frankly, I think that any discussion of performance is purely academic,
since OP hasn't even said that this is a bottleneck in his code. I
suspect it isn't, since it involves strings, which suggests that this
code fragment occurs at some outer location. And in this case, a
hashmap is the clearest and simplest implementation.

If this really is a bottleneck, he should think about potentially
redefining the problem, s.t. he has continuous integers as input
instead of strings. And if he can't change the problem and he
absolutely must make the code fast, then he shouldn't use iteration or
hashmaps, he should use a tree.

Joseph

 

[Joseph Turian]

P.S. I thought about it some more and I agree that, of course,
iteration is slower than hashing if there are several hundred elements.
I guess the point I was trying to make is that---in practice---I've
observed that hash implementations all seem to be pretty slow, and
should be avoided if you're trying to eke out as much performance as
possible.

Joseph