Inefficient hash map operation provokes OutOfMemory: Java heap space error

Question

I know I can increase the size of the heap but that seems like a poor solution.

This program runs correctly on small files but when run on large data sets it crashes with the OutOfMemory: Java heap space error.

This code executes multiple hash map operations and I'm certain that the haphazard way in which I strung the data structures together is the root of this problem however I'm too inexperienced to think of a solution. I've never before had to think about runtime outside of answering questions about big O notation!

I'm trying to create a program to learn rules by inference, i.e. 'contains'('vitamin c', 'oranges')., 'prevents'('scurvy', 'vitamin c'). would yield the output "rule" 'prevents'('scurvy', 'oranges'). I have code which will produce that output but then I wanted to eliminate duplicate "rules" from the input while keeping track of the number of times they were observed (as a naive confidence measure, since frequently observed rules are more likely to be true), so I implemented a hash map which stores the "rule" as a key and the number of observed instances as the value.

I've reproduced the code here, it's not that long.

Machine learning component architecture:

private List<Sentence> sentences = new ArrayList<>();
/*
 * The following maps store the relation of a string occurring
 * as a subject or object, respectively, to the list of Sentence
 * ordinals where they occur.
 */
private Map<String,List<Integer>> subject2index = new HashMap<>();
private Map<String,List<Integer>> object2index = new HashMap<>();

/*
 * This set contains strings that occur as both,
 * subject and object. This is useful for determining strings
 * acting as an in-between connecting two relations. 
 */
private Set<String> joints = new HashSet<>();

public void addSentence( Sentence s )
{

// add Sentence to the list of all Sentences
sentences.add( s );

// add the Subject of the Sentence to the map mapping strings
// occurring as a subject to the ordinal of this Sentence
List<Integer> subind = subject2index.get( s.getSubject() );
if( subind == null )
{
    subind = new ArrayList<>();
    subject2index.put( s.getSubject(), subind );
}
subind.add( sentences.size() - 1 );

// add the Object of the Sentence to the map mapping strings
// occurring as an object to the ordinal of this Sentence
List<Integer> objind = object2index.get( s.getObject() );
if( objind == null )
{
    objind = new ArrayList<>();
    object2index.put( s.getObject(), objind );
}
objind.add( sentences.size() - 1 );

// determine whether we've found a "joining" string
if( subject2index.containsKey( s.getObject() ) )
{
    joints.add( s.getObject() );
}
if( object2index.containsKey( s.getSubject() ) )
{
    joints.add( s.getSubject() );
}
}

public Collection<String> getJoints()
{
return joints;
}
public List<Integer> getSubjectIndices( String subject )
{
return subject2index.get( subject );
}
public List<Integer> getObjectIndices( String object )
{
return object2index.get( object );
}
public Sentence getSentence( int index )
{
return sentences.get( index );
}
//map to store learned 'rules'
Map<Sentence, Integer> ruleCount = new HashMap<>();
//store data
public void numberRules(Sentence sentence) 
{
if (!ruleCount.containsKey(sentence))
{
    ruleCount.put(sentence, 0);
}
ruleCount.put(sentence, ruleCount.get(sentence) + 1);
}

Sentence Object:

public class Sentence 
{
private String verb;
private String object;
private String subject;
public Sentence(String verb, String object, String subject )
{
    this.verb = verb;
    this.object = object;
    this.subject = subject;
}

public String getVerb()
{
    return verb; 
}

public String getObject()
{
    return object; 
}

public String getSubject()
{
    return subject;
}

public String toString()
{
    return verb + "(" + object + ", " + subject + ").";
}

@Override
public boolean equals(Object other)
{
    if (!(other instanceof Sentence))
        return false;
    if (other == this)
        return true;
    Sentence o = (Sentence) other;
    return o.subject.equals(subject) && o.object.equals(object) && o.verb.equals(verb);
}

@Override
public int hashCode ()
{
    return Objects.hash(object, subject, verb);
}


}

Code that executes:

public static void main(String[] args) throws IOException 
{


Ontology ontology = new Ontology();
BufferedReader br = new BufferedReader(new FileReader("file.txt"));
Pattern p = Pattern.compile("'(.*?)'\\('(.*?)',\\s*'(.*?)'\\)\\.");
String line;
while ((line = br.readLine()) != null) 
{
    Matcher m = p.matcher(line);
    if( m.matches() ) 
    {
        String verb    = m.group(1);
        String object  = m.group(2);
        String subject = m.group(3);
        ontology.addSentence( new Sentence( verb, object, subject ) );
    }
}

for( String joint: ontology.getJoints() )
{
    for( Integer subind: ontology.getSubjectIndices( joint ) )
    {
        Sentence xaS = ontology.getSentence( subind );

        for( Integer obind: ontology.getObjectIndices( joint ) )
        {

            Sentence yOb = ontology.getSentence( obind );

            Sentence s = new Sentence( xaS.getVerb(),
                                       xaS.getObject(),
                                       yOb.getSubject() );

            //System.out.println( s );                
            ontology.numberRules( s );    

        }
    }
}
for (Map.Entry<Sentence, Integer> entry : ontology.ruleCount.entrySet()) 
{
    System.out.println(entry.getKey()+" : "+entry.getValue());
}       
}   

Input:

'prevents'('scurvy', 'vitamin C').
'contains'('vitamin C', 'orange').
'contains'('vitamin C', 'sauerkraut').
'is a'('fruit', 'orange').
'improves'('health', 'fruit').
'contains'('vitamin C', 'orange').
'improves'('health', 'fruit').

Output:

prevents(scurvy, orange). : 2
improves(health, orange). : 2
prevents(scurvy, sauerkraut). : 1

As an aside, is there a good way to store those "rules" so that the most frequently observed instances are on top?

PS: This is reposted from Stack Overflow.

Answer 1

A couple of overall comments.

• String concatenation is bad, bad, bad. Sure, compiler no longer creates tons of Strings, but an instance of StringBuilder and an instance of String are created anyway. They get gc'ed eventually, sure, but String.format does the same with less resources, so try to use it instead, especially in often-called methods.
• You create a new Sentence inside the third nested loop. Some of them (#verb x #object x #subject) are used as keys and don't get collected. How many instances is that? Default maximum heap size is 1/4 th of your machine memory or 1Gb, whichever is smaller; could it be so that there actually are thousands of instances cluttering the memory?
• At any rate, OOM means that you create and retain too much instances of objects. Do you really need them all? Maybe your algorithm could be simplified so it gets less memory-intensive?
• (Not related to OOM) in your Sentence#equals() implementation you don't check other for being null, nor do you check its fields for being null. That may once result in an NPE.

Answer 2

Deduplication

If you're reading in a file with a lot of repeated sentences, you could force them to be unique and hold only one instance of each unique sentence. Combining this with storing the unique sentences in subject2Index and object2Index instead of the indexes into a list and dropping the list would shave more memory to boot.

You can also normalize the verbs, subjects, and objects as well to save even more memory, but this is really digging deep into premature optimization. You're essentially replicating Java's string internalization, but for extremely large files with lots of duplication, it might get you under the limit.

class Ontology {
    private Map<String, String> words = new HashMap<>();
    private Map<Sentence, Sentence> sentences = new HashMap<>();

    public void addSentence(String verb, String object, String subject) {
        addSentence(uniqueSentence(new Sentence(uniqueWord(verb), uniqueWord(object), uniqueWord(subject))));
    }

    public Sentence uniqueSentence(Sentence sentence) {
        String unique = sentences.get(sentence);
        if (unique == null) {
            words.put(sentence, sentence);
            return sentence;
        }
        else {
            return unique;
        }
    }

    public String uniqueWord(String word) {
        String unique = words.get(word);
        if (unique == null) {
            words.put(word, word);
            return word;
        }
        else {
            return unique;
        }
    }
}

All this would be done while reading the file and at the end while generating the final sentences to output.

while ((line = br.readLine()) != null) {
    Matcher m = p.matcher(line);
    if( m.matches() ) {
        ontology.addSentence(m.group(1), m.group(2), m.group(3));
    }
}

...

Sentence s = ontology.uniqueSentence(new Sentence(xaS.getVerb(),
                                                  xaS.getObject(),
                                                  yOb.getSubject()));

Data Structures

Every time an ArrayList needs to grow, it doubles in size. This applies to all those lists in the subject/object maps plus the list of sentences. You could drop the list of sentences and instead store lists of (now unique) sentences for each subject and object, but you would save even more space by instead using a map from sentence to count for each.

class Ontology {
    private Map<String,Map<Sentence,Integer>> subjectSentenceCounts = new HashMap<>();
    private Map<String,Map<Sentence,Integer>> objectSentenceCounts = new HashMap<>();
    private Set<String> joints = new HashSet<>();

    private void addSentence(Sentence s) {
        incrementSentenceCount(s, s.getSubject(), subjectSentenceCounts);
        incrementSentenceCount(s, s.getObject(), objectSentenceCounts);
        addJoiner(s.getObject(), subjectSentenceCounts.keys());
        addJoiner(s.getSubject(), objectSentenceCounts.keys());
    }

    private void incrementSentenceCount(Sentence s, String word, Map<String,Map<Sentence,Integer>> wordCounts) {
        Map<Sentence,Integer> counts = wordCounts.get(word);
        if (counts == null) {
            counts = new HashMap<>();
            counts.put(s, 1);
            wordCounts.put(word, counts);
        }
        else {
            Integer count = counts.get(s);
            if (count == null) {
                counts.put(s, 1);
            }
            else {
                counts.put(s, count + 1);
            }
        }
    }

    private void addJoiner(String word, Set<String> otherWords) {
        if (otherWords.contains(word)) {
            joints.add(word);
        }
    }
}

Adjusting the nested output loops to use the counts should be pretty easy, and you may even be able to use the count directly instead of looping over the duplicated sentences for each subject/object.