Number of calls to createConflictRule() before: 191703 after: 75503

Looks good to me, will test quickly :)

quick test on the biggest project I have lying around:

Memory usage: 121.66MB (peak: 214.93MB), time: 29.92s ## master
Memory usage: 121.02MB (peak: 214.2MB), time: 19.9s ## reduce-conflict-rules

edit
After running both branches some more - master seems to be at around 22s, reduce-conflict-rules at around 19-20s. So the improvement doesn't seem to be quite as extreme.

$ php -v
PHP 5.6.2-1 (cli) (built: Oct 17 2014 17:15:37) 

So no memory improvement for you, that's funny. Still a win CPU wise though.

I think the memory improvement may depend on PHP version, potentially random influences on garbage collection, etc. as the objects were thrown away previously anyway, so you could get lucky and not have much of a memory impact through them, or unlucky and they'd use up a lot.

I got similar results as seen @rwos:

Memory usage: 231.36MB (peak: 407.51MB), time: 24.24s ##master
Memory usage: 232.26MB (peak: 408.16MB), time: 21.05s ##reduce-conflict-rules

PHP 5.6.3 (cli) (built: Nov 17 2014 11:33:26) (DEBUG)

Also getting major speed improvements for shopware/shopware with only slightly lower peak memory usage.

# master
Memory usage: 90.42MB (peak: 171.47MB), time: 16.31s 
# reduce-conflict-rules
Memory usage: 90.42MB (peak: 169.64MB), time: 8.01s

Edit:

Following runs:

# master
Memory usage: 90.42MB (peak: 171.5MB), time: 9.82s
# reduce-conflict-rules# reduce-conflict-rules
Memory usage: 90.42MB (peak: 169.64MB), time: 7.92s

php -v
PHP 5.5.14 (cli) (built: Jul 16 2014 08:56:27) 
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.5.0, Copyright (c) 1998-2014 Zend Technologies
    with Zend OPcache v7.0.4-dev, Copyright (c) 1999-2014, by Zend Technologies

Yup it depends on the workload / set of packages what kind of improvements you get, and possibly php version too, but it has at worst no effect so it's a win :)

Rebased onto merged solver optimize branch

This might indeed be a GC issue. If there are many objects created - all of which cannot be cleaned-up. PHP's GC will kick in frequently trying to clean-up, only to discover that it cannot clean-up anything, and just wastes time/CPU cycles. This might be the reason why you see the effect for big projects (= many objects), but not so much for small projects (= GC is not kicking in frequently).

In these cases, disabling GC entirely is a lot faster (at the cost of some more memory consumption ofc). If no-one has checked yet, it might be worth to add gc_disable() to the update/install command.

This is what I got:

Memory usage: 64.79MB (peak: 98.09MB), time: 38.51s # before
Memory usage: 64.95MB (peak: 98.1MB), time: 12.88s  # after

PHP 5.5.9-1ubuntu4.5 (cli) (built: Oct 29 2014 11:59:10)
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.5.0, Copyright (c) 1998-2014 Zend Technologies
    with Zend OPcache v7.0.3, Copyright (c) 1999-2014, by Zend Technologies

@schmittjoh you are right, I've added gc_disable and the result look good ;)

Memory usage: 227.76MB (peak: 591.29MB), time: 126.22s # before
Memory usage: 227.31MB (peak: 590.78MB), time: 15.23s # after gc_disable()

// php -v

PHP 5.4.27 (cli) (built: Apr 29 2014 16:01:31) 
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.4.0, Copyright (c) 1998-2014 Zend Technologies
    with Xdebug v2.2.5, Copyright (c) 2002-2014, by Derick Rethans

// before
Memory usage: 125.68MB (peak: 344.78MB), time: 109.21s

// after
Memory usage: 126.08MB (peak: 303.56MB), time: 76.78s

// php -d zend.enable_gc=0 ~/bin/composer update --dry-run --profile
Memory usage: 125.58MB (peak: 302.78MB), time: 27.09s

😄

Hm the lack of peak increase with enable_gc=0 is making me curious what is going on there. This makes it sound as if we should just always do that?

@naderman the GC in PHP is only used to be able to handle circular object graphs. For non-circular graphs, the refcount is enough to destroy values without needing the GC. So as long as you avoid circular object graphs in objects used a lot in Composer, you could indeed disable it.

My results on a decent sized symfony2 application (45 dependencies in composer.json)
php -v

PHP 5.6.3 (cli) (built: Nov 17 2014 17:01:58) 
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.6.0, Copyright (c) 1998-2014 Zend Technologies
    with Xdebug v2.2.6, Copyright (c) 2002-2014, by Derick Rethans

before b23a3cd

$ composer update --dry-run --profile
Memory usage: 144.99MB (peak: 396.44MB), time: 242.63s

$ php -d zend.enable_gc=0 /usr/local/bin/composer update --dry-run --profile
Memory usage: 144.69MB (peak: 396.07MB), time: 79.32s

after 91dd999

$ composer update --dry-run --profile
Memory usage: 145MB (peak: 379.15MB), time: 97.54s

$ php -d zend.enable_gc=0 /usr/local/bin/composer update --dry-run --profile
Memory usage: 144.68MB (peak: 378.79MB), time: 49.71s

It seems like the changes have made a big difference and disabling gc would further enhance the gains.

Great Scot! that’s drastic, thanks a lot.

PHP 5.3.10-1ubuntu3.13 with Suhosin-Patch (cli) (built: Jul 7 2014 18:54:55)

Before: Composer version 1.0-dev (a309e1d89ded6919935a842faeaed8e888fbfe37) 2014-10-20 19:16:14

Project 1:

Memory usage: 243.68MB (peak: 746.48MB), time: 123.35s
Memory usage: 243.78MB (peak: 746.92MB), time: 101.88s
Memory usage: 243.78MB (peak: 746.27MB), time: 102.5s

Project 2:

Memory usage: 272.95MB (peak: 898.45MB), time: 144.32s
Memory usage: 273.25MB (peak: 898.74MB), time: 134.78s
Memory usage: 273.28MB (peak: 899.35MB), time: 149.06s

After: Composer version 1.0-dev (91dd999eb6fe6169e8dde75ca1ada16d611c3a7f) 2014-12-01 19:19:35

Project 1:

Memory usage: 225.64MB (peak: 538.64MB), time: 46.92s
Memory usage: 225.32MB (peak: 538.24MB), time: 52.56s
Memory usage: 225.55MB (peak: 538.69MB), time: 46.18s

Project 2:

Memory usage: 255.97MB (peak: 608.14MB), time: 56.92s
Memory usage: 257.08MB (peak: 609.1MB), time: 56.55s
Memory usage: 255.63MB (peak: 607.23MB), time: 56.96s

Project 2 with GC disabled:

Memory usage: 257.05MB (peak: 608.25MB), time: 24.34s
Memory usage: 257.43MB (peak: 608.78MB), time: 25.53s
Memory usage: 257.88MB (peak: 608.57MB), time: 25.57s

Life changing.

@stof well it certainly looks like composer itself would be fine. I'm just not sure what the impact on plugins/scripts would be, there may be some around that do create such graphs.

@naderman, generally if you create many many objects, you pretty much want to always disable GC. This is because PHP has a hard-coded limit (compile-time) of root objects that it can track in its GC implementation (I believe it's set to 10000 by default).

If you get close to this limit, GC kicks in. If it cannot clean-up, it will still keep trying in frequent intervals. If you go above the limit, any new root objects are not tracked anymore, and cannot be cleaned-up whether GC is enabled, or not.

This might also be why the memory consumption for bigger projects does not vary. If GC is enabled, it's just not working anymore even if there is potentially something to clean-up. For smaller projects, you might see a memory difference.

The difference is kinda crazy, thanks @schmittjoh for pointing this out! I did the change, we'll see how it goes but it seems unanimously better, and indeed here shaves off another ~50% of runtime.

Should there be a gc_enable() call after it is finished to get the environment back to normal? Or grab gc_enabled() first and reset as necessary? Usually not needed, but if someone were using bits of the composer code programmatically it could get messy.

@RSully Yup I've been wondering about this too. I'll check what the impact is to re-enable it.

Impact seems to be low enough but I think I'll open a new issue for this because it requires more considerations.

@Seldaek we could also call gc_collect_cycles() before gc_disable() in order to free up some memory :-)

Having looked at the actual stats of what the garbage collector used to do, a composer update on packagist used to trigger the garabage collector 175 times, 174 times it did not collect anything, and one time it managed to collect 256 items, so a gc_collect_cycles() seems pretty unnecessary.

For anyone playing around with the information @naderman just gave, you can do this by compiling QafooLabs/php-profiler-extension#2 - it adds two new keys to the result gc (# of GC runs) and gcc (number of collected objects in runs) for every function call parent => child.

It is not possible at the moment to hook into how long the garbage collection takes. Evaluating right now what Zend Engine would need for that.

@hadjedjvincent it's been done already :)

@naderman Let's call it only one time then ? As gc is disabled after that, it's not really needed to call it again right ?
@Seldaek Okay thanks for the information :)

I think this is causing some issues with my project. Currently I'm running symfony 2.1. After self-updating composer then running composer update, it started downloading symfony 2.7 components, which broke the project.

After rolling back the composer self-update and running composer update again, the 2.7 packages were deleted and everything was fixed. Am I in the right place, or should I submit a general bug report?

Please submit a general bug report. The GC disabling cannot be the cause for this, but other refactorings done yesterday could be

I'm not referencing the garbage collection disabling. I'm referencing this pull request.

I just confirmed that the commit naderman@4a945da is causing the problem.

After changing line 244 in src/Composer/DependencyResolver/RuleSetGenerator.php to:

} elseif (!$this->obsoleteImpossibleForAlias($package, $provider)) {

The problem is fixed.

Created pull request #3493

Lol, oh PHP you so crazy.

Before: Memory usage: 127.39MB (peak: 280.46MB), time: 119.66s
After: Memory usage: 109.74MB (peak: 192.59MB), time: 15.79s

And I always thought composer was slow because I was in Australia lol