Re: [PATCH] git tag --contains : avoid stack overflow

On Thu, Apr 17, 2014 at 07:31:54PM +0200, Johannes Schindelin wrote:

I tried running the test on my Linux box, but it doesn't fail with the existing recursive code. So I tried a few different stack sizes, like:

  for i in `seq 1 64`; do
    bash -c "
      ulimit -s $i &&
      ../../git tag --contains HEAD ||
      echo fail $i"
  done

The results are strangely non-deterministic, but with -O0, we generally die reliably below about 60. With -O2, though, it's more like 43. We can't go _too_ low here, though, as lots of things start breaking around 32.

If we instead bump the size of the history to 2000 commits, then I reliably fail with a 64k stack (even with -O2, it needs around 80k).

Of course those numbers are all black magic, and are going to vary based on the system, the compiler, settings, etc. My system is 64-bit, and the current code needs at least 3 pointers per recursive invocation. So we're spending ~46K on those variables, not counting any calling convention overhead (and presumably we at least need a function return pointer there). So a 32-bit system might actually get by, as it would need half as much.

So we can bump the depth further; probably 4000 is enough for any system to fail with a 64k stack. The deeper we make it, the longer it takes to run the test, though. At 4000, my machine seems to take about 300ms to run it. That's may be OK.

-Peff