bugGNU Octave - Bugs: bug #51329, nth_element / median function fail...

 
 

bug #51329: nth_element / median function fail with disable_range(true) (or with --traditional)

Submitted by:  None
Submitted on:  Tue 27 Jun 2017 08:51:52 PM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Incorrect Result
Status: FixedAssigned to: None
Originator Name: Brad KennedyOriginator Email: -unavailable-
Open/Closed: ClosedRelease: 4.2.1
Operating System: GNU/Linux

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 Jump to the original submission)

Wed 05 Jul 2017 10:56:23 PM UTC, comment #29:

Fixed, pushed your change on the default branch along with some tests added:

https://hg.savannah.gnu.org/hgweb/octave/rev/3e93a2a66cdf

If you would like to get more involved with Octave, take a look at the changes I made to your patch (style was perfect, just removed a couple of unnecessary parens and used octave_idx_type instead of int), check out how we add unit tests on functions (and tag them with bug numbers if applicable). You also might want to create an account on savannah so your comments are tagged with your username.

Mike Miller <mtmiller>
Project Administrator
Thu 29 Jun 2017 09:50:40 PM UTC, comment #28:

Yes, you may use the OP email and name for the patch, I'd like to get more involved so this is a good start.

- OP

Anonymous
Thu 29 Jun 2017 08:04:10 PM UTC, comment #27:

I think we're starting to get a little off-topic here.

I think that this bug is worth fixing, I think the latest patch in comment #18 looks good. I haven't yet applied it and tested it myself, but it seems reasonable at a glance.

This bug does not only affect people using --traditional, it just happens to manifest that way for users of --traditional calling the median function.

The easiest way to demonstrate this bug without --traditional is with

The error is not very clear to the user why the first is acceptable but the second is not a "contiguous range" for some reason.

This patch is relatively non-invasive, not too complicated, and should fix that without making the normal case any worse.

Do you want this patch to be attributed to you (full name and email address)? Are you the originator, can I use the name and email address in the bug fields above?

Mike Miller <mtmiller>
Project Administrator
Thu 29 Jun 2017 04:28:53 PM UTC, comment #26:

I had a misunderstanding of what --traditional actually did. The only case this could cause an issue with is some odd use of eval. (Which might actually exist given what I've seen in Matlab)

Two options enabled with --traditional are vital for us.

This option:
Fsave_default_options (octave_value ("-mat-binary"));

Prevents us from have to edit save options in Matlab libraries and existing to accomplish that. Or having a runtime switch at the top of each script like this:

if exists('OCTAVE_VERSION', builtin)
save_default_options ("-mat-binary")
end

This option:
confirm_recursive_rmdir
Has bearing on a lot of our tools built in Matlab/Octave code that would have to be set with a runtime flag as well.

So for now, the traditional option is vital to our, and I expect, others scripts. Instead of removing --traditional we could remove the range option from --traditional as a start, that would fix this bug and likely not affect people who are trying to run Matlab in Octave.

I think in our scripts we may try to ease out of --traditional in the meantime.

Anonymous
Thu 29 Jun 2017 04:16:01 PM UTC, comment #25:

Well, this whole thread is about something that fails with --traditional but shouldn't, because it turns off an Octave optimization that didn't have a workaround.

Can you provide an example of something that should error out in Matlab, but doesn't in Octave without --traditional? I believe Matlab still let's you specify ranges, it just doesn't store them as such. Similar for diagonal_ and permutation_matrix. Seems no other changes from --traditional should affect operation.

Nicholas Jankowski <nrjank>
Thu 29 Jun 2017 04:04:57 PM UTC, comment #24:

> Some Matlab code may rely on errors that Octave would allow.


Can you be more specific? Looking at what the traditional option does

http://hg.savannah.gnu.org/hgweb/octave/file/69a111259a2c/libinterp/corefcn/interpreter.cc#l175

it only disables warnings but not errors. And then it disables
internal optimisations for ranges, diagonal matrices, and permutation
matrices none which would be Matlab errors since they don't exist in
Matlab in the first place.

Carnë Draug <carandraug>
Project Member
Thu 29 Jun 2017 03:55:49 PM UTC, comment #23:

Removing the traditional option would hamper the migration to Octave from Matlab. Some Matlab code may rely on errors that Octave would allow. Some of the code that I am converting to Octave has really poor practices. Obviously this is not ideal but cause groups to not upgrade Octave to avoid the removal of --traditional in the future.

We have very complex Matlab code that is hard enough as is to convert to Octave, we don't need additional barriers to Octave adoption.

Anonymous
Thu 29 Jun 2017 03:47:45 PM UTC, comment #22:

The idea of the traditional option seems to be to make Octave more
similar to Matlab by disabling a set of features (you can see what
features get disabled and variables set in maximum_braindamage
function):

http://hg.savannah.gnu.org/hgweb/octave/file/69a111259a2c/libinterp/corefcn/interpreter.cc#l175

Then this means that we can't use such Octave features at all in the
whole Octave, or that we need to always code alternative for when said
features are disabled. I'm not sure if that's the way to go, it seems
more work for no good reason.

I would rather just remove the traditional option. Alternatively,
change the option to only set some style variables and to not disable
any feature.

The previous name for the traditional option (braindamage) was maybe
more fitting since you mainly set Octave to have less features.

Carnë Draug <carandraug>
Project Member
Thu 29 Jun 2017 02:56:53 PM UTC, comment #21:

Here is my build without the patch, as you requested. I misread sorry.

Anonymous
Thu 29 Jun 2017 02:44:56 PM UTC, comment #20:

With the exact patch as below #18.

Anonymous
Thu 29 Jun 2017 02:38:38 PM UTC, comment #19:

regarding the timings in comment #16, were those all with the patch? can you run similar timings without the patch applied? just want to have an idea of the delta/penalty from fixing the bug.

Nicholas Jankowski <nrjank>
Thu 29 Jun 2017 02:22:52 PM UTC, comment #18:

This patch passes the median tests and the other tests I've put in this bug.

This is the extent of my knowledge of the GNU style so someone else will have to fix it up as necessary.

Anonymous
Thu 29 Jun 2017 05:31:47 AM UTC, comment #17:

I just noticed the && (mode != UNSORTED) part, never mind the comment about breaks.

- OP

Anonymous
Thu 29 Jun 2017 05:28:30 AM UTC, comment #16:

Usually, n in this case will be always two elements when used in median([1,2,3,4,5,6]) for instance. Unless you call nth_element(X, N) with a long vector for the second argument you usually will exit out of the for loop immediately 2 < length(2). If we use #14, which I agree is better for the most part.

w/r/t the breaks:

Removing the first break precludes the ability to exit out of the block over n if it finds that
[1, 3, 4, 5, 6, ..., 300] has a difference of 2 at index 1.

Similarly, the for loop break precludes the ability to exit out of the loop if index 2 has a difference of 2...
n = [1, 2, 4, 5, 6, ..., 300]

Knowing that my current patch #12 performs as such:

Which makes sense, seems to be within acceptable limits.

I will gladly add a comment and please, consider the breaks once more. In practice it might not matter, since code that raises errors probably doesn't need to perform quickly anyway.

- OP

Anonymous
Thu 29 Jun 2017 01:12:44 AM UTC, comment #15:

Also maybe a small comment explaining the purpose of the for loop and what use case this additional case is addressing, since no one has seen a need for it until this bug report.

Mike Miller <mtmiller>
Project Administrator
Thu 29 Jun 2017 01:11:25 AM UTC, comment #14:

+1 on the timing test. Would be good to compare a range and the vector form of the same range.

This patch looks better. I would recommend removing the extra "break" statements, more than one way to exit from this case is confusing. I would also make this case the last one, not sure if it makes a difference in compiled code but it helps readability if the less complex cases come before the more complex ones.

Something like this (untested) should help clean up the "break"s:

Some small additional cleanup with the indentation, line break should be before the || operator, braces for the for loop are unnecessary, etc.

Mike Miller <mtmiller>
Project Administrator
Thu 29 Jun 2017 01:03:46 AM UTC, comment #13:

can you do a quick tic/toc test on it just to see what the extra checking overhead is?

Nicholas Jankowski <nrjank>
Thu 29 Jun 2017 12:59:22 AM UTC, comment #12:

This works as we seem to expect, thanks for showing me the test command.

Provides

- OP

Anonymous
Wed 28 Jun 2017 11:45:29 PM UTC, comment #11:

For the most part my currently patch will work, the only issue is that this section looks at the first difference in the n.increment() call to determine if it is ascending or descending, a range, of course, must have constant differences so it can check them correctly however if you provide a non constant difference it misbehaves.

I will adjust my code such that it verifies that the differences between the elements is always either increasing by one or decreasing one.

- OP

Anonymous
Wed 28 Jun 2017 10:53:05 PM UTC, comment #10:

The algorithm is relying on the input being both sorted and a contiguous range of integers.

The suggested patch in comment #3 may work in this limited case where the argument looks like it should be a contiguous range, but falls apart in other cases.

Allowing an arbitrary index vector as the second argument would need a lot more code than suggested here so far, making this a more expensive operation in that case, to either verify that the vector is indeed a contiguous sorted range of integers, or to recursively call nth_element for each distinct index value for example.

I can confirm that nth_element (and thus median) do fail when disable_range has been set:

Mike Miller <mtmiller>
Project Administrator
Wed 28 Jun 2017 07:57:17 PM UTC, comment #9:

yes, right. Since the only affect of disable_range is to change median's range input to nth_element into a vector, and it only seems to be triggering a type-check failure, allowing a vector input should fix it.

The only other issue I could imagine is that a range is inherently sorted, so the code might be relying on that assumption. It may be necessary to do a sort check of some kind for input-type=vector. (suggested by the fact that the error is triggered by mode = UNSORTED)

Nicholas Jankowski <nrjank>
Wed 28 Jun 2017 07:36:35 PM UTC, comment #8:

@Nicholas Jankowski

As in this comment, allowing nth_element to accept range valid vectors fixes this.

https://savannah.gnu.org/bugs/?51329#comment3

With my patch:

- OP

Anonymous
Wed 28 Jun 2017 07:29:24 PM UTC, comment #7:

at a minimum, median shouldn't break from --traditional. I still have that same line in my modified median over at bug #48690. so if we fix it by avoiding nth_element I'll try to rememebr to update that one as well.

Nicholas Jankowski <nrjank>
Wed 28 Jun 2017 07:27:08 PM UTC, comment #6:

ok, so for disable_range: "If this option is disabled Octave will store ranges as full matrices."

median calls nth_element in the line:

where the k:k+1 part is the N supposedly causing the error.

so it seems --traditional would have it pass as:

in the median(1:2) example, it would be passing:

trying that directly also produces the error under --traditional. seems like an incomplete input check choking on [1,2] not looking like 1:2 within nth_element.

I don't venture outside of m-code often, but the only line i see with that error in Array.cc:

so, something is setting mode = UNSORTED simply because it's not a range, even though the passed matrix is sorted ?

Nicholas Jankowski <nrjank>
Wed 28 Jun 2017 06:48:48 PM UTC, comment #5:

In traditional mode disable_range is set

Avinoam Kalma <avinoam>
Project Member
Wed 28 Jun 2017 06:13:32 PM UTC, comment #4:

I can confirm nth_element does not work the way median calls it if --traditional is used. Is that intentional?

Matlab doesn't have an nth_element function, so why does calling with --traditional change the error state?

normal octave:

octave with --traditional:

Nicholas Jankowski <nrjank>
Wed 28 Jun 2017 05:51:05 PM UTC, comment #3:

Hi there, Carnë Draug,

I agree with you w/r/t --traditional, and since the patch is likely to take some time we will be looking into our need for the use of --traditional.

However, I debugged the code and found out the type of the argument passed to the nth_element function in Array.cc is different with --traditional and without. The added line represents the type of the variable with --traditional.

This might be fixing the symptom and not the actual problem. But this works for our test case. I also note that this might cause other previously invalid commands to work incorrectly.

Anonymous
Wed 28 Jun 2017 03:54:07 PM UTC, comment #2:

> It ONLY happens with --traditional, but we think we need that flag for the time being.


Why? What does not work if you do not add that flag? The only thing that the flag should be doing is disabling features and changing error states. Nothing that works in traditional should stop working without that flag.

Carnë Draug <carandraug>
Project Member
Wed 28 Jun 2017 03:52:09 PM UTC, comment #1:

> It ONLY happens with --traditional, but we think we need that flag for the time being.

Carnë Draug <carandraug>
Project Member
Tue 27 Jun 2017 08:51:52 PM UTC, original submission:

We use Octave on clusters with mostly converted MatLab code that uses the --traditional flag when we start a script. We ran into this bug after switching from 3.8.2 to 4.2.1. It ONLY happens with --traditional, but we think we need that flag for the time being.

It fails due to the underlying call to nth_element which also only fails under --traditional

Anonymous

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by avinoam (Posted a comment)
  • -unavailable- added by nrjank (Posted a comment)
  • -unavailable- added by None (Submitted the item)
  •  

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

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 05 Jul 2017 10:56:23 PM UTCmtmillerStatusConfirmed=>Fixed
      Open/ClosedOpen=>Closed
    Wed 28 Jun 2017 10:53:05 PM UTCmtmillerStatusNone=>Confirmed
      SummaryMedian fails due to nth_element in --traditional=>nth_element / median function fail with disable_range(true) (or with --traditional)

    Back to the top


    Powered by Savane 3.1-cleanup1