[Octave-bug-tracker] [bug #55909] Performance of hist

[Michael Leitner]

URL:
  <https://savannah.gnu.org/bugs/?55909>

                 Summary: Performance of hist
                 Project: GNU Octave
            Submitted by: 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: 
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any
                 Release: dev
        Operating System: Any

    _______________________________________________________

Details:

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. 



    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Wed 13 Mar 2019 01:02:50 PM UTC  Name: hist.m  Size: 11KiB   By:
mleitner

<http://savannah.gnu.org/bugs/download.php?file_id=46517>

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?55909>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/