# Is anyone clever enough to reinvent Ben's Method for improving disk performance? **URL:** \ **Category:** Miscellaneous and Personal Stuff I Must Share\ **Created:** [August 8, 2018, 11:25am UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265 "2018-08-08T11:25:48Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 8, 2018, 11:25am UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/1 "2018-08-08T11:25:48Z")
In the late 1980’s I came across a fun idea in the domain of disk storage design for computers. I’ll call it “Ben’s Method” because Ben was the inventor’s name. (Yes, it is a Method, not an Apparatus.) I thought “Aha!” when I first heard of the invention and wondered what leading questions I’d ask to guide a fellow computer buff to the joy of re-invention. To lay some context, I was myself an inventor, with dozens of U.S. patents (not even counting continuations-in-part). Though none of my patents were in the fields of disk storage or file system design, I had considerable experience therewith. But road led onto road, and zig to zag, and here I am thirty years later, with the Method almost forgotten, wondering if any computer buff wants to enjoy the thrill of invention discovery. It would seem like a shame that this simple but “cute” method pass away completely unremembered. _ **But humor me please.** _ When I heard of the invention, my reaction was “Could I have thought of that? What hints would someone need for that solution to pop into their mind?” If nobody takes up the challenge, fine — I’ll just let Ben’s Method pass into oblivion. If you can detect that a large sequential file is gradually being read, aggregate performance may improve if you do “_pre-caching_” — if you speculatively read blocks from that large file that you expect to be requested since. Doing this when the disk is otherwise idle is trivial; a challenge arises when you must prioritize the pre-caching with other requests. I’ll post yes/no answers if there’s interest in asking questions, but briefly: **Ben’s Method was used in conjunction with _pre-caching_ to improve net disk performance while simplifying firmware.** (You don’t need to be a disk expert to grasp the Method — many computer nerds will know enough.) AFAIK, Ben’s method was never implemented, never patented, never published, and is not generally known today. But I still wonder if, after all, the idea might have merit. (If you should apply the idea, please give credit to Ben!) Maybe the idea is flawed, but it’s still a nifty idea! And especially pleasing because of its utter simplicity. I posed this puzzle several months ago in the “53 bicycles: A lateral thinking puzzle” thread, but little progress was made. An SDMB disk expert answered > [@53 bicycles: A lateral thinking puzzle](https://boards.straightdope.com/t/53-bicycles-a-lateral-thinking-puzzle/790868/2469): > > Speaking as someone who’s done disk drive firmware for the past twenty years, you got me curious. There have been so many tricks like this, it would probably boggle your mind. > > It looks like pre-caching was the one you were aiming for but that’s been implemented many, many times, especially in streaming applications. Heck, I’ve implemented it myself 20 years ago. (As someone who was doing disk drive firmware forty years ago, I’d like to hear about some other mind-boggling methods! Post them in this thread if you wish. But **RadioWave** ’s response only confirms that Ben’s Method is unknown.) Hint: From one perspective, Ben’s Method is quite simple; so simple that some puzzlers might become disgruntled (“Is _that_ all there is?”) It is that simplicity that makes the invention seem elegant to me. Anyone want to challenge themselves? Ask a series of yes-no questions that will lead to a rediscovery of Ben’s clever invention. ---
**Author:** ![Heracles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/heracles/32/487_2.png) [@Heracles](https://boards.straightdope.com/u/Heracles)\ **Post date:** [August 8, 2018, 6:16pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/2 "2018-08-08T18:16:47Z")
All right, is it a scheme for choosing the physical layout of consecutive blocks of a file? For instance, staggering them on the track (or cylinder) so that they’ll pass the read head exactly when the controller is ready for them? ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 8, 2018, 7:19pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/3 "2018-08-08T19:19:22Z")
> [@Heracles](#): > > All right, is it a scheme for choosing the physical layout of consecutive blocks of a file? For instance, staggering them on the track (or cylinder) so that they’ll pass the read head exactly when the controller is ready for them? Yes! Though not that of you ‘for instance.’ ---
**Author:** ![markn\_1](https://avatars.discourse-cdn.com/v4/letter/m/f9ae1b/32.png) [@markn\_1](https://boards.straightdope.com/u/markn_1)\ **Post date:** [August 8, 2018, 7:25pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/4 "2018-08-08T19:25:12Z")
I’ve done a lot of work on disk drivers and file systems, so I’ll be interested to hear what Ben’s method is. I don’t have time to play the guessing game though. I once implemented a driver that used SSTF (Shortest Seek Time First) rather than the more common elevator algorithm. It was quite tricky because to be useful you have to know the _actual_ time it will take to read a block, given the current position of the head and the rotational position of the platters. It’s not good enough to just estimate it based on the delta between the last block number and the requested one. This requires making a mathematical model of the disk including the number of platters, the layout of blocks across the platters, the number of sectors in each cylinder in each disk zone, the rotational speed of the disk, the time required to move the heads across N cylinders (including accelerating and decelerating the heads), etc. It was quite involved, but very interesting work (and it did make a big improvement in disk throughput). ---
**Author:** ![markn\_1](https://avatars.discourse-cdn.com/v4/letter/m/f9ae1b/32.png) [@markn\_1](https://boards.straightdope.com/u/markn_1)\ **Post date:** [August 8, 2018, 7:43pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/5 "2018-08-08T19:43:49Z")
Oh, and all this had to be deduced by doing test reads of selected blocks and observing how long each read took. ---
**Author:** ![wguy123](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/wguy123/32/3161_2.png) [@wguy123](https://boards.straightdope.com/u/wguy123)\ **Post date:** [August 8, 2018, 7:52pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/6 "2018-08-08T19:52:16Z")
Does it work on SSDs or only spinning platters? ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 8, 2018, 8:12pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/7 "2018-08-08T20:12:01Z")
> [@markn\_1](#): > > I once implemented a driver that used SSTF (Shortest Seek Time First) rather than the more common elevator algorithm. It was quite tricky because …, the rotational speed of the disk, the time required to move the heads across N cylinders (including accelerating and decelerating the heads), etc. It was quite involved, but very interesting work (and it did make a big improvement in disk throughput). I’d thought of such things back in the 1980’s but rejected them as too complicated. Problems were generally more severe! 🆒 For example, one major manufacturer of servers had gross driver bugs, and bugs in the interface to the seek “elevator” that led to _huge_ performance degradation. _ **But it was precisely to avoid** _ (at least in one case) _ **the complexity of which you speak that Ben proposed his method.** _ > [@wguy123](#): > > Does it work on SSDs or only spinning platters? I doubt it will be helpful on SSD’s (unless they’re similar to spinning platters) but am too unfamiliar to be sure. It _might_ have been helpful on old CCD memories — are they still in use? ---
**Author:** ![markn\_1](https://avatars.discourse-cdn.com/v4/letter/m/f9ae1b/32.png) [@markn\_1](https://boards.straightdope.com/u/markn_1)\ **Post date:** [August 8, 2018, 8:17pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/8 "2018-08-08T20:17:27Z")
> [@wguy123](#): > > Does it work on SSDs or only spinning platters? If you’re replying to me, the SSTF algorithm (and for that matter, the common elevator algorithm) is only relevant on spinning disks. In SSDs there is essentially no location-dependent overhead between reads, so these techniques are moot. At the time I did this work, all mass storage was spinning disks; SSDs did not exist yet. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 8, 2018, 8:38pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/9 "2018-08-08T20:38:12Z")
> [@markn\_1](#): > > … At the time I did this work, all mass storage was spinning disks; SSDs did not exist yet. [Circa 1980 one company offered a high-speed big-box CCD replacement for disk and drum memories.](https://books.google.co.th/books?id=xO3lFEMUpVoC&pg=PA12&lpg=PA12&dq=STC+ccd+memory&source=bl&ots=j_VnA63kJL&sig=3IZ5n1keLsDosaQw0hyoV0ZaA4Y&hl=en&sa=X&ved=2ahUKEwiYh6H9pt7cAhXaeisKHfxgBN4Q6AEwAnoECAgQAQ#v=onepage&q=STC%20ccd%20memory&f=false)\* (Perhaps they sold very few of these boxes.) Does your work predate that? - - I visited STC HQ circa 1980 in connection with their 4305, though I don’t remember details — it was some possible partnership between them and the company I was consulting for. . ---
**Author:** ![Musicat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/musicat/32/20189_2.png) [@Musicat](https://boards.straightdope.com/u/Musicat)\ **Post date:** [August 8, 2018, 8:59pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/10 "2018-08-08T20:59:17Z")
I can’t think of any way you could read a disk faster than a single pass per track with sequential data, with the next data at a different platter of the same cylinder (repeat as needed) and next-next data at an adjacent cylinder. This would require an interleave of 0, so there would be one read pass per revolution per platter surface. This can be done with a fast enough CPU and appropriate interface software. The only way to speed this up would be to increase the rotation speed, increase the number of heads that can be read simultaneously, or use a read-ahead buffer. If you are using a read-ahead RAM buffer, you need to take into account the time elapsed from the start of the entire read, or you are cheating to make the read speed look good. Or maybe Ben’s plan was compressed data storage? ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 8, 2018, 9:48pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/11 "2018-08-08T21:48:38Z")
> [@Musicat](#): > > I can’t think of any way you could read a disk faster than a single pass per track with sequential data, Suppose you have two discrete read requests pending on distant cylinders. You finish one read but you’ve somehow monitored activity enough to suspect that a read of neighboring data may be likely in the near future. Do you read the speculative data, or part thereof, while you’re on that track, saving that data in a buffer? (_Possibly thereby saving a future seek altogether._) Or do you hurry off to fulfill the existing request on a different cylinder? With **markn+**'s method above _you can calculate how much time you have_ until you need to initiate the seek, and get some speculative reads in “for free.” But in addition to the complexities **markn+** mentions, you’ll have a slight quandary if a third unrelated request arrives while doing those speculative reads. Ben’s method avoids these complexities. ---
**Author:** ![Heracles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/heracles/32/487_2.png) [@Heracles](https://boards.straightdope.com/u/Heracles)\ **Post date:** [August 8, 2018, 10:04pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/12 "2018-08-08T22:04:25Z")
The cache manager could give the firmware a wish list of sectors (or sector sequences) that it would like to read ahead. When the disk is busy, the firmware can return the sectors in question when the head happens to be on the right cylinder; when the disk becomes idle, it can seek and process whatever remains on the wish list. ---
**Author:** ![Melbourne](https://avatars.discourse-cdn.com/v4/letter/m/b5e925/32.png) [@Melbourne](https://boards.straightdope.com/u/Melbourne)\ **Post date:** [August 8, 2018, 10:11pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/13 "2018-08-08T22:11:24Z")
> [@markn\_1](#): > > If you’re replying to me, the SSTF algorithm (and for that matter, the common elevator algorithm) is only relevant on spinning disks. In SSDs there is essentially no location-dependent overhead between reads, so these techniques are moot. At the time I did this work, all mass storage was spinning disks; SSDs did not exist yet. SSDs are made of blocks (Like tracks. Like RAM.). You set up the block address, wait, then read the block. Which is why the random access speed of SSDs is not the same as the sequential access speed. This is hidden because the integrated (ss) disk controller maps the actual disk sector address, but of course not totally hidden, because you can observe different random access and sequential access speeds. (Then you normally read the block sequentially, so that’s like reading a sector.: it happens at bus speed, which is slower than memory speed, which is slower than cache speed) ---
**Author:** ![markn\_1](https://avatars.discourse-cdn.com/v4/letter/m/f9ae1b/32.png) [@markn\_1](https://boards.straightdope.com/u/markn_1)\ **Post date:** [August 8, 2018, 11:24pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/14 "2018-08-08T23:24:57Z")
@Melbourne, I haven’t worked with SSDs per se, but I’ve worked a lot with raw Flash (mostly NAND but some NOR; I designed a really cool filesystem for a NOR Flash system that I’m rather proud of). In the Flash controllers I’ve used, you set up the address and then read a whole block, as you say. Are you saying that in an SSD, after doing one block read, some blocks will be faster than others when you make the next request? That would be surprising to me based on my experience with Flash, but if it is true, then indeed there could be benefit in a nontrivial scheduling algorithm. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 9, 2018, 8:27pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/15 "2018-08-09T20:27:54Z")
Don’t give up! The idea of Ben’s Method can be expressed in one simple sentence. In may not be a _good_ idea—after all, it’s never been implemented AFAIK, nor published, nor patented—but it does have a distinct “niftiness”! > [@Heracles](#): > > All right, is it a scheme for choosing the physical layout of consecutive blocks of a file? Yes!! But you’ll need another sentence, or at least 2 or 3 key words, to Win the Brass Ring! Again, here’s the problem Ben wanted to solve: > [@septimus](#): > > Suppose you have two discrete read requests pending on distant cylinders. You finish one read but you’ve somehow monitored activity enough to suspect that a read of neighboring data may be likely in the near future. > > Do you read the speculative data, or part thereof, while you’re on that track, saving that data in a buffer? (_Possibly thereby saving a future seek altogether._) Or do you hurry off to fulfill the existing request on a different cylinder [itself possibly just a chunk of another large file being read sequentially] ? > > With **markn+**'s [complex] method above _you can calculate how much time you have_ until you need to initiate the seek, and get some speculative reads in “for free.”… > > _ **Ben’s method avoids those complexities.** _ ---
**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\ **Post date:** [August 9, 2018, 10:16pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/16 "2018-08-09T22:16:30Z")
Is this somehow a Free Lunch effect, that will only improve performance, or does it improve average performance under certain assumptions that might not always hold? The example of alternating between two long reads with a possible third read request that might come in while you’re busy optimizing those first two makes me think it has to be the latter. If so, what are the assumptions? ---
**Author:** ![Quartz](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/quartz/32/267_2.png) [@Quartz](https://boards.straightdope.com/u/Quartz)\ **Post date:** [August 9, 2018, 11:44pm UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/17 "2018-08-09T23:44:28Z")
Is it anything to do with interleaving sectors or staggering the sectors on cylinders? Because both were well known when I was doing my IT degree in the late 80s. ---
**Author:** ![Heracles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/heracles/32/487_2.png) [@Heracles](https://boards.straightdope.com/u/Heracles)\ **Post date:** [August 10, 2018, 4:32am UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/18 "2018-08-10T04:32:14Z")
You could stripe consecutive blocks of a file across different disk surfaces, but on the same sector. Block 1 of file A is at track 27, sector 33, disk surface 3. Block 2 of the same file is also at track 27, sector 33, but on disk surface 4, and so on. With an arrangement like this, if you have N heads, then up to N consecutive blocks are read in parallel by the controller, which can cache them if needed. The writing is a bit more complex than the usual scheme of filling each track serially. (Isn’t this approach commonly used, though?) ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 10, 2018, 5:10am UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/19 "2018-08-10T05:10:15Z")
> [@iamthewalrus\_3](#): > > Is this somehow a Free Lunch effect, that will only improve performance … under certain assumptions that might not always hold? > … If so, what are the assumptions? Perhaps. Maybe this is part of the reason Ben’s method wasn’t enthusiastically adopted. 🙂 To focus on the scenario for which Ben’s method may be optimal, imagine a disk kept busy concurrently reading two or more large sequential files (on different cylinders) in which the priorities are (1) to respond quickly to the actual system requests, which come in quantum chunks; and (2) to do anticipatory speculative reads without impacting priority (1). ~ ~ ~ ~ ~ ~ ~ > [@Quartz](#): > > Is it anything to do with interleaving sectors or staggering the sectors on cylinders? **Because both were well known** when I was doing my IT degree in the late 80s. > [@Heracles](#): > > **(Isn’t this approach commonly used, though?)** AFAIK Ben’s Method has never been implemented nor published. Comments in the thread only confirm this. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [August 10, 2018, 5:35am UTC](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265/20 "2018-08-10T05:35:41Z")
Ben’s method was proposed for use with a Unix operating system. Some versions of the Unix file system issue their own anticipatory reads of sequential files, unbeknownst to and independent of, any “smarts” the disk controller may be attempting. Anticipatory reads at the disk controller level may supplement OR replace those kernel “pre-fetches.” Ben’s method is implemented at the disk controller level and may interact (sometimes unfavorably?) with kernel-initiated anticipatory reads. > [@septimus](#): > > … to respond quickly to the actual system requests, which come in quantum chunks … “Quantum”? The applications issue read requests and then sleep until fulfillment. (Writes can be asynchronous or delayed, but not reads.) [Next page](https://boards.straightdope.com/t/is-anyone-clever-enough-to-reinvent-bens-method-for-improving-disk-performance/819265.md?page=2)