Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!

Bug 279623

Summary: add emerge option for aggressive --jobs parallelization so packages may be built before their satisfied dependencies
Product: Portage Development Reporter: Zac Medico <zmedico>
Component: Core - Interface (emerge)Assignee: Portage team <dev-portage>
Status: CONFIRMED ---    
Severity: normal CC: ast, broken.zhou, canarauc, esigra, marcan, pacho, totktonada.ru
Priority: High    
Version: 2.1   
Hardware: All   
OS: All   
URL: http://git.chromium.org/gitweb/?p=crosutils.git;a=blob_plain;f=parallel_emerge;hb=HEAD
See Also: https://bugs.gentoo.org/show_bug.cgi?id=452172
https://bugs.gentoo.org/show_bug.cgi?id=608900
https://bugs.gentoo.org/show_bug.cgi?id=681312
Whiteboard:
Package list:
Runtime testing required: ---
Bug Depends on: 192319    
Bug Blocks: 184128    

Description Zac Medico gentoo-dev 2009-07-29 20:26:25 UTC
We can add an option to make --jobs parallization more aggressive, so that packages may be built before their satisfied dependencies when appropriate.

Also note that bug 256616 and bug 259954 also place limits on parallelization.
This is mentioned in the faq:

  http://www.gentoo.org/proj/en/portage/doc/faq.xml
Comment 1 Zac Medico gentoo-dev 2009-07-29 20:28:55 UTC
*** Bug 279049 has been marked as a duplicate of this bug. ***
Comment 2 Cănărău Constantin 2009-07-30 11:51:01 UTC
This would be nice, and certainly possible and useful during emerge -e "set_name", when there are no new packages to build, therefore dependencies could be emerged before.

Thank you.
Comment 3 Cănărău Constantin 2009-08-02 21:16:29 UTC
First: I don't know only basics about python and only very few things about portage internals.
I think that portage "somehow" already have this feature.
Environment condition: User have to do:
1. emerge --sync
2. emerge -uDN world
3. emerge @preserved-rebuild
so there are no new packages, no new use flags.
In this condition it's safe to do:
for f in `emerge -pe system | grep ebuild | gawk ' { print "="$4; } '` ; do echo -n $f" " ; done > build.list ; emerge --nodeps --jobs=x --load-average=y --keep-going `cat build.list`

If my preconditions aren't wrong, portage have to:
1. internal generate list of packages (it is done however);
2. check there are no new packages or flag change (--verbose option generate this statistics).
3. append the "--nodeps" option (equivalent).

I'm certainly that my presumptions could be TERRIBLY WRONG when I speak about portage internals, and I'm sure there are more cases or opportunities to implement Zac Medico idea, but I thought at the safest way.
Comment 4 Zac Medico gentoo-dev 2009-08-03 18:32:39 UTC
(In reply to comment #3)
> 3. append the "--nodeps" option (equivalent).

I still want to account for dependencies, in order to ensure that a package's dependencies are not merged/replaced/upgraded _while_ it's being built.
Comment 5 Cănărău Constantin 2009-10-08 08:14:48 UTC
Are there any plans regarding this bug ? Have you, developers, time to take a look at it ?
I don't want to be rude or hurry up anybody, I'm just interested about the status of this bug.

Thank you!
Comment 6 Zac Medico gentoo-dev 2009-10-08 08:19:27 UTC
No, nothing yet. If you're interested in working on it, the relevant code is in the Scheduler._choose_pkg() method:

http://sources.gentoo.org/viewcvs.py/portage/main/trunk/pym/_emerge/Scheduler.py
Comment 7 Zac Medico gentoo-dev 2010-08-28 13:14:23 UTC
ABI slot dependencies as discussed in bug 192319 and bug 327809 will provide important data for use in aggressive --jobs parallelization, since it will be possible to intelligently avoid building packages at a times when they will be linked to a dependency that will later be upgraded to a new ABI.
Comment 8 Zac Medico gentoo-dev 2010-08-28 13:31:56 UTC
We can provide options to control the conditions under which a package will be built before its dependencies. One form of control is to vary behavior based on differences between dependency types DEPEND (build-time), RDEPEND (run-time), and PDEPEND (post-run-time). Another form of control is to vary behavior based on whether a dependency is scheduled to be upgraded to a new version, or whether it is scheduled to be rebuilt without version change. These two forms of control can be mixed, so that version changes in build-time dependencies affect scheduling differently than version changes in run-time dependencies.
Comment 9 Cănărău Constantin 2010-08-28 18:41:18 UTC
That's wonderful news. Thank you for your time!
Actually, since February I use the following scripts to recompile entire world or system. I know it's not entire safe but it is faster and didn't cause any problem until now: http://forums.gentoo.org/viewtopic-p-6391227.html#6391227
Should I worry about it ?
Comment 10 Zac Medico gentoo-dev 2010-08-28 21:59:39 UTC
(In reply to comment #9)
> problem until now: http://forums.gentoo.org/viewtopic-p-6391227.html#6391227
> Should I worry about it ?

It looks like that could give you some intermittent build failures due to dependencies being merged while something is building. It might also lead to subtle corruption without build failure, for the same reason.
Comment 11 Zac Medico gentoo-dev 2010-08-29 01:55:37 UTC
In order to make quick and safe decisions for aggressive parallelization, it seems that the Scheduler is going to have to maintain a dependency graph that represents the state of the installed packages at every moment. Without this information, it doesn't seem possible to make the necessary decisions quickly and safely.

Because of the way that the existing (non-aggressive) parallelization algorithm works, it is able to make relatively safe decisions while relying on a static dependency graph that only represents the final state of the system.
Comment 12 Zac Medico gentoo-dev 2011-12-12 07:48:29 UTC
*** Bug 383439 has been marked as a duplicate of this bug. ***
Comment 13 Joe Breuer 2012-03-03 11:11:04 UTC
I still think there's something different wrong with dependency calculation WRT parallelization, in conjunction with building packages in the system set.

See bug #403895, which was classified a transitive duplicate of this one.

On the system described in the above-mentioned bug, I'm just now doing another set of updates, and I see the following behavior:

# emerge -bDNauvt @system
>>> Emerging (1 of 26) dev-libs/expat-2.0.1-r6
>>> Emerging (2 of 26) dev-libs/icu-4.8.1.1-r1
>>> Emerging (3 of 26) sys-devel/gcc-config-1.5-r2
>>> Emerging (4 of 26) sys-devel/autoconf-wrapper-12
>>> Emerging (5 of 26) sys-devel/automake-wrapper-6
>>> Installing (4 of 26) sys-devel/autoconf-wrapper-12
>>> Emerging (6 of 26) media-sound/alsa-headers-1.0.25
>>> Installing (5 of 26) sys-devel/automake-wrapper-6
>>> Installing (6 of 26) media-sound/alsa-headers-1.0.25
>>> Installing (3 of 26) sys-devel/gcc-config-1.5-r2
>>> Installing (1 of 26) dev-libs/expat-2.0.1-r6
>>> Installing (2 of 26) dev-libs/icu-4.8.1.1-r1
>>> Emerging (7 of 26) net-misc/rsync-3.0.9
>>> Installing (7 of 26) net-misc/rsync-3.0.9
>>> Emerging (8 of 26) dev-perl/URI-1.590.0
>>> Installing (8 of 26) dev-perl/URI-1.590.0
>>> Emerging (9 of 26) dev-libs/libtasn1-2.11
>>> Installing (9 of 26) dev-libs/libtasn1-2.11
>>> Emerging (10 of 26) dev-perl/HTML-Parser-3.690.0
>>> Installing (10 of 26) dev-perl/HTML-Parser-3.690.0
>>> Emerging (11 of 26) virtual/perl-Digest-SHA-5.47
>>> Installing (11 of 26) virtual/perl-Digest-SHA-5.47
>>> Emerging (12 of 26) dev-perl/Digest-HMAC-1.30.0
>>> Installing (12 of 26) dev-perl/Digest-HMAC-1.30.0
>>> Emerging (13 of 26) media-libs/alsa-lib-1.0.25-r1
>>> Installing (13 of 26) media-libs/alsa-lib-1.0.25-r1
>>> Emerging (14 of 26) media-sound/alsa-utils-1.0.25-r1
>>> Installing (14 of 26) media-sound/alsa-utils-1.0.25-r1
>>> Emerging (15 of 26) app-editors/vim-core-7.3.409
>>> Installing (15 of 26) app-editors/vim-core-7.3.409
>>> Emerging (16 of 26) app-editors/vim-7.3.409
>>> Installing (16 of 26) app-editors/vim-7.3.409
>>> Emerging (17 of 26) media-libs/libsdl-1.2.15
>>> Installing (17 of 26) media-libs/libsdl-1.2.15
>>> Emerging (18 of 26) www-client/links-2.5
>>> Installing (18 of 26) www-client/links-2.5
>>> Emerging (19 of 26) dev-libs/libxml2-2.7.8-r5
>>> Installing (19 of 26) dev-libs/libxml2-2.7.8-r5
>>> Emerging (20 of 26) sys-libs/tdb-1.2.9
>>> Installing (20 of 26) sys-libs/tdb-1.2.9
>>> Emerging (21 of 26) sys-libs/talloc-2.0.7
>>> Jobs: 21 of 26 complete, 1 running              Load avg: 1.40, 3.52, 2.34

I.e.: At the very beginning a number of packages are built in parallel, and after installing the first of the parallel packages at the beginning emerge degrades to a linear 'build one, install one'.

CPU is at 8% (one of twelve logical cores working). The higher load avgs come from a little paralellism due to MAKOPTS -j etc.; but the machine is by far not fully utilized.

To pick one arbitrary example: I cannot see a depency chain which hinders alsa-lib from being built way sooner parallel to other packages; IMO it could have been started right after installing alsa-headers.
Comment 14 Sebastian Luther (few) 2012-03-03 20:18:03 UTC
Imo, for this bug to go anywhere, we'll need a reduced test case. That is, a set of (possibly automatically created) ebuilds that shows this problem. Otherwise there are so much possibilities for subtle interactions that describing the merge order isn't enough to decide if there is an bug.
Comment 15 Yichao Zhou 2013-01-15 04:21:11 UTC
I think Joachim Breuer is right.  I bumped into this problem today.
The packages
[ebuild  N     ] x11-drivers/xf86-video-ati-7.0.0  USE="udev (-glamor)" 
[ebuild  N     ] x11-drivers/xf86-video-intel-2.20.13  USE="dri sna udev -glamor -uxa -xvmc" 
[ebuild  N     ] x11-drivers/xf86-input-synaptics-1.6.2-r1 
[ebuild  N     ] x11-drivers/xf86-input-evdev-2.7.3 
do not emerge parallelly.  They obviously not depend on each other.  Maybe I should open a new bug report.

Example:

Gentoo-20121221 / # emerge xorg-drivers xorg-server

These are the packages that would be merged, in order:

Calculating dependencies... done!
[ebuild  N     ] sys-libs/mtdev-1.1.3  USE="-static-libs" 
[ebuild  N     ] x11-apps/xauth-1.0.7  USE="ipv6" 
[ebuild  N     ] x11-apps/xkbcomp-1.2.3 
[ebuild  N     ] x11-proto/trapproto-3.4.3 
[ebuild  N     ] x11-proto/bigreqsproto-1.1.2  USE="-doc" 
[ebuild  N     ] x11-proto/xf86dgaproto-2.1-r1 
[ebuild  N     ] x11-proto/xf86rushproto-1.1.2-r1 
[ebuild  N     ] x11-misc/xbitmaps-1.1.1 
[ebuild  N     ] x11-proto/xcmiscproto-1.2.2  USE="-doc" 
[ebuild  N     ] x11-apps/xrdb-1.0.9 
[ebuild  N     ] x11-misc/xkeyboard-config-2.7 
[ebuild  N     ] x11-apps/xinit-1.3.2  USE="minimal" 
[ebuild  N     ] x11-base/xorg-server-1.13.1  USE="ipv6 nptl suid udev xorg -dmx -doc -kdrive -minimal (-selinux) -static-libs -tslib -xnest -xvfb" 
[ebuild  N     ] x11-base/xorg-drivers-1.13  INPUT_DEVICES="evdev synaptics -acecad -aiptek -elographics -fpit -hyperpen -joystick -keyboard -mouse -mutouch -penmount -tslib -vmmouse -void -wacom" VIDEO_CARDS="intel radeon -apm -ark -ast -chips -cirrus -dummy -epson -fbdev -fglrx (-geode) -glint -i128 (-i740) -mach64 -mga -modesetting -neomagic (-newport) -nouveau -nv -nvidia (-omap) (-omapfb) -qxl -r128 -rendition -s3 -s3virge -savage -siliconmotion -sis -sisusb (-sunbw2) (-suncg14) (-suncg3) (-suncg6) (-sunffb) (-sunleo) (-suntcx) -tdfx -tga -trident -tseng -v4l -vesa -via -virtualbox -vmware (-voodoo)" 
[ebuild  N     ] x11-drivers/xf86-video-ati-7.0.0  USE="udev (-glamor)" 
[ebuild  N     ] x11-drivers/xf86-video-intel-2.20.13  USE="dri sna udev -glamor -uxa -xvmc" 
[ebuild  N     ] x11-drivers/xf86-input-synaptics-1.6.2-r1 
[ebuild  N     ] x11-drivers/xf86-input-evdev-2.7.3 

Would you like to merge these packages? [Yes/No] Y
>>> Verifying ebuild manifests
>>> Running pre-merge checks for x11-base/xorg-server-1.13.1
>>> Running pre-merge checks for x11-drivers/xf86-input-synaptics-1.6.2-r1
 * Determining the location of the kernel source code
 * Found kernel source directory:
 *     /usr/src/linux
 * Found kernel object directory:
 *     /lib/modules/3.6.11-gentoo/build
 * Found sources for kernel version:
 *     3.6.11-gentoo
>>> Starting parallel fetch
>>> Emerging (1 of 18) sys-libs/mtdev-1.1.3
>>> Emerging (2 of 18) x11-apps/xauth-1.0.7
>>> Emerging (3 of 18) x11-apps/xkbcomp-1.2.3
>>> Emerging (4 of 18) x11-proto/trapproto-3.4.3
>>> Installing (1 of 18) sys-libs/mtdev-1.1.3
>>> Emerging (5 of 18) x11-proto/bigreqsproto-1.1.2
>>> Installing (2 of 18) x11-apps/xauth-1.0.7
>>> Emerging (6 of 18) x11-proto/xf86dgaproto-2.1-r1
>>> Emerging (7 of 18) x11-proto/xf86rushproto-1.1.2-r1
>>> Installing (4 of 18) x11-proto/trapproto-3.4.3
>>> Emerging (8 of 18) x11-misc/xbitmaps-1.1.1
>>> Installing (3 of 18) x11-apps/xkbcomp-1.2.3
>>> Emerging (9 of 18) x11-proto/xcmiscproto-1.2.2
>>> Installing (5 of 18) x11-proto/bigreqsproto-1.1.2
>>> Emerging (10 of 18) x11-apps/xrdb-1.0.9
>>> Installing (6 of 18) x11-proto/xf86dgaproto-2.1-r1
>>> Emerging (11 of 18) x11-misc/xkeyboard-config-2.7
>>> Installing (7 of 18) x11-proto/xf86rushproto-1.1.2-r1
>>> Installing (8 of 18) x11-misc/xbitmaps-1.1.1
>>> Installing (9 of 18) x11-proto/xcmiscproto-1.2.2
>>> Installing (10 of 18) x11-apps/xrdb-1.0.9
>>> Emerging (12 of 18) x11-apps/xinit-1.3.2
>>> Installing (11 of 18) x11-misc/xkeyboard-config-2.7
>>> Installing (12 of 18) x11-apps/xinit-1.3.2
>>> Emerging (13 of 18) x11-base/xorg-server-1.13.1
>>> Installing (13 of 18) x11-base/xorg-server-1.13.1
>>> Recording x11-base/xorg-server in "world" favorites file...
>>> Emerging (14 of 18) x11-base/xorg-drivers-1.13
>>> Installing (14 of 18) x11-base/xorg-drivers-1.13
>>> Recording x11-base/xorg-drivers in "world" favorites file...
>>> Emerging (15 of 18) x11-drivers/xf86-video-ati-7.0.0
>>> Installing (15 of 18) x11-drivers/xf86-video-ati-7.0.0
>>> Emerging (16 of 18) x11-drivers/xf86-video-intel-2.20.13
>>> Installing (16 of 18) x11-drivers/xf86-video-intel-2.20.13
>>> Emerging (17 of 18) x11-drivers/xf86-input-synaptics-1.6.2-r1
>>> Installing (17 of 18) x11-drivers/xf86-input-synaptics-1.6.2-r1
>>> Emerging (18 of 18) x11-drivers/xf86-input-evdev-2.7.3
>>> Installing (18 of 18) x11-drivers/xf86-input-evdev-2.7.3
>>> Jobs: 18 of 18 complete                         Load avg: 2.19, 1.96, 2.12
>>> Auto-cleaning packages...
Comment 16 Zac Medico gentoo-dev 2013-01-15 10:56:57 UTC
(In reply to comment #15)
> I think Joachim Breuer is right.

His issue was different from yours, see bug 403895.

> I bumped into this problem today.
> The packages
> [ebuild  N     ] x11-drivers/xf86-video-ati-7.0.0  USE="udev (-glamor)" 
> [ebuild  N     ] x11-drivers/xf86-video-intel-2.20.13  USE="dri sna udev
> -glamor -uxa -xvmc" 
> [ebuild  N     ] x11-drivers/xf86-input-synaptics-1.6.2-r1 
> [ebuild  N     ] x11-drivers/xf86-input-evdev-2.7.3 
> do not emerge parallelly.  They obviously not depend on each other.  Maybe I
> should open a new bug report.

Your issue it triggered by the following circular dependency:

    x11-drivers/* -> xorg-server -> xorg-drivers -> x11-drivers/*

It happens because of the following dependency in the xorg-drivers ebuild:

   PDEPEND=xorg? ( >=x11-base/xorg-drivers-1.13 )
Comment 17 Hector Martin 2018-01-25 14:04:28 UTC
This is certainly something that I see often when doing world updates or full rebuilds - it's more obvious the more packages are involved. I just pulled in a worldfile and /etc/portage from my workstation into a beefy buildhost with a clean stage3 chroot and am running an --emptytree rebuild of everything (2500+ packages). While there are instances of significant parallelism, there are long stretches of single-file "build one, install one" (sometimes with the occassional two in parallel), like this:

>>> Emerging (720 of 2058) sys-apps/file-5.32::gentoo
>>> Installing (720 of 2058) sys-apps/file-5.32::gentoo
>>> Emerging (721 of 2058) sys-libs/cracklib-2.9.6-r1::gentoo
>>> Installing (721 of 2058) sys-libs/cracklib-2.9.6-r1::gentoo
>>> Emerging (722 of 2058) dev-python/extras-1.0.0::gentoo
>>> Installing (722 of 2058) dev-python/extras-1.0.0::gentoo
>>> Emerging (723 of 2058) dev-python/linecache2-1.0.0::gentoo
>>> Installing (723 of 2058) dev-python/linecache2-1.0.0::gentoo
>>> Emerging (724 of 2058) dev-python/traceback2-1.4.0::gentoo
>>> Installing (724 of 2058) dev-python/traceback2-1.4.0::gentoo
>>> Emerging (725 of 2058) dev-python/pypax-0.9.2::gentoo
>>> Emerging (726 of 2058) dev-python/pyxattr-0.6.0::gentoo
>>> Installing (725 of 2058) dev-python/pypax-0.9.2::gentoo
>>> Installing (726 of 2058) dev-python/pyxattr-0.6.0::gentoo
>>> Emerging (727 of 2058) dev-python/mimeparse-1.6.0::gentoo
>>> Installing (727 of 2058) dev-python/mimeparse-1.6.0::gentoo
>>> Emerging (728 of 2058) dev-python/unittest2-1.1.0::gentoo
>>> Installing (728 of 2058) dev-python/unittest2-1.1.0::gentoo
>>> Emerging (729 of 2058) dev-python/pyrsistent-0.13.0::gentoo
>>> Installing (729 of 2058) dev-python/pyrsistent-0.13.0::gentoo

With such a large number of packages, I have a hard time believing there isn't ample opportunity for much more parallelism; unless there is some deep detail of the dependency tree that I don't understand, I'd say there is no way that all of the remaining ~1300 packages wind up depending on dev-python/pyrsistent. This is rather wasteful on a 32-thread machine.

Is there a way I can help debug/improve this? Now that I have a proper build box I'm motivated to, well, actually be able to make good use of it.
Comment 18 Hector Martin 2018-01-25 15:16:48 UTC
Just to prove that something is obviously broken: cancelling the emerge while a single package is being built and doing a --resume goes back to utilizing full parallelism again. Thus, amusingly, with the current code it's probably in my best interest to periodically kill emerge and resume it to optimize build times!
Comment 19 Zac Medico gentoo-dev 2018-01-25 20:07:03 UTC
(In reply to Hector Martin from comment #17)
> >>> Emerging (723 of 2058) dev-python/linecache2-1.0.0::gentoo
> >>> Installing (723 of 2058) dev-python/linecache2-1.0.0::gentoo
> >>> Emerging (724 of 2058) dev-python/traceback2-1.4.0::gentoo
> >>> Installing (724 of 2058) dev-python/traceback2-1.4.0::gentoo

linecache2 is a dependency of traceback2.

> >>> Emerging (725 of 2058) dev-python/pypax-0.9.2::gentoo
> >>> Emerging (726 of 2058) dev-python/pyxattr-0.6.0::gentoo

You can see that some parallelization is happening, because pypax and pyxattr are building simultaneously.

(In reply to Hector Martin from comment #18)
> Just to prove that something is obviously broken: cancelling the emerge
> while a single package is being built and doing a --resume goes back to
> utilizing full parallelism again. Thus, amusingly, with the current code
> it's probably in my best interest to periodically kill emerge and resume it
> to optimize build times!

If you can reproduce it, then you can send emerge a SIGUSR1 signal. From the pdb shell, you can set a breakpoint in the _dependent_on_scheduled_merges method like I did in bug 608900, comment #1. It may be a similar issue, where there's a merge for a system package queued, and it's preventing some things that depend on it from being immediately built.
Comment 20 Hector Martin 2018-01-26 05:51:08 UTC
(In reply to Zac Medico from comment #19)
> linecache2 is a dependency of traceback2.

Sure, but the >one thousand packages coming after aren't. The issue isn't necessarily that the packages I listed aren't themselves being built in parallel, but rather that nothing else is being built in parallel with them.

> If you can reproduce it, then you can send emerge a SIGUSR1 signal. From the
> pdb shell, you can set a breakpoint in the _dependent_on_scheduled_merges
> method like I did in bug 608900, comment #1. It may be a similar issue,
> where there's a merge for a system package queued, and it's preventing some
> things that depend on it from being immediately built.

Thanks, I didn't know about the SIGUSR1 trick. I'm going to be doing some other large builds and I'll see if I catch this.

Is the any documentation to get an idea of how this is supposed to work?
Comment 21 Zac Medico gentoo-dev 2018-01-26 06:32:26 UTC
(In reply to Hector Martin from comment #20)
> Is the any documentation to get an idea of how this is supposed to work?

Just the Scheduler code itself. The _choose_pkg method is called periodically, and it's supposed to return a package if it finds one that's ready to build, and otherwise it returns None.

If it's not behaving as you would expect, it might be because the _dependent_on_scheduled_merges method is return True for some reason like in bug 608900. The _dependent_on_scheduled_merges method traverses a directed graph to see if it can find any dependencies that should be built first.

Also the _choose_pkg method is not called when the system is in a potentially fragile state involving system packages like in bug 256616 or bug 259954. The _schedule_tasks_imp method uses the _merge_wait_scheduled and _unsatisfied_system_deps attributes to account for these things.