mbrc's blog

MLE in Java
By mbrc, history, 8 years ago, In English

I was trying to solve 618E - Robot Arm from the last contest using 15683254. But (strangely?) I suffer a MLE on (pre)test 5. I thought I was using only static memory (each of the 3 arrays has fixed size), so any memory limit exceed error must occur right on the first test, if it occurs later.

I'm new to Java, so can anyone explain why I'm getting a MLE on #5? Where is the extra memory I'm using being allocated?

Thanks in advance!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think it's because of object headers: each object stores some "header" (size may vary, something like 12 bytes, afaik) together with fields. Plus, Cmplx[] a is not the same as Cmplx a[] or vector<Cmplx> a in C++, it's more like Cmplx* a[] — array of pointers to objects.

Not so sure how all these add together to occupy more than 256 MB of memory, though. Maybe it's garbage collector who does not do his job properly because default run parameter is to worry about fitting into 512MB of memory, not 256MB. If that's correct, then each operation with complex number creates another object and does not get rid of the previous one and memory leaks quickly.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the reply. :)

    I tried changing Complx[] S to Complx S[] and also changed the other arrays : 15689135 . Still MLE remains. :(

    Is there any way to change the default run parameter to make the garbage collector fit into 256 MB?

    According to my calculations. I have (in effect) 2 arrays of size 8*4*10^5, each element taking up 8+8+12 = 28 for the two doubles and overhead. So total memory ~ 179 MB.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      There is no difference between Complx[] S and Complx S[]. There is no way in Java to allocate an "in-place" array of objects.

      Have you measured memory footprint on maxtest locally? If yes, and it's over 256, try some memory profilers. Or simple PM some top coder who uses Java :)

      → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Can you try add static to Cmplx declaration?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, that change made it Accepted : 15715799 :o :D

    Thanks! :)

    BTW : Why was static so magical?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You may read about that here. Briefly: each instance of non-static nested class holds an additional reference to the object of outer class which 'created' it. Additional pointer. Static nested classes do not do that, they're not tied to a specific 'outer' object.

      → Reply