Type pool

[weirdan]

Problem statement

Psalm, naturally, operate on a lot of types. My intuition (and some preliminary testing) suggests that we have a lot of duplicate type instances, maybe about ten times more than strictly necessary. This leads to Psalm having to use more memory and prevents some performance optimizations.

Where do duplicates come from?

One example could be literally duplicate types used by the inspected codebase. E.g., how many instances of TTrue do we have during analysis? And how many do we actually need? I'd say we should ideally have just two - one with $from_docblock = true and one with $from_docblock = false.

Idea

Instead of having multiple instances of identical types, we could have a central pool of type instances and return instances from that pool instead of creating new instances.

Possible optimizations it enables

Comparing types could be short-circuited to identity comparison. If there's only a single instance of a non-docblock TArray<array-key, mixed> we could first check if ($input_type === $container_type) { return true; } and save some CPU cycles that are otherwise wasted comparing key and value types.

Why can't we do this already?

Several architectural issues are preventing the immediate implementation of this approach.

1. Types do have transient state. E.g. Atomic::$checked
2. Types carry source information. E.g. Atomic::$offset_start & Atomic::$offset_end

There's also a question of how this should work with the cache. We would probably need to serialize the type pool into the cache and replace all type references with some kind of pointer to the serialized pool.

What would the code look like if we implemented it?

Parts of the code that create new types would need to register the created type with the pool, and let it replace the type instance. E.g. parser would do this:

public function parse(string $type_string): Union 
{
  // ... do the parsing resulting in $type being created
  // register the type with the pool, potentially receiving another instance with identical content
  $type = TypePool::register($type);
  // return the type
  return $type;
}

@orklah @danog @muglug do you think this is feasible and actually makes sense?

[danog]

I like the idea a lot.
Ever since implementing immutability, I saw this as a chance to reuse at least some types; I actually played around with the idea a bit, implementing memoization for all type getter methods in https://github.com/vimeo/psalm/blob/master/src/Psalm/Type.php (with from_docblock distinction); this didn't yield a noticeable performance improvement, but it did reduce memory usage.

Extending the idea with a full union and atomic type cache, including composite types like arrays and simplifying comparisons should improve performance a lot more IMO.

[orklah]

If we manage to extract dynamic parts from Atomic, it may make sense to make something like singletons for simple type. Atomic/Union creation are pretty centralised already so it would not be a big change to make the constructor private and just rely on the single instance available. That would make the need for a whole pool system unnecessary

[edsrzf]

This makes a lot of sense to me. Is it something I can help with? (Keeping in mind I'm still pretty new to the code base.)

I've started looking at Atomic::$offset_start and Atomic::$offset_end, and it looks like they really only need to be present on TNamedObject, here:

psalm/src/Psalm/Internal/TypeVisitor/TypeChecker.php

Lines 140 to 141 in c0e757c

	$this->code_location->raw_file_start + $atomic->offset_start,
	$this->code_location->raw_file_start + $atomic->offset_end,

Intuitively this kinda makes sense to me, since you typically wouldn't ask questions like "Where are all the places in the code base I'm using bool?" You'd only care about named types that you've defined.

To make the most of a type pool, I suppose you'd want to eliminate offset info even on these named type objects, but it seems to me there'd be a lot of benefit in covering the built-in types by themselves.

I guess this work would need to target Psalm 6, since it would almost certainly contain breaking changes for plugins?

[edsrzf]

Same analysis, with clones included this time. TArray has really started catching up in both. TTemplateParam didn't even show up in the first analysis because it was below 1%, but here it makes a solid appearance in both code bases.

Psalm Code Base

Psalm is up to 1,034,740 Atomic allocations and TArray takes the lead.

Type	Percent
TArray	16.3%
TLiteralString	11.1%
TKeyedArray	9.6%
TNever	7.6%
TNamedObject	7.1%
TString	7.0%
TBool	6.4%
TLiteralInt	3.6%
TTemplateParam	3.5%
TNonEmptyArray	3.3%
TIntRange	2.8%
TNonEmptyString	2.6%
TNull	2.6%
TInt	2.6%
TConditional	2.4%
TMixed	2.1%
TFalse	1.7%
TTrue	1.5%
TLowercaseString	1.0%

Closed-Source Code Base

We're up to 5,125,195 allocations, with TMixed still solidly in front. TArray is catching up to TLiteralString. I'm very surprised that TTemplateParam is so high because this code base hardly uses any templated types.

Type	Percent
TMixed	17.8%
TLiteralString	13.7%
TArray	12.1%
TTemplateParam	7.3%
TBool	6.3%
TNever	5.3%
TKeyedArray	5.3%
TNamedObject	5%
TConditional	4.5%
TNonEmptyArray	3.9%
TString	3.1%
TNull	2.6%
TLiteralInt	2.2%
TIntRange	1.6%
TFalse	1.3%
TArrayKey	1.2%

[weirdan]

Psalm is up to 1,034,740 Atomic allocations

This sounds a bit too low. Did you run it with --threads=1?

My backfire profile shows ~4M calls to Union::__construct() alone, and I'd expect to see at least that number of Atomic instances.

[weirdan]

Did you run it with --threads=1?

With multiprocessing (--threads set to anything higher, and it's >1 by default) analysis happens in child processes, so you may miss all the allocations that happen there.

[edsrzf]

Yes, I ran with --threads=1.

[edsrzf]

Is it possible that I'm missing some allocations through unserialize? I also ran with --no-cache, but maybe there's still some (de)serializing happening somewhere?