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

[Rik]

Update of bug #59840 (project octave):

                  Status:                    None => In Progress            

    _______________________________________________________

Follow-up Comment #6:

I wrote an objective function to attempt to find a constant to use to switch
between an indexing implementation or a kron-based implementation.  The
function is attached and listed below.


function retval = objf (x)

  m = round (x(2));  n = round (x(1));

  p = 50;  q = 50;
  A = rand (m, n);
  N = 1000;

  tic;
  for i = 1:N
    tmp = repmatidx (A, p, q);
  endfor
  tm.idx = toc;

  tic;
  for i = 1:N
    tmp = repmatkron (A, p, q);
  endfor
  tm.kron = toc;

  retval = tm.idx - tm.kron;
  
endfunction


First, I found that individual measurements of timing bounced around too much
so I ran each timing test 30 times (N = 30) in order to try to get more
consistent results.  That still didn't work very well.  Eventually I bumped it
to N = 1000.

Using fminsearch() did not work for me.  The algorithm had difficulty
converging.  This may be because there is still to much  variability in the
result returned from the objective function.

But I did notice some trends.  When M and N, and likewise P and Q, are roughly
equal implying roughly square matrices the indexing operations tend to be
faster.  If, instead, M and N or P and Q are vastly different implying a very
rectangular matrix then kron works better.

The choice to switch between the two implementations probably needs to be more
in depth than just summing the number of rows and columns.

As an example, with p=25, q=25:

objf ([100, 100]) = -1.4   # implies indexing is better
objf ([199, 1  ]) = +.06   # implies kron is better

In both of these case M+N = 200 so a decision based only on that sum cannot
distinguish these two cases.

It does make me think that this is very input data dependent.  Can you
discover a more precise criterion for switching between implementations?

(file #50727)
    _______________________________________________________

Additional Item Attachment:

File name: objf.m                         Size:0 KB
    <https://file.savannah.gnu.org/file/objf.m?file_id=50727>



    _______________________________________________________

Reply to this item at:

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

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