bugGNU Octave - Bugs: bug #55909, Performance of hist

 
 

bug #55909: Performance of hist

Submitted by:  Michael Leitner <mleitner>
Submitted on:  Wed 13 Mar 2019 01:02:50 PM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  Closed
Release:  dev Operating System:  Any

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Sat 08 Jun 2019 11:57:02 PM UTC, comment #8: 

No answer so I went ahead and checked in a changeset here (https://hg.savannah.gnu.org/hgweb/octave/rev/47c0b11da31a).  I renamed "x_is_range" to "equal_bin_spacing" for clarity.  I also changed the threshold which switches between the old and new algorithms from 26 to 11 based on performance testing on my machine.

Marking as fixed and closing report.

Rik <rik5>
Project Administrator
Fri 31 May 2019 06:47:58 PM UTC, comment #7: 

Oops, I meant to say "I think it is worthwhile to detect equally-spaced bins even when they aren't ranges".

Rik <rik5>
Project Administrator
Fri 31 May 2019 06:46:39 PM UTC, comment #6: 

Okay, now I can spot the difference.  Here are test results

################################################################################
Current Implementation (N = 10)
1e6: 0.028456
1e4: 0.000546
1e3: 0.000537
1e2: 0.000283

################################################################################
New Implementation (N = 10)
1e6: 0.027834
1e4: 0.000546
1e3: 0.000539
1e2: 0.000302

################################################################################
Current Implementation (N = 30)
1e6: 0.153529
1e4: 0.001585
1e3: 0.001599
1e2: 0.000714

################################################################################
New Implementation (N = 30)
1e6: 0.022552
1e4: 0.000548
1e3: 0.000541
1e2: 0.000399

As noted, for small N there is no difference in performance.  That's actually good, the changes haven't disrupted anything.  For large N, the new algorithm is 2-7X faster.

I made some additional modifications for review.  Instead of isequal() I used strcmp because it is faster (even though this only occurs once in input validation).  Second, I think it is worthwhile to detect equally-spaced bins even when they aren't vectors.  I added code to do that as well which shifts a specification of N like "linspace (1,30,30)" in to using the faster algorithm.

+      x_is_range = strcmp (typeinfo (x), "range");
+      if (! x_is_range)
+        diffs = diff (x);
+        if (all (diffs == diffs(1)))
+          x_is_range = true;
+        endif
+      endif

Should the variable "x_is_range" be renamed to be more reflective of what it means, which is that the bins are equally spaced?

The use of in-place operators is a simple performance improvement so I made this change as well

-    freq = freq .* norm ./ sum (! isnan (y));
+    freq .*= norm ./ sum (! nanidx);

Finally, I also updated certain BIST tests because the underlying code has changed.

@@ -257,9 +286,9 @@ endfunction
%! assert (nn, n);
%! assert (xx, x);
%!
-%! ## test again with N > 30 because there's a special case for it
-%! [n, x] = hist (y, 35);
-%! [nn, xx] = hist (uint8 (y), 35);
+%! ## test again with N > 26 because there's a special case for it
+%! [n, x] = hist (y, 30);
+%! [nn, xx] = hist (uint8 (y), 30);
%! assert (nn, n);
%! assert (xx, x);

@@ -271,9 +300,9 @@ endfunction
%! assert (nn, n);
%! assert (xx, x);
%!
-%! ## test again with N > 30 because there's a special case for it
-%! [n, x] = hist (y, 35);
-%! [nn, xx] = hist (logical (y), 35);
+%! ## test again with N > 26 because there's a special case for it
+%! [n, x] = hist (y, 30);
+%! [nn, xx] = hist (logical (y), 30);
%! assert (nn, n);
%! assert (xx, x);

I fleshed out the changeset to have a commit message and to cite Michael Leitner as the author.  See the attached bug55909.cset.

(file #47008)

Rik <rik5>
Project Administrator
Fri 31 May 2019 12:49:01 PM UTC, comment #5: 

Thanks for testing, Rik.

But yes, as I wrote in my initial post: "you should have exactly the same performance up to bin widths of 25 or 51, depending on whether you request equidistant bins or not". In your test script, you always use just the one-argument version of hist, which defaults to ten equidistant bins. I modified the script to allow an arbitrary number of bins (line 30), so that now you should see a performance increase.

(file #47007)

Michael Leitner <mleitner>
Thu 30 May 2019 04:46:50 AM UTC, comment #4: 

I wrote a script to test the performance of hist.  It is attached as bm_hist.m. 

################################################################################
# Preamble to load or create data
if (exist ("hist.var") == 2)
  load hist.var               # Load variables
else
  rand ("state", 1);
  x1 = rand (1e6,1);
  x2 = rand (1e4,1);
  x3 = rand (1e3,1);
  x4 = rand (1e2,1);
  save -binary hist.var x1 x2 x3 x4
endif

[nn, xx] = hist (1:10);       # compile m-file by running once

################################################################################
# Utility function
function retval = discard_minmax (x)
  [~, idx] = min (x);
  x(idx) = [];
  [~, idx] = max (x);
  x(idx) = [];
  retval = x;
endfunction

################################################################################
# Run benchmarking

N = 50 + 2;   # Number of tests at each size (plus 2 for discarding)

bm.x1e6 = zeros (N,1);
for i = 1:N
  tic;
  [nn, xx] = hist (x1);
  bm.x1e6(i) = toc;
endfor
bm.x1e6 = discard_minmax (bm.x1e6);

bm.x1e4 = zeros (N,1);
for i = 1:N
  tic;
  [nn, xx] = hist (x2);
  bm.x1e4(i) = toc;
endfor
bm.x1e4 = discard_minmax (bm.x1e4);

bm.x1e3 = zeros (N,1);
for i = 1:N
  tic;
  [nn, xx] = hist (x2);
  bm.x1e3(i) = toc;
endfor
bm.x1e3 = discard_minmax (bm.x1e3);

bm.x1e2 = zeros (N,1);
for i = 1:N
  tic;
  [nn, xx] = hist (x3);
  bm.x1e2(i) = toc;
endfor
bm.x1e2 = discard_minmax (bm.x1e2);

################################################################################
# Report results
printf ("1e6: %f\n", mean (bm.x1e6));
printf ("1e4: %f\n", mean (bm.x1e4));
printf ("1e3: %f\n", mean (bm.x1e3));
printf ("1e2: %f\n", mean (bm.x1e2));

After running with the current implementation, and the proposed implementation, I don't see much difference.

################################################################################
Current Implementation
1e6: 0.028456
1e4: 0.000546
1e3: 0.000537
1e2: 0.000283

################################################################################
New Implementation
1e6: 0.027834
1e4: 0.000546
1e3: 0.000539
1e2: 0.000302

(file #47003)

Rik <rik5>
Project Administrator
Thu 14 Mar 2019 09:42:20 AM UTC, comment #3: 

The test passes now. The solution was trivial, just converting to double where it is necessary. Of course this is undesirable, because it increases memory requirements, but the most efficient algorithm of scaling, shifting and rounding y for direct use as indices just does not work in integer arithmetics.

It would be possible to use the old code path for integer input, but I think this would be worse: after all, there is an obvious work-around for keeping the memory down with the present proposal (just computing histograms of parts of the data and adding up), while there would be no possibility to choose the efficient algorithm in the converse case. I admit that one could have it both by doing the piece-meal histogramming in an inner loop inside hist.m itself in the case of very large inputs, but I do not feel this to be warranted (yet).

(file #46532)

Michael Leitner <mleitner>
Wed 13 Mar 2019 08:47:40 PM UTC, comment #2: 

Okay, I will look into the test failure.

My new version is based on the one that I pulled today from the repository, that's why I put dev as release. Yes, I could have provided a diff, and for a final proposal I would have done, but I attached the whole file here so that it is easier to test it.

Michael Leitner <mleitner>
Wed 13 Mar 2019 05:09:42 PM UTC, comment #1: 

When I run the tests on your new version I see the following:

***** test <*47707>
y = [1  9  2  2  9  3  8  9  1  7  1  1  3  2  4  4  8  2  1  9  4  1 ...
      2  3  1  1  6  5  5  3  9  9  1  1  8  7  7  2  4  1];
[n, x] = hist (y, 10);
[nn, xx] = hist (uint8 (y), 10);
assert (nn, n);
assert (xx, x);

## test again with N > 30 because there's a special case for it
[n, x] = hist (y, 35);
[nn, xx] = hist (uint8 (y), 35);
assert (nn, n);
assert (xx, x);
!!!!! regression: https://octave.org/testfailure/?47707
ASSERT errors for:  assert (nn,n)

  Location  |  Observed  |  Expected  |  Reason
    (5)           0            6         Abs err 6 exceeds tol 0 by 6
    (9)           0            4         Abs err 4 exceeds tol 0 by 4
    (14)          0            4         Abs err 4 exceeds tol 0 by 4
    (18)          0            2         Abs err 2 exceeds tol 0 by 2
    (22)          0            1         Abs err 1 exceeds tol 0 by 1
    (27)          0            3         Abs err 3 exceeds tol 0 by 3
    (31)          0            3         Abs err 3 exceeds tol 0 by 3
    (35)          29           6         Abs err 23 exceeds tol 0 by 2e+01
PASSES 25 out of 26 tests

I'm attaching a diff relative to the version at hg id ba0c9e84f6a8 after making some style changes.  Can you please base any future changes on that?  It would also be best to upload patches instead of whole new versions.  If you can't do that for some reason, then please also indicate which version you started with so that someone else can generate diffs.  I know that hist isn't changing rapidly, but it's useful to use diffs anyway to ensure that we aren't undoing some other changes or making some unwanted change by simply replacing a file with a completely new one.

BTW, for changes before we started using Mercurial, you have to look in the files in the etc/OLD-ChangeLogs directory to find who really mad the change.  The info from the imported CVS files is not accurate as only a few people had commit access and we did those under our own IDs instead of attempting to track the Ids of the people who submitted patches.  Here's the entry for the one to switch methods based on number of bins:

2003-05-05  Andy Adler  <adler@site.uottawa.ca>

        * plot/hist.m: Improve performance by using different algorithms
        depending on number of bins.

(file #46519)

John W. Eaton <jwe>
Project Administrator
Wed 13 Mar 2019 01:02:50 PM UTC, original submission:  

In the past, I often found myself writing code for something that in principle could have been done by hist(), but where I was not satisfied with its speed. Now I have taken the time and overhauled hist() itself.

You can understand my proposal as the result of four points:
- First, in the current code there is a switch depending on the number of bins. It is set to 30, and has been since jwe added the switch in 2003. According to my tests (done on a processor that is from 2011) the other code branch becomes more efficient only at much larger values, leading to a jump in execution time of a factor four when the number of bins reaches 30. So the threshold should be set higher, but due to the following points, the branch can be deleted altogether.
- Second, both branches in hist are just vectorized m-code (even though the second branch is ingenious), while today we have accumarray and lookup, where the work is done by a built-in function. This gives a speed-up of a factor of about 2 for reasonable inputs. So the previous second branch can be dropped, while the trivial branch is still optimal for small numbers of bins.
- Third, probably in the majority of cases hist is called with one input argument, giving N=10 equidistant bins between the minimum and the maximum of the data, or with a scalar second argument specifying N. In this case (where the bins are equidistant), the call to lookup can be dropped and replaced by scaling and rounding, giving also roughly a factor of two. Actually, also if the second input argument is a range we know that we can do that, which is the path I follow.
- Finally, there is another choice to make, as under some conditions it can be beneficial for performance to pre-sort the input to lookup.

Please test the attached code (it is a single m-file, you can drop it in a local scope), both with respect to non-standard inputs (such as integers or floats, or non-finite numbers, both with respect to the arguments y and x) as well as whether you can reproduce the performance increases. Compared to the current version, you should have exactly the same performance up to bin widths of 25 or 51, depending on whether you request equidistant bins or not, above which you should see an increase of up to a factor five, without a decrease in performance for any combination of length(x) and length(y). Of course, the result should always be the same.

Something I noticed myself: the current version will accept bin centers of nan, and if they are at the end, it will not even complain, but will return negative values. I do not see any sense in that and would propose to reject such bin centers.

Michael Leitner <mleitner>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #47008:  bug55909.cset added by rik5 (4KiB - application/octet-stream)
file #47007:  bm_hist2.m added by mleitner (2KiB - text/x-matlab)
file #47003:  bm_hist.m added by rik5 (2KiB - text/x-matlab)
file #46532:  hist_diff2 added by mleitner (3KiB - application/octet-stream)
file #46519:  hist-diffs.txt added by jwe (3KiB - text/plain)
file #46517:  hist.m added by mleitner (11KiB - 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 rik5 (Updated the item)
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by mleitner (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-06-08 rik5 StatusPatch Reviewed => Fixed
        Open/ClosedOpen => Closed
    2019-05-31 rik5 Attached File- => Added bug55909.cset, #47008
        StatusNone => Patch Reviewed
    2019-05-31 mleitner Attached File- => Added bm_hist2.m, #47007
    2019-05-30 rik5 Attached File- => Added bm_hist.m, #47003
    2019-03-14 mleitner Attached File- => Added hist_diff2, #46532
    2019-03-13 jwe Attached File- => Added hist-diffs.txt, #46519
    2019-03-13 mleitner Attached File- => Added hist.m, #46517

    Back to the top


    Powered by Savane 3.5