# 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. Commented Sep 30, 2013 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. Commented Oct 1, 2013 at 4:06
• Consider passing the parameters to the lambdas by const & to avoid making copies. Commented Dec 12, 2013 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. Commented Dec 12, 2013 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. Commented Mar 19, 2014 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));
}