How to speed-up a simple method (preferably without changing interfaces or data structures)?
I have some data structures:
all_unordered_m
is a big vector containing all the strings I need (all different)ordered_m
is a small vector containing the indexes of a subset of the strings (all different) in the former vectorposition_m
maps the indexes of objects from the first vector to their position in the second one.
The string_after(index, reverse)
method returns the string referenced by ordered_m after all_unordered_m[index]
.
ordered_m
is considered circular, and is explored in natural or reverse order depending on the se开发者_开发技巧cond parameter.
The code is something like the following:
struct ordered_subset {
// [...]
std::vector<std::string>& all_unordered_m; // size = n >> 1
std::vector<size_t> ordered_m; // size << n
std::tr1::unordered_map<size_t, size_t> position_m;
const std::string&
string_after(size_t index, bool reverse) const
{
size_t pos = position_m.find(index)->second;
if(reverse)
pos = (pos == 0 ? orderd_m.size() - 1 : pos - 1);
else
pos = (pos == ordered.size() - 1 ? 0 : pos + 1);
return all_unordered_m[ordered_m[pos]];
}
};
Given that:
- I do need all of the data-structures for other purposes;
- I cannot change them because I need to access the strings:
- by their id in the all_unordered_m;
- by their index inside the various ordered_m;
- I need to know the position of a string (identified by it's position in the first vector) inside ordered_m vector;
- I cannot change the string_after interface without changing most of the program.
How can I speed up the string_after
method that is called billions of times and is eating up about 10% of the execution time?
EDIT:
I've tried making position_m
a vector
instead of a unordered_map
and using the following method to avoid jumps:
string_after(size_t index, int direction) const
{
return all_unordered_m[ordered_m[
(ordered_m.size()+position_m[index]+direction)%ordered_m.size()]];
}
The change in position_m seems to be the most effective (I'm not sure that eliminating the branches made any difference, I'm tempted to say that the code is more compact but equally efficient with that regard).
vector
lookups are blazing fast. size()
calls and simple arithmetic are blazing fast. map
lookups, in comparison, are as slow as a dead turtle with a block of concrete on his back. I have often seen those become a bottleneck in otherwise simple code like this.
You could try unordered_map
from TR1 or C++0x (a drop-in hashtable replacement of map
) instead and see if that makes a difference.
Well, in such cases (a small function that is called often) every branch can be very expensive. There are two things that come to mind.
- Could you leave out the
reverse
parameter and make it two separate methods? This only makes sense if that doesn't simply push theif
-statement to the calling code. - Try the following for calculating
pos
:pos = (pos + 1) % ordered_m.size()
(this is for the forward case). This only works if you are sure thatpos
never overflows when incrementing it.
In general, try to replace branches with arithmetic operations in such cases, this can give you substantial speedup.
精彩评论