Fastest way to get minimum of four integer values?

[anders.johansen@gmail.com]

Hi,

I have a tight loop where I basically do this over and over (millions
of times):

int cell = <calculation>
const int above = <calculation>
if (cell above) cell = above;
const int below = <calculation>
if (cell below) cell = below;
const int trans = <calculation>
if (cell trans) cell = trans;

Is there a faster way to do this?

Sincerely,
Anders

[kasthurirangan.balaji@gmail.com]

Re: Fastest way to get minimum of four integer values?

On Apr 1, 1:42 pm, anders.johan... @gmail.com wrote:

Hi,
>
I have a tight loop where I basically do this over and over (millions
of times):
>
int cell = <calculation>
const int above = <calculation>
if (cell above) cell = above;
const int below = <calculation>
if (cell below) cell = below;
const int trans = <calculation>
if (cell trans) cell = trans;
>
Is there a faster way to do this?
>
Sincerely,
  Anders

the if could be replaced like
cell=(cell trans ? trans : cell);

By replacing i cannot say what would be the improvement. There are
other factors to be considered.
moreover, you haven't said anything about the <calculations >. you may
also want to consider running in parallel. all depends on what you are
trying to achieve, about which you haven't said much.

Thanks,
Balaji.

[Martin]

Re: Fastest way to get minimum of four integer values?

On Apr 1, 1:42 pm, anders.johan... @gmail.com wrote:

Hi,
>
I have a tight loop where I basically do this over and over (millions
of times):
>
int cell = <calculation>
const int above = <calculation>
if (cell above) cell = above;
const int below = <calculation>
if (cell below) cell = below;
const int trans = <calculation>
if (cell trans) cell = trans;
>
Is there a faster way to do this?
>
Sincerely,
  Anders

One obvious improvement is moving all <calculations(o r at least some
of them) out of the loop, if it's possible. If no - IMO there is no
considerable improvement.

[Kai-Uwe Bux]

Re: Fastest way to get minimum of four integer values?

anders.johansen @gmail.com wrote:

Hi,
>
I have a tight loop where I basically do this over and over (millions
of times):
>
int cell = <calculation>
const int above = <calculation>
if (cell above) cell = above;
const int below = <calculation>
if (cell below) cell = below;
const int trans = <calculation>
if (cell trans) cell = trans;
>
Is there a faster way to do this?

Not from an algorithmic point of view. To find the minimum of four
values will require computing all of them and three additional comparisons.

On the other hand, there could be bit-fiddling techniques to find the
minimum without using branch operations. This can lead to better pipelining
on some processors. See, for instance:

https://www.cellperformance.com/articles/2006/04/benefits_to_branch_elimination.html

YMMV


Best

Kai-Uwe Bux

[Puppet_Sock]

Re: Fastest way to get minimum of four integer values?

On Apr 1, 4:42 am, anders.johan... @gmail.com wrote:

I have a tight loop where I basically do this over and over (millions
of times):
>
int cell = <calculation>
const int above = <calculation>
if (cell above) cell = above;
const int below = <calculation>
if (cell below) cell = below;
const int trans = <calculation>
if (cell trans) cell = trans;
>
Is there a faster way to do this?

Question: In the above psuedo code, the various <calculation>
entries use a lot of time, yes? That is, the various if-greater
tests are a tiny portion of the overall run-time, yes?
So, if the calcs happen every time through this loop, you
probably will find more opportunity for optimizing in those
calcs rather than the comparatively small potential in
the if-greater tests.

Also: Every time somebody starts asking about "make it faster"
I have a standard response I trot out. Where's your stop-watch?
Where's your performance spec? First measure how much time
various parts of the code take to run. Then look to your spec
to see if that is acceptable. If you've made the spec, relax!
And don't sweat the stuff that takes a small part of the time.
Socks

[anders.johansen@gmail.com]

Re: Fastest way to get minimum of four integer values?

Hmmm,

How about this:

int cell = (acceptMatrix[false][source[i-1]][target[1]]) ?
distmatrix[i-1][1] : distmatrix[i-1][1]+1 ;
// Newval replaces above. All add one instrs. moved down
int newval (distmatrix[i-1][2]);
const int left (distmatrix[i][1]);
const int trans (
distmatrix[i-2][0] +
(!acceptMatrix[false][source[i-2]][target[1]]) +
(!acceptMatrix[true][source[i-1]][target[0]])
);
if (left < newval) newval = left;
if (trans < newval) newval = trans;
// Add one moved here
if (++newval < cell) cell=newval;
if (distmatrix[i][2]=cell < thismin) thismin=cell;

This saves two "+ 1" instructions, and replaces the remaining one with
a preincrement. The ++newval could (should?) be moved out of the if
statement for clearer code.

[James Kanze]

Re: Fastest way to get minimum of four integer values?

On Apr 7, 2:15 am, Martin York <Martin.YorkAma ...@gmail.comwr ote:

On Apr 6, 2:43 pm, Daniel Pitts

<newsgroup.spam fil...@virtuali nfinity.netwrot e:

Array lookups aren't terribly expensive, but they do have a cost. if
you can save a reference to distmatrix[i-1] (since its used in a few
places), that might shave a nanosecond or two.

Daniel Pitts' Tech Blog: <http://virtualinfinity .net/wordpress/>

Not sure I buy that. Could be wrong!

More to the point (and this applies to the last response by ppi
as well, concerning pipeline stall): the compiler knows this
better than you, and turning on optimization will normally
result in the best solution here. Compilers have been caching
array accesses and common subexpressions for several decades
now, and all modern compilers know about pipelines, memory
caches, etc., and take them into account when optimizing. All
such micro-optimizations do in source code is make it more
convoluted---more difficult for the human reader to understand,
and more difficult for the compiler to optimize.

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34