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

 
 

bug #61788: arrays of type int16 contain wrong numbers

Submitter:  Hartmut <hardy>
Submitted:  Mon 10 Jan 2022 09:03:35 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Regression
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * 7.0.90 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 22 Mar 2022 05:53:54 PM UTC, comment #22: 

@Markus: Thanks also for the fixing the infinite loop/division by zero error.

I will try again soon to make the colon operator generate ranges for single and integer types.

John W. Eaton <jwe>
Group administrator
Tue 22 Mar 2022 05:18:16 PM UTC, comment #21: 

This seems to be fixed now.

Thanks jwe for your changes.

Closing report.

Markus Mützel <mmuetzel>
Group administrator
Fri 18 Mar 2022 08:07:11 PM UTC, comment #20: 

I have now done (preliminary) tests with the current Octave 7.0.92 release candidate and the current (but inofficial) image package release candidate. Good news: "pkg test image" now eventually passes fine, at least under Linux.

Also the test code from comment #0 now gives the expected result, but that's probably expected after John's fix.

Hartmut <hardy>
Fri 18 Mar 2022 02:20:52 PM UTC, comment #19: 

Quick note to say that @jwe has fixed the range behavior as described towards the end of this discussion: https://octave.discourse.group/t/announcing-octave-7-1-release-candidate-1-availability/2080/88

A new pre-release 7.0.92 is now available at https://alpha.gnu.org/gnu/octave/?C=M;O=D

@Hartmut, since you're copied here, please run your package tests on 7.0.92.

Arun Giridhar <arungiridhar>
Group Member
Tue 22 Feb 2022 02:24:55 AM UTC, comment #18: 

Sorry for the delay, I had hoped to fix this problem by now.

What I would like to do:

  1. Eliminate all range objects from Octave and have the colon operator syntax always produce vectors of the appropriate type.
  2. Handle "for var = colon_expression ... end" syntax as a special case so that the colon expression in this case does not produce a vector.
  3. Preserve but deprecate the old Range class so that external code that uses it can continue to work for some time.  But the "octave_value (const Range&)" constructor would convert the Range object to a vector because Octave itself would no longer handle Range objects internally.
  4. Preserve enough of the old octave_range octave_value type so that loading old data files will work.  But instead of creating range objects in Octave, they would be converted to vectors when they are loaded.


But all of that is probably too much to do this late in the release process.

I've also considered doing all of the above except for ranges of double precision floating point numbers (the only type of range supported by previous versions of Octave) but having that one range type as a special case seems even worse to me.

So, another option for the release is to revert the changes that introduced the new range types and then work on making the changes outlined above in the next major release of Octave.

John W. Eaton <jwe>
Group administrator
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>
Group 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>
Group 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>
Group 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>
Group 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>
Group administrator
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>
Group Member
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>
Group Member
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>
Group 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]:


octave:1> x = 1:10; y = (1:10); z = [1:10]; whos
Variables visible from the current scope:

variables in scope: top scope

  Attr   Name        Size                     Bytes  Class
  ====   ====        ====                     =====  =====
         x           1x10                        24  double
         y           1x10                        24  double
         z           1x10                        80  double

Total is 30 elements using 128 bytes
-verbatim+

Note that I would only propose changing the way that elements of arrays are computed from range expressions for integer ranges.  I don't think it is appropriate to repeatedly add the increment for floating point ranges.

I have proposed eliminating special data types (range, permutation matrix, and diagonal matrix) in the past but have met resistance because it will cause some operations to consume much more memory.  OTOH, it will improve compatibility and reduce maintenance issues.  I'm even more convinced now that these storage optimizations are not worth the effort.

John W. Eaton <jwe>
Group 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>
Group Member
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>
Group Member
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>
Group 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>
Group Member
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>
Group Member
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>
Group 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)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-03-22 mmuetzel StatusNone Fixed
        Open/ClosedOpen Closed
    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.13-4448.
    Corresponding source code