Thursday, June 28, 2012

A Realistic Test

There was an interesting post on the mailing list (https://mailman.cae.wisc.edu/pipermail/help-octave/2012-June/052642.html). The problem is, given some logical array, A = [1 0 0 1 0 0 1 1 1 ...], and minimum length of consecutive ones, K, all sequences of ones less than K should be filtered out.

The exciting part for me is that the JIT compiler is currently far enough along to compile the loopy solution.

Input generation

I used a simple script to generate some random input data. A double matrix is used, because JIT does not yet work for logical matrices.
function result = gen_test (n)
  result = double (rand (1, n) > .01);
endfunction

Vectorized

Vectorized code (based off of code from the mailing list)
function z = vectorized (A, K)
  tic;
  temp = ones (1, K);
  z = conv (A, temp);
  z = z > K-1;
  z = conv (z, temp);
  z = z(K:end-K+1);
  z = z >= 1;
  toc;
endfunction

Loopy

I didn't do anything fancy here.
function z = loopy (A, K)
  tic;
  z = A;
  n = numel (A);
  counter = 0;
  for ii=1:n
    if z(ii)
      counter = counter + 1;
    else
      if counter > 0 && counter < K
        z(ii-counter:ii-1) = 0;
      endif
      counter = 0;
    endif
  endfor

  if counter > 0 && counter < K
    z(end-counter+1:end) = 0;
  endif
  toc;
endfunction

Results

These numbers were taken from a AMD FX(tm)-4100 Quad-Core Processor with 8 GB of RAM. I just ran each test once. For each test, the number of elements in A was 1,000,000.

Vectorized Loopy JIT Loopy JIT (no overhead) Loopy (No JIT)
K=3 0.078s 0.059s 0.028s 5.27s
K=100 0.43s 0.063s 0.028s 5.66s
K=500 1.58s 0.082s 0.033s 5.73s

These results are expected. The efficiency of the vectorized approach depends on K, while the loopy version does not. While JIT support is not complete or stable yet1, I think this shows that the current JIT implementation is able to handle a few practical examples, not just interpreter benchmarks.

hg id for regular octave branch: 52cb71787cd1
hg id for jit branch: f649b66ef1af

1 Occasionally I break functionality like assignment, addition, and function calls.

6 comments:

  1. What does JIT without overhead mean?

    ReplyDelete
    Replies
    1. That would be without the compile time overhead. So that's the time it takes for the second and successive runs.

      Delete
  2. Max, I ran your tests on MacOS X 10.7.5 (2.2 GHz Intel Core i7)

    No JIT Vectorized: Elapsed time is 6.45197 seconds.
    No JIT Loopy: Elapsed time is 14.8093 seconds.
    With JIT Vectorized: Elapsed time is 6.37535 seconds.
    With JIT Loopy: Elapsed time is 0.166505 seconds.

    ReplyDelete
    Replies
    1. Thanks for building JIT. It is good to know JIT works on the Mac.

      Delete