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

 
 

patch #9415: Streamline hermitian transpose routine of Array.cc for efficiency

Submitted by:  Dan Sebald <sebald>
Submitted on:  Sun 23 Jul 2017 09:06:08 PM UTC  
 
Category: NonePriority: 5 - Normal
Status: NonePrivacy: Public
Assigned to: NoneOpen/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 88 with SPANCSPANR. 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 Array.cc. 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:

+verbatim*
Test scripts:

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

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

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

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

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

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

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

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 File(s):
   
   
Comment:
   

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

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

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun 23 Jul 2017 10:00:44 PM UTCsebaldAttached File-=>Added octave-hermitian_cache_full_block-djs2017jul24.patch, #41306
    Sun 23 Jul 2017 09:09:31 PM UTCsebaldAttached File-=>Added octave-hermitian_cache_full_block-djs2017jul23.patch, #41305

    Back to the top


    Powered by Savane 3.1-cleanup1