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:  None Assigned to:  None
Originator Name:  Open/Closed:  Open
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.

 

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:

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:

(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 #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 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 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    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.4