bugGNU Octave - Bugs: bug #60409, [octave forge] (communications)...

 
 

bug #60409: [octave forge] (communications) huffmandeco throws out of memory or dimension too large for Octave's index type error

Submitter:  Tasos Papastylianou <tpapastylianou>
Submitted:  Sat 17 Apr 2021 06:01:15 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Unexpected Error or Warning
Status:  None Assigned to:  None
Originator Name:  Tasos Papastylianou Open/Closed:  * Open
Release:  * 6.2.0 Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Fri 30 Apr 2021 10:05:38 AM UTC, comment #3: 

Underlying cause of memory allocation problems aside, the current tree-based implementation of huffmandeco replaced an older one, which was relying on a slower, brute-force algorithm.

Perhaps the earlier algorithm would be more robust to this issue, and could be used as a fallback? (obviously it could also be worse, I have no idea).

Tasos Papastylianou <tpapastylianou>
Fri 30 Apr 2021 09:42:47 AM UTC, comment #2: 

Re comment #1: That sounds like the behavior of the OOM killer on Linux.
If it is, there is little to nothing Octave can do to prevent becoming a victim of the OOM killer, afaict.

The point when the OOM killer gets active depends on the available and installed memory, the swap, the over-provisioning strategy, ...
It's probably hard to predict it.

Markus Mützel <mmuetzel>
Group administrator
Fri 30 Apr 2021 06:51:49 AM UTC, comment #1: 

The line of the problem is


tree = zeros (1, 2^(m+1)-1)-1;


The link shows the user was able to have a result for

tree = zeros (1, 2^(82+1)-1)-1.


For me the error was still present.

Trying to find which number worked for me.
octave crashed on

tree = zeros (1, 2^(29+1)-1)-1.


This is a zeros function or hardware limitation issue which was discovered by the huffmandeco.

For this function or the zeros function there needs to be checks added to prevent this crash.
 
And a warning added so the user understands the limits.




Anonymous
Sat 17 Apr 2021 06:01:15 PM UTC, original submission:  

Please see https://stackoverflow.com/q/67106887/4183191 for context and details regarding this bug.

In summary, when this algorithm was last changed in 2011 in the repository (https://sourceforge.net/p/octave/communications/ci/83aeb09e7255c3953ac11b56299dab426831b419/), it was changed from a brute-force algorithm to a tree-based one; however, under certain conditions, this seems to result in really large theoretical trees, which exceed Octave's indexing capacity, resulting in a 'dimension too large' error inside huffmandeco.m

Steps to reproduce:

+verbose+
pkg load communications
rand( 'seed', 0 );   Text  = randi( [0,127], 1, 100 );   Fdata = randi( [0,127], 1, 30  );
for i = 0 : 127;   Nlet = length( find( Text == i ) );   p(i + 1) = Nlet / length( Text );   end

Symb       = 0 : 127;
Dict       = huffmandict( Symb, p );        % Create dictionary
[ ~, Idx ] = ismember( Fdata, Symb );       % Data indices from data
Compdata   = huffmanenco( Idx, Dict );      % Encode data indices
Dsig       = huffmandeco( Compdata, Dict ); % Decode Huffman code
Symb( Dsig )                                % Indices to symbols
-verbose-

Output:

+verbose+
error: out of memory or dimension too large for Octave's index type
error: called from
    huffmandeco>dict2tree at line 95 column 19
    huffmandeco at line 55 column 8
    testo at line 9 column 12
-verbose-

Incidentally, as a minor aside, the huffman functions also seem to have a slightly different API from their matlab counterparts, which has also caused problems to users migrating to Octave. See: https://stackoverflow.com/q/66929744/4183191

Also, the huffman functions seem to be getting quite a few hits on stackoverflow lately, not sure why. Perhaps some recently launched nanodegree that uses them is recommending Octave? We saw a huge number of octave questions in stackoverflow relating to Andrew Ng's course ever since that course first went online -- if something analogous is now causing people to interact with the huffman functions, we might reasonably expect that these functions will start getting a lot of attention soon ...

Tasos Papastylianou <tpapastylianou>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by tpapastylianou (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.

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-04-30 mmuetzel Operating SystemAny GNU/Linux

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code