Floyd Warshall

[ibi22]

Hi all!

I have implemented floyd warshall's algorithm but I'm facing problems when running it.
The problem occurs when I initialise a 2D array of doubles.

for i = 0..n
for j = 0..n
if(i == j) {
w[i][j] = 0;
} else {
w[i][j] = Double.POSITIVE_INFINITY;
}

The graph that I use, is a graph of a small city, from which I use about 18 000 nodes (n = 18 000)
This matrix initialisation always cause a exception on the Java heap size being exceeded (I put the heap size on the maximum of 1024M already)

What troubles me is how to get by this problem. I can't imagine everybody who ever implemented this algorithm to be using a supercomputer with loads of memory. So I know I must be doing something terribly wrong, but I just have no clue where I'm screwing things up.

[DavidFongs]

Not sure what your problem is, since you posted pseudo code. Also keep in mind if n is 18,000, and you are using two nested loops from 0 to n, you actually have 18,000 * 18,000 = 324,000,000 nodes

[ibi22]

Yeah, I know space complexity is n square, so indeed about 300 million iterations. this is the code I use, basic thing:

double[][] weights = new double[18000][18000];
for(int i = 0; i < weights.length; i++) {
for(int j = 0; j < weights.length; j++) {
if(i == j) {
weights[i][j] = 0;
} else {
weights[i][j] = Double.POSITIVE_INFINITY;
}
}
}

Don't know whether the out of memorybounds exception is natural for an array this size. But either way I thought heap size is only affected by allocation for objects, not primitives?

I'm without a clue :)

[ajhampson]

I used the following code (from your post)
class FloydWarshall
{
public static void main(String[] args)
{
double[][] weights = new double[18000][18000];
System.out.println("weights.length = " + weights.length);

for(int i = 0; i < weights.length; i++)
{
for(int j = 0; j < weights.length; j++)
{
if(i == j)
{
weights[i][j] = 0;
}
else
{
weights[i][j] = Double.POSITIVE_INFINITY;
}
}
}
}
}


Using the command line

$JAVA_HOME/bin/java -Xms1G -Xmx3G FloydWarshall

ran the program on my system. I do have 4 Gig of system RAM, so there was space to go up to 3 gig for the runtime. Once I did that, the new statement was able to run to completion.

Where did you see the JVM limit as 1024M? You are limited to the physical RAM in your system, but memory is cheap these days.

[ibi22]

How much time did completion take with your hardware setup?

If buying extra memory is the only solution, then I may need to do so. But I just want to make sure that there is absolutely no way to make this program more efficiënt. (Just in the same way that building more fuel-efficient cars is better than harvesting more fossil fuels)

[ajhampson]

How much time did completion take with your hardware setup?

If buying extra memory is the only solution, then I may need to do so. But I just want to make sure that there is absolutely no way to make this program more efficiënt. (Just in the same way that building more fuel-efficient cars is better than harvesting more fossil fuels)

It takes about 2.5 minutes: around 1 minute 50 seconds to get to the println, the rest of the time in the loops.

[ibi22]

Ok, I upgraded my core 2 duo imac from 2x512MB RAM to 1GB RAM + 2GB RAM. The system recognizes the new 3GB RAM on Mac OSX and on my bootcamp booted windows partition.

I use eclipse and had the VM arguments on -Xmx1024M and tried switching it to -Xmx2G. This gives this error:

Error occurred during initialization of VM
Could not reserve enough space for object heap

I tried gradually decreasing the amount of used memory, every time getting the same error. The highest amount of RAM I could use is -Xmx1600M. Which still isn't enough to run the program without running out of heap size.

Why can't I use the full amount of memory? (well not the full 3GB ofcourse, but at least I would like to be able to use 2GB to 2,5GB)

[ajhampson]

Why can't I use the full amount of memory? (well not the full 3GB ofcourse, but at least I would like to be able to use 2GB to 2,5GB)

I think this is either an eclipse question (eclipse forums) or a Win on Mac question. I can't help there.

How are you specifying the Xm* arguments? I think eclipse might be using enough memory on its own that combined with the OS, you don't have enough left to create the required heap space.

What I suggest is that you export an ant build file from eclipse and try to build and run the program from the command line. When I built the test I used, I edited with Kate and built from bash; no IDE involved. Less convenient, but more efficient.

[ProgramThis]

I tried gradually decreasing the amount of used memory, every time getting the same error. The highest amount of RAM I could use is -Xmx1600M. Which still isn't enough to run the program without running out of heap size.

Why can't I use the full amount of memory? (well not the full 3GB ofcourse, but at least I would like to be able to use 2GB to 2,5GB)
Java in and of itself was not designed to be a high performance language used to calculate such complex algorithms. If you want a language that can easily handle things like this you should look at LISP, Scheme, ML or F#.

That being said, eclipse is even worse. It is a huge memory hog (not that visual studio isn't, just saying) and really can't handle heavily memory intensive programs. My suggestion would be to code the program in eclipse, but run it outside of eclipse at the command line. You are then not limited by the capabilities of the IDE. I have run into numerous problems with eclipse being able to handle even large ANT scripts for compiling, let alone complex algorithms.