BaseInventory functions slow due to unnecessary item cloning

[KN19294]

[ tell us what you want ] To implement protected internalGetContents() function that builtin inventory functions will use.

Justification

Basic inventory functions like contains() all() first() are slow because of item cloning. Many times these cloning are not needed to be evaluated and slow down many functions. Example, firstEmpty() clones 27 items for a filled single chest inventory to only retrieve slot number. https://github.com/pmmp/PocketMine-MP/blob/8633804f156817eb4db9f44ed2125e44ded01667/src/inventory/BaseInventory.php#L154-L162

In future, there can also be additional helpful functions example $inv->filter(callback) which can call internalGetContents() to improve performance in comparison with array_filter($inv->getContents(), callback).

Alternative methods

Tested on Server version: 4.19.3. I have evaluated this code. It reimplements a faster firstEmpty() function where I just replaced $this->getContents() with $this->slots:

$items = [];
for ($i = 0; $i < 27; $i++) {
    $items[] = VanillaItems::IRON_SWORD();
}

$inv = new class(27) extends SimpleInventory{
    public function firstEmptyFast() : int{
        foreach($this->slots as $i => $slot){
            if($slot === null || $slot->isNull()){
                return $i;
            }
        }

        return -1;
    }
};
$inv->setContents($items);

$start = microtime(true);
for($i = 0; $i < 100000; $i++){
    $inv->firstEmpty();
}
$end = microtime(true);
echo "Slow Inventory: " . round(($end - $start) * 1000) . "ms\n";

$start = microtime(true);
for($i = 0; $i < 100000; $i++){
    $inv->firstEmptyFast();
}
$end = microtime(true);
echo "Fast Inventory: " . round(($end - $start) * 1000) . "ms\n";

The result: 400% faster in worst case runtime of firstEmpty() because of inventory is full: Slow Inventory: 689ms Fast Inventory: 157ms

[dktapps]

Nice work for writing a proper performance test case. Not often I see one written this well, though you might find it more interesting to use hrtime(), which gives you resolution down to the nanosecond.

I'm aware that inventories are pretty sub-optimal for performance in many cases, but the truth is I hadn't considered these functions at all, since they aren't hot functions. I haven't analyzed plugin usages at all.

[KN19294]

Thank you very much. I did not know hrtime() function but i will use it in future. Some plugins that come to mind are redstone plugins like RedstoneCircuit and VanillaX which have hoppers that have to check the above inventory every 8 ticks for finding first empty but this can differs between implementations.

Sometimes this can happen with pocketmine entities. Example: when player has full inventory and trying to pick dropped items. Then this will call getAddableItemQuantity() which will clone 36 items (invetory size of a player).

[dktapps]

Interesting. Thanks for the insights, I will definitely be looking into this.

[dktapps]

So I had a think about this, and I think a good addition to the system would be to keep a map of itemId -> list<slots> in the inventory.

While this wouldn't always avoid unnecessary item cloning, it would (in many cases) allow O(1) discovery of the first slot containing a particular type of item. Resolving NBT is a different story (of course), but such a change would provide performance advantages in many situations, and wouldn't require any BC breaks.

An internalGetContents() method is a bit problematic because it would require a BC break, since all descendents of BaseInventory would have to implement a new method. That kind of change can only be done in a major version.

[KN19294]

The idea of mapping item ID to slots is nice. And list<slots> can be sorted by item count to speed-up functions such as addItem() to find addable slot without completely traversal of the list of the slots.

To avoide BC break is it good idea if in stable version internalGetContents() was a non abstract function in BaseInventory and returned $this->getContents():

class BaseInventory{
    protected function internalGetContents() : array{ // To-do: Convert it to abstract
        return $this->getContents();
    }
}
class SimpleInventory extends BaseInventory{
    protected function internalGetContents() : array{
        return $this->slots;
    }
}

[dktapps]

is it good idea if in stable version internalGetContents() was a non abstract function in BaseInventory and returned $this->getContents():

I considered this, but it creates some inconsistencies (some implementations may clone it, others may not).

list can be sorted by item count to speed-up functions such as addItem() to find addable slot without completely traversal of the list of the slots.

Not sure this is practical. addItem() has specific behaviour - it's supposed to add items to the earliest matching slots, and then use the first available empty slots for the remainder.

[dktapps]

Between 7f6269c432e5341c7ad128c065a3bcda5060cf17 and eb136e60c8011548e0d84f5def1cc1063e83559e, I think the original reason for this issue is now addressed, so I'm going to close it.

There is a case to be made for tracking item type -> list to improve the performance of canAddItem() and addItem(), but that's a topic for another issue.