patchGNU Octave - Patches: patch #9415, Streamline hermitian transpose...


patch #9415: Streamline hermitian transpose routine of for efficiency

Submitted by:  Dan Sebald <sebald>
Submitted on:  Sun 23 Jul 2017 09:06:08 PM UTC  
Category:  None Priority:  5 - Normal
Status:  None Privacy:  Public
Assigned to:  None Open/Closed:  Open

Add a New Comment(Rich Markup)

You are not logged in

Please log in, so followups can be emailed to you.


Wed 26 Jul 2017 04:55:02 AM UTC, comment #2:

Version info from an SVG file:

Dan Sebald <sebald>
Sun 23 Jul 2017 10:00:44 PM UTC, comment #1:

I forgot replace the 8*8 with SPANC*SPANR. New patch attched.

(file #41306)

Dan Sebald <sebald>
Sun 23 Jul 2017 09:06:08 PM UTC, original submission:

Attached is a patch that improves upon the Hermitian transpose in The main oversight is the fact that no blocking is done on the last few columns, and I think that is most likely to be the case where the cache misses are going to occur. Cases where there are large numbers of rows and only a few columns (very conceivable user-construct) take a large hit as a result. Call this "partial blocking".

So I've actually simplified the code by moving those left-over partial blocks into the main save/copy loops and discarding the extra loops. Call this "full blocking".

I also found that moving fcn() to the first loop (i.e., saving into temp buffer) rather than the second loop (i.e., copying out of temp buffer) is 10% better, or so. Don't know why...probably has something to do with the function call with data that is more spread out in memory.

Then, as I looked at the resulting code, I wondered why the special case of NR > 8 and NC > 8. I constructed a test for that and found that the blocking is beneficial for certainly NR or NC equal 7. There is marginal loss for more complicated looping when NR=1 or NC=1, so I see no point in not always using the the block looping and simply tossed that second case code.

I replaced the remaining 8s with SPANC and SPANR where appropriate.

The algorithms tested are:

Test scripts:

start = cputime; x = rand(10000) + i*rand(10000); cputime - start
start = cputime; x'; cputime - start

start = cputime; x = rand(10000000,10) + i*rand(10000000,10); cputime - start
start = cputime; x'; cputime - start

start = cputime; x = rand(10,10000000) + i*rand(10,10000000); cputime - start
start = cputime; x'; cputime - start

start = cputime; x = rand(12000000,7) + i*rand(12000000,7); cputime - start
start = cputime; x'; cputime - start

start = cputime; x = rand(7,12000000) + i*rand(7,12000000); cputime - start
start = cputime; x'; cputime - start

start = cputime; x = rand(100000000,1) + i*rand(100000000,1); cputime - start
start = cputime; x'; cputime - start

start = cputime; x = rand(1,100000000) + i*rand(1,100000000); cputime - start
start = cputime; x'; cputime - start

A summary of the results are as follows:

Here's a more detailed description and numbers:

Dan Sebald <sebald>


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by sebald (Submitted the item)

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.




    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-07-23 sebald Attached File- => Added octave-hermitian_cache_full_block-djs2017jul24.patch, #41306
    2017-07-23 sebald Attached File- => Added octave-hermitian_cache_full_block-djs2017jul23.patch, #41305

    Back to the top

    Powered by Savane 3.3