I have one probably dumb question. I am currently testing CSP solvers choco and jacop. When I run profiling of the app (graph colouring, about 3000 nodes), I dont fully understand the results.

The used heap space declared by profiler is about 1GB of memory. The sum of all object created is less than 100MB. Where are the other 900MB of RAM?

I think that method calls (solvers probably use massive backtracking) are being alocated on stack, so here should not be the problem. When I reduce maximum memory by using Xmx param, the app fails with exception:

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded

So it seems, that the rest isnt unused uncollected memory (because in this case the GC would dealocate it (and would not fail)).

Thanks for your help.

Can you get a map of the heap? Most likely it's fragmented so those 100M of objects are spread out across the entire memory space. The memory needed is both a function of allocated objects and how fast they're being allocated and then de-referenced. That error means the memory area is too small for the work load, the garbage collector is consuming a lot CPU managing it, and it went beyond the allowed threshold.