For those looking for a technical explanation, the PHP garbage collector in this case is probably wasting a ton of CPU cycles trying to collect thousands of objects (a LOT of objects are created to represent all the inter-package rules when solving dependencies) during the solving process. It keeps trying and trying as objects are allocated and it can not collect anything but still has to check them all every time it triggers.

Disabling GC just kills the advanced GC but leaves the basic reference counting approach to freeing memory, so Composer can keep trucking without using much more memory as the GC wasn't really collecting anything. The memory reduction many people report is rather due to some other improvements we have made yesterday.

As to why the problem went unnoticed for so long, it seems that the GC is not able to be observed by profilers, so whenever we looked at profiles to improve things we obviously did not spot the issue. In most cases though this isn't an issue and I would NOT recommend everyone disables GC on their project :) GC is very useful in many cases especially long running workers, but the Composer solver falls out of the use cases it's made for.