CODEWITHSUNDEEP
cperformance
lightburst
lightburst

Reputation: 231

Concerning efficiency, logical compares vs redundant memory manipulation

Which is more taxing? Is enclosing an array element exchange with a conditional if statement to prevent redundant exchanges, like say exchanging with itself, more efficient?

Or is having to check for an only probabilistic condition all the time more inefficient? Say the chance of the special condition increases every invocation.

Say you're developing an algorithm and is trying to check for efficiency: compares or exchanges(like insertion sort).

if(condition)
   exchange two elements

Upvotes: 1

Views: 96

Answers (2)

Mike Dunlavey
Mike Dunlavey

Reputation: 40679

A useful way to look at any condition-evaluation code to ask, "What is the probability of each outcome?"

For example, it there's a test expression test, and it's probability of being true is 1/100, then on average it is telling you very little, for your investment in processor cycles.

In fact you can quantify that. If it's true, then the the amount of information you've learned is pretty good. It is log2(100/1) = 6.6 bits, roughly, but that only happens 1 out of 100 times. The other 99 times, the amount of information you learn is log2(100/99) = .014 bits. Practically nothing. So a condition like that is telling you very little, on average. It's not "working" very hard.

A good way to finish quantifying it is to multiply what you learn from each outcome by the probability of that outcode, and add those up. That tells you what you learn on average.

That is 6.6 * 1/100 + .014 * 99/100 = .066 + .014 = .08 bits, which is very poor. (This number is called the entropy of the decision.)

On the other hand, if you have a decision point where each outcome is equally likely, it learns a full 1 bit on average. In fact that's the most work a binary decision can possibly do.

So if you're worried about the performance of a conditional test (you may not be) try to make it earn its cycles.

Upvotes: 0

Necrolis
Necrolis

Reputation: 26181

This very much depends on your processor architecture, how often this would be done, the throughput its required to handle and the cost of doing said exchanges, in which case, the only viable, real world-answer is: "profile, profile and profile some more".

Basically, if you CPU suffers badly from branch miss-prediction, and the swapping of elements is trivial, then its makes sense to leave out the conditional. however, if your target CPU architecture can support a fair amount of branch miss-predictions with cause too much stalling or the cost of swapping elements is not trivial, then you might gain performance, depending on the size of said array. you may also benefit from the use of instructions like MOVcc/CMPXCHG, or there non-x86 counterparts (though it this situation, you'd still need a read + compare, but it removes the branching).

With so many variable inputs, it makes sense to profile your code and find where its really bottlenecking, things like VTune or CodeAnalyst will also give you stats on branch miss-prediction so you can see how much it affects your algorithm as a whole.

Upvotes: 3

Related Questions