Thread: ArrayList memory bloat that I cannot comprehend

I apologise for jumping right into a question, but I ran into the sort of behaviour that just makes no sense to me. It's like looking into the face of Great Cthulu - it's something that should not be, or at least I don't get why it is.

Here's the situation: I've been given what should be an embarrassingly basic task - load two files into memory. My plan was to load them in as ArrayLists, but I started running out of memory for the second file. I was attempting to load tab-delimited rows and split them into arrays, constructing an ArrayList of actual arrays. Probably inefficient, yes, but I didn't expect to run out of a GB of memory for a 100M file. Switching to simply loading the file's rows as basic Strings cut the memory usage down to a mere fraction of what it was before. OK, so lesson learned, I thought. A String split into arrays takes up more memory than a basic array.

Except then I did the same to the first file and that started using MORE memory. For the first file, I was loading two rows from the hard drive at a time and combining them into a single array of two elements, then adding them to the ArrayList. So I changed this to instead concatenate the the two rows into a single String, and that bloated both my memory used and the time taken by almost double. Processing time I get - concatenation messes with Strings, so it presumably takes longer. Fair enough. But why does switching from an array to a String now cost me MORE physical memory?

My actual working code is kind of spaghetti, so I compiled a small example that's actually very telling:

public class Test
{
	public static void main(String[] args)
	{		
		String string1 = "cat";
		String string2 = "dog";
		String string3 = "rabbit";
		String string4 = "mouse";
		String string5 = "eagle";
		String line = string1 + " " + string2 + " " + string3 + " " + string4 + " " + string5;
 
		ArrayList<String> list = new ArrayList<String>();
		for(int i = 0; i <= 1000000; i++)
		{
			list.add(line);
		}
		System.out.println("Total used memory so far:" + (Runtime.getRuntime().totalMemory()/1048576) + "MB");
 
		ArrayList<String> list2 = new ArrayList<String>();
		for(int i = 0; i <= 1000000; i++)
		{
			list2.add(string1 + " " + string2 + " " + string3 + " " + string4 + " " + string5);
		}
		System.out.println("Total used memory so far:" + (Runtime.getRuntime().totalMemory()/1048576) + "MB");
	}
 
}

Run together, this produced the output of:

Total used memory so far:15MB
Total used memory so far:155MB

Just the first cycle creates a footprint of 15MB, which I believe is within the footprint of he JVM, while just the second cycle produces a footprint of 137MB.

But why is this happening? Both cycles do the exact same thing, with the only difference being how they do it. The first cycle uses the concatenated variable "line" that's built from the five previous variables while the second cycle uses the five variables directly and concatenates them in the process of creating the list. The result is two identical lists with the same number of elements and the same element contents, yet the second one is ten times as big as the first one, and I do not know why. I don't know enough about Java "under the hood," but I can speculate some kind of garbage builds up as this is happening. I scoured the Web and it seems like I can't call the Garbage Collector. I can suggest it run, and running it through System does take down a good 20MB off the total pile, but it doesn't take down the 100+MB that make up the bulk of the difference.

Why do two ArrayLists with IDENTICAL contents differ in size so massively, and what can I do to avoid it? At this point, I've pieced it together that directly loading strings takes less memory than loading arrays, which takes less memory than loading concatenated strings and this just makes no sense to me. I'm sorry if this doesn't seem to make sense, but I failed my saving throw upon seeing the above example, lost 10 Sanity and now have a phobia of formatted text. I cannot understand why this is happening, and if I can't understand why it's happening, I don't know what I can do to prevent my programme blowing through a GB of memory for something which should not take this much.

*edit*
I do have a few more tests I can post, but I'd like to wait for a response so I know I'm not just going crazy.

They may have identical contents but when you concatenate strings in Java it needs to create a new string to store the data. Strings in Java can also be interned, meaning that strings with identical contents are cached as a single copy. I don't think concatenated strings are automatically interned, but this isn't something I've paid too close attention to. Java also utilizes a Garbage Collector which means that the runtime can decide when it wants to reclaim memory. Almost always this is not immediately when an object is no longer referred to.

Lastly (and probably most importantly), the Javadoc for totalMemory says that this method returns the amount of memory current available to the JVM. This is memory which is currently being used for objects, memory being used for objects waiting to be garbage collected, and memory currently not in use (free memory). The JVM will allocate memory lazily (i.e. it will increase the amount of available memory if it thinks it needs to). To get the amount of memory in use subtract the amount of free memory (see: What is the exact meaning of Runtime.getRuntime().totalMemory() and freeMemory()). Note that this method doesn't account for memory currently waiting to be garbage collected. You can try to mitigate this by calling System.gc() to suggest a garbage collect, but no guarantees (see: Why is it a bad practice to call System.gc())

There are a couple misunderstandings here.

The value returned by Runtime.totalMemory() isn't what your program is currently using- it's how much total memory it has had to use. Java allocates memory lazily, and the total memory is simply how much of the max it has allocated. You can also compare it to Runtime.freeMemory() to get an idea of how much is currently in use.

But even that isn't really telling the whole story- even if you use System.gc(), you don't have control over when garbage collection occurs. So even if you see that you're using a bunch of memory at a given time, that could just mean that the garbage collector hasn't run yet.

Also, you're using String concatenation in a loop, which is a pretty big memory no-no. Under the hood, Java is instantiating a StringBuilder for each concatenation. The better way to do this is instantiate your own StringBuilder and use that single instance instead of creating a million instances.

Hope that helps.

Well, you're doing two very different things here: in the first loop, you're adding the same instance of String to a List over and over again. That's not going to take up much memory. In the second loop, you're creating a new instance of a String array for each iteration. That's a million different instances versus only one instance in the first loop.

To show what I mean, try this as your first loop:

ArrayList<String> list = new ArrayList<String>();
		for(int i = 0; i <= 1000000; i++)
		{
			list.add(new String(line));
		}

And this as your second loop:

ArrayList<String[]> list2 = new ArrayList<String[]>();
		String[] arr = line.split(" ");
		for(int i = 0; i <= 1000000; i++)
		{
			list2.add(arr);
		}

I would like to offer some musings and opinions and some data.

First of all, the OP was not asking about how to write efficient programs, but how to understand the results of using Runtime methods in determining memory requirements for a particular type of object, an ArrayList of Strings.

The setup for the experiment that I am reporting here is:
32-bit Java version 1.6.0_22 running on a 32-bit Centos 5.8 Linux workstation.

Here's my assumption. I welcome any enlightenment by anyone who has anything to offer.

I think that the difference between Runtime.totalMemory() and Runtime.freeMemory() can be calculated before and after creating an object and the difference would be an estimate of the amount of memory taken up by that object. It's only approximate, since the JVM is doing lots of things over which we have precious little direct control. (Garbage collection with occasional heap compaction, etc.)

Anyhow...

I put the two different types of loops into separate functions so that I could change them easily without accidentally screwing anything up in the main program.

I created the ArrayList in each case by using a constructor that designates the initial size of the array list rather than risking fragmentation of the ArrayList itself as I added the Strings.

For the first type of loop, I defined the common String in the main() method and passed it as a parameter to the function.
For the second type of loop, I created the String on the fly inside the function.

So: Here's my test program.

// Populate ArrayList<String> two different ways:
//
// loop1 uses a single common String for each element that is added
//
// loop2 adds a String created on the fly. The String itself
// is identical to the common String used in loop 1
//
//   Zaphod_b
 
import java.util.*;
import java.lang.*;
 
public class Z
{
    public static void main(String[] args) throws Exception
    {       
        long total, free, size0, size1, size2;
 
        int number = 1000000;
 
        String string1 = "cat";
        String string2 = "dog";
        String string3 = "rabbit";
        String string4 = "mouse";
        String string5 = "eagle";
        String line = string1 + " " + string2 + " " + string3 + " " + string4 + " " + string5;
 
        // Show memory parameters before the fun begins
        total = Runtime.getRuntime().totalMemory();
        free  = Runtime.getRuntime().freeMemory();
        size0 = total-free;
        System.out.printf("Initially   : totalMemory = %10d Bytes\n", total);
        System.out.printf("              freeMemory  = %10d Bytes\n", free);
        System.out.printf("              difference  = %10d Bytes\n", size0);
        System.out.println();
 
        System.out.printf("Creating ArrayList<String> objects with %d elements\n", number);
        System.out.printf("Length of string = %d\n\n", line.length());
 
        // First method: will put the "line" String in all of the elements
        ArrayList<String> list = loop1(number, line);
 
        total = Runtime.getRuntime().totalMemory();
        free  = Runtime.getRuntime().freeMemory();
        size1 = total-free;
 
        System.out.printf("After loop1 : totalMemory = %10d Bytes\n", total);
        System.out.printf("              freeMemory  = %10d Bytes\n", free);
        System.out.printf("               difference = %10d Bytes\n", size1);
 
        // How many bytes used in creating the ArrayList with 'number' elements
        System.out.printf("                    delta = %10d Bytes\n", size1-size0);
 
        // Is this meaningful?  How many bytes memory for each element.  I think so.
        System.out.printf("                delta / n = %10.6f\n", (double)(size1-size0)/number);
        System.out.println();
 
        // loop2 puts in the same string, but creates it on the fly
        // for each one.
        ArrayList<String> list2 = loop2(number);
 
        total = Runtime.getRuntime().totalMemory(); // Bytes
        free  = Runtime.getRuntime().freeMemory(); // Bytes
        size2 = total-free;
 
        // Summary for this one
        System.out.printf("After loop2 : totalMemory = %10d Bytes\n", total);
        System.out.printf("              freeMemory  = %10d Bytes\n", free);
        System.out.printf("              difference  = %10d Bytes\n", size2);
        System.out.printf("                    delta = %10d Bytes\n", size2-size1);
        System.out.printf("                delta / n = %10.6f\n", (double)(size2-size1)/number);
        System.out.println();
    }
 
    // Add a fixed String each time
    static ArrayList<String> loop1(int n, String line) {
        long total = Runtime.getRuntime().totalMemory();
        long free  = Runtime.getRuntime().freeMemory();
        long size0 = total-free;
        System.out.printf("Entry into Loop1 : totalMemory = %10d Bytes\n", total);
        System.out.printf("                   freeMemory  = %10d Bytes\n", free);
        System.out.printf("                   difference  = %10d Bytes\n", size0);
        System.out.println();
 
        // Allocate storage for length n
        ArrayList<String> list = new ArrayList<String>(n);
 
        total = Runtime.getRuntime().totalMemory();
        free  = Runtime.getRuntime().freeMemory();
        long size1 = total-free;
        System.out.printf("After allocation : totalMemory = %10d Bytes\n", total);
        System.out.printf("                   freeMemory  = %10d Bytes\n", free);
        System.out.printf("                   difference  = %10d Bytes\n", size1);
        System.out.printf("                         delta = %10d Bytes\n", size1-size0);
        System.out.println();
 
 
        for(int i = 0; i < n; i++)
        {
            list.add(line);
        }
        return list;
    }
 
    // Add a temporary String each time
    static ArrayList<String> loop2(int n) throws Exception {
        String string1 = "cat";
        String string2 = "dog";
        String string3 = "rabbit";
        String string4 = "mouse";
        String string5 = "eagle";
 
        long total = Runtime.getRuntime().totalMemory();
        long free  = Runtime.getRuntime().freeMemory();
        long size0 = total-free;
        System.out.printf("Entry into Loop2 : totalMemory = %10d Bytes\n", total);
        System.out.printf("                   freeMemory  = %10d Bytes\n", free);
        System.out.printf("                   difference  = %10d Bytes\n", size0);
        System.out.println();
 
        // Allocate storage for length n
        ArrayList<String> list = new ArrayList<String>(n);
 
        total = Runtime.getRuntime().totalMemory();
        free  = Runtime.getRuntime().freeMemory();
        long size1 = total-free;
        System.out.printf("After allocation : totalMemory = %10d Bytes\n", total);
        System.out.printf("                   freeMemory  = %10d Bytes\n", free);
        System.out.printf("                   difference  = %10d Bytes\n", size1);
        System.out.printf("                         delta = %10d Bytes\n", size1-size0);
        System.out.println();
 
        for(int i = 0; i < n; i++)
        {
            list.add(string1 + " " + string2 + " " + string3 + " " + string4 + " " + string5);
        }
        return list;
    }
}

Output on my system:

Initially   : totalMemory =    47841280 Bytes
              freeMemory  =    47590920 Bytes
              difference  =      250360 Bytes
 
Creating ArrayList<String> objects with 1000000 elements
Length of string = 26
 
Entry into Loop1 : totalMemory =    47841280 Bytes
                   freeMemory  =    47590920 Bytes
                   difference  =      250360 Bytes
 
After allocation : totalMemory =    47841280 Bytes
                   freeMemory  =    43590904 Bytes
                   difference  =     4250376 Bytes
                         delta =     4000016 Bytes
 
After loop1 : totalMemory =    47841280 Bytes
              freeMemory  =    43590904 Bytes
               difference =     4250376 Bytes
                    delta =     4000016 Bytes
                delta / n =   4.000016
 
Entry into Loop2 : totalMemory =    47841280 Bytes
                   freeMemory  =    43340480 Bytes
                   difference  =     4500800 Bytes
 
After allocation : totalMemory =    47841280 Bytes
                   freeMemory  =    39340464 Bytes
                   difference  =     8500816 Bytes
                         delta =     4000016 Bytes
 
After loop2 : totalMemory =   232128512 Bytes
              freeMemory  =   134134640 Bytes
              difference  =    97993872 Bytes
                    delta =    93743496 Bytes
                delta / n =  93.743496

Conclusion: For one million elements we see that the first loop allocates about four million bytes for the ArrayList. Then, after the ArrayList is populated, the memory usage reported back in the main() method hasn't changed. Still four million bytes. I conclude that the elements are actually pointers to the common String that they all refer to. In other words, I am seeing that it doesn't actually copy the Strings into the ArrayList object. (Maybe this is documented somewhere, but I wanted to test it on my system.)

If I just look at the bottom line for the second loop, the amount of memory after populating the second ArrayList is a lot more. I think this is because, inside the loop, a "temporary String" is allocated each time through the loop and each ArrayList member is set to point to a (different) "temporary String." The temporary Strings" must remain in memory after the loop2() function returns to main(), since references to them exist in the ArrayList. (A really smart optimization might recognize that the Strings are actually all the same so that it wouldn't need a million separate "temporary Strings," only one. You know, the kind of optimization you get with GNU g++ when you give it an -O3 command-line switch.) I'm kind of glad that it didn't optimize them down into one String, since that wouldn't have been so dramatic, right? I place no importance on the number of bytes per string in the results of loop2, but I printed them just the same. (Change number from a million to, say, one hundred thousand, and the results change.)

One further experiment:
After repeating the above experiment, set all of the elements of list2 to null. Then all of the "temporary Strings" have nothing referring to them, so the Garbage Collector can reclaim their memory.

So, add the following at the end of main():

        // Now, set list2 elements to "null" so that the Strings that they refer to
        // can be garbage-collected.
        for (int i = 0; i < list2.size(); i++) {
            list2.set(i, line);
        }
        // Force the Garbage Collector to do the deed
        System.gc();
        Thread.sleep(1000); // Give Garbage Collection a little time to work
        total = Runtime.getRuntime().totalMemory(); // Bytes
        free  = Runtime.getRuntime().freeMemory(); // Bytes
        long size3 = total-free;
        // Summary for this one
        System.out.printf("Grand finale: totalMemory = %11d Bytes\n", total);
        System.out.printf("              freeMemory  = %11d Bytes\n", free);
        System.out.printf("              difference  = %11d Bytes\n", size3);
        System.out.printf("                    delta = %11d Bytes\n", size3-size2);
        System.out.println();

The following appears at the end of the output on my system:

Grand finale: totalMemory =   289472512 Bytes
              freeMemory  =   287075336 Bytes
              difference  =     2397176 Bytes
                    delta =   -95596696 Bytes

So, indeed, it did reclaim the storage no longer needed as "temporary Strings." I didn't actually calculate the difference per String or anything else...

Warnings: The numbers may vary from run to run. Depending on what else is going on in my system, the JVM may be performing its tasks interleaved with other system operations. In particular, Garbage Collection/Heap Compaction may be going on at different rates, so, for example the allocation in loop2 might end up taking more memory. (Believe it or not.) Putting gc() and a second's delay before each allocation made my numbers more consistent when I ran this on a really old, really, really slow machine.

The real bottom line for me is that the test program is interesting because it made me examine some things that I, as a newcomer to Java, hadn't thought about (much) before. I mean, the results from the "loop1" test has no practical application as far as I can see, and, in fact, if we are trying to estimate system resource requirements before tackling a big project, simple little "tests" like loop1 can be very misleading. (I mean, in a "real" program what would be the point of creating an ArrayList with identical elements that would never change?)

Furthermore, as far as I can determine...

Figuring out the actual storage requirements for a particular object (especially something involving, say, Lists) may not be as obvious as "simple logical reasoning" and naive testing might suggest.

Cheers!

Z

The whole point is that the second loop is allocating a lot more instances, either of String or of a String array depending on which version of the code we're looking at. The first loop is only pointing a bunch of references to the *same* instance.

Let's say the ArrayList is something like a card catalog in a library. The books it references are on the shelves. The first loop is simply making a million copies of a card catalog reference for the same book. So you have references to a million books, right? Nope. You have a million references to one book. Now the second loop does something completely different, it creates a million books and a card catalog entry for each. So even though the card catalog in each library contains the same amount of entries, the shelves in the first library (which only contains a single book) are going to weigh a lot less than the second library (which contains a million books). I hope that metaphor didn't get away from me, haha.

OK, show of hands - that I was simply creating more references to the SAME ArrayList completely skipped my mind, and that would indeed explain a lot of the differences. I'll need to come up with a more comprehensive test that creates a brand new string for each repetition so that we can better imitate the behaviour of a real programme. Specifically, so we can better imitate the behaviour of a programme reading from memory, where a new String object would be fed in by a BufferedReader on every step, this ensuring I have unique objects.

My question stands, though, as what spawned it was more proper than the "test" I was using to try it out. My bad. I'll see if I can't come up with something better. Will update when I can, and see if I have more insight.

*edit*
OK, I found a bit more of a realistic example. Again, I apologise for the messy code. It's midnight and I'm trying to run fast experiments and not fuss over neatness until I know I'm doing the right thing so I can spend more effort on making it read well. Here's what I have:

package test;
 
import java.util.ArrayList;
 
public class Test
{
	public static void main(String[] args)
	{		
		String string1 = "cat";
		String string2 = "dog";
		String string3 = "rabbit";
		String string4 = "mouse";
		String string5 = "eagle";
		String line = string1 + " " + string2 + " " + string3 + " " + string4 + " " + string5;
 
		ArrayList<String> list = new ArrayList<String>();
		for(int i = 0; i <= 1000000; i++)
		{
			String testLine = new String(line);
			list.add(testLine);
		}
		long memory = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
		System.out.println("Total used memory so far:" + memory/1048576 + "MB");
 
		ArrayList<String> list2 = new ArrayList<String>();
		for(int i = 0; i <= 1000000; i++)
		{
			list2.add(string1 + " " + string2 + " " + string3 + " " + string4 + " " + string5);
		}
		long memory2 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
		System.out.println("Total used memory so far:" + memory2/1048576 + "MB");
 
		ArrayList <String> list3 = new ArrayList <String>();
		StringBuilder builder = new StringBuilder();
		for(int i = 0; i < 1000000; i++)
		{
			builder.append(string1);
			builder.append(string2);
			builder.append(string3);
			builder.append(string4);
			builder.append(string5);
			list3.add(builder.toString());
			builder.setLength(0);
		}
		long memory3 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
		System.out.println("Total used memory so far:" + memory3/1048576 + "MB");
	}
}

This runs three loops. I made sure the first loop created a separate String object for each iteration by explicitly invoking a new constructor for each string. They construct with the same contents, but the invoking the String constructor should ensure they're still separate instances. Running JUST that gave me 27MB of memory, which is much more significant than what it was using when just copying references. No surprise there. I'm also dividing to get MB because this absorbs some of the "signal noise" from catching the various bits here and there for JVM components. The 27MB number does not change.

The second loop is what I had before - concatenations inside a loop. As before, this bloats significantly, ending up with a used memory amount of 103MB, several times more. I can see why putting concatenation in a loop is a bad idea. I just wish I'd known about this before

The third loop is the new one, using a single StringBuilder that I "reset" on each iteration. I'm not entirely sure how to clear a StringBuilder, but I looked online and setting its size to 0 is what was suggested, so I did that. This uses up 86MB when it's done. That's less than direct concatenation but still considerably more than straight up adding strings, so something is clearly still leaving a footprint, and I still don't know what that is. You were right - using a single StringBuilder drops memory usage considerably and I'll definitely be using that, but I have to wonder why I'm still seeing bloat. Is the StringBuilder itself leaving garbage behind? Will that balloon badly when I go up to, say, 5 000 000 lines of text?

*edit*
And KevinWorkman, no, your metaphor did run away from you I actually rather like it, and I think I'm going to use it in the future. Thank you.

Plus, I'm glad I'm not the only one who puts opening curly brackets on a new line these days.

Your new loop is still allocating a new instance of String each iteration. It has less overhead because it's only using a single instance of StringBuilder, but you're still creating a new String each iteration. In your first loop, you're still only creating a single instance and simply pointing a bunch of references to it, which doesn't take up much memory. The program behavior you described is pretty much what I would expect to see.

You could probably get around this by interning the Strings, which only works because you happen to be dealing with the same String over and over again. I'm not sure how well that translates to your actual problem.

Sorry, I actually read it wrong- I didn't realize you were calling new String(string). That actually does create a new instance of String. You can test this by using the == operator on the original String and the newly created one.

But I think another major issue here is that your test doesn't really allow for garbage collection. For example, try adding a System.gc() before each memory calculation.

I suspect that you're experiencing a slightly different problem- even with the worst coding practices, using String concatenation in a loop shouldn't give you an OutOfMemoryError, it'll just use up more memory over time and be slower. I'd be curious to see an example that repeats the OutOfMemory problem, because that almost definitely shouldn't happen.

Oh, and using a HashMap won't fix any of these problems for you- in fact, they use more memory than a List. The only reason to use one is if you need the functionality that a Map gives you (looking things up by key instead of by index). I'm not sure why your coworker was suggesting to use them over a List, but they won't fix the memory problems.

Originally Posted by KevinWorkman

I suspect that you're experiencing a slightly different problem- even with the worst coding practices, using String concatenation in a loop shouldn't give you an OutOfMemoryError, it'll just use up more memory over time and be slower. I'd be curious to see an example that repeats the OutOfMemory problem, because that almost definitely shouldn't happen.

*edit*
4 AM, and my brain is slowing down

What's causing the OutOfMemoryEorror is the code I listed in this post, specifically the second loop. It's a mirror of what I was doing at work, and that depletes whatever the default memory allocation is before the loop ends. JUUUST before it ends, mind you, at step ~900 000 or some such, but before the end nevertheless.

I assume that if you fill the stack with enough crap, the whole JVM will eventually tap out stop prematurely. It has an upper memory limit, after all.

Originally Posted by KevinWorkman

Oh, and using a HashMap won't fix any of these problems for you- in fact, they use more memory than a List. The only reason to use one is if you need the functionality that a Map gives you (looking things up by key instead of by index). I'm not sure why your coworker was suggesting to use them over a List, but they won't fix the memory problems.

His suggestion wasn't really for efficiency so much as for ease of coding. He's a Perl programmer and REALLY loves using hashes, to the point where we've had arguments over what he should use in his programmes, so that's his prerogative. And to be fair, the programme I'm loading this data in memory for will benefit from using hashes, since I need to compare two unsorted files and pair rows with matching headers, among other things. I'm told a Hash Map searches faster than an ArrayList, but either should do, I think.

So a HashMap is more resource-intensive than an ArrayList? That's news to me, thank you for letting me know. I'm being asked to work with some sizeable files so I need to cut corners wherever I can. I'd rather it were clunkier to write if it worked better.

*edit*
Speaking of OutOfMemoryError, I just managed to construct another example. This one:

public class Test
{
	public static void main(String[] args)
	{		
		String string1 = "cat";
		String string2 = "dog";
		String string3 = "rabbit";
		String string4 = "mouse";
		String string5 = "eagle";
		String line = string1 + " " + string2 + " " + string3 + " " + string4 + " " + string5;
 
		ArrayList<String[]> list4 = new ArrayList <String[]>();
		for(int i = 0; i < 1000000; i++)
		{
			list4.add(line.split(" "));
		}
		long memory3 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
		System.out.println("Total used memory so far:" + memory3/1048576 + " MB");
	}
}

This one doesn't finish. Instead, it ends in this:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.util.ArrayList$SubList.listIterator(Unknown Source)
	at java.util.AbstractList.listIterator(Unknown Source)
	at java.util.ArrayList$SubList.iterator(Unknown Source)
	at java.util.AbstractCollection.toArray(Unknown Source)
	at java.lang.String.split(Unknown Source)
	at java.lang.String.split(Unknown Source)
	at test.Test.main(Test.java:51)

This is the other big one I wanted to ask about. I presume it's a big no-no to use split inside a loop for a similar reason to concatenation, but this one is actually by far the worst offender. The OutOfMemoryError test from before I could finish at work when I permitted Java more memory, but this one I couldn't finish anywhere. I'm assuming that string splitting produces some kind of cascading clutter, possibly a zillion arrays that it bifurcates into smaller and smaller pairs, but something about the whole process just kills my programme. Literally, in this case - it caused the runtime to crash. That's not even an exception, I've never seen OutOfMemoryError before.

HashMaps take up more memory but they are significantly faster at searching. However, in many cases I doubt the size of the base Hashmap structure will be significant compared to the size of the data you're trying to put into it.

If you have a sorted array it takes O(log(n)) to find something using a binary search. If it's unsorted it would take O(n) by iterating through the whole list.

HashMaps have an amortize O(1) search, depending on how many collisions there are and how you're handling collisions. The most common way to mitigate collisions is to have a large underlying memory footprint (much larger than the number of elements being stored by the hash).

Note that ArrayLists aren't completely free from wasting memory space, either. The way ArrayLists work is they allocate an array with an initial capacity and have a separate counter for the number of items in that Array. As you add items to the ArrayList they simply get put at the location of the "virtual end". When the virtual end reaches the actual capacity a new array with a larger capacity is allocated and all the items are copied over. A common implementation is to double the capacity each time the array fills up.

This may sound silly, but perhaps you simply just need more memory. Have you tried increasing the maximum amount of memory you allow the JVM to allocate? How to increase the JVM maximum heap memory:

java -Xmx1g ...

This increases the maximum heap size to 1GB. Note that to get larger than 2GB of memory you need a 64-bit JVM.

This is the other big one I wanted to ask about. I presume it's a big no-no to use split inside a loop for a similar reason to concatenation, but this one is actually by far the worst offender. The OutOfMemoryError test from before I could finish at work when I permitted Java more memory, but this one I couldn't finish anywhere. I'm assuming that string splitting produces some kind of cascading clutter, possibly a zillion arrays that it bifurcates into smaller and smaller pairs, but something about the whole process just kills my programme. Literally, in this case - it caused the runtime to crash. That's not even an exception, I've never seen OutOfMemoryError before.

If you're storing all the same data then this is definitely not the way to go because as you said you're just creating tons of new objects. However, for different data there really aren't a lot of ways around it.

I suspect the fundamental problem might be associated with how you're trying to solve the bigger problem. What problem are you trying to solve? You mentioned something about pairing rows with matching headers.

You say you don't need to write out the zero data to the new file, but do you need to keep it in memory? If you don't, as you read in the data file you can do a check first to see if you should keep that data or get rid of it.

Also, if you read in the data first then you don't have to keep every header item from the first file, only those you find in the second file which are valid. To make searches much faster this would be a good place to use HashMaps if the data is indeed unsorted.

Lastly I would suggest you change the way you read in data. Use a Scanner object so you can read in tokens directly rather than trying to read in a line and split it into the appropriate data. Read in numerical data as a float or double, unless you're not allowed to. These data types usually take up less memory than a String representation of the number.