Speeding Up Logical Operations

Hi Guys,

I am trying to uses the function below

function coords = distancePerBound(coords,L)
  hL = L/2;
  coords(coords > hL) = coords(coords > hL) - L;
  coords(coords < -hL) = coords(coords < -hL) + L;
end

where coords is a 3xn (where n is ~100,000). In the function that uses it, this function gets called many times and is a bottle neck in speed. Is there any thing I can do to improve this?

On a side note, I know that for a vector 'x', x.*x is faster than x.^2. Is there any speeding possibility for 1./x as well? Thank you.

Answer 1

[Matt J]

      function coords = distancePerBound(coords,L)
        hL = L/2;

        idx=coords > hL;

        coords(idx) = coords(idx) - L;

        idx=coords < -hL;

        coords(idx) = coords(idx) + L;
      end

[Amit]

Matt, this improves the speed a little bit.

[Sean de Wolski]

If one of the ops could be changed to >= or <=, or you know that no value will be equal, then you could negate the idx (~idx) which should be faster than recomputing > hL.

[Sean de Wolski]

Also, when you call this function, are you reusing coords as the output?

whatever;
coords = distancePerBound(coords,L)
etc;

If so, I don't see any reason why the operation would not be done in-place thus not requiring a memory copy of coords.

[Amit]

Sean, actually no because the second time it calculates less than (-hL) not less than hL.

[Matt J]

Sean,

Complenting idx (~idx) would not work even with nonstrict inequalities >=, <=. Note that the second logical operation involves -hL instead of +hL.

[Sean de Wolski]

Ahh! minus signs matter!

[Carlos Adrian Vargas Aguilera]

Well, after all you already get important info with >hL. Maybe

function coords = distancePerBound(coords,L)
    hL           = L/2;
    idx          = coords > hL;
    coords(idx)  = coords(idx) - L;
    idx(~idx)    = coords(~idx) >= -hL;
    coords(~idx) = coords(~idx) + L;
end

Answer 2

[Adam]

What does the profiler say about the speed of this?

Is it the function that is slow or the number of times you call it?

Within the function it is vectorised, but calling it many times lessens that effect because the many calls are not vectorised together.

Can you not concatenate the data input to the many calls to make just a single call?

Again though this comes down to where exactly the profiler is pointing to as being slow.

As an aside there are various alternatives that can be tried. If it were me and this function were found to be slow I would create a quick test script containing as many of those options as I can think of and see which is fastest because it is often hard to tell without simply trying and timing the different implementations.

[Amit]

The profiler suggests that both lines take same amount of time.

What you mean (or how can I identify) by 'Is it the function that is slow or the number of times you call it?'

Concatenate the data input? Any suggestions how?

[Matt J]

Like so:

    >> coords1=reshape(1:12,3,[])

    coords1 =

         1     4     7    10
         2     5     8    11
         3     6     9    12

    >> coords2=reshape(13:24,3,[])

    coords2 =

        13    16    19    22
        14    17    20    23
        15    18    21    24

      >> coords=[coords1,coords2]; distancePerBound(coords,L);

      coords =

           1     4     7    10    13    16    19    22
           2     5     8    11    14    17    20    23
           3     6     9    12    15    18    21    24

[Adam]

The profiler will tell you how many calls there are to a function and you can determine from that whether an individual call is slow or the whole lot of calls. If total call time is 1000s and you call it twice then each call is 500s which is clearly a lot. If the total call time is 1000s and you call it 1 million times then each call is 0.001s which is not significant for an individual call, but clearly the number of calls is a problem.

x1 = rand( 3, 100000 );
x2 = rand( 3, 120000 );

x = [x1 x2];

will concatenate two inputs of the type you suggest into a single input that you can run through that vectorised function.

Not knowing where all your inputs come from and when though I don't know if that is possible.

[Amit]

I think I should further clarify. The concatenation is not possible in this fashion because the function is called in a loop. These are Monte Carlo type simulations and the function gets called in every loop.

[Adam]

How long is a single call to the function actually taking?

When I run it on random data of the size you suggest it takes 0.03s for a single call.

So is the total time of your loop so relatively fast that that kind of time is really a bottleneck?

[Amit]

Adam, a single call takes ~0.015 s but this function gets called nearly ~100000 times in other function.The other function which calls it, actually does many other operations and I have removed all the bottlenecks in that function and overall time in those processes is much much lower than the time taken by distancePerBound() shown here.

The processing is on same size of matrix in both functions. I just thought that I might be doing something (which could be improved) as an overhead in this simple function which checks only 2 conditions.

[Adam]

In that case it would come down to what i said earlier I guess. Create a simple test program with different implementations of that one function, make sure they all give the same answer, time them all and see if any is faster than the current.

I don't personally see much that I would be able to say would be a lot faster than you have, but optimised functions in Matlab can be strange sometimes so only the implementation and timing of the alternatives will tell for sure.

[Amit]

Very true Adam. Actually that was what I was doing :P when I ran out of ideas, I thought to ask more experienced programmers here !!