bugGNU Octave - Bugs: bug #63444, "if (COND)" is much...

 
 

bug #63444: "if (COND)" is much slower than "if (all (COND))"

Submitter:  Rik <rik5>
Submitted:  Tue 29 Nov 2022 05:19:23 PM UTC
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Wed 30 Nov 2022 03:32:52 AM UTC, comment #9: 

I tried with "NDArray A" and "const NDArray A" and the difference in execution time is about the same but the percentage change is less significant when using the non-const NDArray because the overhead of the indexing operation is much higher.

It seems to me that we could do slightly better with a single loop that does both operations but I don't know that it is worth the trouble.

Also, I guess we should be careful about the difference between "if (val)" and "if (all (val))", not just when val might be empty but also if it might contain NaN elements.  I wouldn't have thought about the latter case before today.

John W. Eaton <jwe>
Project Administrator
Wed 30 Nov 2022 01:09:14 AM UTC, comment #8: 

I wasn't thinking this was production code.  This was just to see if the slow down was coming from the loop body or the loop structure.  I used the same indexing structure in each loop body because I was only interested in relative performance rather than absolute performance.

Rik <rik5>
Project Administrator
Tue 29 Nov 2022 08:25:56 PM UTC, comment #7: 

Beware the cost of checking the reference count with the "A(i)" indexing.  You might want to avoid that by using "const NDArray A = ..." or by using "args(1).array_value().data()".

Also, how smart is GCC these days?  Does it compile the two-loop case to be essentially the same as the single loop?  What happens if each loop in the two loop case is defined in a separate function as I think we have in Octave?

John W. Eaton <jwe>
Project Administrator
Tue 29 Nov 2022 08:02:25 PM UTC, comment #6: 

I made another octfile which tests how much time the test for isnan() adds.  It turns out that this seems to be a bigger portion of the slowdown (20%) than the actual loopisg structure (1x or 2x).

The file is shown below and attached as loop_tst_nan.cc

#include <octave/oct.h>

DEFUN_DLD (loop_tst_nan, args, nargout,
           "Test single or double loop equivalent to all()\n"
           "ARG1 : TRUE/FALSE, test for NaNs?\n"
           "ARG2 : numeric array")
{
  if (args.length () != 2)
    print_usage ();

  bool do_nan_test = args(0).bool_value ();
  NDArray A = args(1).array_value ();
  octave_idx_type N = A.numel ();
  bool retval = true;

  if (do_nan_test)
    {
      for (octave_idx_type i = 0; i < N; i++)
        {
          if (std::isnan (A(i)))
            error ("loop2: Can not convert NaN to logical value");
          if (! A(i))
            retval = false;
        }
    }
  else
    {
      for (octave_idx_type i = 0; i < N; i++)
        {
          if (! A(i))
            retval = false;
        }
    }

  return ovl (retval);
}

Results are

octave:4> tic; for i = 1:100, loop_tst_nan (0,x); end; toc
Elapsed time is 0.301775 seconds.

octave:9> tic; for i = 1:100, loop_tst_nan (1,x); end; toc
Elapsed time is 0.383141 seconds.

(file #54040)

Rik <rik5>
Project Administrator
Tue 29 Nov 2022 07:53:15 PM UTC, comment #5: 

I don't think looping over the array twice is that big a deal because it is what is inside the body of the loop which is taking the time rather than the loop structure itself (at least in C++, not Octave).

I made a test case as a .oct file.  This is attached as loop2.cc and shown below.

#include <octave/oct.h>

DEFUN_DLD (loop2, args, nargout,
           "Test single or double loop equivalent to all()\n"
           "ARG1 : TRUE/FALSE, do 1 combined loop?\n"
           "ARG2 : numeric array")
{
  if (args.length () != 2)
    print_usage ();

  bool do_1_loop = args(0).bool_value ();
  NDArray A = args(1).array_value ();
  octave_idx_type N = A.numel ();
  bool retval = true;

  if (do_1_loop)
    {
      for (octave_idx_type i = 0; i < N; i++)
        {
          if (std::isnan (A(i)))
            error ("loop2: Can not convert NaN to logical value");
          if (! A(i))
            retval = false;
        }
    }
  else
    {
      for (octave_idx_type i = 0; i < N; i++)
        {
          if (std::isnan (A(i)))
            error ("loop2: Can not convert NaN to logical value");
        }
      for (octave_idx_type i = 0; i < N; i++)
        {
          if (! A(i))
            retval = false;
        }
    }

  return ovl (retval);
}

I then ran the benchmark and it is basically equivalent.

octave:7> tic; for i = 1:100, loop2 (0,x); end; toc
Elapsed time is 0.385158 seconds.

octave:10> tic; for i = 1:100, loop2 (1,x); end; toc
Elapsed time is 0.382482 seconds.

(file #54039)

Rik <rik5>
Project Administrator
Tue 29 Nov 2022 07:32:56 PM UTC, comment #4: 

Just for fun, I benchmarked Matlab and they have the same issue (slightly worse even).  "if (COND)" is 42% slower than using "if (all (COND))".

Rik <rik5>
Project Administrator
Tue 29 Nov 2022 06:47:15 PM UTC, comment #3: 

But if you do 'isnan (X) && all (X)' for a large array, you are looping over the array twice.  I'm proposing that we combine those operations in a single function that only loops once.

John W. Eaton <jwe>
Project Administrator
Tue 29 Nov 2022 06:30:20 PM UTC, comment #2: 

Oh boy, things are always so complicated. 

comment #1:

> This comparison also points out that "if (all (NaN))" is not the same as "if (NaN)".  Is that difference compatible with Matlab?


Checking with Matlab, "all (NaN)" returns true while "if (NaN)" produces an error about converting NaN to logical value.  So, Octave is Matlab compatible.

I also checked "if ([0, 1, NaN])" to see if Matlab would short-circuit out, but it does not.  Hence, if we want to stay Matlab-compatible I don't think  we can really make this more efficient.  Octave has to process all N items of the array.  The advantage of not running, effectively, "! isnan (x) && all (x)" is that the value you are checking would definitely be available on a CPU register.  I doubt this is what is killing performance.

Rik <rik5>
Project Administrator
Tue 29 Nov 2022 05:50:14 PM UTC, comment #1: 

The function tree_evaluator::visit_if_command_list in pt-eval.cc calls tree_evaluator::is_logically_true, which calls octave_value::is_true.  If you've already called "all(data)" and data is a vector, then it is fast because you are looking at a scalar value.  For a double array, you end up in octave_base_matrix<MT>::is_true in ov-base-mat.cc:

// Return true if this matrix has all true elements (non-zero, not NA/NaN).
template <typename MT>
bool
octave_base_matrix<MT>::is_true (void) const
{
  bool retval = false;
  dim_vector dv = m_matrix.dims ();
  int nel = dv.numel ();

  if (nel > 0)
    {
      MT t1 (m_matrix.reshape (dim_vector (nel, 1)));

      if (t1.any_element_is_nan ())
        octave::err_nan_to_logical_conversion ();

      if (nel > 1)
        warn_array_as_logical (dv);

      boolNDArray t2 = t1.all ();

      retval = t2(0);
    }

  return retval;
}

Reshape should be fast because it should just modify the dimensions, not copy any data.  The slow part is that we are scanning for NaNs and then again for zero values.  For speed, those could be combined in a single operation.  It should probably be defined in a separate function the Array class rather than doing the operation in octave_base_matrix<MT>::is_true.

This comparison also points out that "if (all (NaN))" is not the same as "if (NaN)".  Is that difference compatible with Matlab?

We should rename this project from Octave to "pitfall".

John W. Eaton <jwe>
Project Administrator
Tue 29 Nov 2022 05:19:23 PM UTC, original submission:  

This observation came up in another bug report, but it deserves its own issue report.  The use of an implicit call to all() in an if statement is 35% slower than directly calling all().  This seems rather strange and hopefully is trivial to fix.

Test code I used is attached as bm_implicit_all.m and reproduced here:

N = 1e3;

data = ones (1e6, 1);

tic;
for i = 1:N
  if (data)
  endif
endfor
bm1 = toc

tic;
for i = 1:N
  if (all (data))
  endif
endfor
bm2 = toc
And a sample test run is
bm_implicit_all
bm1 = 1.9310
bm2 = 1.2500
octave:14> pctchg (bm1, bm2)
ans = -35.266

The function "pctchg" is my own local function that calculates the percentage change of two values.

Rik <rik5>
Project Administrator

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #54040:  loop_tst_nan.cc added by rik5 (808B - text/x-c++src)
file #54039:  loop2.cc added by rik5 (968B - text/x-c++src)
file #54038:  bm_implicit_all.m added by rik5 (148B - text/x-matlab)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by rik5 (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only project members can vote.

     

     

     

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-11-29 rik5 Attached File- Added loop_tst_nan.cc, #54040
    2022-11-29 rik5 Attached File- Added loop2.cc, #54039
    2022-11-29 rik5 Attached File- Added bm_implicit_all.m, #54038

    Back to the top

    Powered by Savane 3.10