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

Submitted by:  Tasos Papastylianou <tpapastylianou>
Submitted on:  Sat 17 Apr 2021 06:01:15 PM UTC  
 
Category:  Octave Forge 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

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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>
Project Member
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)
  •  

    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.

     

     

     

    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.6