Last Comment Bug 603370 - Reorder symbols when linking libxul
: Reorder symbols when linking libxul
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: Build Config (show other bugs)
: Trunk
: All All
: -- normal with 1 vote (vote)
: mozilla13
Assigned To: Mike Hommey [:glandium]
:
Mentors:
Depends on: 584474 605406 616262 746650
Blocks:
  Show dependency treegraph
 
Reported: 2010-10-11 09:34 PDT by Mike Hommey [:glandium]
Modified: 2014-03-02 19:43 PST (History)
14 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
WIP patch (32.40 KB, patch)
2010-10-18 09:18 PDT, Mike Hommey [:glandium]
no flags Details | Diff | Splinter Review
WIP patch (30.88 KB, patch)
2010-11-29 01:25 PST, Mike Hommey [:glandium]
no flags Details | Diff | Splinter Review
WIP patch v3 (36.13 KB, patch)
2010-12-07 10:57 PST, Mike Hommey [:glandium]
no flags Details | Diff | Splinter Review
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list (6.55 KB, patch)
2011-01-17 08:45 PST, Mike Hommey [:glandium]
ted: review-
Details | Diff | Splinter Review
part 2 - Use an object reorder list for libxul (22.55 KB, patch)
2011-01-17 08:45 PST, Mike Hommey [:glandium]
no flags Details | Diff | Splinter Review
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list, v2 (10.42 KB, patch)
2011-02-24 05:07 PST, Mike Hommey [:glandium]
no flags Details | Diff | Splinter Review
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list, v2.1 (10.43 KB, patch)
2011-02-24 09:22 PST, Mike Hommey [:glandium]
ted: review+
Details | Diff | Splinter Review
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list. (11.87 KB, patch)
2012-01-16 09:19 PST, Mike Hommey [:glandium]
mh+mozilla: review+
Details | Diff | Splinter Review
Add an option to expandlibs-exec to allow to reorder the symbols when linking (35.15 KB, patch)
2012-02-29 08:58 PST, Mike Hommey [:glandium]
no flags Details | Diff | Splinter Review
Add an option to expandlibs-exec to allow to reorder the symbols when linking (35.57 KB, patch)
2012-03-05 05:15 PST, Mike Hommey [:glandium]
khuey: review+
Details | Diff | Splinter Review
Avoid Identical Code Folding messing with symbol reordering (15.48 KB, patch)
2012-03-06 05:28 PST, Mike Hommey [:glandium]
no flags Details | Diff | Splinter Review
Avoid Identical Code Folding messing with symbol reordering (15.55 KB, patch)
2012-03-06 05:42 PST, Mike Hommey [:glandium]
khuey: review+
Details | Diff | Splinter Review

Description Mike Hommey [:glandium] 2010-10-11 09:34:49 PDT
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] 2010-10-18 09:18:46 PDT
Created attachment 483995 [details] [diff] [review]
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] 2010-10-18 10:48:37 PDT
Try server builds will be available here:
http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/mh@glandium.org-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] 2010-10-19 02:32:48 PDT
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] 2010-11-29 01:25:01 PST
Created attachment 493646 [details] [diff] [review]
WIP patch

New version against new patches from bug 584474. The reorder list still needs to be tweaked, though.
Comment 5 Mike Hommey [:glandium] 2010-12-07 10:57:52 PST
Created attachment 495889 [details] [diff] [review]
WIP patch v3

Same as the previous one, but with a better profile after bug 616262.
Comment 6 Robert Kaiser 2011-01-04 15:23:43 PST
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] 2011-01-04 23:34:51 PST
(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) (afk until 26th July) 2011-01-05 00:42:51 PST
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 Ted Mielczarek [:ted.mielczarek] 2011-01-05 05:09:36 PST
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] 2011-01-17 08:45:08 PST
Created attachment 504488 [details] [diff] [review]
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] 2011-01-17 08:45:57 PST
Created attachment 504490 [details] [diff] [review]
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 Ted Mielczarek [:ted.mielczarek] 2011-02-11 10:13:55 PST
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] 2011-02-24 05:07:55 PST
Created attachment 514767 [details] [diff] [review]
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] 2011-02-24 09:22:11 PST
Created attachment 514815 [details] [diff] [review]
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list, v2.1

There were missing parens.
Comment 15 Ted Mielczarek [:ted.mielczarek] 2011-02-25 05:36:41 PST
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] 2012-01-16 09:19:53 PST
Created attachment 588912 [details] [diff] [review]
part 1 - Add an option to expandlibs-exec to allow to reorder the objects list.

Refreshed against current trunk.
Comment 17 Mike Hommey [:glandium] 2012-01-16 09:21:18 PST
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] 2012-01-20 00:56:28 PST
Landed part 1
https://hg.mozilla.org/integration/mozilla-inbound/rev/283408b8d8a3
Comment 19 Ed Morley [:emorley] 2012-01-21 07:06:50 PST
https://hg.mozilla.org/mozilla-central/rev/283408b8d8a3

Leaving open for part 2.
Comment 20 Mike Hommey [:glandium] 2012-02-29 08:52:39 PST
It turns out reordering objects doesn't have so much benefit. Reordering symbols does.
Comment 21 Mike Hommey [:glandium] 2012-02-29 08:58:53 PST
Created attachment 601632 [details] [diff] [review]
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] 2012-03-05 05:15:26 PST
Created attachment 602854 [details] [diff] [review]
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] 2012-03-06 05:28:41 PST
Created attachment 603240 [details] [diff] [review]
Avoid Identical Code Folding messing with symbol reordering
Comment 24 Mike Hommey [:glandium] 2012-03-06 05:42:15 PST
Created attachment 603241 [details] [diff] [review]
Avoid Identical Code Folding messing with symbol reordering

Small testcase change.
Comment 25 Kyle Huey [:khuey] (khuey@mozilla.com) 2012-03-07 09:23:53 PST
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 27 Mike Hommey [:glandium] 2012-03-08 00:17:02 PST
Fixup:
https://hg.mozilla.org/integration/mozilla-inbound/rev/59148c7434aa

Note You need to log in before you can comment on or make changes to this bug.