[PATCH] UBI: fastmap convert used list to rb tree

[Brian Pomerantz]

On May 6, 2013, at 6:45 AM, richard -rw- weinberger <richard.weinberger at gmail.com> wrote:

> On Mon, May 6, 2013 at 2:47 AM, Brian Pomerantz <bapper at gmail.com> wrote:
>> After some profiling of the attach process, it was found that
>> a considerable amount of time was spent spinning through the list of
>> used PEBs in ubi_attach_fastmap().  This patch converts the list into
>> a RB tree saving considerable time when the volumes fill up.
>> 
>> Signed-off-by: Brian Pomerantz <bapper at gmail.com>
> 
> Nice!
> Looks good so far, but this week I'm on the road.
> As soon as I the have time to test it, I'll ack your patch.
> 
> Do you have some numbers?
> I'm interested in how much faster the rbtree is compared to list in this case...
> 

Using a Samsung 1GB NAND with 3958 PEBs and only 510 left available (nearly full), without the patch I get around a 300ms attach time and with the patch it is around 50ms attach time.  I made the same change in u-boot, our kernel image is stored in UBI along with a backup image, and saw the same speedup.  So I shaved off 500ms from my boot time with the two changes.  The attach time should be much more constant using the tree, not getting much longer as the volumes fill up.  There wasn't a noticeable difference in how long it took to fill the tree verses appending to a list, so with empty volumes there shouldn't be much overhead.


--Brian