[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Octave-bug-tracker] [bug #55909] Performance of hist
From: |
Michael Leitner |
Subject: |
[Octave-bug-tracker] [bug #55909] Performance of hist |
Date: |
Wed, 13 Mar 2019 09:02:52 -0400 (EDT) |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0 |
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/
- [Octave-bug-tracker] [bug #55909] Performance of hist,
Michael Leitner <=