check memory consumption

[oblonski]

and whether there is room to reduce it

[anurag1paul]

Can you suggest any areas where we can focus to reduce memory consumption?

[rajendrauppal]

@oblonski marvelous library. I too have same pain point. memory consumption is too high at present. can you please suggest any areas where memory footprint can be brought down. is it already done for jsprit? or is in pipeline? was profiling done for memory and time consumption? Would highly appreciate any pointers or starting points. Thanks!

[oblonski]

Hi, Why is it a pain point? How do you use jsprit?

[PGWelch]

@rajendrauppal Would you be able to run profiling using VisualVM (comes in the java jdk bin directory) to identify the part of the code causing the large memory consumption?

@oblonski I did once notice an out-of-memory exception running a larger problem (1000 jobs?) with limited memory available but I'm afraid I didn't note where it was coming from, although as I recall it might have been connected with one of ruin implementations. Do any of the ruin implementations (or a structure you use to record nearby jobs for ruins?) have O(n3) memory allocation? Or O(n2) but not using jagged arrays?

[oblonski]

There are various sources consuming significant memory.

• the neighborhood is definitely smth we should improve. there might be a) ways to do it faster and b) with less memory consumption. The neighborhood is used for the radial ruin strategy to select neighboring jobs faster.
• due to its generic nature, the StateManager use Objects rather than primitive types
• in generel we should look at Objects we can actually turn into Primitives and
• Maps/Sets we can turn into Arrays (latter does not only make it more memory efficient but also usually much faster)

If memory really is/gets an issue we can also think about storing states and other attributes with a very low-level approach such as it is done by @karussell in GraphHopper. He stores all attributes of an edge in a single long value using low-level bit operations. I think we should only do this if this is really an issue.

Edit: "From Java code to Java heap" is - I think - a nice article to understand memory consumptions of Objecs and Maps/Sets etc. better

[oblonski]

This https://github.com/graphhopper/jsprit/blob/master/jsprit-core/src/main/java/com/graphhopper/jsprit/core/problem/VehicleRoutingProblem.java#L571 is a very good example where we can use an Array of Arrays since at this point every job has an index. It would make it more memory efficient and faster to retrieve activities.

[karussell]

@PGWelch what does memory restricted mean? 2gb? I think we should not invest time here if e.g. 4gb is sufficient even for largish ~5k problems. Although on the other side: often a reduced memory usage leads to a good speed up (better caching, less GC, ...)

[PGWelch]

Probably around 1 GB, although as said I didn't record details at the time. I agree that there's no point reducing memory consumption if the benefits are low. Really we need some profiling and to find out the circumstances where this is becoming a problem ( @rajendrauppal ?), then make the call if its worth doing anything.

[anurag1paul]

Hi,
We were trying to solve a problem with 1000 shipments (both pick up and drop), 200 vehicles, multiple depots and with time window constraints. We were using Array based cost matrix, with fast regret. We tried to solve this problem on different servers but faced 'out of memory' error in servers with configurations of RAM upto 16 GB. Finally we were able to solve it on a 8 core, 16 GB RAM, 4 GB swap server with a max heap size of 17.5 GB. We used 15 threads with 1024 iterations and we got run-time as 29 minutes. Run-time can be reduced further if we use more cores, but we were wondering if it is possible to bring memory usage down.

[anurag1paul]

I used VisualVM to do memory profile for a 200 shipment, 50 vehicles, MPMD CVRPTW problem using array based cost matrix and fast regret and 1024 iterations. You can see the top memory using objects in the attached image.

[karussell]

We were using Array based cost matrix, with fast regret.

how exactly does it look like int[][] or double[][] or List<List<Double>>?

Can you find out where the source for the many and large ArrayList$Itr comes from?

[karussell]

Also we would be interested to list your use case here - let us know via email if you would like this too :)

[anurag1paul]

We are basically creating cost matrix as an object of class jsprit.core.util.FastVehicleRoutingTransportCostsMatrix, it is double[][][2]

    private Builder(int noLocations, boolean isSymmetric) {
        this.isSymmetric = isSymmetric;
        matrix = new double[noLocations][noLocations][2];
    }

For my case, isSymmetric is false. I will try to find out where ArrayList$Itr comes from.
Regarding listing, I will contact you via mail.

[oblonski]

This a807024 optimizes memory consumption significantly. When having 5000 services and 100 vehicles, it reduces memory consumption for the neighborhood calculation from 800MB to 50MB. Additionally, it reduces com time from 9sec to 5sec (which is - given the problem size - not that important ;)).

[PGWelch]

@anurag1paul (and @oblonski ) The code:

matrix = new double[noLocations][noLocations][2];

Looks to me like it allocates a single block of memory noLocations x noLocations x2 x 8 bytes (for double) big. I believe this will create OutOfMemory exceptions a long time before the system actually runs out of memory, because of memory fragmentation - e.g. the system might have 1 GB available but the longest continuous piece of free memory is only 10 MB.

To be safe, the allocation should be jagged:

matrix = new double[noLocations][][];
    for(int i =0 ; i < noLocations ; i++){
        matrix[i] = new double[noLocations][2];
    }

[PGWelch]

p.s. @oblonski - great work on bringing the neighbourhood memory consumption down. I think that was where I hit the out-of-memory when running in a limited memory environment

[karussell]

I believe this will create OutOfMemory exceptions a long time before the system actually

And I doubt that it requests a contiguous block from the JVM - where did you read about this?

Also for 5K locations this is just 25MB and for 10K it is 800MB where probably other tweaks like using float instead double should be tried.

[PGWelch]

@karussell The java spec doesn't state whether its a contiguous block or not, so it may well be contiguous, and if this is the case the non-jagged version of the allocation is potentially dangerous. I know in C++ this kind of allocation would be contiguous (so I'm mainly guessing based on parallels with C++).

I calculate 5K locations as 381 MB using 5000 * 5000 * 2 * 8 / (1024 * 1024) and 10K as 1.5 GB. How do you get 25MB? Am I missing something obvious here?

[karussell]

Ups, missed the factor 8 but why 2?

Did you ever had an issue related to continguos and not?

[oblonski]

I assume 2 is related to time AND distance, i.e. you need to memorize two double values for each relation.

[PGWelch]

I've had an issue with a contiguous 1d array in java, causing out of memory on a few hundred thousand entries when there was easily enough memory available for it (but just not contiguous memory). Of course new double[noLocations][noLocations][2] is multi-dimensional but (AFAIK) the java spec doesn't say whether this would be one contiguous block or not (so I would consider it dangerous). Memory fragmentation is a well-known issue in high-performance C++ but of course the java memory model is different.

[karussell]

Just thought about the big matrix. For really big ones we could use a GraphHopper DataAccess object (or similar on disc approach) and access the matrix via memory mapping (or if enough memory via RAM). This way the access will be a bit slower but OS will make it faster for frequently used entries.

[PGWelch]

Interesting. I think for problems that big, you'd need to apply clustering techniques anyway before running in jsprit (though the clustering techniques would need a big matrix).

[oblonski]

close this for now

[karussell]

@oblonski maybe it could be interesting to comment on the 'large vrp' discussion too? Was it this one? https://discuss.graphhopper.com/t/very-large-vrp/766/5

[oblonski]

Jari Kytöjoki, Teemu Nuortio, Olli Bräysy, Michel Gendreau [p.2748] proposed a way to reduce memory consumption of storing 20k x 20k time and distance matrix from 5.96GB to 0.186-0.378GB (case dependent).

[karussell]

I would think 6gb is okayish but probably the matrix is not the (only) issue :)

[muzuro]

may be it is related with #282

[rajendrauppal]

@oblonski any tentative timeline on releasing this

[oblonski]

it is partly contained in the master already. we plan to make a new release this month

[oblonski]

We made huge improvements here also thanks to @muzuro. I close this for now.