Thread: Increase heap size; 4 GB wall?

Hello everyone,

First, let me thank you for looking at my problem and any time you put into helping me.

For my own entertainment and as a learning project, I have created a Java app that plays scrabble. It is meant to be used as a complement to a physical scrabble set. It is essentially a scrabble AI that will let you add one (or more) computer-controlled players to your traditional sit-down scrabble board game. It does not have the functionality to let you play without a physical board (adding such functionality would, for one, violate the IP rights of Mattel, Inc).

My system:
Eclipse SDK 64-bit
Version: 3.6.0
Build id: I20100608-0911
java -version returns:
java version "1.6.0_21"
Java(TM) SE Runtime Environment (build 1.6.0_21-b06)
Java HotSpot(TM) 64-Bit Server VM (build 17.0-b16, mixed mode)
Windows 7 64-bit
Hardware
Dual Opteron "Shanghai" quad-cores (~2.9 GHz)
16 GB system memory

The AI algorithm is straightforward and brute-force. It finds every playable word, figures out the point value of each, and plays the highest scoring one. This requires vast amounts of memory and CPU time. The analysis is run with one thread per square on the game board, these threads are dispatched to a thread pool that runs as many threads in parallel as there are logical cores on the system.

When creating all these threads (450 in all, 2 for each tile), I get an OutOfMemoryException. Not unexpected. Each thread does after all have its own instance of a 160 000-entry dictionary. Problem is, this happens at a mere ~4 GB (according to windows task manager). Now before you say it, yes, I should get a hold of myself and only instantiate the new threads as the old ones finish. I probably will do that eventually. But since this is a learning project, I would like to figure out why I can't seem to increase the heap past 4 GB.

I have tried setting -Xmx in the eclipse.ini file, and a number of other options. My current settings are:
-startup
plugins/org.eclipse.equinox.launcher_1.1.0.v20100507.jar
--launcher.library
plugins/org.eclipse.equinox.launcher.win32.win32.x86_64_1. 1.0.v20100503
-showsplash
org.eclipse.platform
--launcher.XXMaxPermSize
256m
--launcher.defaultAction
openFile
-vmargs
-Xms8g
-Xmx12g
-Xmn6g
-XX:+UseParallelOldGC

-Xloggc:c:tempe.txt
-XX:+PrintGCDetails
-XX:+PrintGCTimeStamps
-XX:+PrintTenuringDistribution
-verbose:gc
-XX:+UseParallelGC

My last run returned this GC log file:
1042.360: [GC
Desired survivor size 805306368 bytes, new threshold 7 (max 15)
[PSYoungGen: 2548108K->42180K(5505024K)] 2548108K->42180K(7602176K), 0.0444170 secs] [Times: user=0.22 sys=0.06, real=0.05 secs]
1042.405: [Full GC (System) [PSYoungGen: 42180K->0K(5505024K)] [ParOldGen: 0K->41782K(2097152K)] 42180K->41782K(7602176K) [PSPermGen: 65435K->65402K(65600K)], 0.1811456 secs] [Times: user=0.47 sys=0.06, real=0.20 secs]
1097.871: [GC
Desired survivor size 805306368 bytes, new threshold 7 (max 15)
[PSYoungGen: 309330K->96K(5505024K)] 351112K->41878K(7602176K), 0.0021289 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
1097.874: [Full GC (System) [PSYoungGen: 96K->0K(5505024K)] [ParOldGen: 41782K->41656K(2097152K)] 41878K->41656K(7602176K) [PSPermGen: 65411K->65411K(65600K)], 0.1760697 secs] [Times: user=0.66 sys=0.00, real=0.19 secs]
Heap
PSYoungGen total 5505024K, used 315971K [0x0000000305420000, 0x0000000485420000, 0x0000000485420000)
eden space 4718592K, 6% used [0x0000000305420000,0x00000003188b0d40,0x0000000425 420000)
from space 786432K, 0% used [0x0000000455420000,0x0000000455420000,0x0000000485 420000)
to space 786432K, 0% used [0x0000000425420000,0x0000000425420000,0x0000000455 420000)
ParOldGen total 2097152K, used 41656K [0x0000000185420000, 0x0000000205420000, 0x0000000305420000)
object space 2097152K, 1% used [0x0000000185420000,0x0000000187cce1c8,0x0000000205 420000)
PSPermGen total 67136K, used 67133K [0x0000000180020000, 0x00000001841b0000, 0x0000000185420000)
object space 67136K, 99% used [0x0000000180020000,0x00000001841af6e8,0x0000000184 1b0000)

I must admit that I'm still a novice at trying to configure the Garbage Collector. I only have a vague idea of what the generations are and how they interact etc...

I can think of a couple reasons I would see this behavior:
1) For some reason my attempts at setting the heap size are not having any effect, and GC ergonomics auto-initialize to 1/4 of available memory, aka 4 GB.
2) Windows for some reason will not give the process more than 4 GB of memory, and the GC times out due to excessive paging. If this were happening, shouldn't I be seeing an entry in the log about it?
3) For some reason, I'm still limited to a 32-bit virtual address space, even though I'm running both 64-bit eclipse and 64-bit java. 2^32 = 4 294 967 296 and I usually top out at a memory usage of ~4 220 000 kb, so it certainly seems plausible.

Does anyone have any insight? I'd be happy to provide the source code, but it's pretty long so I figured I'd ask if you want to see it first.

Thank you in advance for any help!

Edit: I pasted the wrong log file at first

Hmm no I didn't set the parameter for the program. I had assumed that Eclipse would do that for me.

I do need separate instances of the dictionary; I eliminate words from the dictionary if they wouldn't be a valid play. That way I don't have to calculate scores for words that I couldn't play anyway. I was kind of surprised at the memory footprint this evidently requires; I though ArrayList.clone() would return only a shallow copy, which shouldn't really be all that huge.

I will try setting the parameters as you suggested.

Even if ArrayList.clone creates a shadow copy, you still need references to every object in the array (and a few others not actually accessible at that time due to the underlying implementation of ArrayList), and 64 bit pointers take 8 bytes each. So, that's about 550 MB of memory just to keep track of the references. The big memory waster is the having 450 running threads. There is no performance benefit from running so many threads (unless you have 450 cores or are using the GPU to do the calculations), and actually will reduce performance (450 threads is a ton of memory).

A better way to solve the problem is to create ~4-8 threads (depending on how many cores the computer has) and just assign them new tasks as they finish their last task.

Some small tidbits about how the JVM performs garbage collection (and other Java memory management things):

The JVM doesn't garbage collect right away once an object can be garbage collected. Instead, it will allow the item to sit in memory for a while. You can manually tell the JVM to perform a garbage collect, but normally this is unecessary. As a side note, even though the physical limit for 32-bit applications is 4GB, Windows limits 32-bit applications to 2GB (because windows needs some memory for itself and also because other programs will need memory, too).

Also, this program could probably run with 2-3 GB memory. The default Java setting I believe is to limit the heap size to 256MB, or it may be 512MB.