Messages in this thread | | | Date | Wed, 16 May 2012 13:29:46 +0200 | From | Richard Weinberger <> | Subject | Re: [RFC v4] UBI: Fastmap support (aka checkpointing) |
| |
On 16.05.2012 13:18, Artem Bityutskiy wrote: > On Wed, 2012-05-16 at 14:09 +0300, Artem Bityutskiy wrote: >>> The maximum size of a fastmap is limited to UBI_FM_MAX_BLOCKS. >>> As I said, in worst case we'd have to scan 192 PEBs, which is a constant. >> >> In this case you cannot use O notation at all because it is just used >> when talking about asymptotic things. > > OK, we are talking about different things. It is fine that you need to > scan 192 eraseblocks, this is kind of your journal. And this part may be > O(1). But there is another part as well.
Yeah, seems to.
> But as I already explained, you have a _table_ on the flash, and this > table stores Erase Counter and LEB number for (roughly) each PEB. The > more PEBs, the large is the table, linerarly. > > As I explained, you have to _read_ and _interpret_ each record in this > table when attaching. And the more of these records you have, the longer > it takes to attach. And this is where you have your O(N).
Okay, now I understand your point. :)
> So basically fastmap makes UBI's linerar dependency multiplier a lot > smaller, so it is still a great improvement.
Yep.
Thanks, //richard
| |