Databases
StackOverflow2013
Postsdbo
POIs indexing vectors in MATLAB inefficient?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIs indexing vectors in MATLAB inefficient?
    primarykey
    data
    text
    <p><strong>Background</strong></p> <p>My question is motivated by simple observations, which somewhat undermine the beliefs/assumptions often held/made by experienced MATLAB users:</p> <ul> <li>MATLAB is very well optimized when it comes to the built-in functions and the fundamental language features, such as indexing vectors and matrices.</li> <li>Loops in MATLAB are slow (despite the JIT) and should generally be avoided if the algorithm can be expressed in a native, 'vectorized' manner. </li> </ul> <p>The bottom line: core MATLAB functionality is efficient and trying to outperform it using MATLAB code is hard, if not impossible.</p> <p><strong>Investigating performance of vector indexing</strong></p> <p>The example codes shown below are as fundamental as it gets: I assign a scalar value to all vector entries. First, I allocate an empty vector <code>x</code>:</p> <pre><code>tic; x = zeros(1e8,1); toc Elapsed time is 0.260525 seconds. </code></pre> <p>Having <code>x</code> I would like to set all its entries to the same value. In practice you would do it differently, e.g., <code>x = value*ones(1e8,1)</code>, but the point here is to investigate the performance of vector indexing. The simplest way is to write:</p> <pre><code>tic; x(:) = 1; toc Elapsed time is 0.094316 seconds. </code></pre> <p>Let's call it method 1 (from the value assigned to <code>x</code>). It seems to be very fast (faster at least than memory allocation). Because the only thing I do here is operate on memory, I can estimate the efficiency of this code by calculating the obtained <em>effective memory bandwidth</em> and comparing it to the <em>hardware memory bandwidth</em> of my computer:</p> <pre><code>eff_bandwidth = numel(x) * 8 bytes per double * 2 / time </code></pre> <p>In the above, I multiply by <code>2</code> because unless SSE streaming is used, setting values in memory requires that the vector is both read from and written to the memory. In the above example:</p> <pre><code>eff_bandwidth(1) = 1e8*8*2/0.094316 = 17 Gb/s </code></pre> <p><a href="https://www.cs.virginia.edu/stream/" rel="noreferrer">STREAM-benchmarked memory bandwidth</a> of my computer is around 17.9 Gb/s, so indeed - MATLAB delivers close to peak performance in this case! So far, so good.</p> <p>Method 1 is suitable if you want to set <em>all</em> vector elements to some value. But if you want to access elements every <code>step</code> entries, you need to substitute the <code>:</code> with e.g., <code>1:step:end</code>. Below is a direct speed comparison with method 1:</p> <pre><code>tic; x(1:end) = 2; toc Elapsed time is 0.496476 seconds. </code></pre> <p>While you would not expect it to perform any different, method 2 is clearly big trouble: factor 5 slowdown for no reason. My suspicion is that in this case MATLAB explicitly allocates the index vector (<code>1:end</code>). This is somewhat confirmed by using explicit vector size instead of <code>end</code>:</p> <pre><code>tic; x(1:1e8) = 3; toc Elapsed time is 0.482083 seconds. </code></pre> <p>Methods 2 and 3 perform equally bad.</p> <p>Another possibility is to explicitly create an index vector <code>id</code> and use it to index <code>x</code>. This gives you the most flexible indexing capabilities. In our case:</p> <pre><code>tic; id = 1:1e8; % colon(1,1e8); x(id) = 4; toc Elapsed time is 1.208419 seconds. </code></pre> <p>Now that is really something - 12 times slowdown compared to method 1! I understand it should perform worse than method 1 because of the additional memory used for <code>id</code>, but why is it so much worse than methods 2 and 3?</p> <p>Let's try to give the loops a try - as hopeless as it may sound.</p> <pre><code>tic; for i=1:numel(x) x(i) = 5; end toc Elapsed time is 0.788944 seconds. </code></pre> <p>A big surprise - a loop beats a <code>vectorized</code> method 4, but is still slower than methods 1, 2 and 3. It turns out that in this particular case you can do it better:</p> <pre><code>tic; for i=1:1e8 x(i) = 6; end toc Elapsed time is 0.321246 seconds. </code></pre> <p>And that is the probably the most bizarre outcome of this study - <strong>a MATLAB-written loop significantly outperforms native vector indexing</strong>. That should certainly not be so. Note that the JIT'ed loop is still 3 times slower than the theoretical peak almost obtained by method 1. So there is still plenty of room for improvement. It is just surprising (a stronger word would be more suitable) that usual 'vectorized' indexing (<code>1:end</code>) is even slower.</p> <p><strong>Questions</strong></p> <ul> <li>is simple indexing in MATLAB <strong>very</strong> inefficient (methods 2, 3, and 4 are slower than method 1), or did I miss something?</li> <li>why is method 4 <strong>(so much) slower</strong> than methods 2 and 3?</li> <li>why does using <code>1e8</code> instead of <code>numel(x)</code> as a loop bound speed up the code by factor 2?</li> </ul> <p><strong>Edit</strong> After reading Jonas's comment, here is another way to do that using logical indices:</p> <pre><code>tic; id = logical(ones(1, 1e8)); x(id) = 7; toc Elapsed time is 0.613363 seconds. </code></pre> <p>Much better than method 4.</p> <p>For convenience:</p> <pre><code>function test tic; x = zeros(1,1e8); toc tic; x(:) = 1; toc tic; x(1:end) = 2; toc tic; x(1:1e8) = 3; toc tic; id = 1:1e8; % colon(1,1e8); x(id) = 4; toc tic; for i=1:numel(x) x(i) = 5; end toc tic; for i=1:1e8 x(i) = 6; end toc end </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USangainor
    1. USangainor
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIs indexing vectors in MATLAB inefficient?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIs indexing vectors in MATLAB inefficient?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POIs indexing vectors in MATLAB inefficient?
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1. Keep on researching the mysterious ways of Matlab :)
      singulars
      1. POIs indexing vectors in MATLAB inefficient?
      1. USAndrey Rubshtein
    2. COVery interesting. I added two more to your comparison: using `length(x)` instead of `numel(x)` is much slower. Using `x = x*6;` is as fast as method 1.
      singulars
      1. POIs indexing vectors in MATLAB inefficient?
      1. USR. Schifini
    3. CO@Cyrgo: unfortunately, your comment seems to have been cut off.
      singulars
      1. POIs indexing vectors in MATLAB inefficient?
      1. USJonas
 

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