Re: DBE table ordering

["Gleb O. Raiko" <raiko@niisi.msk.ru>]

Keith Owens wrote:
> 
> On Thu, 18 Apr 2002 13:37:14 +0400,
> "Gleb O. Raiko" <raiko@niisi.msk.ru> wrote:
> >If you really hate this behaviour and want to change it, I guess just
> >linear serach is OK.
> 
> Performance matters for these tables.  It is worth doing one sort at
> boot time to let the kernel run faster all the time.  For some tables
> (ia64 unwind) the API mandates that the table be in ascending order.
> 

No, performance doesn't matter here. First, we are speaking about DBE
exception which slowdowns performance. Second, get/put_dbe are used for
peripherial accesses which are slow anyway. Third, do you really want to
speed up probe routines where those macros are used? I guess, not.

Then, how many addresses you have in your dbe_table, 1000 or 6 ? I guess
the latter. In the worst case, linear search requires 12 comparisons,
while binary search takes 6. 6 extra comparisons is nothing in the dbe
handler. If you have more than 6 addresses in the table, just replace
macros by routines and get exactly 6. And 6 comparisons, btw, there is
no need for loop, just 6 if-statements.

I dont't know about other tables and other arches. Perhaps, they need
sorting of some tables. But, definetely, sorting isn't required for mips
dbe/unaligned access tables.

Regards,
Gleb.