Re: [Fwd: saw your comments on hacker news]

[Daniel J Sebald]

On 11/19/2016 02:38 PM, Daniel J Sebald wrote:
> On 11/19/2016 11:47 AM, John Swensen wrote:
[snip]
> > I wish we could find some language/interpreter expert with lots of time
> > to spend on JIT for Octave. Most discussions I have with students and
> > other researchers who have used Octave in the past (and reiterated in
> > the ycombinator discussion), their complaint has always been the speed
> > of for loops and lack of JIT. The problem is that it really requires
> > pretty much a domain expert on JIT to keep a robust solution always up
> > to date with a language.
[snip]
> Let's take a look at the example in that link, and perhaps you or
> someone else at that link could explore things just a little more and
> give insight.
>
> A smart interpreter would realize that the expression
>
> for i=1:100 for j=1:100 k=x(i,j); end; end;
>
> could be evaluated as
>
> k=x(100,100)
>
> and done.  (And maybe Octave should be that perceptive.)  My point is
> that the above loop isn't of much intrinsic value, so it really isn't
> worth it being a point of comparison.  Instead, I'd think comparing
> something like the following is more meaningful:
>
> octave:38> x=rand(300);
> octave:39> k=ones(300);
> octave:40> tic; for i=1:300 for j=1:300 k(j,i)=x(i,j); end; end; toc;
> Elapsed time is 1.69623 seconds.
>
> That is, a loop interpreter couldn't reduce the loop to something
> independent of i and j and quickly get the final result.  (A person can
> recognize that this is simply k = x', sure, but not a general looping
> mechanism.)
>
> So, I'd say make that comparison between the two programs.  It will tell
> us whether something inherent in Octave looping is really time consuming
> or whether Octave just needs to be a little smarter in recognizing
> certain conditions.

In an attempt to answer my own question, here are a few times of interest:

octave:38> x=rand(300);
octave:50> tic; k = x'; toc;
Elapsed time is 0.000827074 seconds.
octave:51> tic; for i=1:300 for j=1:300 k(j,i)=x(i,j); end; end; toc;
Elapsed time is 1.7148 seconds.
[The transpose operation is blazing fast compared to looping transpose.]

octave:52> tic; for i=1:300 for j=1:300 ; end; end; toc;
Elapsed time is 0.022603 seconds.
[Looping that does nothing consumes a fair amount of CPU, using the k=x' 
as measure.]

octave:53> tic; for i=1:300 for j=1:300 k=3; end; end; toc;
Elapsed time is 0.037637 seconds.
[Doing something within the loop adds some, but without using an index 
it isn't much.]

octave:56> tic; for i=1:300 for j=1:300 k(j,i)=3; end; end; toc;
Elapsed time is 0.871632 seconds.
[OK, here's a factor of ten jump by indexing into the array.]

octave:57> tic; for i=1:300 for j=1:300 k(2,5)=3; end; end; toc;
Elapsed time is 0.661854 seconds.
[Using array indexing, but not the loop iterators is also consuming a 
fair amount of CPU.]

Maybe some speedup can be achieved in the interpreter array indexing 
mechanism; don't know.

So, what is JIT meant to do?  Is it supposed to be something that takes 
the looping expression and "internalize" it?  That is, rather than 
interpret the line "k(j,i)=x(i,j)" for each iteration

for i=1:300
  for j=1:300
    INTERPRET["k(j,i)=x(i,j)"]
  end
end

it should first interpret it's contents and then loop?  I.e.,

CodeHunkOfSomeSort(i,j) = INTERPRET["k(j,i)=x(i,j)"]

for i=1:300
  for j=1:300
     (*CodeHunkOfSomeSort)(j,i);
  end
end

Does that then cut out the large percentage of time spent interpreting?

Dan