[Heap] Switch to a custom _Index type that incrementally tracks depth

[lorentey]

The Heap implementation currently uses naked integers as indices, and uses _binaryLogarithm to determine whether a particular index addresses a min or max node. This is a relatively expensive(*) operation that may have some measurable performance impact.

(*) Well, at least compared to a mov?

Instead, try switching to a custom _Index struct containing both a storage position and its associated depth.

Beyond a potential performance win, this would also allow for better code organization -- by allowing us to move the utility methods for retrieving the parents/children of an index to the Index type itself:

struct _Index: Comparable {
  let offset: Int
  let level: Int

  func parent() -> _Index?
  func grandParent() -> Index?
  func leftChild() -> _Index
  func rightChild() -> _Index
}

[hassila]

Might also consider trying to access the BSR (bit scan reverse) function which at least for x64 should be fairly quick, see more information here: https://probablydance.com/2020/08/31/on-modern-hardware-the-min-max-heap-beats-a-binary-heap/ quote:

When you push an item you first have to check if you’re on a min-layer or on a max-layer. If the heap (including the new item) is length 1, you’re on a min-layer. If the heap is length 2 or 3, you’re on a max layer. If the heap is length 4, 5, 6 or 7, you’re on a min-layer etc. The cheapest way of checking this is to use the position of the most significant bit. (at least I couldn’t find a cheaper way) Meaning use the “bit scan reverse” instruction and then check if the most significant bit as in an even- or odd-numbered position. It looks like C++20 finally added a way of accessing this instruction, using std::countl_zero. I don’t have C++20 though so I had to do it the old platform specific ways: Microsoft offers _BitScanReverse64(size), but on Linux you have to do (63 – __builtin_clzl(size)). The benefit of doing it like this is that I verified that my code actually just calls “bsr”, where the standard C++ version has an interface that might force it to do a branch. (Not sure about that though, so just check the assembly for extra branches if you’re able to use C++20)

[xwu]

@hassila That's exactly what _binaryLogarithm does (and it too optimizes down to the bsr instruction).

[hassila]

@hassila That's exactly what _binaryLogarithm does (and it too optimizes down to the bsr instruction).

Aha, thanks @xwu for clarification.

[lorentey]

Having a dedicated type for nodes in the tree was a good idea -- I find node.parent() far more pleasant to read than self. _parentIndex(of: node).

Unfortunately, the original goal of putting the levels in the index (a.k.a. _Node) structure wasn't a straightforward win. For trickleDown, the level never needs to be accessed, but it still needs to be maintained, which is annoying. (Luckily the compiler gets rid of the unused calculations, so there is no performance impact; but readability suffers a bit.)

An alternative option would've been to remove level from _Node and simply maintain it in a separate variable as needed. I don't think it's worth implementing this, though.