FlashVM: Revisiting the Virtual Memory Hierarchy

Interesting paper about shortcomings of Linux VM subsystem when applied to NAND Flash storage:

Flash memory is the largest change to storage in recent history. Most research to date has focused on integrating flash as persistent storage in file systems, with little emphasis on virtual memory paging. However, the VM architecture in most of the commodity operating systems is heavily customized for using disks through software layering, request clustering, and prefetching.

We revisit the VM hierarchy in light of flash memory and identify mechanisms that inhibit utilizing its full potential. We find that software latencies for a page fault could be as high as the time taken to read a page from flash, and that swap systems are overly tuned towards the characteristics of disks.

Dull combinatorial explosion

One of my lessons from pocking around Plan 9 is "cleverness matters".

Compare Unix execv* functions (note the absense of execlpe and execvpe):

int execve(const char *filename, char *const argv[], char *const envp[]);
int execl(const char *path, const char *arg, ...);
int execlp(const char *file, const char *arg, ...);
int execle(const char *path, const char *arg, ..., char * const envp[]);
int execv(const char *path, char *const argv[]);
int execvp(const char *file, char *const argv[]);

and their counterpart in Plan 9:

void* exec(char *name, char* argv[])
void* execl(char *name, ...)

Combinatorial explosion was prevented by introducing overlay directories which completely eliminated concept of directory lists like PATH, and another clever trick of turning environment variables which are separate concept in Unix into ordinary filesystem in Plan 9.

Further, changing or extending language as done in Limbo would lead to the single exec function.

Another lesson (sad one) from Plan 9 is that cleverness not automatically marketable.

GNU Toolchain: Link-time optimization

I always wanted it: a big new feature has been added to gcc: Link-Time Optimization.

In a nutshell:

$ gcc -flto -O2 -c hello.c
$ gcc -flto -O2 -c world.c
$ gcc -flto -O2 -o hw hello.o world.o
$

will not only optimize code inside single object file, but also between compilation units.

Additionally -fwhole-program could be used to enable even more agressive optimization by hinting compiler that no symbols need to be exported from binary and hence anything except main could be inlined or completely removed.

Replugging the Modern Desktop

Presentation of David Zeuthen (author of HAL and DeviceKit) on Plumbers 2009 «Replugging the Modern Desktop», discussing history and current state of affairs in bringing Linux to current world of notebooks and hotplug devices.

Slides

Linkers internals

Ian Lance Taylor, author of gold (alternative GNU linker), wrote a list of articles about the linkers' internals: [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]. Yes, 20 articles.

Unladen Swallow: fast CPython

Unladen Swallow is a CPython patchset developed by Google people, aimed at improving performance of interpreter and slated for submission back to CPython once stable enough.

Latest release (milestone 2009Q2) has a JIT-compiler implemented on top of LLVM. Some performance improvements were achieved though the large-scale optimizations are scheduled for Q3.

There are quite interesting documents coming with the project (I should admit all Google-originated free software projects provide such non-trivial design documents :):

• Project plan


• Relevant papers (lot of links to studies in optimization of dynamic languages)

The quite important observation which can be inferred from reading the project plan is that CPython (and probably many similar ad-hoc VMs) does not benefit from the paramount of scientific knowledge accumulated to-date, including works studying optimization techniques applicable "as is".

PDF Evolution and Compatibility

James C. King wrote a paper about the PDF evolution and attempts to make it compatible for a 15 years:

The challenge has been, with each new version, to add features to the PDF language while
at the same time preserving the ability of newer software to process old files and older
software to process new files to whatever extent possible. Of course, older and newer are
defined in terms of having PDF version numbers increasing over time.

• James' blog post


• Paper (pdf)