Determinism is a sexxy property for software verification. Given a known input
a deterministic program should produce the same output, consistently. This
makes testing trivial, simply match the program's output with what has been
previously been determined as the correct output. If the two outputs match, *bang bang*
we passed output verification and the
PHB is pleased. This is,
of course, assuming that the program is void of any side effects that would
cause some bit of non-pure/non-deterministic output.
For a deterministic program, any unexpected output is a
clear sign of a bug. For other types of programs, non-deterministic output can
result from the program relying on clock values, random values, or other input which can be hard
to replicate in testing (such as mouse or other device interrupts). However, a
proper verification setup should have a way to statically set such variables so
that the program can have a proper output testing. For instance, seeding
the random number generator used in the program to a known value during testing.
I was recently surprised to find one of my memory management test cases
producing non-deterministic output, even though the program is trivial and
relies on little or few external libraries, and no obvious random or
non-deterministic input. Actually, I discovered this a
while back, but recently revisited it. Simply, I was gathering data for my
thesis work, region-based memory management (RBMM), and found that the garbage
collector I was comparing my RBMM system against kept producing different
collection counts (the number of times the collector executed during my test
case's run). See, both garbage collection and RBMM are forms of automatic
memory management and I wanted to see how well my RBMM system compares to the more
common garbage collection. My research is based on implementing an RBMM system
in Go and then comparing my work against the stable garbage collector that Go
ships with.
Anyways, I was able to replicate the effect I had previously
witnessed in a simpler test (below) using the Go runtime provided by
gcc-4.8.1.
Remember that Go is garbage collected, thus its garbage collector was
producing different collection counts (NumGC below) for each execution of the
test.
package main
import "runtime"
func main() {
for i:=0; i<10000000; i++ {
f := new(float64)
*f++
}
var m runtime.MemStats
runtime.ReadMemStats(&m)
println("NumGC: ", m.NumGC)
}
Why would Go's collector be producing non-deterministic collection counts?
This program obviously does the same thing every execution, and generates the
same amount of garbage each execution. Well, a couple things could be
happening. Perhaps Go's collector was looking at overall system resources, and
not just for the test case, and deciding when to collect. Or, perhaps it uses a
random value which might affect collection. As it turns out, the latter was
the case. Go, by default, enables some statistics/profiling information during
runtime. What tipped me off was that I ran a grep for "rand" within the runtime
source and I found the following in its memory allocation function
"runtime_mallocgc" located in gcc-4.8.1/libgo/runtime/malloc.goc.
Note that I modified the whitespace some:
if(!(flag & FlagNoProfiling) && (rate = runtime_MemProfileRate) > 0) {
if(size >= (uint32) rate)
goto profile;
if((uint32) m->mcache->next_sample > size)
m->mcache->next_sample -= size;
else {
// pick next profile time
// If you change this, also change allocmcache.
if(rate > 0x3fffffff) // make 2*rate not overflow
rate = 0x3fffffff;
m->mcache->next_sample = runtime_fastrand1() % (2*rate);
profile:
runtime_setblockspecial(v, true);
runtime_MProf_Malloc(v, size);
}
}
So their profiler is having an affect on the amount of memory pressure on the
garbage collector, thus causing the collector to kick-in more often than
a non-profiled runtime. So, what does this mean? Well, if you do not need any profiling
support (probably not if you are running production) then disable the profiler!
What I did, was just that, and then executed my simple test multiple times.
Bingo! With the profiler disabled I was able to achieve consistent predictable
garbage collection counts from Go's collector. To disable the
profiler, simply add this line to your main()
runtime.MemProfileRate = 0
The latter flag will set the profiling rate to zero, thus the runtime will not
collect allocation metadata. Otherwise, this collection of metadata will
influence the garbage collector, and that probably is not wanted if you run a
production executable (or are performing some verification/testing).
-Matt
