ImmutableTable.Builder builds array backed table for large sparse tables due to overflow error

[GoogleCodeExporter]

When creating an ImmutableTable using a builder, the builder uses a heuristic 
to determine what data structure to use for storing data, as seen below from 
line 163 of RegularImmutableTable.java (in version 14.0):

    // use a dense table if more than half of the cells have values
    // TODO(gak): tune this condition based on empirical evidence
    return (cellList.size() > ((rowSpace.size() * columnSpace.size()) / 2)) ?
        new DenseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace) :
        new SparseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace);

If the data for the table is large and sparse, then 
rowSpace.size()*columnSpace.size() may overflow to a negative number, causing a 
DenseImmutableTable to be created instead of a sparse one.  This in turn will 
use enough memory to crash the program on a large 2d array allocation.

A minimal fix might be to change the logical condition to:

cellList.size() > ((long)rowSpace.size()) * columnSpace.size()/2

Attached is a short piece of code where a very sparse Table of 5,000,000 
entries is created successfully, and then the ImmutableTable creating with the 
builder on the same data fails.

Original issue reported on code.google.com by rma...@gmail.com on 7 Mar 2013 at 12:19

Attachments:

• TestImmutableTable.java

[GoogleCodeExporter]

Original comment by lowas...@google.com on 3 May 2013 at 11:36

• Changed state: Accepted

[GoogleCodeExporter]

Original comment by kurt.kluever on 4 May 2013 at 12:16

• Changed state: Fixed
• Added labels: Milestone-Release15

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:13

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:08

• Added labels: Restrict-AddIssueComment-Commit