Extremely slow even with TLongObjectHashMap

Question

I need to put about 20 million entries into a HashMap. I chose TLongObjectHashMap as per :Why is Java HashMap slowing down?

The code looks like:

StringBuilder sb = new StringBuilder("");
StringBuilder value = new StringBuilder("");
TLongObjectHashMap<String> map = new TLongObjectHashMap<String>();

in = new FileInputStream(new File(inputFile));
br = new BufferedReader(new InputStreamReader(in), 102400);
for (String inLine; (inLine = br.readLine()) != null;) {
    sb.setLength(0);
    for (i = 0; i < 2; i++) {
                for (j = 1; j < 12; j++) {
                    sb.append(record.charAt(j));
                }
            }

            for (k = 2; k < 4; k++) {
                value.append(record.charAt(k));
            }
            for (k = 7; k < 11; k++) {
                value.append(record.charAt(k));
            }
    map.put(Long.parseLong(sb.toString()), value.toString());
    value.delete(0, value.length());
}

I used the GNU Trove. Still, becomes extremely slow and almost stops at about 15 million entries. There is no OutOfMemoryError yet. What is the problem?

I have no option to use DB for this.

Note: the values like are 1, 12, 2,4, etc are calculated before this loop and stored in a variable, which in turn will be used here. I just replaced them with some values now

Answer 1

I used the GNU Trove. Still, becomes extremely slow and almost stops at about 15 million entries. There is no OutOfMemoryError yet. What is the problem?

The problem is that you're making assumptions and not verifying them.

And you're not profiling your code. Your real code, not the half-edited stuff that you've posted here (hint: when the variable names don't match up, it's obvious that it's not the real code).

Yes, you're writing inefficient code. Those loops for copying characters, for example, duplicate String.substring(). You've already been told that. but it was buried in the mass of comments and you probably missed it. Another good comment was to use simple concatenation of those substrings, rather than mucking around with StringBuilder.

But the real problem is assuming that your map is inefficient, based on something that you read on the internet, and have done nothing to challenge that assumption. I can guarantee that the time taken to read records from disk is far greater than the time to insert one value in the map for each record.

What you need to do is to prove that to yourself. Profiling your code is the best way to do this, but you can also separate out the pieces of the program. Use a simple loop like the following to get a sense of how fast your map really is (I used HashMap because I don't have the Trove library installed; it took approximately 2 minutes to fill the map with 100,000,000 entries). I'll leave it to you to write a similar test for reading data from your file.

private static Map<Long,String> fillMap(int items)
{
    Map<Long,String> map = new HashMap<Long,String>(items);
    Random rnd = new Random();

    long start = System.currentTimeMillis();

    for (int ii = 0 ; ii < items ; ii++)
    {
        map.put(new Long(rnd.nextLong()), new String("123456789012345678901234567890"));
    }

    long finish = System.currentTimeMillis();
    double elapsed = ((finish - start) / 1000.0);
    System.out.format("time to produce %d items: %8.3f seconds (map size = %d)\n", items, elapsed, map.size());
    return map;
}

Answer 2

I do not belive JDK built-in HashMap can not deal with this. There are 2 problems I see

• Constant rehashing of the map as it grows
• String builder objects that are not nessasary

Rehashing takes place when underlying storage array load factor reaches 75%

DEFAULT_INITIAL_CAPACITY = 16;  
DEFAULT_LOAD_FACTOR = 0.75;  
THRESHOLD = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR;

I assume following is exponentially less work and does the same

double expected_maximal_number_of_data = 30000000d;
int capacity = (int) ((expected_maximal_number_of_data)/0.75+1);
HashMap<Long, String> map = new HashMap<Long, String>(capacity);
for (String inLine; (inLine = br.readLine()) != null;) {
    Long key = Long.parseLong(record.substring(1, 12));
    String value = record.substring(2, 4) + record.substring(7, 11);
    map.put(key, value);
}

If your computer has 2gb ram you should not have a problem, estimated completion time is <16s.