9
\$\begingroup\$

My application needs to read 20-million-line text files and count the word frequencies for one and two words.

For example:

A B A B SSS G D A

One word Frequency

  1. A: 3
  2. B: 2
  3. SSS: 1
  4. G: 1

Two Word Frequency

  1. A B: 2
  2. B A: 1
  3. B SSS: 1
  4. SSS G: 1

After the reading method, it puts all HashMap values in the TreeMap for sorting and gets an OutOfMemoryException.

Note: it took 40 minutes to read a file.

Please also help me to find a way to decrease its processing time, such as by speeding up the file reading.

package tweetfile20million;

import java.util.Comparator;
import java.util.Map;

enum FileType {
    OneWord, TwoWord
}

/**
 *
 * @author KayD
 */
public class ValueComparator implements Comparator<String> {

    Map<String, Integer> map;

    public ValueComparator(Map<String, Integer> base) {
        this.map = base;
    }

    public int compare(String a, String b) {
        if (map.get(a) >= map.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys 
    }
}

Second File

package tweetfile20million;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.charset.Charset;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 *
 * @author KayD
 */
public class FileOperation{
    String fileDir = "B:\\20milyontweet\\";
    String dataFile = fileDir + "all_tweets.txt";
    HashMap<String, Integer> hash = new HashMap<>();
    long startTime;

    public void readText(FileType fileType){
        try{
            //Reading Starting
            startTime = (System.currentTimeMillis());
            this.readFile(fileType);

            //Writer Starting
            long middleTime = (System.currentTimeMillis());
            this.writeFile(fileType);
            long endTime = (System.currentTimeMillis());

            System.out.println("Total Reading time: "+(middleTime-startTime));
            System.out.println("Total Writing time: "+(endTime-middleTime));

        }catch(FileNotFoundException ex){
            System.err.println("File Not Found: " + ex.getMessage());
        }catch(IOException ex){
            System.err.println("IO: " + ex.getMessage());
        }
    }

    private void readFile(FileType fileType) throws IOException, FileNotFoundException{
        Charset utf8 = Charset.forName("UTF-8");
        BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(dataFile),utf8));
        int count = 0;
        String line;

        int mb = 1024*1024;
        Runtime runtime = Runtime.getRuntime();

        System.out.println("##### Heap utilization statistics [MB] #####");

        //Print used memory
        System.out.println("\n\nUsed Memory:" + (runtime.totalMemory() - runtime.freeMemory()) / mb);

        //Print free memory
        System.out.println("Free Memory:" + runtime.freeMemory() / mb);

        //Print total available memory
        System.out.println("Total Memory:" + runtime.totalMemory() / mb);

        //Print Maximum available memory
        System.out.println("Max Memory:" + runtime.maxMemory() / mb);

        while((line = reader.readLine())!=null){
            count++;
            if(count%2000000==0){
                //System.gc();
                 //Print used memory
                 System.out.println("\n\nUsed Memory:" + (runtime.totalMemory() - runtime.freeMemory()) / mb);

                //Print free memory
                System.out.println("Free Memory:" + runtime.freeMemory() / mb);

                long time = System.currentTimeMillis();
                System.out.println(count+" %2000000: "+ (time-startTime));
            }

            String no_special_char_in_line = line.replaceAll("[-+.^:,&$#@!~;_`'{}|\\/><\"()%=?\\t\\r\\n0-9–\\[\\]]"," ");
            String[] words = no_special_char_in_line.split("\\s+");

            if(fileType==FileType.OneWord){
                for (String keyword : words) {
                    StringBuilder word = new StringBuilder();
                    word = word.append(keyword);
                    String key = word.toString().toLowerCase();
                    hash.put(key, hash.getOrDefault(key, 0) + 1);

                    word = null;
                    key = null;
                }
            }else{
                for(int i=0;i<words.length-1;i++){
                    String word1 = new StringBuffer(words[i]).toString().toLowerCase();
                    String word2 = new StringBuffer(words[i+1]).toString().toLowerCase();

                    StringBuffer word = new StringBuffer();

                    word = word.append(word1).append(" ").append(word2);
                    String key = word.toString().toLowerCase();

                    hash.put(key, hash.getOrDefault(key, 0) + 1);
                    word1 = word2 = null;
                }
            }
        }
        reader.close();
    }

    private void writeFile(FileType fileType) throws IOException, FileNotFoundException{
        System.gc();
        ValueComparator vc = new ValueComparator(hash);
        TreeMap sortedMap = null;
        if(fileType == FileType.OneWord){
            sortedMap = new TreeMap(vc);
        }else{
            sortedMap = new TreeMap();
        }
        sortedMap.putAll(hash);

        String outFile = "";
        if(fileType == FileType.OneWord){
            outFile = fileDir + "data_one_word.txt";
        }else{
            outFile = fileDir + "data_two_word.txt";
        }

        Charset utf8 = Charset.forName("UTF-8");
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(outFile),utf8));

        HashMap map = null;
        Set<Map.Entry> entries = null;

        if(fileType == FileType.TwoWord){
            map = new HashMap(sortedMap);
            entries = map.entrySet();
        }else{
            entries = sortedMap.entrySet();
        }

        for (Iterator<Map.Entry> i = entries.iterator(); i.hasNext(); ) {
            Map.Entry e = (Map.Entry) i.next();
            writer.append(e.getKey()+"\t = \t"+e.getValue());
            writer.newLine();
        }
        writer.close();
    }
}

Third File:

package tweetfile20million;


/**
 *
 * @author KayD
 */
public class TweetFile20Million {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        FileOperation obj = new FileOperation();

        long startTime = System.currentTimeMillis();
        obj.readText(FileType.OneWord);

        long middleTime = System.currentTimeMillis();
        obj.readText(FileType.TwoWord);

        long endTime = System.currentTimeMillis();

        long elapsedTime = endTime - middleTime;
        System.out.println("Total elapsed time of File 02: "+ elapsedTime);

        long elapsedTime2 = middleTime - startTime;
        System.out.println("Total elapsed time of File 01: "+ elapsedTime2);
    }
}
\$\endgroup\$
  • \$\begingroup\$ @Zak Code is working fine but its slow and throwing an outofmemory exception with 699 MB text file with 20 million lines. \$\endgroup\$ – Karandeep Singh Dec 17 '15 at 2:19
  • 2
    \$\begingroup\$ Thanks for adding the code. I'm reopening this question, with the assumption that the code works correctly on smaller files, and that it's a matter of scalability. \$\endgroup\$ – 200_success Dec 17 '15 at 4:17
8
\$\begingroup\$

Your code looks fine, but the situation you are running into is because you are loading everything into memory and doing everything linearly.

There are 3 aspects you can optimize your code which should give you pretty large gains:

1. Optimize Your Memory Utilization

Consider Storing Your Data In a DB or datastore. For 20 million words, you can have a maximum of 20 million records in your hash, which is doable, but by the time you get to 2 word combinations - you are talking about a ton of records. Let us conservatively say there are only 2000 unique words and we are picking 2 words each, we get nearly 2,000,000 records ( C(n,r) C(2000,2) - http://stattrek.com/online-calculator/combinations-permutations.aspx). 2 million records * 32 bytes per record + 4 * capacity = 100-200MB just for the hash. (http://java-performance.info/memory-consumption-of-java-data-types-2/). Chances are that there are many more than 2000 unique words and even if you don't have every single combination, it is still alot.

The first thing you can do is optimize your hashmap for the large size that you should be expecting. One of the reasons your code is slow is because hashmap is constantly trying to grow its size as it approaches its limit. If you set new HashMap<>(2100000), you can prevent some of this slowdown as it tries to grow the capacity of your hashmap.

Better yet though, I would recommend pushing this off to dedicated system like Redis. This would save you from running out of memory on the Java VM. Also, this will allow you to run multiple instances of this which segways into my next point of optimization.

2. Optimize your CPU Utilization

Right now, you're only running 1 CPU core. The modern computer has 2 if not 4 or 8 cpu cores which you are not using at all. So theoretically, you are only using 1/2, 1/4, or even 1/8 of your computing power. You can optimize this after you switch over to using a separate datastore like redis by spawning multiple processes doing the same task. The easiest way to do that is to divide the file up 4 or 8 files and run the same program on each of the files. You'll notice that your system utilization will go from 25% to a lot higher.

3. Optimize your IO

Lastly, you can optimize your IO. Disks generally read large chunks of data much faster than 1 line at a time. You are requesting bytes of data to be read which is a lot of overhead. If you re-write your code to read in 10 or 20 or 50MB at a time, you should see a performance increase in IO. You should be able to do this after you kick out storing the hash in memory and to redis.

Other Methodologies

Hope these suggestions help! Finally, if you are really looking to approach the task differently, you can look into using some Map/Reduce algorithm/framework like hadoop (https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html). With something like this, you can distribute the work to multiple computers and get the job completed extremely fast, though I think if you follow the 3 optimization techniques, you'll be in good shape enough.

\$\endgroup\$
  • \$\begingroup\$ PressingOnAlways's comment must be helpful above. \$\endgroup\$ – Jack Dec 17 '15 at 6:57
8
\$\begingroup\$

One smaller detail to add to PressingOnAlways' points:

Optimize your loops

Right now you're looping through the input file twice, once for FileType.OneWord and again for TwoWord. You may see a speed improvement by interchanging these two operations, so you get something more like

for line in reader {
    String[] words = lineToWords(line);
    updateHashOneWord(hash, words);
    updateHashTwoWords(hash, words);
}

And on a similar note, right now you're calling toLowerCase more than once per word. It may be faster to just turn the whole line to lowercase right before splitting it:

String[] lineToWords(line) {
    return line.replaceAll(...specialchars...)
               .toLowerCase()
               .split("\\s+");
}

void updateHashOneWord(hash, words) {
    for word in words {
        hash.put(word,
                 hash.getOrDefault(word, 0) + 1);
    }
}

void updateHashTwoWords(hash, words) {
    for wordPair in partition(2, 1, words) {
        key = new StringBuilder(wordPair[0])
                  .append(" ")
                  .append(wordPair[1])
                  .toString();
        hash.put(key,
                 hash.getOrDefault(key, 0) + 1);
    }
\$\endgroup\$
  • \$\begingroup\$ its still giving me error on updateHashTwoWords's line hash.put(key, hash.getOrDefault(key, 0) + 1); \$\endgroup\$ – Karandeep Singh Dec 17 '15 at 8:56
  • \$\begingroup\$ @KarandeepSingh This is all a bit pseudocode-y since I mostly write clojure. I was just trying to show a more efficient way to organize the functions. What kind of error are you getting? \$\endgroup\$ – BenC Dec 18 '15 at 3:36
  • \$\begingroup\$ I have changed my source file according to your suggestions, it was nice advice but I am still getting java.lang.OutOfMemoryError: Java heap space \$\endgroup\$ – Karandeep Singh Dec 18 '15 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.