Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance problem - nested loops #8503

Closed
ondrejmirtes opened this issue Dec 11, 2022 · 2 comments · Fixed by phpstan/phpstan-src#2088
Closed

Performance problem - nested loops #8503

ondrejmirtes opened this issue Dec 11, 2022 · 2 comments · Fixed by phpstan/phpstan-src#2088

Comments

@ondrejmirtes
Copy link
Member

Feature request

PHPStan can be really slow when analysing code like this:

<?php

class HelloWorld
{
	public function test(): void
	{
		$matrix = [];
		$db = new \PDO('conn');
		$qry = $db->prepare('SELECT x FROM z');
		$rows = $qry->fetchAll() ?: [];

		foreach($rows as $row) {
			$matrix[$row['x']] = [];

			foreach($rows as $row2) {
				$matrix[$row['x']][$row2['x']] = [];

				foreach($rows as $row3) {
					$matrix[$row['x']][$row2['x']][$row3['x']] = [];

					foreach($rows as $row4) {
						$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']] = [];

						foreach($rows as $row5) {
							$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']] = [];

							foreach($rows as $row6) {
								$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']][$row6['x']] = [];

								foreach($rows as $row7) {
									$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']][$row6['x']][$row7['x']] = [];

									foreach($rows as $row8) {
										$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']][$row6['x']][$row7['x']][$row8['x']] = [];
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

PHPStan analyses different PHP loops a similar way: Go through the loop, observe if the scope changes, “generalize” the scope. If the scope is different than the last time, re-run the same process up until 3 times. Use the final scope and run the analysis with the rules etc.

The generalization is a bit hazy, basically I’m trying to write some code that compares types and tries to figure out if the loop does $i++ vs. $i = 5, to see what the type should be in the final scope.

The problem is that my algorithm (here’s the foreach loop logic: https://github.com/phpstan/phpstan-src/blob/3c3b17f238d1ec085f74aee320e9dd321d1258d8/src/Analyser/NodeScopeResolver.php#L823-L846) is very ineffective with multiple nested loops

The more the loop is nested, the more times it’s going to be analysed. If I put var_dump($stmt->getLine()); at the beginning of the foreach handler in NodeScopeResolver, the output when analysing the linked file looks like this:

int(14)
int(17)
int(20)
int(23)
int(26)
int(29)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
int(35)
int(29)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
…

And goes on like that for more than 3,000 times.

I'd like to know how compilers of different languages handle this effectively...

@mvorisek
Copy link
Contributor

mvorisek commented Dec 11, 2022

copying here, from #8353 (comment), a repro link: https://phpstan.org/r/03cef78d-271b-46d6-9d3a-d585fdb58c8f (the response time is ~4 seconds, when 1 more level is added, it crashes (time needed is exponential))

@github-actions
Copy link

This thread has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.

@github-actions github-actions bot locked as resolved and limited conversation to collaborators Jan 12, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants