bugGNU Octave - Bugs: bug #61788, arrays of type int16 contain wrong...

 
 

bug #61788: arrays of type int16 contain wrong numbers

Submitted by:  Hartmut <hardy>
Submitted on:  Mon 10 Jan 2022 09:03:35 PM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Regression
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  Open
Release:  7.0.90 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)

Tue 18 Jan 2022 09:11:48 PM UTC, comment #17: 

@Hartmut, I intend to fix the saturation problem for integer ranges before the release.

John W. Eaton <jwe>
Project Administrator
Tue 18 Jan 2022 09:03:54 PM UTC, comment #16: 

Will this bug be (probably) fixed in the Octave 7 release, or shall we better start to work around it for the image package to function properly under Octave 7? (I only refer the original buggy behavior in comment #0.) It would already help me to have an educated guess in this case.

Hartmut <hardy>
Fri 14 Jan 2022 11:39:30 PM UTC, comment #15: 

@Hartmut: The code should be written to assume that created ranges are of the corresponding data type as the base, increment, and limit.  If the range is formed from uint8 values then the range itself will be of class uint8.

The implementation proposals being discussed here (full support for integer ranges or support only for floating point ranges) only affect storage requirements and not the class of the range.

Rik <rik5>
Project Administrator
Fri 14 Jan 2022 11:24:30 PM UTC, comment #14: 

I have observed another change in Octave 7.0.90, that is connected to arrays of integers:

n = uint8(2)
class(1:n)

In Octave 6.4.0 this gave a class of "double". But now in Octave 7.0.90 this gives a class of "uint8".

But (Online-)Matlab also gives "uint8" in this case, so maybe this is just an improvement in Octave 7.0.90?

How will this behave in the future? I ask because I realised that the function regionprops.m in the image package relies on the old (and not Matlab compatible) Octave behavior (and so behaves wrongly at the moment with Octave 7.0.90).

Hartmut <hardy>
Tue 11 Jan 2022 09:33:05 PM UTC, comment #13: 

Extending ranges to integers has been really problematic.  I would support cutting that back to just floating point.  For one thing, I think these are the most common so if an 80/20 rule (See Pareto Principle) applies here we will get most of the benefits (80%) by having code for 20% of the cases.

Rik <rik5>
Project Administrator
Tue 11 Jan 2022 05:09:34 PM UTC, comment #12: 

To do C arithmetic with Octave integers requires extracting the C integer from the Octave integer.  That most likely means additional specializations in the range<T> template.  Yes, we can do that, but I see that path (and all of the current discussion, and the need for special load/save functions, etc., etc.) as additional present and future maintenance burden.  At this point, I'm strongly in favor of eliminating that additional complexity.

John W. Eaton <jwe>
Project Administrator
Tue 11 Jan 2022 04:47:08 PM UTC, comment #11: 

Most (or all?) platforms that Octave supports use two's complement for signed integer. Could we use the overflow behavior of (un)signed C integers to make this work?

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

§6.2.5 9:

> A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.


We could extend that specification to signed integers if we assume two's complement...

Markus Mützel <mmuetzel>
Project Member
Tue 11 Jan 2022 03:52:16 PM UTC, comment #10: 

Sorry, I posted comment #9 before I read your comment #8.

Yes, what you describe makes good sense, since it won't break Matlab compatibility.

Does this affect file reading? Should we worry about any users who may have saved integer ranges in mat files in the past few months? Are we promising backwards compatibility at all with the dev version of Octave?

Arun Giridhar <arungiridhar>
Tue 11 Jan 2022 03:47:16 PM UTC, comment #9: 

WIP Patch 2 attached.

I am trying to do something safe but need a check from you if this is the right thing to do. If it is, there are multiple places that would need the same code, so perhaps a private function might help.

(file #52647)

Arun Giridhar <arungiridhar>
Tue 11 Jan 2022 03:43:30 PM UTC, comment #8: 

We could begin by keeping the special range type for floating point ranges (as in previous versions of Octave) but making integer range expressions always generate arrays.  This change is very low risk because integer range expressions were not supported in previous versions of Octave.  For example, in Octave 6 and earlier versions:

octave:1> x = uint8(1):uint8(10)
x =

    1    2    3    4    5    6    7    8    9   10

octave:2> class (x)
ans = double

which was not Matlab compatible, so fixing compatibility in this case could mean

  1. generating a uint8 object from the range expression
  2. generating an array instead of a special range object

In a later version (when we have had more time for testing) we could make Octave also generate arrays by default for floating point range expressions.

To make maintenance easier, I would be in favor of simply eliminating range objects entirely, but if we do keep them, I would argue for making that behavior optional with the default being to create arrays from range expressions.

John W. Eaton <jwe>
Project Administrator
Tue 11 Jan 2022 03:36:57 PM UTC, comment #7: 

Yes, you can see from the output of whos that x = 1:10 or y = (1:10) is different from z = [1:10]:

John W. Eaton <jwe>
Project Administrator
Tue 11 Jan 2022 03:27:22 PM UTC, comment #6: 

@jwe: Your idea of converting ranges to arrays is OK too.

In the expression (1:10:100)(3), is that a range indexing or an array indexing?

I expect that [1:10:100](3) with the square brackets makes it an array indexing. Is this correct?

Arun Giridhar <arungiridhar>
Tue 11 Jan 2022 03:22:45 PM UTC, comment #5: 

Here is a partial fix, still a work in progress.

I now get this result. The final value calculation is still buggy due to saturation but the rest of the elements are OK.

octave:4> int16(-3e4) : int16(1e4) : int16(+3e4)
ans =

  -30000  -20000  -10000       0   10000   20000    2767

WIP patch attached. Feedback and advice solicited.

(file #52646)

Arun Giridhar <arungiridhar>
Tue 11 Jan 2022 03:16:39 PM UTC, comment #4: 

Doing what you suggest is fine for generating all the numbers in an array.  But in Octave, we have ranges stored as base, limit, and increment and allow indexing to obtain arbitrary elements.  I don't think you really want to have to count from the beginning of an array all the way to the end just to access the last element (or one near the last).

OTOH, to me, this appears to be just another example showing how the idea I had years ago of storing ranges as special objects may just not be worth it.  I would be glad to just eliminate ranges as a special storage type and simply make colon expressions be syntactic shorthand for creating arrays with evenly spaced elements (as I believe they are in Matlab).

Note that we also have the same problem for things like

for i = int8(-100):int8(100), i, end

but this problem can be fixed using the "increment previous value" method since we are iterating over all elements, not indexing arbitrary elements.

And now, ranges in for loops are handled separately so that the range object is not created directly, so we don't have to worry about memory issues in range expressions if we eliminate the special range type.

John W. Eaton <jwe>
Project Administrator
Tue 11 Jan 2022 02:33:17 PM UTC, comment #3: 

I did some benchmarking in standalone C++ with the two variants (base + i * increment) and (preceding value + increment). The serial version is slower but by such a tiny amount that it is viable. Over 1e9 iterations, the first loop took 0.14 seconds and the second took 0.28 seconds, which might look like half-speed but it's only 0.14 nanoseconds per iteration, so even for a range with say 1e7 elements, it slows down only by 1.4 milliseconds.

@jwe: does the change have to be done only in Range.h and Range.cc or are there other locations too?

Arun Giridhar <arungiridhar>
Mon 10 Jan 2022 09:47:34 PM UTC, comment #2: 

@jwe: Which file has the code you refer to?

Without knowing the ramifications in detail yet, one way to do it is to say

element(i) = element(i-1) + increment;

Such a serial definition will avoid overflow, but there may be a performance penalty because that code is serial, compared with the expression in your comment which can be loop-unrolled by the compiler, etc. I do not know the tradeoff yet.

Also, how is it possible that test/range.tst is passing while the range in comment #0 is clearly saturating and not reaching the final value? Do we need range tests closer to the respective intmax?

Arun Giridhar <arungiridhar>
Mon 10 Jan 2022 09:26:55 PM UTC, comment #1: 

This problem is happening because we are computing the elements of the range using Matlab's rules for integer arithmetic that use saturation semantics.  So when we compute

range_element(i) = base + i * increment

with base and increment both being int16, the "i * increment" part can saturate.  In this case, the saturation value is 32767, so for all elements beyond the one where saturation happens, you get "base + 32767".  For the specific example, the result is 2767.

We need a better way of doing this calculation.  What would be the best way to do it that will work naturally in a template function?

John W. Eaton <jwe>
Project Administrator
Mon 10 Jan 2022 09:03:35 PM UTC, original submission:  

Here is a regression (I think) that I observed with the current Octave release candidate 7.0.90. Run the following code:

a = int16 ( int16(-30000) : int16(30000) );
a(end)

  • in Octave 7.0.90 this gives 2767
  • in Octave 6.3.0 this gives 30000
  • in Online-Matlab (R2021b) this gives 30000

I have observed this under linux, but I think it will be the same for all OS'ses. I found this by a failing BIST test in the image package.

I could not provoke this wrong behavior with the commonly used integer type uint8, but maybe it happens also with other integer types and not only with int16.

Hartmut <hardy>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #52647:  range_v2.patch added by arungiridhar (4KiB - text/x-patch)
file #52646:  range_v1.patch added by arungiridhar (4KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by arungiridhar (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by hardy (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 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-01-11 arungiridhar Attached File- => Added range_v2.patch, #52647
    2022-01-11 arungiridhar Attached File- => Added range_v1.patch, #52646

    Back to the top


    Powered by Savane 3.7