Feature request

Last night I came up with an idea how to optimize TypeCombinator::union(). It's one of the most heavily used methods in PHPStan. In PHPStan itself, it's responsible for about 7.5% of total run time. So the ROI here might be really big.

One of the worst cases is when the method gets a huge UnionType as the first argument (for example with 64 types), and another single type as another argument. These types are then collapsed into a single flat array of 65 types. And these types are all compared against each other.

But what if we knew that the first 64 types are already normalized? That's why I added this information: phpstan/phpstan-src@96e4443

So instead of 2080 comparisons (65 * 64 / 2), we'd just have to do 64 comparisons.

The idea is that we'd introduce $buckets (one bucket = array<Type>) and inside these buckets, we'd know that the types are not subtypes of each other, that they are normalized inside one bucket.

And after that we'd compare buckets against each other. The logic would be as follows:

• If type A from bucket J is a supertype of type B from bucket K: remove type B from bucket K. If bucket K becomes empty, remove bucket K.
• If type B from bucket K is a supertype of type A from bucket J: remove type A from bucket J, remove type B from bucket K, add a new bucket that only contains type B. If bucket J becomes empty, remove it. If bucket K becomes empty, remove it too.

And at the end, we'd be able to collapse all of the buckets into a single array of $types :)

Currently the main logic of union is these few lines: https://github.com/phpstan/phpstan-src/blob/da8413c493cbb9d800228f996836207e9598920c/src/Type/TypeCombinator.php#L316-L339

A lot of stuff around this in the union method is just about optimization, especially the scalar type handling. It's possible we'd be able to get rid of a lot of this code if the main logic became faster.

I think that @rajyan or @rvanvelzen are well-equipped to try this out, so feel free (but don't feel obligated) to do so. This idea might make you interested same as it made me interested :)

Thank you.