0xDEADBEEF

PHP heap benchmark

echo ini_get("opcache.jit"), "\n";

class Item {
  public $weight;
}

$items = [];
$count = intval($argv[1]);

mt_srand(47);

for ($i = 0; $i < $count; $i++) {
  $items[] = $item = new Item;
  $item->weight = mt_rand() / mt_getrandmax() / 2;
}

$limit = 25;
$iters = 1000 * (20000 / $count);

function measure($label, $iters, $items, $f) {
  $total = 0;
  for ($iter = 0; $iter < $iters; $iter++) {
    $start = microtime(true);
    $res = $f($items);
    $delta = microtime(true) - $start;
    $total += $delta;
    //printf("%s %.3f ms\n", $label, $delta * 1000);
    //echo "\n";
  }
  printf("%-24s %6.3f ms\n", $label, ($total * 1000)/$iters);
  //echo "\n";
}


measure('sort', $iters, $items, function ($items) use ($limit) {
  usort($items, function ($a, $b) {
    return $b->weight <=> $a->weight;
  });

  return array_slice($items, 0, $limit);
});


measure('index + asort', $iters, $items, function ($items) use ($limit) {
  $indexedWeights = array_fill(0, count($items), 0.0);
  foreach ($items as $i => $item) {
    $indexedWeights[$i] = $item->weight;
  }

  arsort($indexedWeights, SORT_NUMERIC);
  $indexes = array_reverse(array_slice($indexedWeights, 0, $limit, true), true);
  return array_intersect_key($items, $indexes);
});


measure('heap', $iters, $items, function ($items) use ($limit) {
  $heap = new class extends \SplHeap {
    function compare($a, $b) {
      return $b->weight <=> $a->weight;
    }
  };

  foreach ($items as $item) {
    $heap->insert($item);
    if ($heap->count() > $limit) {
      $heap->extract();
    }
  }

  return iterator_to_array($heap);
});


measure('heap + guard', $iters, $items, function ($items) use ($limit) {
  $heap = new class extends \SplHeap {
    function compare($a, $b) {
      return $b->weight <=> $a->weight;
    }
  };

  foreach ($items as $item) {
    if ($heap->count() >= $limit) {
      if ($item->weight > $heap->top()->weight) {
        $heap->insert($item);
        $heap->extract();
      }
    } else {
      $heap->insert($item);
    }
  }

  return iterator_to_array($heap);
});


measure('priority queue', $iters, $items, function ($items) use ($limit) {
  $heap = new \SplPriorityQueue;

  foreach ($items as $item) {
    $heap->insert($item, -$item->weight);
    if ($heap->count() > $limit) {
      $heap->extract();
    }
  }

  return iterator_to_array($heap);
});


measure('priority queue + guard', $iters, $items, function ($items) use ($limit) {
  $heap = new \SplPriorityQueue;

  foreach ($items as $item) {
    if ($heap->count() >= $limit) {
      if ($item->weight > $heap->top()->weight) {
        $heap->insert($item, -$item->weight);
        $heap->extract();
      }
    } else {
      $heap->insert($item, -$item->weight);
    }
  }

  return iterator_to_array($heap);
});