What is Prelinking?
Prelinking is a process that allows you to speed up the process of dynamic linking. What it does is, through a process of magic that is incredibly complex, but basically it speeds up the relocation process, in loading shared libraries.. by setting preferred load addresses.

What is he talking about, you ask? Well, here's how it goes. Dynamically linked libraries (often referred to as DSO's or in the windows world DLLs) are libraries which are loaded at runtime. The advantage of shared libraries versus static libraries is, that it reduces the size of executables, since each program doesn't need its libraries built in, but will dynamically locate and use it at run time. This adds some overhead, because the address space of the library, instead of being known in advance, has to be mapped at runtime. Another advantage of shared libraries is that due to the magic of copy-on-write, you can save memory when you have multiple programs sharing the same library (though it's not as simple as that.. it is pretty complicated)

Pre-linking sets preferred address space for the libraries to be loaded at. Note they are _preferred_ spaces, and if that address space is not available, then it will use relocation to load it dynamically.. hence pre-linking is not 100% foolproof.

What do I need to prelink?
To prelink, you need at least:
- glibc 2.3.1 or greater
- libelf or elfutils 0.7, though 0.8 is preferred. Latest version as of this writing is 0.84
- Your shared libraries have to be compiled with -fPIC
- the prelink program from ftp://people.redhat.com/jakub/prelink

Okay, so now how do I do it?
First, you need to set up a prelink.conf . This file tells prelink where to search for shared libraries and where to search for apps to prelink if you decide to use the -a feature to prelink everything.

 # /etc/prelink.conf
 -l /bin
 -l /sbin
 -l /usr/bin
 -l /usr/sbin
 -l /lib
 -l /usr/lib
 -h /usr/local/lib
 -h /usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.1
 -h /usr/lib/mozilla
 -h /usr/X11R6/lib

# prelink /path/to/executable

# prelink --undo /path/to/executable

I wanna see numbers! Does it really help?
Well, the results with prelinking is mixed. I haven't seen any tests where prelinking hurt execution speed, but while some people get spectacular improvements, some people get only minimal improvements. I've combined data from my tests on mozilla and konqueror, along with Jekub Jelinek's tests on konqueror, to see how much elf prelinking really helps.

In my tests with prelinking, I have been unable to get any sort of results with it. However, it may work better for you. I guess, the only thing to do is try it. The process is reversible at least. It won't work on just any system though, all the libraries have to be compiled with -fPIC and you need a recent glibc. A recently compiled gentoo will work with prelink enabled, you will have to kludge with other distros.

To prelink or not to prelink?
Prelink theoretically can cause large performance boosts. It avoids a lot of calls to mmap that have to be done in the dynamic linking process. On some systems and with very large programs that load a lot of shared libraries, prelinking in tests has shown speed increases in load time. Keep in note, however, that prelinking only really helps the load time of your applications, for the most part actual runtime speed is not affected.

also note that, in order for prelink to be useful, you need to have all your libraries compiled with fPIC, and be running glibc 2.3.1 or higher. I don't know if this is the case for the major distributions, aside from Gentoo which does support prelinking if you have a recently compiled gentoo setup.

The final word: if you have all the requirements to prelink, and really want to get that speed bost, it's worth a try. else, wait and see if it catches on enough that your distribution will begin prelinking executables for you.

Sources:
- GlibC 2.3 paper: changes in the new GlibC http://people.redhat.com/drepper/lt2002talk.pdf
- Gentoo Linux Prelink Guide http://www.gentoo.org/doc/en/prelink-howto.xml