Undeterministic GC behavior

[manuel-serrano]

Dear Ivan,

I have recently observed a strange (at least to me) behavior that I would like to share with you, mostly to know if, i) you understand it, ii) it is the sign of something going wrong, iii) it impacts performance.

On several deterministic benchmars that are GC intensive, I have observed that succesive runs produce different GC execution traces. More precisely, I have observed that running succesively the same (deterministic) program with the same inputs on the same computer does not necessarily yield to the same number of collections and the semae memory occupation. Here is an example of two traces (I have instrumented the collector so that at each collection, it displays the heap size, the number of allocations since the last collection, and the live space). Here are two observed traces:

-----	-----	-----	-----	-----	-----	-----	-----	-----	-----	-----	-----	----- gc 1: alloc size=3.74MB, heap size=4.09MB, live size=2.66MB gc 2: alloc size=2.41MB, heap size=5.52MB, live size=4.53MB gc 3: alloc size=4.85MB, heap size=9.95MB, live size=3.45MB gc 4: alloc size=6.04MB, heap size=10.20MB, live size=3.87MB gc 5: alloc size=5.88MB, heap size=10.20MB, live size=3.26MB gc 6: alloc size=6.48MB, heap size=10.20MB, live size=3.25MB gc 7: alloc size=6.51MB, heap size=10.20MB, live size=3.30MB gc 8: alloc size=6.46MB, heap size=10.20MB, live size=3.27MB gc 9: alloc size=6.49MB, heap size=10.20MB, live size=3.83MB gc 10: alloc size=5.91MB, heap size=10.20MB, live size=6.86MB gc 11: alloc size=6.46MB, heap size=13.80MB, live size=6.00MB gc 12: alloc size=7.28MB, heap size=13.80MB, live size=4.06MB gc 13: alloc size=9.16MB, heap size=13.80MB, live size=8.98MB gc 14: alloc size=8.83MB, heap size=18.40MB, live size=5.87MB gc 15: alloc size=11.90MB, heap size=18.40MB, live size=5.64MB gc 16: alloc size=12.13MB, heap size=18.40MB, live size=3.96MB gc 17: alloc size=13.76MB, heap size=18.40MB, live size=5.64MB gc 18: alloc size=12.14MB, heap size=18.40MB, live size=4.01MB gc 19: alloc size=13.71MB, heap size=18.40MB, live size=4.72MB gc 20: alloc size=13.02MB, heap size=18.40MB, live size=6.45MB gc 21: alloc size=11.06MB, heap size=18.40MB, live size=6.92MB gc 22: alloc size=10.85MB, heap size=18.40MB, live size=4.79MB gc 23: alloc size=13.00MB, heap size=18.40MB, live size=4.04MB gc 24: alloc size=13.69MB, heap size=18.40MB, live size=4.71MB gc 25: alloc size=13.03MB, heap size=18.40MB, live size=4.79MB gc 26: alloc size=12.94MB, heap size=18.40MB, live size=5.90MB gc 27: alloc size=11.79MB, heap size=18.40MB, live size=7.19MB gc 28: alloc size=10.61MB, heap size=18.40MB, live size=5.38MB gc 29: alloc size=12.30MB, heap size=18.40MB, live size=10.21MB gc 30: alloc size=7.40MB, heap size=18.40MB, live size=6.45MB gc 31: alloc size=11.15MB, heap size=18.40MB, live size=7.85MB gc 32: alloc size=9.74MB, heap size=18.40MB, live size=8.39MB gc 33: alloc size=9.14MB, heap size=18.40MB, live size=7.32MB gc 34: alloc size=10.26MB, heap size=18.40MB, live size=8.67MB gc 35: alloc size=4.33MB, heap size=18.40MB, live size=4.77MB Total size: 81MB

-----	-----	-----	-----	-----	-----	-----	-----	-----	-----	-----	-----	----- gc 1: alloc size=3.73MB, heap size=4.09MB, live size=2.57MB gc 2: alloc size=2.48MB, heap size=5.52MB, live size=4.45MB gc 3: alloc size=4.92MB, heap size=9.95MB, live size=3.56MB gc 4: alloc size=5.92MB, heap size=10.20MB, live size=3.05MB gc 5: alloc size=6.67MB, heap size=10.20MB, live size=3.26MB gc 6: alloc size=6.47MB, heap size=10.20MB, live size=3.25MB gc 7: alloc size=6.49MB, heap size=10.20MB, live size=3.19MB gc 8: alloc size=6.54MB, heap size=10.20MB, live size=5.09MB gc 9: alloc size=4.35MB, heap size=10.20MB, live size=4.35MB gc 10: alloc size=5.38MB, heap size=10.20MB, live size=3.25MB gc 11: alloc size=6.49MB, heap size=10.20MB, live size=5.09MB gc 12: alloc size=4.35MB, heap size=10.20MB, live size=4.36MB gc 13: alloc size=5.38MB, heap size=10.20MB, live size=3.25MB gc 14: alloc size=6.49MB, heap size=10.20MB, live size=3.30MB gc 15: alloc size=6.43MB, heap size=10.20MB, live size=3.19MB gc 16: alloc size=6.55MB, heap size=10.20MB, live size=3.31MB gc 17: alloc size=6.42MB, heap size=10.20MB, live size=3.19MB gc 18: alloc size=6.55MB, heap size=10.20MB, live size=6.30MB gc 19: alloc size=6.81MB, heap size=13.60MB, live size=5.01MB gc 20: alloc size=8.08MB, heap size=13.60MB, live size=8.43MB gc 21: alloc size=9.11MB, heap size=18.14MB, live size=8.10MB gc 22: alloc size=9.45MB, heap size=18.14MB, live size=6.41MB gc 23: alloc size=11.08MB, heap size=18.14MB, live size=6.82MB gc 24: alloc size=10.73MB, heap size=18.14MB, live size=5.65MB gc 25: alloc size=11.81MB, heap size=18.14MB, live size=6.85MB gc 26: alloc size=10.69MB, heap size=18.14MB, live size=4.64MB gc 27: alloc size=12.79MB, heap size=18.14MB, live size=6.39MB gc 28: alloc size=10.75MB, heap size=18.14MB, live size=7.14MB gc 29: alloc size=10.22MB, heap size=18.14MB, live size=5.90MB gc 30: alloc size=11.54MB, heap size=18.14MB, live size=5.52MB gc 31: alloc size=11.86MB, heap size=18.14MB, live size=7.48MB gc 32: alloc size=9.97MB, heap size=18.14MB, live size=8.25MB gc 33: alloc size=9.29MB, heap size=18.14MB, live size=8.00MB gc 34: alloc size=9.23MB, heap size=18.14MB, live size=9.98MB gc 35: alloc size=7.17MB, heap size=18.14MB, live size=10.90MB gc 36: alloc size=12.56MB, heap size=24.18MB, live size=10.24MB gc 37: alloc size=13.23MB, heap size=24.18MB, live size=10.06MB gc 38: alloc size=13.38MB, heap size=24.18MB, live size=13.41MB gc 39: alloc size=10.03MB, heap size=24.18MB, live size=9.63MB gc 40: alloc size=3.08MB, heap size=24.18MB, live size=8.64MB

For some runs, the traces may even be much more different. For instance the number of executed collections might different by a factor of 2 or 3.

These traces correspond to the execution of a test that mostly allocates lisp pairs, i.e., a C struct containing exactly two pointers. List pairs are tagged with p & 0x3, that is the collector uses

GC_REGISTER_DISPLACEMENT( 0x3 )

These traces have been collected on a Linux x86 (32bit) machine. I have compiled with -fpie and I have disable memory randomization with

sudo echo 0 > /proc/sys/kernel/randomize_va_space

My questions are then:

• is this GC nondeterminism expected?
• what it the reason for it?
• doest it impact the overall performance?
• is it possible to prevent it?

Thanks in advance for your lights on that matter.

Sincerely,

[manuel-serrano]

Oops. And I have forgotten to mention: the benchmark is single-threaded...

[ivmai]

Please retry with the single-threaded collector and GC source from master branch. It should be deterministic provided the OS is deterministic (regarding mmap'ed memory block addresses).

[manuel-serrano]

Hi Ivan,

Thanks for your response.

Please retry with the single-threaded collector and GC source from master branch. It should be deterministic provided the OS is deterministic (regarding mmap'ed memory block addresses). Sorry for the confusion. As I have said, this is already a single-threaded collector. The version I'm currently using is 7.5.0 released 27may2016. I will try with a newest version as soon as I have some spare time.

For your information, I have noticed this undeterministic behavior on many benchmarks...

-- Manuel

[Jesin]

@manuel-serrano Check whether your OS is configured to use ASLR. ASLR necessarily causes the kind of nondeterminism you are seeing.

[manuel-serrano]

Thanks for your answer.

I have tried to disable PIE using standard gcc option but maybe this is not enough. I will investigate more as soon as I have some spare time.

-- Manuel

----- Original Message -----

From: "Jesin" notifications@github.com To: "ivmai/bdwgc" bdwgc@noreply.github.com Cc: "manuel-serrano" Manuel.Serrano@inria.fr, "Mention" mention@noreply.github.com Sent: Tuesday, November 7, 2017 10:58:39 PM Subject: Re: [ivmai/bdwgc] Undeterministic GC behavior (#189)

@manuel-serrano Check whether your OS is uses ASLR . ASLR necessarily causes the kind of nondeterminism you are seeing.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub , or mute the thread .