Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>What kind of processor are you testing this on? I dimly remember that unrolling loops helps when the processor can handle multiple operations at once, but only up to the maximum number of parallel executions. So if your processor can only handle 8 simultaneous instructions, then unrolling to 16 won't help. But someone with knowledge of more recent processor design will have to pipe up/correct me.</p> <p><strong>EDIT</strong>: According to <a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CBIQFjAA&amp;url=http%3A%2F%2Fwww.intel.com%2Fassets%2Fpdf%2Fperfbrief%2Fmobiletechnology.pdf&amp;ei=PrsHTMH2GZesNcCQ5bUE&amp;usg=AFQjCNEcy0M5i-USBuaiw652kSB-3m8qgQ" rel="nofollow noreferrer">this PDF</a>, the centrino core2 duo has two processors, each of which is capable of 4 simultaneous instructions. It's generally not so simple, though. Unless your compiler is optimizing across both cores (ie, when you run the task manager (if you're on windows, top if you're on linux), you'll see that CPU usage is maxed out), your process will be running on one core at a time. The processor also features 14 stages of execution, so if you can keep the pipeline full, you'll get a faster execution. </p> <p>Continuing along the theoretical route, then, you get a speed improvement of 33% with a single unroll because you're starting to take advantage of simultaneous instruction execution. Going to 4 unrolls doesn't really help, because you're now still within that 4-simultaneous-instruction limit. Going to 8 unrolls helps because the processor can now fill the pipeline more completely, so more instructions will get executed per clock cycle.</p> <p>For this last, think about how a McDonald's drive through works (I think that that's relatively widespread?). A car enters the drivethrough, orders at one window, pays at a second window, and receives food at a third window. If a second drive enters when the first is still ordering, then by the time both finish (assuming each operation in the drive through takes one 'cycle' or time unit), then 2 full operations will be done by the time 4 cycles have elapsed. If each car did all of their operations at one window, then the first car would take 3 cycles for ordering, paying, and getting food, and then the second car would also take 3 cycles for ordering, paying and getting food, for a total of 6 cycles. So, operation time due to pipelining decreases. </p> <p>Of course, you have to keep the pipeline full to get the largest speed improvement. 14 stages is a lot of stages, so going to 16 unrolls will give you some improvement still because more operations can be in the pipeline.</p> <p>Going to 32 causing a decrease in performance may have to do with bandwidth to the processor from the cache (again a guess, can't know for sure without seeing your code exactly, as well as the machine code). If all the instructions can't fit into cache or into the registers, then there is some time necessary to prepare them all to run (ie, people have to get into their cars and get to the drive through in the first place). There will be some reduction in speed if they all get there all at once, and some shuffling of the line has to be done to make the operation proceed.</p> <p>Note that each movement from src to dst is not free or a single operation. You have the lookups into the arrays, and that costs time.</p> <p>As for why the second version works so quickly, I'm going to hazard a guess that it has to do with the [] operator. Every time that gets called, you're doing some lookups into both the src and dst arrays, resolving pointers to locations, and then retrieving the memory. The other code is going straight to the pointers of the arrays and accessing them directly; basically, for each of the movements from src to dst, there are less operations involved in the move, because the lookups have been handled explicitly through pointer placement. If you use [], these steps are followed:</p> <ul> <li>do any math inside the []</li> <li>take a pointer to that location (startOfArray + [] in memory)</li> <li>return the result of that location in memory</li> </ul> <p>If you walk along with a pointer, you just do the math to do the walk (typically just an addition, no multiplication) and then return the result, because you've already done the second step.</p> <p>If I'm right, then you might get better results with the second code by unrolling its inner loop as well, so that multiple operations can be pipelined simultaneously.</p>
    singulars
    1. This table or related slice is empty.
    1. POPerformance Optimization for Matrix Rotation
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USmmr
    1. USmmr
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POPerformance Optimization for Matrix Rotation
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COI've editted my question following your advice. :-)
      singulars
      1. PO
      1. USSummer_More_More_Tea
    2. COJust a comment on your first paragraph: Loop unrolling generally isn't so much about instruction parallelism as it is about keeping the CPU's instruction fetch pipeline full.
      singulars
      1. PO
      1. USMichael Burr
    3. CO@Michael Burr: I'm going off of the thoughts in this: http://cs.oberlin.edu/~jdonalds/317/lecture18.html and also with the intel compiler, where there are directives that parallelize the independent operations inside a loop. I'm not sure if gcc does that though, or if it's as you say, with keeping the CPU pipeline full.
      singulars
      1. PO
      1. USmmr
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload