Today, I was checking the official solution for problem grassplant of USACO 2011 December Contest. I ran the solution on 12th test and it gave me runtime error (segmentation fault). I realized it was caused by stack overflow. Then (somewhy) I added (int) before E[u].size() in the function hang() and ran it on 12th test again. Surprisingly, stack did not overflow this time.
I tried doing it several times, and the code without (int) always run out of 8Mb of stack memory and the code with it used less than 8Mb of stack memory.
Can anyone who gets this stuff tell why this happens?
Hey, From the solution that you have mentioned I could see E as a vector they how can you calculate E[u].size() as E[u] is an int
E is array of vector of ints. E[u] is vector of ints. So it is possible to get the size() of E[u]. :P
Try to replace
int i = 0bysize_t i = 0.That should work too, I guess.
I was able to repeat it only when compiling with -O0 on 64 bit system.
Stack usage for both versions is close to limit, increasing it from 8MB to 9MB allowed nocast version to pass, decreasing from 8MB to 7MB caused both versions to fail.
Looking at disassembled code first version uses 96 bytes of stack, but second 80. Why is that?
Comparing int to equal or bigger size unsigned integer (vector::size()) causes it to be casted to the same size unsigned integer, which used one more register. That resulted in this register being saved in stack at the beginning of function thus resulting slightly bigger stack usage. But single register takes only 8 bytes, other 8 bytes were probably used for alignment.
When compiling with -O2 both versions use 80 bytes of stack.
Keep in mind that most of this is specific to this combination of architecture, compiler, compiler flags and code.
What you should remember that in C/C++ comparing integer to unsigned integer will result in integer casted to the same type as unsigned integer, unless intger type is bigger. That may result in unexpected results if integer is negative.
I like it when things make sense :) Thank you.