Typecombinator union optimization by rajyan · Pull Request #2078 · phpstan/phpstan-src

rajyan · 2022-12-11T08:28:47Z

No description provided.

rajyan · 2022-12-11T08:53:58Z

I've reset the latest commit because it looked like causing a infinite loop or something in the CI.

rajyan · 2022-12-20T01:05:05Z

The bucket logic is almost working, but I suspect that the performance improvement is going to be small. We can only optimize large union of non-constant and non-array types.

staabm · 2022-12-20T08:05:05Z

just ran a few blackfire profiles.

it seems to improve this example by 40% (45secs -> 26 secs). all other things I tested (my oversized array cases) were nearly the same as before:

<?php
/*
 * priv.defs.inc - Default Privilege Definitions
 * Generated by pfSense/tools/scripts/generate-privdefs.php
 *
 * ***************************************************
 * DO NOT EDIT THIS FILE. IT IS GENERATED BY A SCRIPT.
 * ***************************************************
 *
 * Text is pulled from metadata headers in the referenced files.
 *
 */

$priv_list = array();

$priv_list['page-all'] = array();
$priv_list['page-all']['name'] = gettext("WebCfg - All pages");
$priv_list['page-all']['descr'] = gettext("Allow access to all pages");
$priv_list['page-all']['warn'] = "standard-warning-root";
$priv_list['page-all']['match'] = array();
$priv_list['page-all']['match'][] = "*";

$priv_list['page-diagnostics-crash-reporter'] = array();
$priv_list['page-diagnostics-crash-reporter']['name'] = gettext("WebCfg - Crash reporter");
$priv_list['page-diagnostics-crash-reporter']['descr'] = sprintf(gettext("Uploads crash reports to %s and or deletes crash reports."), $g['product_label']);
$priv_list['page-diagnostics-crash-reporter']['match'] = array();
$priv_list['page-diagnostics-crash-reporter']['match'][] = "crash_reporter.php*";

$priv_list['page-diagnostics-arptable'] = array();
$priv_list['page-diagnostics-arptable']['name'] = gettext("WebCfg - Diagnostics: ARP Table");
$priv_list['page-diagnostics-arptable']['descr'] = gettext("Allow access to the 'Diagnostics: ARP Table' page.");
$priv_list['page-diagnostics-arptable']['match'] = array();
$priv_list['page-diagnostics-arptable']['match'][] = "diag_arp.php*";

$priv_list['page-diagnostics-authentication'] = array();
$priv_list['page-diagnostics-authentication']['name'] = gettext("WebCfg - Diagnostics: Authentication");
$priv_list['page-diagnostics-authentication']['descr'] = gettext("Allow access to the 'Diagnostics: Authentication' page.");
$priv_list['page-diagnostics-authentication']['match'] = array();
$priv_list['page-diagnostics-authentication']['match'][] = "diag_authentication.php*";

$priv_list['page-diagnostics-backup-restore'] = array();
$priv_list['page-diagnostics-backup-restore']['name'] = gettext("WebCfg - Diagnostics: Backup & Restore");
$priv_list['page-diagnostics-backup-restore']['descr'] = gettext("Allow access to the 'Diagnostics: Backup & Restore' page.");
$priv_list['page-diagnostics-backup-restore']['warn'] = "standard-warning-root";
$priv_list['page-diagnostics-backup-restore']['match'] = array();
$priv_list['page-diagnostics-backup-restore']['match'][] = "diag_backup.php*";

$priv_list['page-diagnostics-command'] = array();
$priv_list['page-diagnostics-command']['name'] = gettext("WebCfg - Diagnostics: Command");
$priv_list['page-diagnostics-command']['descr'] = gettext("Allow access to the 'Diagnostics: Command' page.");
$priv_list['page-diagnostics-command']['warn'] = "standard-warning-root";
$priv_list['page-diagnostics-command']['match'] = array();
$priv_list['page-diagnostics-command']['match'][] = "diag_command.php*";

$priv_list['page-diagnostics-configurationhistory'] = array();
$priv_list['page-diagnostics-configurationhistory']['name'] = gettext("WebCfg - Diagnostics: Configuration History");
$priv_list['page-diagnostics-configurationhistory']['descr'] = gettext("Allow access to the 'Diagnostics: Configuration History' page.");
$priv_list['page-diagnostics-configurationhistory']['warn'] = "standard-warning-root";
$priv_list['page-diagnostics-configurationhistory']['match'] = array();
$priv_list['page-diagnostics-configurationhistory']['match'][] = "diag_confbak.php*";

$priv_list['page-diagnostics-factorydefaults'] = array();
$priv_list['page-diagnostics-factorydefaults']['name'] = gettext("WebCfg - Diagnostics: Factory defaults");
$priv_list['page-diagnostics-factorydefaults']['descr'] = gettext("Allow access to the 'Diagnostics: Factory defaults' page.");
$priv_list['page-diagnostics-factorydefaults']['warn'] = "standard-warning-root";
$priv_list['page-diagnostics-factorydefaults']['match'] = array();
$priv_list['page-diagnostics-factorydefaults']['match'][] = "diag_defaults.php*";

$priv_list['page-diagnostics-dns'] = array();
$priv_list['page-diagnostics-dns']['name'] = gettext("WebCfg - Diagnostics: DNS Lookup");
$priv_list['page-diagnostics-dns']['descr'] = gettext("Allow access to the 'Diagnostics: DNS Lookup' page.");
$priv_list['page-diagnostics-dns']['match'] = array();
$priv_list['page-diagnostics-dns']['match'][] = "diag_dns.php*";

$priv_list['page-diagnostics-showstates'] = array();
$priv_list['page-diagnostics-showstates']['name'] = gettext("WebCfg - Diagnostics: Show States");
$priv_list['page-diagnostics-showstates']['descr'] = gettext("Allow access to the 'Diagnostics: Show States' page.");
$priv_list['page-diagnostics-showstates']['match'] = array();
$priv_list['page-diagnostics-showstates']['match'][] = "diag_dump_states.php*";

$priv_list['page-diagnostics-sourcetracking'] = array();
$priv_list['page-diagnostics-sourcetracking']['name'] = gettext("WebCfg - Diagnostics: Show Source Tracking");
$priv_list['page-diagnostics-sourcetracking']['descr'] = gettext("Allow access to the 'Diagnostics: Show Source Tracking' page.");
$priv_list['page-diagnostics-sourcetracking']['match'] = array();
$priv_list['page-diagnostics-sourcetracking']['match'][] = "diag_dump_states_sources.php*";

$priv_list['page-diagnostics-edit'] = array();
$priv_list['page-diagnostics-edit']['name'] = gettext("WebCfg - Diagnostics: Edit File");
$priv_list['page-diagnostics-edit']['descr'] = gettext("Allow access to the 'Diagnostics: Edit File' page.");
$priv_list['page-diagnostics-edit']['warn'] = "standard-warning-root";
$priv_list['page-diagnostics-edit']['match'] = array();
$priv_list['page-diagnostics-edit']['match'][] = "diag_edit.php*";
$priv_list['page-diagnostics-edit']['match'][] = "browser.php*";
$priv_list['page-diagnostics-edit']['match'][] = "vendor/filebrowser/browser.php*";

$priv_list['page-diagnostics-gmirror'] = array();
$priv_list['page-diagnostics-gmirror']['name'] = gettext("WebCfg - Diagnostics: GEOM Mirrors");
$priv_list['page-diagnostics-gmirror']['descr'] = gettext("Allow access to the 'Diagnostics: GEOM Mirrors' page.");
$priv_list['page-diagnostics-gmirror']['match'] = array();
$priv_list['page-diagnostics-gmirror']['match'][] = "diag_gmirror.php*";

$priv_list['page-diagnostics-haltsystem'] = array();
$priv_list['page-diagnostics-haltsystem']['name'] = gettext("WebCfg - Diagnostics: Halt system");
$priv_list['page-diagnostics-haltsystem']['descr'] = gettext("Allow access to the 'Diagnostics: Halt system' page.");
$priv_list['page-diagnostics-haltsystem']['match'] = array();
$priv_list['page-diagnostics-haltsystem']['match'][] = "diag_halt.php*";

$priv_list['page-diagnostics-limiter-info'] = array();
$priv_list['page-diagnostics-limiter-info']['name'] = gettext("WebCfg - Diagnostics: Limiter Info");
$priv_list['page-diagnostics-limiter-info']['descr'] = gettext("Allows access to the 'Diagnostics: Limiter Info' page");
$priv_list['page-diagnostics-limiter-info']['match'] = array();
$priv_list['page-diagnostics-limiter-info']['match'][] = "diag_limiter_info.php*";

$priv_list['page-diagnostics-ndptable'] = array();
$priv_list['page-diagnostics-ndptable']['name'] = gettext("WebCfg - Diagnostics: NDP Table");
$priv_list['page-diagnostics-ndptable']['descr'] = gettext("Allow access to the 'Diagnostics: NDP Table' page.");
$priv_list['page-diagnostics-ndptable']['match'] = array();
$priv_list['page-diagnostics-ndptable']['match'][] = "diag_ndp.php*";

$priv_list['page-diagnostics-packetcapture'] = array();
$priv_list['page-diagnostics-packetcapture']['name'] = gettext("WebCfg - Diagnostics: Packet Capture");
$priv_list['page-diagnostics-packetcapture']['descr'] = gettext("Allow access to the 'Diagnostics: Packet Capture' page.");
$priv_list['page-diagnostics-packetcapture']['match'] = array();
$priv_list['page-diagnostics-packetcapture']['match'][] = "diag_packet_capture.php*";

$priv_list['page-diagnostics-pf-info'] = array();
$priv_list['page-diagnostics-pf-info']['name'] = gettext("WebCfg - Diagnostics: pfInfo");
$priv_list['page-diagnostics-pf-info']['descr'] = gettext("Allows access to the 'Diagnostics: pfInfo' page");
$priv_list['page-diagnostics-pf-info']['match'] = array();
$priv_list['page-diagnostics-pf-info']['match'][] = "diag_pf_info.php*";

$priv_list['page-diagnostics-system-pftop'] = array();
$priv_list['page-diagnostics-system-pftop']['name'] = gettext("WebCfg - Diagnostics: pfTop");
$priv_list['page-diagnostics-system-pftop']['descr'] = gettext("Allows access to the 'Diagnostics: pfTop' page");
$priv_list['page-diagnostics-system-pftop']['match'] = array();
$priv_list['page-diagnostics-system-pftop']['match'][] = "diag_pftop.php*";

$priv_list['page-diagnostics-ping'] = array();
$priv_list['page-diagnostics-ping']['name'] = gettext("WebCfg - Diagnostics: Ping");
$priv_list['page-diagnostics-ping']['descr'] = gettext("Allow access to the 'Diagnostics: Ping' page.");
$priv_list['page-diagnostics-ping']['match'] = array();
$priv_list['page-diagnostics-ping']['match'][] = "diag_ping.php*";

$priv_list['page-diagnostics-rebootsystem'] = array();
$priv_list['page-diagnostics-rebootsystem']['name'] = gettext("WebCfg - Diagnostics: Reboot System");
$priv_list['page-diagnostics-rebootsystem']['descr'] = gettext("Allow access to the 'Diagnostics: Reboot System' page.");
$priv_list['page-diagnostics-rebootsystem']['match'] = array();
$priv_list['page-diagnostics-rebootsystem']['match'][] = "diag_reboot.php*";

$priv_list['page-diagnostics-resetstate'] = array();
$priv_list['page-diagnostics-resetstate']['name'] = gettext("WebCfg - Diagnostics: Reset states");
$priv_list['page-diagnostics-resetstate']['descr'] = gettext("Allow access to the 'Diagnostics: Reset states' page.");
$priv_list['page-diagnostics-resetstate']['match'] = array();
$priv_list['page-diagnostics-resetstate']['match'][] = "diag_resetstate.php*";

$priv_list['page-diagnostics-routingtables'] = array();
$priv_list['page-diagnostics-routingtables']['name'] = gettext("WebCfg - Diagnostics: Routing tables");
$priv_list['page-diagnostics-routingtables']['descr'] = gettext("Allow access to the 'Diagnostics: Routing tables' page.");
$priv_list['page-diagnostics-routingtables']['match'] = array();
$priv_list['page-diagnostics-routingtables']['match'][] = "diag_routes.php*";

$priv_list['page-diagnostics-smart'] = array();
$priv_list['page-diagnostics-smart']['name'] = gettext("WebCfg - Diagnostics: S.M.A.R.T. Status");
$priv_list['page-diagnostics-smart']['descr'] = gettext("Allow access to the 'Diagnostics: S.M.A.R.T. Status' page.");
$priv_list['page-diagnostics-smart']['match'] = array();
$priv_list['page-diagnostics-smart']['match'][] = "diag_smart.php*";

$priv_list['page-diagnostics-sockets'] = array();
$priv_list['page-diagnostics-sockets']['name'] = gettext("WebCfg - Diagnostics: Sockets");
$priv_list['page-diagnostics-sockets']['descr'] = gettext("Allow access to the 'Diagnostics: Sockets' page.");
$priv_list['page-diagnostics-sockets']['match'] = array();
$priv_list['page-diagnostics-sockets']['match'][] = "diag_sockets.php*";

$priv_list['page-diagnostics-statessummary'] = array();
$priv_list['page-diagnostics-statessummary']['name'] = gettext("WebCfg - Diagnostics: States Summary");
$priv_list['page-diagnostics-statessummary']['descr'] = gettext("Allow access to the 'Diagnostics: States Summary' page.");
$priv_list['page-diagnostics-statessummary']['match'] = array();
$priv_list['page-diagnostics-statessummary']['match'][] = "diag_states_summary.php*";

$priv_list['page-diagnostics-system-activity'] = array();
$priv_list['page-diagnostics-system-activity']['name'] = gettext("WebCfg - Diagnostics: System Activity");
$priv_list['page-diagnostics-system-activity']['descr'] = gettext("Allows access to the 'Diagnostics: System Activity' page");
$priv_list['page-diagnostics-system-activity']['match'] = array();
$priv_list['page-diagnostics-system-activity']['match'][] = "diag_system_activity.php*";

$priv_list['page-diagnostics-tables'] = array();
$priv_list['page-diagnostics-tables']['name'] = gettext("WebCfg - Diagnostics: pf Table IP addresses");
$priv_list['page-diagnostics-tables']['descr'] = gettext("Allow access to the 'Diagnostics: Tables' page.");
$priv_list['page-diagnostics-tables']['match'] = array();
$priv_list['page-diagnostics-tables']['match'][] = "diag_tables.php*";

$priv_list['page-diagnostics-testport'] = array();
$priv_list['page-diagnostics-testport']['name'] = gettext("WebCfg - Diagnostics: Test Port");
$priv_list['page-diagnostics-testport']['descr'] = gettext("Allow access to the 'Diagnostics: Test Port' page.");
$priv_list['page-diagnostics-testport']['match'] = array();
$priv_list['page-diagnostics-testport']['match'][] = "diag_testport.php*";

$priv_list['page-diagnostics-traceroute'] = array();
$priv_list['page-diagnostics-traceroute']['name'] = gettext("WebCfg - Diagnostics: Traceroute");
$priv_list['page-diagnostics-traceroute']['descr'] = gettext("Allow access to the 'Diagnostics: Traceroute' page.");
$priv_list['page-diagnostics-traceroute']['match'] = array();
$priv_list['page-diagnostics-traceroute']['match'][] = "diag_traceroute.php*";

$priv_list['page-firewall-easyrule'] = array();
$priv_list['page-firewall-easyrule']['name'] = gettext("WebCfg - Firewall: EasyRule add/status");
$priv_list['page-firewall-easyrule']['descr'] = gettext("Allow access to the 'Firewall: EasyRule' add/status page.");
$priv_list['page-firewall-easyrule']['match'] = array();
$priv_list['page-firewall-easyrule']['match'][] = "easyrule.php*";

taken from rectorphp/rector#7649

rajyan · 2022-12-20T08:17:35Z

it seems to improve this example by 40% (45secs -> 26 secs). all other things I tested (my oversized array cases) were nearly the same as before:

Oh, that was better than I thought 👍 Thanks for the info, I am now still motivated to continue this PR:smile:

ondrejmirtes · 2022-12-20T08:24:01Z

My main motivation for this optimization was to speed up situation where we have ObjectType and in subtractedType there's like 64 ObjectTypes in a union - typical when analysing NodeScopeResolver or MutatingScope...

rajyan · 2022-12-20T08:27:31Z

Yeah, I think it has improved a little already, but not as significant than I thought.
Maybe because I haven't implemented correctly yet.

rajyan · 2022-12-21T16:32:48Z

ok
the error of the current implementation is that
[1, 2] and [int] is merged as [2] and [int]

rajyan · 2022-12-23T00:56:24Z

The current implementation should be faster significantly.
Not implemented yet, but I finally found the goal.
Instead of the scalar type optimization, the same preprocessing as isArray types can be done for isFloat, isBoolean, isInteger, isString types.
After that, the result of the preprocessed types can be a one large bucket, because the result types are mutually exclusive (eg. isFloat type is never a super/sub type of isArray type)
We can apply the bucket logic proposed in phpstan/phpstan#8499 after the preprocess, because union of those buckets won't cause the problems I explained in phpstan/phpstan#8499 (comment)

staabm · 2022-12-23T11:49:39Z

running #2078 (comment)

thru 22f2012 is already way faster then 1.9.x-dev

great job

rajyan · 2023-01-19T22:59:55Z

The former implementation ran comparedTypesInUnion loop twice for IntegerType in

phpstan-src/src/Type/TypeCombinator.php

Line 201 in 80b5cdd

$compareResult = self::compareTypesInUnion($types[$i], $scalarTypeItems[$j]);

and

phpstan-src/src/Type/TypeCombinator.php

Line 238 in 80b5cdd

$compareResult = self::compareTypesInUnion($types[$i], $types[$j]);

This could union int<min, 1>, int<3, max>, 2 correctly in two steps like
int<min, 1>, int<3, max>, 2 => int<min, 2>, int<3, max>
in the first comparedTypesInUnion loop
and
int<min, 2>, int<3, max> => int
int the second comparedTypesInUnion loop

If we sort IntegerType correctly, we only need one comparedTypesInUnion loop

staabm · 2023-01-20T13:18:16Z

fyi, I compared the latest revision of this PR with 1.9.x-dev and it seems there is no perf difference anymore.

ondrejmirtes · 2023-01-20T13:22:55Z

What about analyzing this file? #2078 (comment)

staabm · 2023-01-20T13:37:55Z

What about analyzing this file? #2078 (comment)

mstaab@NB-COMPLEX-45 MINGW64 /c/dvl/Workspace/phpstan-src-staabm (1.9.x)
$ time php bin/phpstan analyze test.php --debug
Note: Using configuration file C:\dvl\Workspace\phpstan-src-staabm\phpstan.neon.dist.
C:\dvl\Workspace\phpstan-src-staabm\test.php
 ------ -----------------------------------
  Line   test.php
 ------ -----------------------------------
  25     Variable $g might not be defined.
 ------ -----------------------------------

 [ERROR] Found 1 error

real    0m8.076s
user    0m0.000s
sys     0m0.000s



mstaab@NB-COMPLEX-45 MINGW64 /c/dvl/Workspace/phpstan-src-staabm (pr/2078)
$ time php bin/phpstan analyze test.php --debug
Note: Using configuration file C:\dvl\Workspace\phpstan-src-staabm\phpstan.neon.dist.
C:\dvl\Workspace\phpstan-src-staabm\test.php
 ------ -----------------------------------
  Line   test.php
 ------ -----------------------------------
  25     Variable $g might not be defined.
 ------ -----------------------------------

 [ERROR] Found 1 error

real    0m9.055s
user    0m0.000s
sys     0m0.000s

no improvement. (don't look at the absolute numbers.. I don't know on which computer I did the measures within comment of this file

I also did blackfire profiles and these also don't show a difference on my windows computer.
I can have another look at my macbook this evening.

rajyan · 2023-01-23T00:42:26Z

Thank you for confirming the performance!

there is no perf difference anymore.

Yeah, I'm stuck with this problem now...
I don't have enough time to look into this problem this month, but would try it again sometime

ondrejmirtes · 2023-01-23T06:57:35Z

Alright, don't worry about this, it was my idea and it wasn't very good 😊 If you get a new insight you can try it again but don't feel obligated to do so 😊 Thank you:

rajyan force-pushed the typecombinator-union-optimization branch from cdeb6c1 to a93a987 Compare December 11, 2022 08:52

rajyan mentioned this pull request Dec 11, 2022

TypeCombinator optimization idea phpstan/phpstan#8499

Closed

rajyan mentioned this pull request Dec 19, 2022

Use isArray, isConstantArray instead of instanceof in TypeCombinartor::union #2118

Merged

rajyan force-pushed the typecombinator-union-optimization branch 2 times, most recently from 368ae34 to 092264b Compare December 20, 2022 00:54

rajyan force-pushed the typecombinator-union-optimization branch from 8a49c21 to 04ccb01 Compare December 21, 2022 01:11

rajyan force-pushed the typecombinator-union-optimization branch from cc710e8 to 22f2012 Compare December 23, 2022 00:48

ondrejmirtes force-pushed the 1.9.x branch from a5d90c1 to a69c7f0 Compare January 5, 2023 14:23

rajyan force-pushed the typecombinator-union-optimization branch 2 times, most recently from a961cc9 to b3a88d8 Compare January 7, 2023 09:49

rajyan force-pushed the typecombinator-union-optimization branch from bd4da1d to ac998f5 Compare January 19, 2023 22:58

rajyan added 9 commits January 20, 2023 08:03

quit spreading normalized UnionTypes

3903c7e

tmp

1f6193d

tmp

1e983e3

tmp

900dd4f

tmp

c234f92

implement UnionType merging logic correctly

15df576

fix flatten

4ecec98

fix

83e8f08

micro optimization

8aae7e2

rajyan added 6 commits January 20, 2023 08:03

temp

d5e5c93

fix BenevolentUnionType

a7bcb23

fix

0643c15

fix cs

a5cbc4c

fix IntegerType

eba5bc3

fix cs

406c9b9

rajyan force-pushed the typecombinator-union-optimization branch from ac998f5 to 406c9b9 Compare January 19, 2023 23:03

fix tests for improved IntegerRangeType union

f8670fc

ondrejmirtes closed this Jan 23, 2023

Conversation

rajyan commented Dec 11, 2022

Uh oh!

rajyan commented Dec 11, 2022

Uh oh!

rajyan commented Dec 20, 2022

Uh oh!

staabm commented Dec 20, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

rajyan commented Dec 20, 2022

Uh oh!

ondrejmirtes commented Dec 20, 2022

Uh oh!

rajyan commented Dec 20, 2022

Uh oh!

rajyan commented Dec 21, 2022

Uh oh!

rajyan commented Dec 23, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

staabm commented Dec 23, 2022

Uh oh!

rajyan commented Jan 19, 2023

Uh oh!

staabm commented Jan 20, 2023

Uh oh!

ondrejmirtes commented Jan 20, 2023

Uh oh!

staabm commented Jan 20, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

rajyan commented Jan 23, 2023

Uh oh!

ondrejmirtes commented Jan 23, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

staabm commented Dec 20, 2022 •

edited

Loading

rajyan commented Dec 23, 2022 •

edited

Loading

staabm commented Jan 20, 2023 •

edited

Loading