<br><br><div class="gmail_quote">On Nov 9, 2007 7:23 PM, David Cournapeau <<a href="mailto:cournape@gmail.com">cournape@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On Nov 10, 2007 1:12 AM, Travis E. Oliphant <<a href="mailto:oliphant@enthought.com">oliphant@enthought.com</a>> wrote:<br><div class="Ih2E3d">> Hans Meine wrote:<br>> > | static void<br>> > | DOUBLE_add(char **args, intp *dimensions, intp *steps, void *func)
<br>> > | {<br>> > |     register intp i;<br>> > |     intp is1=steps[0],is2=steps[1],os=steps[2], n=dimensions[0];<br>> > |     char *i1=args[0], *i2=args[1], *op=args[2];<br>> > |     for(i=0; i<n; i++, i1+=is1, i2+=is2, op+=os) {
<br>> > |         *((double *)op)=*((double *)i1) + *((double *)i2);<br>> > |     }<br>> > | }<br>> ><br>> > If I understood David correctly, he suggested an unstrided variant of<br>> > this inner loop, which simply uses pointer increments.
<br>> I'm not sure if he was saying that or not.  But, more generally, I'm all<br>> for optimizations at this level.  But, they will have to be done<br>> differently for different cases with this loop as the fall-back.
<br><br></div>I was not really clear, but yes, his was part of my argument: I don't<br>think compilers can optimize the above well when there is no stride<br>(more exactly when the stride could be done by simply using array
<br>indexing).<br><br>This would need some benchmarks, but I have always read that using<br>pointer arithmetics should be avoided when speed matters (e.g. *a + n<br>* sizeof(*a) compared to a[n]), because it becomes much more difficult
<br>for the compiler to optimize, Generally, if you can get to a function<br>which does the thing the "obvious way", this is better. Of course, you<br>have to separate the case where this is possible and where it is not.
<br>But such work would also be really helpful if/when we optimize some<br>basic things with MMX/SSE and co, and I think the above is impossible<br>to auto vectorize (gcc 4.3, not released yet, gives some really<br>helpful analysis for that, and can tell you when it fails to
<br>auto-vectorize, and why).<br><div class="Ih2E3d"></div></blockquote><div><br>The relative speed of pointers vs indexing depends on a lot of things:<br><br>1) the architecture (registers, instruction sets, implementation)
<br>2) the compiler<br>3) the code (number of base addresses, etc.)<br><br>My subjective feel is that on newer intel type hardware and using a recent compiler, indexing is generally faster. But it does depend. I wrote an indexed version of the code above:
<br><br><span style="font-family: courier new,monospace;">typedef int intp;</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
void</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">DOUBLE_add_ptr(char **args, intp *dimensions, intp *steps, void *func)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">{</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    register intp i;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">    intp is1=steps[0],is2=steps[1],os=steps[2], n=dimensions[0];</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    char *i1=args[0], *i2=args[1], *op=args[2];
</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    for(i=0; i<n; i++, i1+=is1, i2+=is2, op+=os) {</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
        *((double *)op)=*((double *)i1) + *((double *)i2);</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    }</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">}</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
void</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">DOUBLE_add_ind(char **args, intp *dimensions, intp *steps, void *func)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">{</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    const intp i1s=steps[0]/sizeof(double);</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">    const intp i2s=steps[1]/sizeof(double);</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    const intp ios=steps[2]/sizeof(double);
</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    const n=dimensions[0];</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
    double * const p1 = (double*)args[0];</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    double * const p2 = (double*)args[1];</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">    double * const po = (double*)args[2];</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    intp i, io, i1, i2;</span>
<br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">    for(i=0, io=0, i1=0, i2=0; i<n; ++i) {</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        po[io] = p1[i1] + p2[i2];</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        io += ios;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        i1 += i1s;</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        i2 += i2s;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">    }</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">}</span><br><br>Compiled with gcc -O2 -fno-strict-aliasing -march=prescott -m32 -S, the inner loop of the pointer version looks like
<br><br><span style="font-family: courier new,monospace;">.L4:</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        fldl    (%edx)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        faddl   (%ecx)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        fstpl   (%eax)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        addl    $1, %ebx</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        addl    -20(%ebp), %edx</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        addl    -16(%ebp), %ecx</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        addl    %edi, %eax</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        cmpl    %esi, %ebx</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        jne     .L4</span><br><br>While the indexed version looks like
<br><br><span style="font-family: courier new,monospace;">.L11:</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        movl    -24(%ebp), %esi</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        fldl    (%esi,%ecx,8)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        movl    -20(%ebp), %esi</span>
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        faddl   (%esi,%edx,8)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
        movl    -16(%ebp), %esi</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        fstpl   (%esi,%eax,8)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
        addl    -36(%ebp), %eax</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        addl    -32(%ebp), %ecx</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        addl    %edi, %edx</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        addl    $1, %ebx</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">        cmpl    -28(%ebp), %ebx</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">        jne     .L11</span><br><br>
Note that the indexed version is rather short of registers and has to load all of the pointers and two of the indexes from the stack.<br><br>Chuck<br><br></div></div><br>