DiskOnChip write performance

David Woodhouse dwmw2 at infradead.org
Fri Sep 7 04:08:47 EDT 2001

ollie at sis.com.tw said:
> > Don't forget "don't use O(n^3) algorithms when trying to find a new
> > block to write to".

> What does this suppose to mean ?? 

Algorithms which take time proportional to the cube of 'n', where n is some 
variable indicating the complexity of the task - in this case it would be 
the number of blocks on the DiskOnChip which are to be considered for 

In fact, I don't think there's anything quite as stupid as O(n^3) in there, 
but it _is_ extremely naïve in places and needs a rethink of some of the 
data structures to allow some operations to operate in linear time, and to 
improve the wear levelling. The wear levelling at the moment is nonexistent 
- we always pick the longest chain, and if you have a one-block chain which 
never gets rewritten, NFTL will never cycle the block it's in.

> 	Did you "threaded" NFTL code yet ?? Or we still get locked when NFTL
> is syncing/flushing ?? 

I've put the necessary locking into the doc2000 driver. We can call it 
concurrently now. But haven't threaded NFTL to take advantage of it.

The core of the current NFTL code has just sort of evolved from my initial
hacks to see if I could get it to understand a DiskOnChip, and then to see
if I could write to it without confusing the DOS drivers. And it hasn't
evolved far. Ideally, it wants to be completely rewritten.


More information about the linux-mtd mailing list