1

Since Hack is faster in strict mode, I tried to translate the first benchmarkgame to dito, but get stuck on a stack overflow that never occur in the un-strict version (different with recursive calls using objects?). Any reasons why? How could I increase the stack size? And googling for "php stack overflow" is useless, as you can imagine. ^^

The problem happens on the first recursive call.

My code:

<?hh // strict

class Tree {
  public function bottomUpTree(?num $item, ?num $depth) : array<?num>
  {
    if ($depth === null) return array(null,null,$item);
    if ($item !== null) {
      $item2 = $item + $item;
      $depth--;
      return array( // <--- Stack overflow here
        $this->bottomUpTree($item2-1,$depth),
        $this->bottomUpTree($item2,$depth),
        $item);
    }
    else {
      throw new Exception("Fatal");
    }
  }

  public function itemCheck(array<?int, ?int> $treeNode) : int {
    if ($treeNode !== null && $treeNode[2] !== null) {
      $someNumber = $treeNode[2];
      $a = $someNumber + 10;
      return $someNumber
        + ($treeNode[0][0] === null ? $this->itemCheck($treeNode[0]) : $treeNode[0][2])
        - ($treeNode[1][0] === null ? $this->itemCheck($treeNode[1]) : $treeNode[1][2]);
    }
    else {
      throw new Exception("Fatal");
    }
  }

  public function run($argc, $argv) {

    $minDepth = 4;

    $n = ($argc == 2) ? $argv[1] : 1;
    $maxDepth = max($minDepth + 2, $n);
    $stretchDepth = $maxDepth + 1;

    $stretchTree = $this->bottomUpTree(0, $stretchDepth);
    printf("stretch tree of depth %d\t check: %d\n",
      $stretchDepth, $this->itemCheck($stretchTree));
    unset($stretchTree);

    $longLivedTree = $this->bottomUpTree(0, $maxDepth);

    $iterations = 1 << ($maxDepth);
    do {
      $check = 0;
      for($i = 1; $i <= $iterations; ++$i)
      {
        $t = $this->bottomUpTree($i, $minDepth);
        $check += $this->itemCheck($t);
        unset($t);
        $t = $this->bottomUpTree(-$i, $minDepth);
        $check += $this->itemCheck($t);
        unset($t);
      }

      printf("%d\t trees of depth %d\t check: %d\n", $iterations<<1, $minDepth, $check);

      $minDepth += 2;
      $iterations >>= 2;
    }
    while($minDepth <= $maxDepth);

    printf("long lived tree of depth %d\t check: %d\n",
      $maxDepth, $this->itemCheck($longLivedTree));
  }
}

$tree = new Tree();
$tree->run($argc, $argv);
Olle Härstedt
  • 3,799
  • 1
  • 24
  • 57
  • A couple of comments on the code other than the question you asked. First, you should look into using a tuple instead of an array for the return value of bottomUpTree. Second, the notion that "code in strict Hack is faster" isn't quite as straightforward as that (and is missing the point that Hack is about developer efficiency, not code efficiency), see my answer elsewhere: http://stackoverflow.com/a/26100185/3395144 – Josh Watzman Jun 29 '15 at 17:54

1 Answers1

0

Your recursion will never hit a base case and stop as the values you're passing down while recursing will never be null.

You probably want to exit if $depth is 0 as well as if it is null.