Advanpix vs.VPA – Array Manipulation Operations

by Pavel Holoborodko on November 14, 2014

New version of toolbox (≥3.7.2) has updated engine for array manipulation operations. We would like to show the improved timings and compare with previous version.

The very basic array manipulation operations (subscripted assignment, reference and concatenation) play crucial role in overall performance of the program. The poorly designed and implemented they might deteriorate the speed to the point when program actually spends more time in array indexing then computation itself.

MATLAB interpreter has extremely optimized basic operations for built-in “double” and “single” precision matrices. However situation is quite different when it comes to arrays of custom-defined types (like our multiple-precision class – mp).

As it was reported earlier [1], array manipulation functions provided by MATLAB for custom-defined types have absolutely unacceptable level of performance. We have investigated the issue and proposed our solution [1,2,3].

As a quick demo, here is comparison of sequential element-wise assignment (without pre-allocation):

% Variable-precision arithmetic (Symbolic Math Toolbox, MATLAB R2014a)
p = vpa('pi');
tic
for ii = 1:300
for jj = 1:300
   A(ii,jj) = p;
end
end
toc
 
Elapsed time is 848.209 seconds.
 
% Multiprecision Computing Toolbox >= 3.7.2
p = mp('pi');
tic
for ii = 1:300
for jj = 1:300
   A(ii,jj) = p;
end
end
toc
 
Elapsed time is 7.17263 seconds.

Symbolic Math Toolbox/VPA requires 14 minutes to just fill the 300x300 matrix!
Advanpix toolbox does the same in 7 seconds (118 times faster).

Pre-allocation does make things a little better:

% Variable-precision arithmetic (Symbolic Math Toolbox, MATLAB R2014a x64)
A = vpa(zeros(300,300));
p = vpa('pi');
tic
for ii = 1:300
for jj = 1:300
   A(ii,jj) = p;
end
end
toc
 
Elapsed time is 166.89 seconds.
 
% Multiprecision Computing Toolbox >= 3.7.2
A = mp(zeros(300,300));
p = mp('pi');
tic
for ii = 1:300
for jj = 1:300
   A(ii,jj) = p;
end
end
toc
 
Elapsed time is 6.6745 seconds.

Still there is a 25 times difference in speed.

Timings for more advanced tests, like random sub-matrix assignment/reference, combined sudsasgn & subsref and different variants of concatenation are presented in the table:

Array manipulation operations

Test Id Timing (sec)Speed-up (times)
VPA 3.6.73.7.2Over VPAOver 3.6.7
subsref(1) 28.78 8.404.875.91.7
subsref(2) 294.39 8.885.4254.31.6
subsasgn(1) 74.77 16.523.0424.65.4
subsasgn(2) 317.53 16.933.4791.54.9
combined(1) 670.48 25.748.8475.82.9
vertcat(1) 21981.68 4.233.775830.51.1
horzcat(2) 22750 4.233.766050.51.1
cat(5) 24507 4.173.766517.81.1

This is not a joke, VPA requires a lot of time to do the simple concatenation tests. For example, it spent 6 hours on the following vertical concatenation test:

B = vpa(rand(200,200));                      
s = 0;
for i=1:2000 
    tic;    
    [B; B];
    s = s + toc;    
end;
fprintf('\tvertcat(1):    %.2f sec\n', s);

Multiprecision toolbox completes the same test in under 4 seconds.

Complete code with all tests can be downloaded here [5]. Please run it in your environment to check the results.

Notes.
– Test environment: 64-bit Windows 7, Core i7 930 @ 2.8GHz, MATLAB R2014a x64 bit.
– Speed-up ratio over older version – 3.6.7 is even higher on Linux and Mac OSX.

{ 0 comments… add one now }

Leave a Comment

Previous post:

Next post: