# Optimizing iteration through linked lists

I have a data structure composed of several std::lists, each sorted by a specific criterion. When a new item is inserted into this data structure, there is a need for a reference item already in this data structure. Also all the items between the reference and insertee need to be collected into sets.

According to the profiler, this insertion is the bottleneck of the entire program. Here I present a simplified version of my insertion method.

upperReferenceSet_.clear();
lowerReferenceSet_.clear();
for (int objective = 0; objective < nObjectives_; ++objective)
{
const  Real referenceValue = reference_->value(objective);
const  Real  inserteeValue =  insertee_->value(objective);
const bool lower = referenceValue >= inserteeValue;
const  int directionTowardsInsertee = lower ? -1 : 1;
Iterator it = referencePositions_[objective];

ReferenceSet& referenceSet = lower ? lowerReferenceSet_:
upperReferenceSet_;
const  auto comparison = lower ? [](Real a, Real b){return a >= b;}:
[](Real a, Real b){return a <= b;};

while (comparison(it->value(), inserteeValue))
{
referenceSet.insert(it->individual());
}

lists_[objective].insert(it, Node(insertee_, inserteeValue));
}


Each list is of type std::list<Node> where the Node is defined by:

class Node
{
public:
Node(Individual* ind, Real val)       :individual_(ind),value_(val){}
const Individual* individual() const  {return individual_;}
Real value() const                     {return value_;}

private:
Individual* const individual_;
const Real value_;
};


The Individual is an entity which has n values (objectives), where each value can be accessed by an Individual::value(int index) member function. There are n lists, each containing the same set of Individuals, each sorted by one objective (value). Also the objective pertaining to that list is cached in the node and can be accessed by the Node::value() member function.

I would like to ask how can I make this method faster. I suspect that there are three sources of slowness:

2. The use of lambda functions which produce another indirection.
3. The use of std::advance just to perform one step.

I am thinking of refactoring the function to pass the data structure in two passes, first for the upper reference sets and then for the lower ones. This would solve all three problems.

I am hesitating since it would result in some code duplicity. Also I am curious about any opinions on my theories and my code.

• @MartinDrozdik: The google style guide for c++ is a know terrible style guide. Find a better one. – Martin York Sep 30 '13 at 22:57
• @MartinDrozdik: C++ Coding Standards: 101 Rules, Guidelines, and Best Practices Every company you go to will have its own style guide and you must learn to adapt to the style of the company. Getting a change in a guide once is established is an uphill battle. – Martin York Oct 1 '13 at 4:06
• Consider passing the parameters to the lambdas by const & to avoid making copies. – YoungJohn Dec 12 '13 at 21:20
• Maybe consider using std::generate to build your reference set instead of your while loop. With full optimizations turned on in your compiler you might be able to get the loop unrolled a bit by using std::generate, and who knows, maybe that will give you a performance boost. – YoungJohn Dec 12 '13 at 21:24
• Your can replace lists_[objective].insert(it, Node(insertee_, inserteeValue)); by lists_[objective].emplace(it, insertee_, inserteeValue);, but I doubt that you will have any relevant performance gain. – Morwenn Mar 19 '14 at 13:43

I haven't tested this solution, but I believe that your code could be simplified by using a reverse_iterator.

upperReferenceSet_.clear();
lowerReferenceSet_.clear();
for (int objective = 0; objective < nObjectives_; ++objective)
{
const  Real referenceValue = reference_->value(objective);
const  Real  inserteeValue =  insertee_->value(objective);
const bool lower = referenceValue >= inserteeValue;
Iterator it = referencePositions_[objective];
if (!lower)
{
it = std::reverse_iterator<Iterator>(it);
}
ReferenceSet& referenceSet = lower ? lowerReferenceSet_:
upperReferenceSet_;

do
{
referenceSet.insert(it->individual());
} while (it++->value() != inserteeValue);

lists_[objective].insert(--it, Node(insertee_, inserteeValue));
}