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

Group

Main
- Main
- View members
- Search
Homepage
Download
Mailing lists
Source code
Bugs
- Submit new
- Browse
- Reset to open
- Digest
- Dependencies
- ~~Export~~
- Get statistics
- Search
Tasks
- ~~Submit new~~
- Browse
- Reset to open
- Digest
- Dependencies
- ~~Export~~
- Get statistics
- Search
Patches
- Submit new
- Browse
- Reset to open
- Digest
- Dependencies
- ~~Export~~
- Get statistics
- Search

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

Submitter:	Dan Sebald <sebald>
Submitted:	Sun 23 Jul 2017 09:06:08 PM UTC


Category:	Core : other	Priority:	5 - Normal
Status:	None	Privacy:	Public
Assigned to:	None	Open/Closed:	Open

* Mandatory Fields

Add a New Comment Rich Markup

Wed 26 Jul 2017 04:55:02 AM UTC, comment #2: Version info from an SVG file: Creator: GL2PS 1.3.8, (C) 1999-2012 C. Geuzaine For: Octave CreationDate: Tue Jul 25 23:20:59 2017	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) + irand(10000); cputime - start start = cputime; x'; cputime - start 2-A) start = cputime; x = rand(10000000,10) + irand(10000000,10); cputime - start start = cputime; x'; cputime - start 2-B) start = cputime; x = rand(10,10000000) + irand(10,10000000); cputime - start start = cputime; x'; cputime - start 3-A) start = cputime; x = rand(12000000,7) + irand(12000000,7); cputime - start start = cputime; x'; cputime - start 3-B) start = cputime; x = rand(7,12000000) + irand(7,12000000); cputime - start start = cputime; x'; cputime - start 4-A) start = cputime; x = rand(100000000,1) + irand(100000000,1); cputime - start start = cputime; x'; cputime - start 4-B) start = cputime; x = rand(1,100000000) + irand(1,100000000); cputime - start start = cputime; x'; cputime - start -verbatim- A summary of the results are as follows: SUMMARY NOBLOCK CURRENT PARTIAL FULL PARTIAL BLOCKING BLOCKING BLOCK FCN FIRST FCN FIRST NO NR,NC NO NR,NC ------- ------- --------- --------- 1) 4.05 2.62 2.37 2.35 2-A) 10.3 3.73 3.68 2.47 2-B) 2.08 1.89 1.88 1.88 3-A) 5.77 5.77 5.78 1.60 3-B) 1.59 1.60 1.59 1.58 4-A) 1.79 1.81 1.78 1.78 4-B) 1.77 1.83 1.78 1.83 Here's a more detailed description and numbers: WITHOUT BLOCKING CACHE OPTIMIZATION ----------------------------------- octave:1> start = cputime; x = rand(10000) + irand(10000); cputime - start ans = 8.5840 octave:2> start = cputime; x'; cputime - start ans = 4.0560 octave:3> start = cputime; x'; cputime - start ans = 4.0640 octave:4> start = cputime; x = rand(10000000,10) + irand(10000000,10); cputime - start ans = 9.2800 octave:5> start = cputime; x'; cputime - start ans = 10.264 octave:6> start = cputime; x'; cputime - start ans = 10.344 octave:7> start = cputime; x = rand(10,10000000) + irand(10,10000000); cputime - start ans = 8.6160 octave:8> start = cputime; x'; cputime - start ans = 2.0760 octave:9> start = cputime; x'; cputime - start ans = 2.1000 octave:10> start = cputime; x = rand(12000000,7) + irand(12000000,7); cputime - start ans = 7.2560 octave:11> start = cputime; x'; cputime - start ans = 5.7680 octave:12> start = cputime; x'; cputime - start ans = 5.7840 octave:13> start = cputime; x = rand(7,12000000) + irand(7,12000000); cputime - start ans = 6.9480 octave:14> start = cputime; x'; cputime - start ans = 1.5880 octave:15> start = cputime; x'; cputime - start ans = 1.5920 octave:16> start = cputime; x = rand(100000000,1) + irand(100000000,1); cputime - start ans = 8.4960 octave:17> start = cputime; x'; cputime - start ans = 1.7880 octave:18> start = cputime; x'; cputime - start ans = 1.8000 octave:19> start = cputime; x = rand(1,100000000) + irand(1,100000000); cputime - start ans = 8.5920 octave:20> start = cputime; x'; cputime - start ans = 1.7760 octave:21> start = cputime; x'; cputime - start ans = 1.7760 WITH CURRENT PARTIAL BLOCKING ----------------------------- octave:1> start = cputime; x = rand(10000) + irand(10000); cputime - start ans = 7.4280 octave:2> start = cputime; x'; cputime - start ans = 2.5960 octave:3> start = cputime; x'; cputime - start ans = 2.6640 octave:4> start = cputime; x = rand(10000000,10) + irand(10000000,10); cputime - start ans = 8.3680 octave:5> start = cputime; x'; cputime - start ans = 3.7320 octave:6> start = cputime; x'; cputime - start ans = 3.7400 octave:7> start = cputime; x = rand(10,10000000) + irand(10,10000000); cputime - start ans = 8.0280 octave:8> start = cputime; x'; cputime - start ans = 1.8800 octave:9> start = cputime; x'; cputime - start ans = 1.8960 octave:10> start = cputime; x = rand(12000000,7) + irand(12000000,7); cputime - start ans = 6.4800 octave:11> start = cputime; x'; cputime - start ans = 5.7680 octave:12> start = cputime; x'; cputime - start ans = 5.7720 octave:13> start = cputime; x = rand(7,12000000) + irand(7,12000000); cputime - start ans = 6.3080 octave:14> start = cputime; x'; cputime - start ans = 1.6000 octave:15> start = cputime; x'; cputime - start ans = 1.6080 octave:16> start = cputime; x = rand(100000000,1) + irand(100000000,1); cputime - start ans = 7.8640 octave:17> start = cputime; x'; cputime - start ans = 1.7960 octave:18> start = cputime; x'; cputime - start ans = 1.8320 octave:19> start = cputime; x = rand(1,100000000) + irand(1,100000000); cputime - start ans = 7.8720 octave:20> start = cputime; x'; cputime - start ans = 1.8280 octave:21> start = cputime; x'; cputime - start ans = 1.8320 WITH CURRENT PARTIAL BLOCKING AND FCN MOVED AHEAD NO NR,NC RESTRICTION ---------------------------------------------------------------------- octave:1> start = cputime; x = rand(10000) + irand(10000); cputime - start ans = 7.5600 octave:2> start = cputime; x'; cputime - start ans = 2.3520 octave:3> start = cputime; x'; cputime - start ans = 2.3920 octave:4> start = cputime; x = rand(10000000,10) + irand(10000000,10); cputime - start ans = 8.3320 octave:5> start = cputime; x'; cputime - start ans = 3.6720 octave:6> start = cputime; x'; cputime - start ans = 3.6880 octave:7> start = cputime; x = rand(10,10000000) + irand(10,10000000); cputime - start ans = 8.1120 octave:8> start = cputime; x'; cputime - start ans = 1.8720 octave:9> start = cputime; x'; cputime - start ans = 1.8800 octave:10> start = cputime; x = rand(12000000,7) + irand(12000000,7); cputime - start ans = 6.6080 octave:11> start = cputime; x'; cputime - start ans = 5.7720 octave:12> start = cputime; x'; cputime - start ans = 5.8080 octave:13> start = cputime; x = rand(7,12000000) + irand(7,12000000); cputime - start ans = 6.4880 octave:14> start = cputime; x'; cputime - start ans = 1.5920 octave:15> start = cputime; x'; cputime - start ans = 1.5880 octave:16> start = cputime; x = rand(100000000,1) + irand(100000000,1); cputime - start ans = 7.9680 octave:17> start = cputime; x'; cputime - start ans = 1.7880 octave:18> start = cputime; x'; cputime - start ans = 1.7880 octave:19> start = cputime; x = rand(1,100000000) + irand(1,100000000); cputime - start ans = 8.0720 octave:20> start = cputime; x'; cputime - start ans = 1.7840 octave:21> start = cputime; x'; cputime - start ans = 1.7840 WITH FULL BLOCKING AND FCN MOVED AHEAD AND NR,NC>=8 --------------------------------------------------- octave:1> start = cputime; x = rand(10000) + irand(10000); cputime - start ans = 8.1040 octave:2> start = cputime; x'; cputime - start ans = 2.5840 octave:3> start = cputime; x'; cputime - start ans = 2.5880 octave:4> start = cputime; x = rand(10000000,10) + irand(10000000,10); cputime - start ans = 9.1200 octave:5> start = cputime; x'; cputime - start ans = 2.4560 octave:6> start = cputime; x'; cputime - start ans = 2.4560 octave:7> start = cputime; x = rand(10,10000000) + irand(10,10000000); cputime - start ans = 8.5720 octave:8> start = cputime; x'; cputime - start ans = 1.9960 octave:9> start = cputime; x'; cputime - start ans = 2.0040 octave:10> start = cputime; x = rand(12000000,7) + irand(12000000,7); cputime - start ans = 7.1400 octave:11> start = cputime; x'; cputime - start ans = 5.7600 octave:12> start = cputime; x'; cputime - start ans = 5.7600 octave:13> start = cputime; x = rand(7,12000000) + irand(7,12000000); cputime - start ans = 6.7880 octave:14> start = cputime; x'; cputime - start ans = 1.6120 octave:15> start = cputime; x'; cputime - start ans = 1.6120 octave:16> start = cputime; x = rand(100000000,1) + irand(100000000,1); cputime - start ans = 8.3000 octave:17> start = cputime; x'; cputime - start ans = 1.7840 octave:18> start = cputime; x'; cputime - start ans = 1.8000 octave:19> start = cputime; x = rand(1,100000000) + irand(1,100000000); cputime - start ans = 8.3960 octave:20> start = cputime; x'; cputime - start ans = 1.7880 octave:21> start = cputime; x'; cputime - start ans = 1.7920 WITH FULL BLOCKING AND FCN MOVED AHEAD NO NR,NC RESTRICTION ----------------------------------------------------------- octave:1> start = cputime; x = rand(10000) + irand(10000); cputime - start ans = 7.5440 octave:2> start = cputime; x'; cputime - start ans = 2.3560 octave:3> start = cputime; x'; cputime - start ans = 2.3520 octave:4> start = cputime; x = rand(10000000,10) + irand(10000000,10); cputime - start ans = 8.4320 octave:5> start = cputime; x'; cputime - start ans = 2.4520 octave:6> start = cputime; x'; cputime - start ans = 2.4840 octave:7> start = cputime; x = rand(10,10000000) + irand(10,10000000); cputime - start ans = 8.1520 octave:8> start = cputime; x'; cputime - start ans = 1.8760 octave:9> start = cputime; x'; cputime - start ans = 1.8920 octave:10> start = cputime; x = rand(12000000,7) + irand(12000000,7); cputime - start ans = 6.6000 octave:11> start = cputime; x'; cputime - start ans = 1.5960 octave:12> start = cputime; x'; cputime - start ans = 1.6040 octave:13> start = cputime; x = rand(7,12000000) + irand(7,12000000); cputime - start ans = 6.3280 octave:14> start = cputime; x'; cputime - start ans = 1.5800 octave:15> start = cputime; x'; cputime - start ans = 1.5960 octave:16> start = cputime; x = rand(100000000,1) + irand(100000000,1); cputime - start ans = 7.8520 octave:17> start = cputime; x'; cputime - start ans = 1.7800 octave:18> start = cputime; x'; cputime - start ans = 1.7880 octave:19> start = cputime; x = rand(1,100000000) + irand(1,100000000); cputime - start ans = 7.9280 octave:20> start = cputime; x'; cputime - start ans = 1.8280 octave:21> start = cputime; x'; cputime - start ans = 1.8400	Dan Sebald <sebald>

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

Attach Files:


Comment:

Attached Files

file #41306: octave-hermitian_cache_full_block-djs2017jul24.patch added by sebald (4KiB - text/x-patch)

file #41305: octave-hermitian_cache_full_block-djs2017jul23.patch added by sebald (4KiB - text/x-patch)

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)

There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

Only logged-in users can vote.

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

Follow 3 latest changes.

Date	Changed by	Updated Field	Previous Value	Replaced by
2019-03-07	mtmiller	Category	None	Core : other
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

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

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

<a href="#postcomment">Post a Comment</a>

<a href="#discussion">Discussion</a>

<a href="#attached">Attached Files</a>

<a href="#dependencies">Dependencies</a>

<a href="#cc">Mail Notification Carbon-Copy List</a>

<a href="#votes">Votes</a>

<a href="#history">History</a>