Programming and Data Types

Program 3a -- Vector Comparison, with Loop

This program scans two sorted, input vectors and finds the elements that are common to both. It returns the indices of these common elements.

There are two versions of this program. This version, "Program 3a", processes the vectors using a while loop. The version shown afterward, as "Program 3b", replaces the loop with vectorized code. When run on MATLAB without acceleration, there is a big difference in performance between the two. When run with acceleration, there is no significant difference at all.

Operating System	MATLAB 6.1	MATLAB 6.5	Performance Gain
Windows	10.6 sec.	0.1 sec.	x 106.0
Linux	24.0 sec.	0.1 sec.	x 240.0
Solaris	1 min., 4.7 sec.	1.5 sec.	x 43.1

• function [aIndex, bIndex] = vfind_scalar(avec, bvec)
  
  avecLen = length(avec);
  bvecLen = length(bvec);
  
  % Size aIndex and bIndex to be large enough
  outlen = min(avecLen, bvecLen);
  aIndex = zeros(outlen,1);
  bIndex = zeros(outlen,1);
  
  n  = 0;
  ai = 1;
  bi = 1;
  
  while (ai <= avecLen || bi <= bvecLen)
     % Get vector elements at indices ai and bi
     A = avec(ai);
     B = bvec(bi);
  
     % If equal, record indices where elements match
     if A == B
        n = n + 1;
        aIndex(n) = ai;
        bIndex(n) = bi;
     end
  
     % Advance index of avec, when appropriate
     if A <= B
        if ai < avecLen
           ai = ai + 1;
        else
           break;
        end
     end
  
     % Advance index of bvec, when appropriate
     if A >= B
        if bi < bvecLen
           bi = bi + 1;
        else
           break;
        end    
     end
  end
  
  % Snip aIndex and bIndex to correct size
  aIndex = aIndex(1:n);
  bIndex = bIndex(1:n);
  

In preparation for running the program, you'll need to create two sorted vectors having some number of common elements. The following statements create vectors a and b, append the elements from a third vector, c, to both, and then sort. This gives vectors a and b at least 20,000 common elements.

• a = rand(200000,1);
  b = rand(260000,1);
  c = rand(20000,1);
  a = sort([a;c]);
  b = sort([b;c]);
  

Now pass a and b into the function shown above. Use the tic and toc functions to track how much time it takes to execute.

• tic;  [ia, ib] = vfind_scalar(a, b);  toc
  

What Makes It Faster

MATLAB accelerates every line in this program. The code in the while loop is what matters most since this is what takes up nearly all of the program execution time. Consider the following factors.

Supported Data Types and Array Shapes.   All of the code in the program operates on vectors of type double. This is one of the data types and array shapes that supports acceleration.

Conditional Expression Evaluates to Scalar.   The expressions in the while and if statements all evaluate to scalar values. For example,

• while (ai <= avecLen || bi <= bvecLen)
  

No Disqualifying Statements in Loop.   Every line of code in the while loop qualifies for acceleration. This means that every iteration of the loop can execute at a higher speed without being interrupted to separately process any disqualifying lines.

Function Calls and Overloading.   The only functions called are MATLAB built-ins. No M-file or MEX-file functions are called and no operations are overloaded for the data types being used.

Program 2 -- Relaxation Algorithm

Program 3b -- Vector Comparison, Vectorized