How to make your code more effic

Home Reconstruction   E-mail Notes Meetings Subsystems Search

How to make your code more efficient ?

with contributions from Ivan Belyaev, Marco Cattaneo, Chris Jones, Matthew Needham,  ....

more efficient = faster, simpler, slimmer 

from to

 

 

 

Recommended code changes

Subject Date

VELO

ST RICH CALO Muon Tracking PID Trigger
Inherit your Algorithms and Tools from the new Gaudi base classes 1.7.2004   P P          
Use of Boost utilities is encouraged, see also SEAL utility table                  
Use of  GSL and Mathlib                  
Linker instead of relations                  


Simple optimization guidelines  (random order)

  1. String manipulation:
  2. Use STL algorithm instead of explicit loops.
  3. Boost library: Avoid adding the corresponding '#include' directives into *.h files!
  4. If you fill a vector with more than a few (5 ?) elements using push_back, call reserve() first.
  5. The fastest way to copy elements from one vector to another is the insert member function. Prefer it to, for example copy.
  6. Issue of pow
  7. Be careful with inline function, they might not get inlined by the compiler.
  8. Do not create MsgStream in event loop when not necessary, add test on outputLevel.
    (Taken care automatically if using the methods of the GaudiAlgorithm base class)
  9. Don't use == or != between floats or doubles

 

 

Less of Importance

  1. Use prefix not postfix, ++ not ++  
  2. Test on empty(), not size()
  3. Prefer the initialization list in constructors as opposed to assignment in the constructor body.


 

Good Practice

  • Test code with valgrind and remove all warnings (uninitialised variables, memory leaks), see also LCG website
  • Code Profiling and Analysis
  • Have a look at effective C++ books: Effective C++,  More Effective C++, Effective STL.
     

New base classes:

Inherit your Algorithms and Tools from the new base classes GaudiAlgorithm and GaudiTool ... and make use of the new methods available in these bases.
 

Advantages:

  • Much less code. In ST, around 1000 lines of code saved.
  • More control of debug, messaging options
  • Easier retrieval of tools and services
  • Easier retrieval of data from the store
  • Exception handling
  • Automatic counting of number of warnings in a job.
  • Much easier histogramming
     

Practical implementation:

  • Follow examples in Vanya note (updated 26 July'04), PDF file
  • Look what has already been implemented by other sub-detectors.

< Back to Top >


Linkers versus Relation Tables

Relation Tables: general purpose, source and target can be any object, weight anything including an object. LHCb 2004-022

If speed becomes an issue:

Linker implementation, LHCb 2004-007:

  • Works only with KeyedObject inserted in a container
  • Can not be looked at as a STL container with iterators
  • Reading is fast
  • Simple access

< Back to Top >


Boost utilities,   http://seal.web.cern.ch/seal/snapshot/workbook/boost.html and recommend a few selected utilities (lexical_cast, format, ...)

 

On the issue of empty() vs size(). For associative containers such as maps the implementation of size() can be quite inefficient (see Effective STL). On the other hand empty() is just a one line function returning true or false. You cannot go wrong with empty(), but you can go wrong with size() .

< Back to Top >


The prefix operator will always be faster than the postfix. The postfix version involves a copy and internal call to the prefix. For simple types the relative cost between the two should be small. For more complicated objects (e.g. iterating over a vector) the cost may be larger. The general consensus in C++ literature (More Exceptional C++, More Effective C++) is that the prefix version should always be preferred. Doing this you cannot go wrong. In addition, writing ++ instead of ++ costs nothing.

< Back to Top >


Syntax for boost::lexical_cast:

std::string one = boost::lexical_cast<std::string>(1);
unsigned int = boost_lexical_cast<unsigned int>(one);

< Back to Top >


Use STL algorithm instead of explicit loops. The implementation of "typical" STL algorithm already takes *ALL* possible advantages.
Examples:
Assume that one have some sequence of doubles, it can be e.g. std::vector<double> , double[] , boost::array , etc.. To use algorithm one need only to define the 'begin' and 'end' for sequence.

typedef std::vector<double> container ;
typedef container::iterator iterator ;
 

  1. Find zero element:

    container a = ... ;
    iterator it = std::find( a.begin() , a.end() , 0.0 ) ;
    if( it != a.end() ) { /* element is found! */ }

    or in a more compact way:

    if( a.end() != std::find( a.begin() , a.end() , 0.0 )
    {
    /* element is found! */
    }
    else
    {
    /* there is no elemenet equal to 0.0 */
    }
     
  2. count number of elements, equal to 1.0 :
    size_t number = std::count( a.begin() , a.end() , 1.0 ) ;
     
  3. apply some function to element and produce vector of results:

    container b( a.size() , 0.0 ) ;
    std::transform( a.begin() , a.end() , b.begin() , sin ) ;
     
  4. And one have many more algorithms :
    for_each,mismatch,sort,eliminate_duplicates,binary_search,random_shuffle,next_permutation,accumulate,...
    And all of them are described in many good books, especially in the 3rd edition of B.Straustrup's book.
    Important feature is the algorithm can be applied to *ALL* sequences, e.g. to C-array:

    const size_t Length = 100 ;
    double a[Length] ;
    typedef double* iterator ;

    iterator begin = a ;
    iterator end = a + Length ;

    // sort the sequence
    std::sort( begin , end ) ;
    // count number of values equal to 1.0
    size_t number = std::count( begin , end , 1.0 );

< Back to Top >


Inline function: be careful, otherwise they will not get inlined by the compiler. Don't make them too long  (a few lines are reccomended) and only have one return statement, i.e.use
            return ( a > 0 ? b : c);
instead of
            if ( a > 0 ) {
                return b;
            } else {
               return c;
            }

< Back to Top >


Each time where one has even some very rough estimates on APPROXIMATE size of container (5-10-100-...-1000000) one should use "reserve" before "insert" or "push_back/push_front" etc...

The only one exception is e.g. vector/list/container of VERY large objects. For this case one could loose if an initial guess is ABSOLYTELY wrong
(e.g. if 'typical' size of container is 5 and one invokes reserve(100000) for container of LARGE objects)

Indeed a combination of proper "reserve" with ANY way of copying elements of a vector in very efficient.
(Indeed "insert" internally does the same stuff - it invokes a proper "reserve" and then moves the data blocks).

< Back to Top >


Boost library: Avoid adding the corresponding '#include' directives into *.h files!
The implementation *.cpp files should be used for this purpose! All boost-stuff is highly templated/inlined and it can take ages to compile it. One can drastically decrease this by avoiding the uncontrolled expansion of boost-header files through local header-files.

< Back to Top >