There you have it: fast, asynchronously-loaded waveforms for pitivi. It turns out it was useful to get thumbnails working first. Essentially the waveform is stored as a series of thumbails, and nearly the same drawing code is used to draw the waveform segment as to draw the thumbnails. The waveform segments are drawn into cairo surfaces directly from the sample data, which is fetched using a gstreamer segment seek.
Right now this branch is based off pitivi 0.11 so this could make it into the next minor release. Adding it to the current master branch will require a bit of refactoring. I might also be able to speed up rendering of waveforms a bit, which would mean that the previews will take less time to appear.
As for the cache, I haven't yet decided what scheme I want to use yet. I think LRU or MFU would be good enough, but it's possible that direct mapping would work as well and be much more efficient.
An interesting issue
I have been experiencing choppy audio within pitivi. What's interesting to note is that when you zoom in far enough, the audio waveform has gaps in it. And these visual gaps in the waveform seem to roughly co-incide with the auditory ones.