Attendees at LinuxCon 2010 were lucky enough to have not just
one, but two presentations devoted to boot speed. The first
was "How We Made Ubuntu Faster", by
Upstart creator Scott James
Remnant; the other was
"Improving Android Boot-Up Time", by Tim Bird of Sony. As expected,
Scott's talk was centered around netbooks running Ubuntu, while Tim
focused on different development boards running Android. Nevertheless,
there were some commonalities between both projects.
No discussion of boot up speed would be complete without mentioning
the 5 second boot achieved by
Arjan de Ven and Auke Kok of
Intel's Open Source Technology Center.
In fact, a number of things from Scott's session assumed a knowledge
of that effort by Intel.
Good metrics are pivotal for improving boot time, and to get good
metrics one must standardize the variables. The hardest of these is
the machine, because everyone has different computers that have
various components that are slower or faster than others. The Ubuntu team
realized they would have to buy a whole bunch of "standard"
computers. They chose the Dell Inspiron mini 10 netbook, dubbed the
"touchpad from hell" by Scott because it was hard to
use without the pointer jumping around. The laptop as a whole has the
key requirement of being available in SSD and rotational media
configurations, and is cheap enough to keep the project under budget.
The next important piece is to have a goal in mind. They chose 10
seconds, by "doubling the numbers that Arjan came up
with". The kernel and initramfs get a total of two seconds. The
same is allocated for platform initialization such as init scrips. The
X server gets another two seconds, and the desktop environment, Gnome,
gets four. It turns out these numbers weren't accurate predictors in
the long run, but for some cases such as kernel, they were able to
beat their deadline.
In order to create an automated system to measure the changes over
time, the team threw together a pretty elaborate configuration where
the system would reinstall the latest nightly builds, and then profile
the resulting boot automatically. They compiled all the results and
put them on Scott's
One of the big portions of the Moblin kernel improvement was the early
use of asynchronous kernel threads. They improved boot time by
initializing the SATA controller, to handle
storage, at the same time as the USB host adapters. Canonical built upon on this work by moving
populate_rootfs(), the function responsible for unpacking the
initramfs, to yet another asynchronous thread.
Though Intel claimed a speed boost from statically compiling modules
into the kernel,
the Canonical team has to be able to support more than just Intel
netbooks. To achieve this, they cleaned up some of the slower parts of
the init script, such as a replacement of a 10 millisecond poll of the
blkid binary with an event based call to libudev. In the end the
team was able to surpass their 2 second target, even with the
requirement to use an initramfs.
Scott took some time here to plug Upstart. Though the Intel
ultimately settled on a hand tuned invocation of the old System V init
daemon to improve boot, Scott insisted that an event based system is
better than "thousands of lines of shell script". This is
even more true today because pretty much every system on the market
has more than one CPU.
The Gnome environment took a bit of time to
boot as well. Ubuntu uses Compiz by default, and this took almost half
of the time allocated for the desktop environment. The audience asked
if Compiz could be eliminated, but there are too many features of
Ubuntu that depend on its inclusion. Other large offenders were
gnome-panel and Nautilus. Altogether these components contributed to a
10 second Gnome start up, more than double their 4 second allotment.
Their research revealed that storage is the ultimate bottleneck.
"Hard drives suck, but SSDs suck too" was the specific
wording. To improve the situation, Scott used a well known tool called
readahead. Initially developed
at Red Hat, readahead is a tool that will log the filename for every
instance of open() and execve() for the first 60 seconds of
boot. Then on the next boot, a readahead process is spawned early that
pulls all files in the list into the page cache, ensuring it's just a
simple memory access when they're read later on.
Intel improved Red Hat's readahead with super-readahead, or
sreadahead. This does the same
thing, but was modified to only preload the blocks that will be read
in, instead of the entire file. Since it's assumed to be a MeeGo
system running on SSDs, and all SSDs have negligible seek time, the
order of blocks on disk is not taken into account. Using an SSD, the
Ubuntu system can read all blocks necessary for boot in 3 seconds.
However, Ubuntu has to run on rotating media as well, so yet another
iteration called über-readahead
was created by Scott. The daemon was modified so that it reads blocks
in order when using a rotating hard drive. The graph of this
optimization shows a few random metadata reads, followed by a smooth
linear path across the platter. For the rotational media, all pages
necessary can be read into page cache in fewer than 7 seconds. Scott
said that things can go even faster if the inital reads could be sorted and
done in order prior to performing readahead on the file contents. There
were a few file system patches sent to LKML,
but inclusion does not seem likely at this point.
Scott concluded the discussion by admitting they didn't achieve their
goal. The inability to reduce the desktop environment portion to fewer
than ten seconds precluded a sub-ten second overall boot. Note this is
on a Dell netbook, so the numbers will likely be better for systems
with beefier processors and I/O subsystems, which includes almost all
traditional laptops. In the presentation abstract, it is stated that some
boot Ubuntu in as few as 5 seconds. The good news is that the kernel
now takes fewer than 2 seconds to initialize, even with the initramfs
requirement. And Scott did a lot of useful work that can be used by
the larger community. Only time will tell if the other
distributions take advantage of his work.
Tim ran into a unique set of problems with Android handsets.
Whereas Scott's problems were already well known in the much wider
desktop Linux community, Tim is working with a suite of tools with
names like Dalvik and Zygote, whose source code has rarely been
modified outside of Google. As such, Tim's focus was about getting an
initial performance profile to find what part of the boot process will
yield the largest reduction in time, and in turn should get the most
He profiled three different platforms, the
from HTC, and an
EVM OMAP3 board
from Mistral Solutions. The overall time for these machines to boot
was 57, 36, and 62 seconds, respectively. Though these are all ostensibly
development machines, that number still seemed huge compared to the
netbook boot times, but it should be mentioned that these boards have
a much slower processor and storage. By the same token, you can do a
lot more with a fully functional Gnome desktop than a smart phone. Tim
pointed out that "it's really sad that you can use a stopwatch to
accurately measure a phone booting up".
The boot chart for the EVM board revealed a number of areas for
Android uses a rewritten Java-esque virtual machine called Dalvik in all
of its phones. For optimal user experience, all of the classes must
be preloaded before the phone is used. Zygote, the utility responsible
for doing this work, spends about 21 seconds in I/O wait. The application
don't have to be preloaded, one can choose to load them on
demand, but this is just pushing the problem back and causes longer
application load times. Worse, there is a memory penalty for each
class now has to be loaded in a different heap, so the memory for
identical classes can't be shared.
A potential solution is to figure out how to load every class into
Zygote's heap, so that you can have something akin to shared libraries
in a conventional OS. Another possible solution is to make Zygote
threaded, and have one thread use the CPU while the other is reading
from storage. A more far out possibility avoids reading in the classes
at all and loads the heap as a binary blob, though this would take
the most development effort and would require a rebuild when new
classes are installed.
The other potential speed gain lies in the package scanning tool. The
purpose of this tool wasn't exactly obvious to Tim, but he illustrated
its complexity by showing the call tree. At the end of it all
is the parseZipArchive() function, which is called 138 times. There
is some low hanging fruit there, for example Tim shaved off a few
seconds by commenting out a sanity check of the zip file headers.
Just above that is a ZipFileRO::open() call which will mmap() the
zip file into memory. The problem is that parseZipArchive() walks
the mmaped region and builds a hash table to make subsequent accesses
easier, causing page faults for the entire archive. All this is
done just to extract one file, AndroidManifest.xml, so the time and
memory spent to fault in all those pages and build the hash table is
There is an emerging consensus within the Android development
community that a lot of time can be shaved if readahead is used. But
Tim thought it was masking the underlying problem, and that some of
the blocks shouldn't be read at all, much less used to populate the page
cache. Scott, who was in the audience at this discussion, noted that
readahead isn't really about masking temporal locality of reference or
"papering over problems", but it is about using the CPU
while populating the page cache. Tim still felt that using readahead
would make the problems with the code less noticeable, and developers
wouldn't be as motivated to fix them. They both agreed when this ships
on a device to consumers, it should have readahead enabled.
Unfortunately there were no significant speed ups in boot time yet,
but there is still work to do. Interested readers are encouraged to
sign up for the Android
and check out the
Though Android and Dalvik are a departure from the traditional GNU
userspace that Ubuntu uses, they do have some commonalities. Firstly,
because the kernel is not impacted by user-space differences, kernel
improvements will be available for any and all Linux devices. Tim
didn't mention the kernel because there are already a lot of well
to boot the kernel faster, so
it was outside of the scope of his talk. Presumably, the techniques covered in the Ubuntu
presentation would also help the Android system boot more quickly.
Some improvements in user space carry over as well. Readahead is a
generic enough technique that it can be included in pretty much any
environment. Similarly, profiling techniques like bootchart and
ftrace can be run in both environments. However, generic GNU userspace
has the advantage of more code sharing and reuse than third party
environments like Android. Improvements to booting the X server, for
example, will be felt across Ubuntu, MeeGo, and the other desktop
Linuxes out there. That isn't the case for Android.
Even so, the developer community for Android is growing and Tim is
evidence of that. The problem of slow Android boots has probably not
been thought about much outside of Google's office walls, but that is
changing. The potential for improvement is there, especially
in Android-specific places like the package scanner and Zygote. For
desktop distributions and even specialized distributions like MeeGo,
the fast boot story may be largely coming to an end. For Android, it's
only just beginning.
[ Bootcharts, graph, and photo courtesy of Scott James Remnant of
Canonical and Tim Bird of Sony. ]
to post comments)