Updated Aug 20, 2007 by krzysztof.lichota
Labels:	Featured

Soc2007Progress

Progress of implementation of prefetching during Google Summer Of Code 2007

Introduction

This page will contain information about progress of implementation.

Timeline and progress

Coding period: implementation of tracing facility and integration with Ubuntu boot scripts, analysis of impact on boot time.

Open Office document to measure startup time (done) (see MeasuringOpenOfficeStartupTime)
Firefox script to measure startup time (cancelled)
Scripts to measure startup time (done)
Kernel I/O wait time metric (done, already in kernel as delay io stats)

evaluation of pagecache as tracing tool (done)
integration of tracing into boot scripts (done, see TestingBootPrefetching)
integration of prefetching into boot scripts (done, see TestingBootPrefetching)
Tracing based on pagecache (done)
Prefetching during application startup (done, see InitialPrefetchingImplementationResults)
Tests of impact of prefetching during application startup (done, see InitialPrefetchingImplementationResults)
Disk layout tool initial implementation (done, initial experimental implementation works)
Creating test suite for disk layout tool (done)
Measuring impact of changing disk layout (done, see InitialDiskReorderingResults)

September and later - writing a paper describing results of analysis for later submission to Linux conferences, improving things which were identified as problems during analysis of implemented solution.

State at coding deadline for Google Summer of Code (August 20, 2007):

Boot tracing and prefetching is well tested and ready for deployment.
Application tracing and prefetching works and is ready for deployment. Further tuning might improve its performance. Effect of disk reordering on application has not been measured, it should improve results also.
Disk reordering works, but is highly experimental, not ready for production use yet. Layout tool is quite well tested, test suite has been created. The problematic part is running it on reboot as unmounting root partition is hard to do. Current solution is to remount partition read-only, cache all necessary files in memory and change partition underneat. It somewhat works but is fragile. The following problems were identified in reordering implementation:

Copying necessary files into chroot takes long time (>20s).
Reordering files takes quite some time (~15s). Disk layout tool should be improved to allow fitting prefetch data into multiple free areas and disk access should be streamlined. Also it could check if files need reordering at all to save time.
Disk layout tool not always can find area to fit chunk of prefetch data into it. It should be smarter.

Conclusions:

Kernel with boot prefetching boots faster than standard Ubuntu kernel with readahead by 6.31s (54.91s vs 61.21s). Please note that readahead lists were not updated. See InitialBootPrefetchingResults page for details.
Prefetch adapts automatically to changing boot sequence - for boot with OpenOffice as part of boot sequence boot time is shorter by 15.48s (65.53s vs 81.01s).

Application prefetching gives some gain to disk-intensive applications like OpenOffice.
Performance of app prefetching is better than built-in OpenOffice prefetching by 1.67s.
Prefetching can cut down OpenOffice startup time (in comparison to no prefetching at all, i.e. disabled pagein) by 3.36s, from 14.38s to 11.01s. See InitialPrefetchingImplementationResults page for details.

Files reordering gives even shorter boot time, by 4.93s (47.75s vs 52.68). See InitialDiskReorderingResults page for details.
Impact on application startup or boot with OpenOffice was not measured, but it should help also.
Further work on reordering files on disk seems worth the effort.

Known bugs:

3-aggregation does not work currently for gui and system traces (it works for boot), apparently some bug was introduced in script which processes trace.

To do:

Clean up kernel patch for submission to Ubuntu kernel-team and upstream.
More tests (especially file contents tests) for disk layout tool.
Improving disk layout tool to find free space areas to fit data.
Improvements to reordering on boot (especially copying files).
Measure application startup time and boot time with OpenOffice with disk reordering.
Improve tracing as it seems to be missing accesses to some files.

Special thanks go to:

Tollef Fog Heen - for mentoring me during Summer of Code
Jan Kara - for giving guidance on kernel and filesystem issues
Fengguang Wu - for creating pagecache, whose tracing subsystem was adapted for prefetch needs
Behdad Esfahbod - for creating Preload daemon which inspired me to work on prefetch

Fully functional boot prefetching released for testing, for installation instructions see this page, for announcement see this mail to ubuntu-devel-discuss

Debian packages with initial implementation of boot prefetching are available, see this announcement

Bugs reported and come across during project implementation: