June 12th, 2005

bioqdisksort()

I refactored FreeBSD's disksort on the plane ride back from Israel. The old one had provisions for ordered transactions which you couldn't sort in the queue. We ripped out the top level support some time ago but never simplified the elevator algorithm. The patch is here. Now it's basically a simple hinted insertion sort. Unfortunately, most devices now have deep queues and software sorting is often ineffective although it can have a huge impact on performance. This is most notably a problem with FreeBSD's scsi layer which often takes advantage of 256 entry deep controller queues.

Many years ago I implemented a real-time disk queueing mechanism for Midstream. It was essentially a time bounded disk sort. I also had IO prioritization, which is more difficult than it may first seem. I was thinking about reintroducing these diffs to help improve background fsck performance. I'm sad that FreeBSD fell behind the disk scheduling curve. Years ago the anticipatory disk scheduling research as well as the opportunistic scheduling (free block scheduling) was all done on FreeBSD, but we never integrated it. The linux developers were quick to adopt it, however, and saw some gains. Hopefully we can play catch up now.