[Octave-bug-tracker] [bug #59840] repmat and repelem slower than needed, faster implimentation suggested

[Rik]

Follow-up Comment #2, bug #59840 (project octave):

A true replacement for repmat needs to not only accept an arbitrary number of
dimensions as pointed out in comment #1, but it also needs to accept mostly
arbitrary input including non-numeric input.

This code, for example, is perfectly acceptable


x.a = "123";
x.b = 456;
y = repmat (x, [2, 3])


but fails with the proposed repmatrixfast.

Also, there needs to be input validation to check the elements are correct. 
Your implementation is the core of the algorithm, but I suspect that a large
fraction of the difference is simply that required validation.  This could be
checked with tic/toc calls around just the input validation section.

The beauty of Free Software is that you can go look at the source  code
yourself.  The repmat.m function already has a specialization for 2-D inputs. 
The code is


  elseif (ndims (A) == 2 && length (idx) < 3)
    if (issparse (A))
      x = kron (ones (idx), A);
    else
      ## indexing is now faster, so we use it rather than kron.
      m = rows (A); n = columns (A);
      p = idx(1); q = idx(2);
      x = reshape (A, m, 1, n, 1);
      x = x(:, ones (1, p), :, ones (1, q));
      x = reshape (x, m*p, n*q);
    endif


Form the comments, some programmer has checked the relative speed of indexing
versus kron and decided on indexing.  If I excerpt just this piece of code in
to a new function


function x = repmatidx (A, p, q)
  ## indexing is now faster, so we use it rather than kron.
  m = rows (A); n = columns (A);
  #p = idx(1); q = idx(2);
  x = reshape (A, m, 1, n, 1);
  x = x(:, ones (1, p), :, ones (1, q));
  x = reshape (x, m*p, n*q);
endfunction


and then add it in to the test script I get these timings


Origional attempt
Elapsed time is 2.06363 seconds.
with faster repmat
Elapsed time is 0.880177 seconds.
with faster repmatidx
Elapsed time is 1.33363 seconds.
single repmat call
Elapsed time is 1.28122 seconds.
with faster repmat
Elapsed time is 0.560874 seconds.
loop solution
Elapsed time is 0.278732 seconds.


So the kron solution is still faster.  Note that in repmat.m there is a
special case path for sparse matrices.  One could imagine changing the test
from "issparse (x)" to "isnumeric (x)" to get all numeric matrices.  I tried a
new function


function x = repmatkron (A, p, q)

  x = kron (ones ([p, q]), A);

endfunction


which will only work for numeric matrices.  When I run the original test code
the runtime is 0.70 versus the 0.88 of your implementation.  The difference is
probably due to the minor amount of input argument decoding your function has.
 Since kron() works on logical matrices (but not character matrices) it might
be enough to change the special case to


if (isnumeric (A) || islogical (A))


Separately, the reason why the 'loop' scenario is fast is because it isn't
really a loop.  The top of the script defines 'i = 2' and thus the loop


for k=[1:i-1]
===
for k=[1:2-1]
===
for k=[1:1]


So that loop just executes once.  In the second loop, nv =4, and so it isn't
much of a loop either


for k=i+1:nv
===
for k=2+1:4
===
for k=3:4


So this loop executes twice for the values '3' and '4'.



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?59840>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/