603370 - Reorder symbols when linking libxul

Status: RESOLVED FIXED

(Firefox Build System :: General, defect)

Description

[Mike Hommey [:glandium]]

Filing this bug to track the progress on this subject.

I made an attempt today reordering object files with profiling data coming from a modified icegrind. The test was done on linux x86-64, after the application of the patches from bug 569629. Bug 569629 itself saves about 200ms off around a 4 seconds startup, and .o reordering further saved 500ms!

I'll try to integrate with fakelibs and push to try to see the effect on windows and mac, which is expected to be quite positive.

Comment 1

[Mike Hommey [:glandium]]

Attachment: WIP patch

This is a first implementation depending on the patches I sent to bug 584474, bug 605146 and bug 605153.
The order file used was generated from profiling on linux x86-64 only. I'm waiting for the try builds to see if that has some positive effect on mac and windows, already.

Comment 2

[Mike Hommey [:glandium]]

Try server builds will be available here:
http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-c6eebd7373de/

(some are already)

Surprisingly, the linux64 ts_cold result doesn't exhibit the improvement I'm seeing locally, though the binary is correctly reordered.

Comment 3

[Mike Hommey [:glandium]]

I can't get reliable numbers on mac, but it looks like it is definitely a win. ts_cold on mac64 seems to agree, too. http://perf.snarkfest.net/compare-talos/?oldRevs=e68dd8c5d9cd&newRev=c6eebd7373de&tests=ts_cold&submit=true

On Windows, LTO is getting in the way, and no change can be seen. Though looking at the symbols ordering, I'm wondering what exactly LTO is trying to do... I'd be interested in icegrind-like results on windows.

Comment 4

[Mike Hommey [:glandium]]

Attachment: WIP patch

New version against new patches from bug 584474. The reorder list still needs to be tweaked, though.

Comment 5

[Mike Hommey [:glandium]]

Attachment: WIP patch v3

Same as the previous one, but with a better profile after bug 616262.

Comment 6

[Robert Kaiser]

It feels a bit fragile to me to use a static list of files here, could that somehow be dynamically generated instead?

Comment 7

[Mike Hommey [:glandium]]

(In reply to comment #6)
> It feels a bit fragile to me to use a static list of files here, could that
> somehow be dynamically generated instead?

There are two problems with a dynamically generated list:
- it requires tools that aren't currently in the mozilla build toolbox
- it actually requires manual tweaking to really be awesome.

Seeing how a month old list is still pretty efficient at improving startup time (cf. http://glandium.org/blog/?p=1296 ). Actually the current list would only require a few tweaks for new static initializers and a few new object files.

An advantage of having a static list is that distributors don't need to dynamically generate the list, which is a heavyweight process, to get the gains from this reordering.

Comment 8

[Mark Banner (:standard8)]

If we're going for a manually generated list, then I think we need comprehensive instructions on how to build that list - pointed to from the file itself and probably stored on devmo or something.

It may also need to become part of run-up-to-final release checklists that the tweaking has been done.

Comment 9

[(not currently active) Ted Mielczarek]

I would assume that an out-of-date manually generated list is not really worse than no list at all, in which case you get the quasi-random ordering we've always had.

Comment 10

[Mike Hommey [:glandium]]

Attachment: part 1 - Add an option to expandlibs-exec to allow to reorder the objects list

Updated to fit last changes in bug 584474. I'm now separating the implementation and the actual reordering list.

Comment 11

[Mike Hommey [:glandium]]

Attachment: part 2 - Use an object reorder list for libxul

This is the same list as the previous one, I'll update with a fresh profile soon.

Comment 12

[(not currently active) Ted Mielczarek]

Comment on attachment 504488 [details] [diff] [review]
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list

>diff --git a/config/config.mk b/config/config.mk
>--- a/config/config.mk
>+++ b/config/config.mk
>@@ -842,10 +842,10 @@ endif
> OPTIMIZE_JARS_CMD = $(PYTHON) $(call core_abspath,$(topsrcdir)/config/optimizejars.py)
> 
> EXPAND_LIBS = $(PYTHON) $(DEPTH)/config/expandlibs.py
> EXPAND_LIBS_EXEC = $(PYTHON) $(topsrcdir)/config/pythonpath.py -I$(DEPTH)/config $(topsrcdir)/config/expandlibs-exec.py
> EXPAND_LIBS_GEN = $(PYTHON) $(topsrcdir)/config/pythonpath.py -I$(DEPTH)/config $(topsrcdir)/config/expandlibs-gen.py
> EXPAND_AR = $(EXPAND_LIBS_EXEC) --extract -- $(AR)
> EXPAND_CC = $(EXPAND_LIBS_EXEC) --uselist -- $(CC)
> EXPAND_CCC = $(EXPAND_LIBS_EXEC) --uselist -- $(CCC)
>-EXPAND_LD = $(EXPAND_LIBS_EXEC) --uselist -- $(LD)
>-EXPAND_MKSHLIB = $(EXPAND_LIBS_EXEC) --uselist -- $(MKSHLIB)
>+EXPAND_LD = $(EXPAND_LIBS_EXEC) --uselist $(if $(REORDER),--reorder $(REORDER) --extract )-- $(LD)
>+EXPAND_MKSHLIB = $(EXPAND_LIBS_EXEC) --uselist $(if $(REORDER),--reorder $(REORDER) --extract )-- $(MKSHLIB)

If you always need --extract to reorder, why not just make --reorder imply --extract?

>diff --git a/config/expandlibs-exec.py b/config/expandlibs-exec.py
>--- a/config/expandlibs-exec.py
>+++ b/config/expandlibs-exec.py
>+    def reorder(self, order_file):
>+        '''Given a list of file names without OBJ_SUFFIX, rearrange self
>+        so that the object file names it contains follow that list.
>+        '''
>+        order = map(lambda s: s.strip(), open(order_file).readlines())

order = [line.strip() for line in open(order_file).readlines()]

or if you don't expect trailing whitespace, just newlines, you can just do:

order = open(order_file).read().splitlines()

>+        objs = filter(lambda item: os.path.splitext(item)[1] == OBJ_SUFFIX, self)

objs = [item for item in self if os.path.splitext(item)[1] == OBJ_SUFFIX]

>+        if not len(objs): return

if not objs: works here, empty lists evaluate as False.

>+        idx = self.index(objs[0])
>+        objnames = dict(map(lambda item: [os.path.splitext(os.path.basename(item))[0],item], objs))
>+        ordered = map(lambda item: objnames[item], filter(lambda item: item in objnames.keys(), order))
>+        ordered += filter(lambda item: item not in ordered, objs)
>+        self[0:] = self[0:idx] + ordered + filter(lambda item: os.path.splitext(item)[1] != OBJ_SUFFIX, self[idx:])
>+

This seems...unnecssarily complex. Here's how I'd write this logic:

order = [[line.strip() + OBJ_SUFFIX for line in open(order_file).readlines()]
if any(o not in self for o in order):
  error
objs = [o for o in self if o.endswith(OBJ_SUFFIX)]
idx = self.index(objs[0])
# keep everything before the first object, then the ordered objects, then any other objects, then any non-objects after the first object
self[0:] = self[0:idx] + order + [o for o in objs if o not in order] + [x for x in self[idx:] if not x.endswith(OBJ_SUFFIX)]

Other than that it looks good.

Comment 13

[Mike Hommey [:glandium]]

Attachment: part 1 - Add an option to expandlibs-exec to allow to reorder the objects list, v2

This addresses review from comment 12 and adds a testcase.

Comment 14

[Mike Hommey [:glandium]]

Attachment: part 1 - Add an option to expandlibs-exec to allow to reorder the objects list, v2.1

There were missing parens.

Comment 15

[(not currently active) Ted Mielczarek]

Comment on attachment 514815 [details] [diff] [review]
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list, v2.1

>diff --git a/config/expandlibs_exec.py b/config/expandlibs_exec.py
>--- a/config/expandlibs_exec.py
>+++ b/config/expandlibs_exec.py
>+    def reorder(self, order_list):
>+        '''Given a list of file names without OBJ_SUFFIX, rearrange self
>+        so that the object file names it contains are ordered according to
>+        that list.
>+        '''
>+        objs = [o for o in self if o.endswith(conf.OBJ_SUFFIX)]
>+        if not objs: return

return goes on a new line.

Looks fine otherwise.

Comment 16

[Mike Hommey [:glandium]]

Attachment: part 1 - Add an option to expandlibs-exec to allow to reorder the objects list.

Refreshed against current trunk.

Comment 17

[Mike Hommey [:glandium]]

Comment on attachment 588912 [details] [diff] [review]
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list.

Carrying over r+

Comment 18

[Mike Hommey [:glandium]]

Landed part 1
https://hg.mozilla.org/integration/mozilla-inbound/rev/283408b8d8a3

Comment 19

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/283408b8d8a3

Leaving open for part 2.

Comment 20

[Mike Hommey [:glandium]]

It turns out reordering objects doesn't have so much benefit. Reordering symbols does.

Comment 21

[Mike Hommey [:glandium]]

Attachment: Add an option to expandlibs-exec to allow to reorder the symbols when linking

This applies on top of a backout of part 1 (changeset 283408b8d8a3). It only works for ELF linking. Object reordering didn't really work on other targets anyways.

This new version takes a list of symbols, resolves them into sections, and uses the list of sections to feed the linker. Both GNU ld and gold are supported.

Comment 22

[Mike Hommey [:glandium]]

Attachment: Add an option to expandlibs-exec to allow to reorder the symbols when linking

Reordering with gold was not working entirely. (it was indeed reordering, but putting reordered stuff at the end, not at the beginning)

Comment 23

[Mike Hommey [:glandium]]

Attachment: Avoid Identical Code Folding messing with symbol reordering

Comment 24

[Mike Hommey [:glandium]]

Attachment: Avoid Identical Code Folding messing with symbol reordering

Small testcase change.

Comment 25

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

Comment on attachment 602854 [details] [diff] [review]
Add an option to expandlibs-exec to allow to reorder the symbols when linking

Review of attachment 602854 [details] [diff] [review]:
-----------------------------------------------------------------

A few nits to pick.

::: build/autoconf/expandlibs.m4
@@ +30,5 @@
> +
> +LIBS_DESC_SUFFIX=desc
> +AC_SUBST(LIBS_DESC_SUFFIX)
> +AC_SUBST(EXPAND_LIBS_LIST_STYLE)
> +if test "$GCC_USE_GNU_LD"; then

Put a newline between these.

@@ +41,5 @@
> +             EXPAND_LIBS_ORDER_STYLE=section-ordering-file,
> +             EXPAND_LIBS_ORDER_STYLE=)
> +         LDFLAGS="$_SAVE_LDFLAGS"
> +         if test -z "$EXPAND_LIBS_ORDER_STYLE"; then
> +             if AC_TRY_COMMAND(${CC-cc} ${DSO_LDOPTS} ${LDFLAGS} -o conftest${DLL_SUFFIX} -Wl,--verbose 2> /dev/null | sed -n '/^===/,/^===/p' | grep '\.text'); then

$(DLL_PREFIX)conftest$(DLL_SUFFIX)

@@ +46,5 @@
> +                 EXPAND_LIBS_ORDER_STYLE=linkerscript
> +             else
> +                 EXPAND_LIBS_ORDER_STYLE=none
> +             fi
> +             rm -f conftest${DLL_SUFFIX}

Same.

::: config/config.mk
@@ +789,5 @@
>  EXPAND_AR = $(EXPAND_LIBS_EXEC) --extract -- $(AR)
>  EXPAND_CC = $(EXPAND_LIBS_EXEC) --uselist -- $(CC)
>  EXPAND_CCC = $(EXPAND_LIBS_EXEC) --uselist -- $(CCC)
>  EXPAND_LD = $(EXPAND_LIBS_EXEC) --uselist -- $(LD)
> +EXPAND_MKSHLIB = $(EXPAND_LIBS_EXEC) --uselist $(if $(SYMBOL_ORDER),--symbol-order $(SYMBOL_ORDER) )-- $(MKSHLIB)

I'd prefer
if $(SYMBOL_ORDER)
SYMBOL_ORDER_ARGS = --symbol-order $(SYMBOL_ORDER)
fi
EXPAND_MKSHLIB = $(EXPAND_LIBS_EXEC) --uselist $(SYMBOL_ORDER_ARGS) -- $(MKSHLIB)

o rsomething similar.

Comment 26

[Mike Hommey [:glandium]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/b054a6df1b52
https://hg.mozilla.org/integration/mozilla-inbound/rev/c9d268575baa
https://hg.mozilla.org/integration/mozilla-inbound/rev/42ddb716c71d

Comment 27

[Mike Hommey [:glandium]]

Fixup:
https://hg.mozilla.org/integration/mozilla-inbound/rev/59148c7434aa

Comment 28

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

https://hg.mozilla.org/mozilla-central/rev/b054a6df1b52
https://hg.mozilla.org/mozilla-central/rev/c9d268575baa
https://hg.mozilla.org/mozilla-central/rev/42ddb716c71d
https://hg.mozilla.org/mozilla-central/rev/59148c7434aa