UBI fastmap used PEB search

[richard -rw- weinberger]

Hi!

On Wed, May 1, 2013 at 7:18 PM, Brian Pomerantz <bapper at gmail.com> wrote:
> I have been doing some profiling on why it takes UBI attach longer as UBI volumes fill up.  I found that the majority of time takes place in fastmap.c during the search of the used PEB list when matching for the volume's LEBs.  Specifically, I saw that the inner loop "list_for_each_entry(tmp_aeb, &used, u.list)" gets hit a LOT.  The time it takes to search this list can be reduced if the attached patch is used, all it does is put a break in the loop when the pnum is matched.  This seems so obvious I figure there must be a reason it isn't done this way and I'm just missing it, is the patch valid or will it cause issues?  I'm also wondering if anyone has tried building the used list as a RB tree instead to further reduce the time spent spinning through the list.

Nice catch!

Yeah, the break makes sense. I simply forgot it.
As pnum has to be unique we can stop processing after the found a matching pnum.
Do you have some numbers how much your fix improves the overall performance?

The current fastmap implementation is more or less a prove of concept
implementation,
I'm sure there is potential to gain more performance.
Patches are very welcome!

Thanks,
//richard

P.s: Can you please re-submit your patch in the proper "Linux kernel" format?
See: Documentation/SubmittingPatches
tl;dr: use scripts/checkpatch.pl and git send-email