OpenOffice.org startup and relocation processing

Summary

OpenOffice.org(OO.o) startup is unreasonably slow under Linux, while on Win32 it is reasonably fast. This paper argues that much of the fault of this is down to compiler & tool chain decisions, outside the scope of OO.o. Furthermore since all other large C++ projects suffer from the same problems – fixing these issues has to be a priority for Linux/C++ to be a performant option for developers of large-scale software projects.

Some potential improvements are suggested.

Discussion

OO.o startup is notoriously slow, however – this problem is not isolated to OO.o – all existing, large C++ projects under Linux have had to do substantial work to accelerate startup often by various devious, and unpleasant means. These range in approach, 'kdeinit' doing things quite differently to Firefox . Pre-linking is another approach that is suggested – however, this is expensive in CPU time, and ineffective for dlopen'd libraries . Unfortunately none of these solve the general problem elegantly, making it necessary to come up with yet-another solution for the problems of OO.o performance.

For those unfamiliar with the problems of large C++ application startup, a brief perusal of Ulrich's canonical linking document can prove instructive. Ultimately everything comes down to named relocation processing, the name lookup process being inordinately expensive. Thus for OO.o startup we have (roughly):

link_cost = O( R + r*n*log(s) )

R: relative relocations

r: (uniquely) named relocations

n: shared library (dso) count - ~150

s: total symbol entry count: 2x105

The dominant term being r*n*log(s). Given a uniform distribution of relocations through a given piece of code – it would seem that one can simply partition the code into a large number of smaller libraries, to ensure that only the code necessary for startup is relocated. Thus by (perhaps) doubling n for normal-use halve r and n(startup). However, this would not reduce the total number of relocations for common use & would thus tend to make real-use (such as document load on startup) twice as slow. In addition it would introduce a number of reloc cache/memory/disk access performance issues. Furthermore, OO.o is a cross-platform product already composed of many small component libraries, making further splits somewhat difficult.

There are several common types of relocation. Since JUMP_SLOT relocations are already optimized and can be delayed via the PLT mechanism they have a small impact on startup time. Hereinafter I use 'named relocation' to refer to named relocations that cannot be deferred by this means.

Visibility markup

A first approach to reducing named relocations involves using the visibility attribute markup available in recent gcc builds. This has the effect of hiding many symbols internally, enabling any relocations to be un-named & hence very rapid the effect of this is initially encouraging.

library:	no markup	visibility markup	Reduction
libsvx	23707	9866	58%
libsw	19889	3726	81%
libvcl	3122	2304	26%

So – clearly while there is potentially a 2-fold improvement with visibility markup, we are still left with a large number of relocations to process during startup. Worse – none of this improvement is 'real' since the visibility markup was introduced in response to gcc C++ ABI changes that stopped us using simpler & more complete symbol hiding for many components. ie. if you 'feel' OO.o 1.x is slow, adding visibility markup only (almost) brings us back to that performance datum before the C++ compiler changed.

Of course visibility markup does substantially reduce the number of symbols that are exported, which yields a useful reduction in the overall code size.

Reducing Interposing

The interposing feature of the Elf linker which allows any symbol to be clobbered at runtime, by another library ensures that a large number of relocations that could potentially be locally resolved at link time have to be delayed until startup. This can be overcome for C programs by the use of the -Bsymbolic linker flag. However, the C++ language relies heavily on Vague Linkage such that many names cannot be resolved internally – since they must resolve to a single value across the application. In gcc-3.x these symbols are tagged 'weak', and thus with a further tweak to the linker's -Bsymbolic support we could trivially get another reduction of named relocations:

library:	visibility markup	visibility & internal binding	combined reduction
libsvx	9866	4735	52%
libsw	3726	3060	18%
libvcl	2304	706	70%

Unfortunately – new COMDAT support in gcc/binutils, which will help improve space efficiency, removes the 'weak' tag from these symbols – making this simple approach unusable in the longer term. Another alternative here is link scripts – but these are unattractive from both maintenance and portability angles. Having an export attribute denoting internal binding, that could be applied to virtual methods might give a similar win and hook trivially into the existing source visibility markup.

Analysis of named relocations

A quick analysis of the distribution of relocations confirms what is perhaps intuitively obvious – that the vast majority are to fixup C++ vtables . Taking a build with no symbol reduction in place, and using a small perl script (relocstat ) it is possible to crudely identify how the named relocations break down:

ie. it is clear that the overwhelming majority of named relocations are used in vtable construction.

Analysis of inheritance & overriding

Again using relocstat it is possible to examine how vtables are used, particularly the average size of vtable, number of overridden methods per class, and how many slots are to external names.

Here – the external column clearly confirms vcl's position at the bottom of the C++ stack, and shows why internal -Bsymbolic binding gives such a saving in this library. The balance of inherited vs. overridden methods is interesting:

As expected inheriting functionality typically involves overriding fewer than half of the methods.

A similar intuitive datum is that of all the vtables; not a single slot was overridden by an implementation method external to the implementing library.

Thus the cost of adding a virtual method to a public base class, is proportional to the number of libraries in which it is used. Thus feasibly, in a hierarchy based on a FooObject - used in every library; adding 1 virtual method to FooObject incurs a startup penalty of upper bound O(n^2) where n is the shlib count.

Potential new approaches

With the introduction of visibility markup support into the compiler -we have an extra heuristic with which to optimize. We can be confident with certain options that eg. symbols with 'hidden' visibility are implemented internally, but more interestingly that 'default' symbols are implemented internally, but used externally and for un-marked symbols the reverse is true. This could be made substantially more explicit with the use of both 'import' and 'export' markup.

This extra information makes possible a range of further optimizations, by ensuring we can distinguish & optimize for the internal vs. external symbol cases.

Relocations via signal handler

By sorting relocations by address, and marking .data pages initially unreadable, we could perform relocations idly from a signal handler. While this appears attractive initially – with an average vtable size of ~160 bytes , with ~35 relocations per vtable, we would need to relocate ~25 vtables per page. OO.o would on average have only ~50 pages of vtables anyway. Doing this would also substantially hurt the single-element lookup cache, by distributing the same lookups across multiple pages; thus potentially decreasing overall startup performance.

Hooking (virtual) object construction

Clearly an object's vtable cannot be used until an instance of that object is constructed. That might allow vtables to be heap allocated, for OO.o that is a small win, as it's a singleton process – and vtable descriptions while sharable would still need to be loaded. Vtable objects account for ~70% of the objects in the .data segment; and ~1Mb on OO.o startup .

Hooking the constructor also removes any potential problem with method pointers, since the vtable can be constructed by the time it can be used.

Populating the vtable with stubs

The PLT approach of delaying name lookup would appear to lend itself well to vtables – inasmuch that we already have our vtable function pointers in unshared/writable pages. A similar Virtual function Lookup Table (VLT) behavior may have some advantages; however there are a few complexities beyond those of the PLT.

PLT entries are called from inside the library referencing them, hence the got pointer can be used to find and fixup the local PLT. However – a vtable slot may have been populated by a method in an arbitrary library, hence it's not possible to re-use the existing PLT entries (necessary for each virtual method to be called externally).

A VLT entry per virtual method

PLT slots & stubs are shared between callers; however each vtable relocation is in a discrete location, needing a separate fixup. There are ~20k vtable relocs in libsvx, a VLT entry of 12bytes each might consume 240k giving a 3% overall stripped library size increase. One advantage of having a VLT entry per method is that virtual method pointer comparsions could be let unaffected if the slot always pointed at the VLT entry – however, this would have an unpleasant performance impact. A variant of this method has been prototyped by objprelink2 , giving a substantial speedup.

Relocated PLT entries

The objprelink2 approach is to insert relocations pointing into the PLT into vtables, but to then re-write the PLT entries (with corresponding relocations) to not require a frame pointer. This doubles the relocation count associated with each vtable slot, and adds overhead to every virtual method. It also means that these re-written PLT entries cannot be shared between processes, increasing the per-process cost.

Virtual invocation ABI change

With a minor change to virtual function invocation, it would be possible to drastically reduce the number of VLT entries. By ensuring that the address of the vtable slot is available in a known register on virtual method call, (ie. as an extra implicit register argument) it should be possible to efficiently manipulate that slot (or the entire class vtable) via that pointer and the implicit 'this' pointer. This would entail some efficiency loss, since the register containing this information would have to be kept live, past the vtable slot load .

With this approach – it would be necessary to continue to have a relocation per vtable slot, however it would be an unnamed relocation to the (hidden) fixup trampoline for that class.

A reliable vtable offset register could have many uses in OO.o – potentially removing the need for run-time constructed trampoline code for UNO vtable construction (necessary for bridging to other languages)

As a variation of that, requiring no register, if the vtable slot load / call could be made consistent across all invocations – it may be possible for the fixup routine to fixup the whole class vtable, then simply adjust the return address from the call, to re-execute the previous (load slot/call) instruction(s).

Per-slot offset VLT entries

Instead of generating a VLT entry per relocation, it may be possible to generate 1 VLT entry per slot offset. ie. the number of VLT entries would be equal to the maximum slot size of any vtable in that DSO. The fixup method would of course use the this pointer, from which the correct vtable pointer could be easily deduced; to be fixed up via the per-VLT slot index.

Objections ...

When ld.so relocates a shared library linked with the -zcombreloc multiple relocations driven by the same symbol are placed adjacently. This allows the use of a simple cache that can detect this scenario and do the relocation without a duplicate lookup. Doing idle / individual fixup would make this optimization harder if not impossible. It is however likely that the vast majority of these duplicate relocations are due to a shared / common base class, in which case - the ability to hook the class initialization process should mean that many of these can be eliminated by a further optimization.

Reducing relocations by copying

It was noted earlier, that as expected vtable slots are almost never populated by methods outside the library. Furthermore, even with visibility markup – a large number of virtual methods are inherited from parents external to the library. Hence – it should be possible with fewer relocations to force relocation of a parent's vtable, and simply copy the entries over. This would stop the rather unfortunate case whereby the same (seldom-overridden) methods are relocated repeatedly across multiple libraries; and ensure that we perform a given named method relocation only once.

Other optimizations

Relocations to lookup base class vtables could be special cased for the purpose of populating the vtables, and (potentially) since we know repeated lookup is the common use case, and the set is fairly small (~a few thousand) – the dynamic linker could keep a separate hash to accelerate that lookup.

As an aside, it is interesting that there are 44k relocations to '__pure_virtual' across the OO.o source code, adding ~350k to the binaries; if the function of that is merely alter the failure condition for mis-implemented code, it seems a lot of space.

ABI issues:

Neither approach is without ABI issues, at best some extensions are clearly necessary. Reserving a common register is only marginally backwards compatible wrt. calling old C++ code from new code. However adding hooks to virtual object constructors would seem to be relatively benign, although clearly either some extra source annotation , or a common __vtable_init function that could detect the presence of an already-fixed-up vtable and not work on it. Of course, all new code would have to check if a given vtable needed initializing, in in-line constructors. Adding a new VLT slot per method would be yet more compatible, although bulky.

So – hooking the constructor or adding VLT approaches appear most ABI compatible, giving a typical speed/size tradeoff: the VLT approach would trade higher load time / larger memory use vs. the virtual object constructor hook – taking extra time to load/compare/branch to setup the vtable if necessary.

In addition – a new set of meta-data to describe vtables, wrt. which slots may be copied from which parent vtables (and at what offset), which are internally relocated, which have an associated symbol indices would need to be created, and manipulated by both compiler, linker and run-time.

The potential win:

Clearly then it is possible to very substantially reduce relocations as a source of performance problems linking C++. With a combination of internal binding of virtual functions (relying on new 'export' visibility markup), the copying of (internally bound) parent vtable slots where appropriate, and of course the performing relocations idly as necessary it should be possible to dramatically reduce not only startup relocations, but complete C++ vtable relocation processing to almost zero. This would give a 75% saving on overall relocation processing at startup. ~750ms for OO.o.

Conclusion

Relocating C++ vtables contribute heavily to the startup time of all large C++ applications using shared libraries. The existing performance situation is highly sub-optimal, improving it should be a priority. Doing so will inevitably require changes to gcc, binutils and ld.so, and alter the C++ ABI once again. However – doing this will chop ~1 second off the warm-start time of OO.o, and substantially improve both Mozilla and KDE startup performance, enabling the removal of their various performance related hacks.

Michael Meeks 2005/07/25

There is a stub process 'kdeinit' which links to and relocate most major libraries. Applications are compiled as shared libraries, so to execute an app first kdeinit forks, then dlopens the application code-library, then executes it. Presumably kdeinit is executed with LD_BIND_NOW set appropriately. cf. http://www.suse.de/~bastian/Export/linking.txt

Linking as much as possible statically into a single binary

OO.o dlopens the majority of it's libraries – even many commonly installed libraries due to dependency & ABI stability concerns.

How To Write Shared Libraries: http://people.redhat.com/drepper/dsohowto.pdf

http://gcc.gnu.org/onlinedocs/gcc-3.3/gcc/Vague-Linkage.html

A tiny / 10 line prototype – http://go-oo.org/~michael/symbolic-prototype.diff

An interesting comparison is with the C based GObject vtable setup, that demand instantiates & locally populates vtables, copying & then extending / overriding the parent's vtable. This of course requires manual effort, but results in an extremely named relocation-lean result.

http://go-oo.org/ooo-build/bin/relocstat

Why this was not called __export – cf. the equivalent Win32 name is unclear to me

libsvx on IA32, 4k pages assumes

relocstat –data-profile `cat pagein-writer pagein-common` with no visibility markup yields ~700k – and this is a sub-set of the startup libraries.

IA32, unlike a PLT entry a VLT entry would be called a maximum of 1 times, hence alignment is not important.

Léon Bottou & John Ryland, Faster C++ program startups, http://objprelink.sourceforge.net/#objprelink2

clearly it would be necessary to force vtable population for assignment of a method pointer – and hence for method pointers no further address/location would need to be tracked. Having said that – if it could be tracked – we could delay the fixup until invocation & use the vtable slot address rather than the function pointer itself for comparisons for equality.

From a rather uninformed analysis of some chunks of IA32 assembler – it seems there is little effort put into pushing the vtable slot load well back from the call, to hide cache latency, and frequent use of call *(%eax) constructs.

To disable calling a vtable fixup method for in-line constructors of old-style virtual classes

Michael Meeks

2005-07-25T12:31:45