0

I am translating a piece of software from an old language to c++ and am currently in the optimization stage. The software performs a calculation of loads for several items in a number of timesteps, each of which consists of several iterative loops.

My current testing case contains 400 timesteps, each with 13 iterative loops, each calculating loads for 12 items. Now, if the resulting loads exceed a defined threshold, the item is considered lost and removed from the calculation. The issue I am having is, that the calculation time increases greatly when taking into account that items may be lost, even though the calculation skips them which I thought would descrease execution time.

The items are stored as a std::vector<loads_item*> items and what I'm evaluating at the end of each loop is:

void loads_item::check_excessive_forces()
{
    if (abs(this->force_x) > this->force_x_max) {
        this->lost = true;
    }
}

with the load-calculation checking this flag as:

void loads_container::calc_loads(...)
{
    for (size_t i = 0; i < this->items.size(); i++) {
        if (this->items[i]->is_lost()) { continue; }
        this->items[i]->calc_loads(...);
        ...
    }
}

The execution time is around 4.8s. If I remove the continue statement it drops to around 2.7s.

I am not really familiar with optimization, is this a branch-prediction issue? The pattern for the evaluation would shift from FFFFFFFFFFFF to TFFFFFTFFFFT over the course of the run but this seems rather excessive to me. Am I missing something obvious? Of course I could exchange the bool with an int and multiply the results by it to get rid of the branching but this seems ugly to me and exactly the thing I try to avoid.

4
  • If we're talking about such optimisation, you might need to put the full code. Also if we consider that the optimisation only double the time of computation in a linear way it might not be worth too much to spend time on that. If you could just make your computations parallel you can keep it clean while having it better. Finally if you make it parallel, you'll need to split your list in sublist : a good opportunity to get rid of lost items in the same time.
    – Walfrat
    Commented Aug 21, 2018 at 14:13
  • Did you take a look at the generated assembly? Maybe the compiler is able to perform some fancy optimization it the case without the if (...) continue. Maybe some instruction pipeline can be utilized in a better way if the if is dropped, because the calc_loads execution does not depend on the preceding line.
    – pschill
    Commented Aug 22, 2018 at 11:39
  • @Bowdzone Is it too asinine to just suggest a profiler here? The ones that can estimate branch mispredictions like vtune are really expensive, but even the cheap and free ones (I use only free ones outside my company) can tell you your hotspots down to individual assembly instructions. I lean on CodeXL a lot outside of work which is totally free. It is surprising to me how many developers are concerned with runtime performance that don't seem to be using profiers.
    – user377672
    Commented Nov 2, 2020 at 16:39
  • I used to have this asshole colleague who would run the debugger over release builds and just randomly pause the debugger to try to get an idea of hotspots. Total, counter-productive idiot, and caused a slew of bugs while obsessed with shaving pennies in million-pound transactions. I don't understand this stubbornness against using tools that can pinpoint things with tremendous accuracy of a sort we can't get otherwise.
    – user377672
    Commented Nov 2, 2020 at 16:43

6 Answers 6

3

Over a process which, if i've understood your description correctly, involves making decisions based on your lost field approximately 50,000 times, you're experiencing a slowdown of roughly 1 second due to those checks (or the consequence of behaviour changing after them).

A branch misprediction has a cost that varies depending on processor but is typically no more than 30 processor cycles. On a typical 2GHz machine you could be seeing as much as 1.5ms slowdown if misprediction was happening on every iteration (which would need a really bizarre dataset to achieve as modern processors are quite good at branch prediction).

The effect you're seeing is nearly 3 orders of magnitude higher, so the fault must be algorithmic in origin, not a micro optimization issue like branch prediction.

1

You are purely guessing. The huge difference seems to indicate that you either were not measuring the same thing, that calling items [i] is very slow (are you iterating through a linked list where items [i] is very slow?), or that not calling calc_loads() has side effects that you don't know about. And 2.7 seconds is an awful long time for anything that doesn't involve at least tens of millions of items.

Step through your code using a debugger and see if anything happens that you didn't expect. If that doesn't produce results, use a profiler. If you don't know how to do either, ask a colleague. But I can guarantee that branch prediction has nothing to do with your problem whatsoever, and any hacks that you attempt to solve your perceived "branch prediction" problem will only make your code more complicated and slower.

It is quite possible that using a C++ iterator makes the problem go away. And did you turn optimisation on in the compiler? C++ often relies heavily on compiler optimisation.

1
  • Thanks for the reply, I added the datatype which is a std::vector. 2.7s is actually quite fast since the calc_loads routine of items is huge. As I stated I do not intend to do any hack but search for the actual issue and possibly a better solution. I am very well aware of debugger/profile use which brought me up to this point. Using an iterator instead did unfortunately not improve anything and optimization is active (without, the run takes several minutes)
    – Bowdzone
    Commented Aug 21, 2018 at 12:01
1

Conditional execution can mess with the hardware's branch predictor, which is known to have the potential to slow things down considerably.

You might consider having two collections: one for the lost & one for not lost.  Rather than tagging an item as lost (or perhaps in addition): move it from one collection to the other.  This will have two beneficial effects: you won't find lost items in the traversal so there's fewer items to traverse, and, you won't need the conditional logic messing with the branch predictor.

It will require two collections, though, so YMMV.

(If you use the just the collection mechanism alone to identify the lost, you can also remove the is_lost() method and any associated state making the objects just that much smaller as well.)


If the size of the collection isn't changing during processing, you might also cache the size of the collection in a local variable.  Also, I'd compute this->items[i] only once each iteration, caching that in a local variable.

2
  • Also worth noting that using a linked list rather than a vector could be important if changing to the two collection strategy, as removing items from the middle of a vector can be slow.
    – Jules
    Commented Aug 21, 2018 at 18:03
  • @Jules, good thing to point out.
    – Erik Eidt
    Commented Aug 21, 2018 at 18:04
1

Unless the order of the items in the collection is important (which it doesn't appear to be, at least in any of the code you've shown), I'd partition the collection into two groups, then operate on the one:

auto part = std::partition(items.begin(), items.end(), 
    [&](item const *a) { return a->force <= force_x_max; });

std::for_each(items.begin(), part, 
    [](item *i) { i->calc_loads(...); });

If calc_loads modifies the items as it does the calculations on them, you might be better off with std::transform instead of std::for_each.

Also note that if the order of items in items does matter, it doesn't look like that's a major problem: items apparently only contains 12 pointers, so copying it takes almost no time at all. We can then partition the copy of the pointers without affecting the order of the original items or the order of the original pointers to them. Alternatively, we can combine the two steps using std::copy_if:

std::vector<item *> temp;
std::copy_if(items.begin(), items.end(), std::back_inserter(temp),
             [&](item const *a) { return i->force <= force_x_max; });

std::for_each(temp.begin(), temp.end(),
              [](item *i) { i->calc_loads(...); });

Either way, what you have right now is walking through the data once to set the flag, then making decisions based on the flag during the inner loop. By partitioning the array, we can avoid doing any such check in the inner loop at all.

It's still possible, however, that this won't help. In particular, your original code may have a highly predictable pattern of loading every item in turn. Most modern CPUs will attempt to detect reading patterns, and pre-load data based upon them. It may be that simply having some items that get processed and others that don't will (by itself) prevent that preloading from working, so attempts at optimization in this direction will always fail--but I think it's probably worthwhile to at least try partitioning to see if it works out better for your purposes.

1
  • Thanks a lot. I now think the last paragraph might be true. I now even tested a case in which i created all items, but immediately removed those from the vector which I know will be failing and still there is no improvement (which is also the case in your direct suggestions). So I assume, the actual locations where the items exist in the memory matter and there is not much I can do here. Nevertheless thank you for the good ideas.
    – Bowdzone
    Commented Aug 22, 2018 at 7:13
0

Since clearly something strange is going on: it could be that the compiler inlined the calc_loads call. But with the “continue” there, the call might not be executed at all, so the compiler decides inlining is not worth it. Check the assembler code if one has a function call and the other doesn’t.

0

I really think you ought to grab yourself a nice profiler that shows you statistics like branch mispredictions and cache misses. Done. You can get the precise answer immediately without us guessing.

That said, since I'm enjoying the conjectures, I'll offer one which doesn't relate to branch prediction at all. If your load_item data was, absent this lost member (and I'm assuming the is_lost() method is a simple accessor), a multiple of the size of a cache line (say a multiple of 64 bytes), like so:

struct loads_item
{
    ...        // 64 bytes of data
    bool lost; // extra byte
};

... which might inflate the size of a structure from, say, 64 bytes to 72 or so (depending on the alignment requirements of the first data field), then that would be one possible explanation. I offer this conjecture whether or not it's correct in this case because such awareness can help you become a bit more aware of possible data-oriented hotspots.

In such a case, when combined with how you're storing pointers to these load items (making such a cold field irrelevant as far as cache misses if it's not accessed if the items are not stored contiguously), accessing the lost member in the loop would effectively double the cache misses related to accessing these loads_item pointees, while omitting access to lost would halve them.

That's actually the most sensible "hunch" to me after years of profiling such code and focusing on a data-oriented mindset in such performance-critical contexts, provided your data actually has these characteristics and that calc_loads is not a trivial method to call (otherwise the branching could very well cost more even without too many mispredictions), though of course my hunches still aren't very reliable at all (but at least more than before I gained some experience measuring these things for years).

One thing I can say is that often any hunches I had related to branch mispredictions were far, far more often wrong than correct when I started paying attention to detailed profiling statistics in VTune. Far more often if something peculiar was going on under the hood which seemed very counter-intuitive, it was actually related to memory layout and access with CPU cache. Occasionally the optimizer was doing something weird as far as instruction selection or register allocation. But it's very rarely a case in my experience (though it could be due to the nature of code I work with), related to branch prediction.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.