lkml.org 
[lkml]   [2017]   [Sep]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH V2] tipc: Use bsearch library function
    From
    Date
    On 09/16/2017 05:26 PM, Joe Perches wrote:
    > On Sat, 2017-09-16 at 17:02 +0800, Ying Xue wrote:
    >> On 09/16/2017 03:50 PM, Thomas Meyer wrote:
    >>> Use common library function rather than explicitly coding
    >>> some variant of it yourself.
    >>>
    >>> Signed-off-by: Thomas Meyer <thomas@m3y3r.de>
    >>
    >> Acked-by: Ying Xue <ying.xue@windriver.com>
    >
    > Are you sure you want to do this?
    >
    > Note the comment above nameseq_find_subseq
    >
    > * Very time-critical, so binary searches through sub-sequence array.
    >
    > What impact does this change have on performance?

    Sorry, I couldn't see any essential difference between this new
    implementation and the original one except that the former tries to use
    the library function - bsearch() to replace the original binary search
    algorithm implemented in TIPC itself. Therefore, I don't think the
    change will have a big impact on performance.

    If I miss something, please let me know.

    Thanks,
    Ying

    >
    >>> diff --git a/net/tipc/name_table.c b/net/tipc/name_table.c
    >>> index bd0aac87b41a..eeb4d7a13de2 100644
    >>> --- a/net/tipc/name_table.c
    >>> +++ b/net/tipc/name_table.c
    >>> @@ -44,6 +44,7 @@
    >>> #include "addr.h"
    >>> #include "node.h"
    >>> #include <net/genetlink.h>
    >>> +#include <linux/bsearch.h>
    >>>
    >>> #define TIPC_NAMETBL_SIZE 1024 /* must be a power of 2 */
    >>>
    >>> @@ -168,6 +169,18 @@ static struct name_seq *tipc_nameseq_create(u32 type, struct hlist_head *seq_hea
    >>> return nseq;
    >>> }
    >>>
    >>> +static int nameseq_find_subseq_cmp(const void *key, const void *elt)
    >>> +{
    >>> + struct sub_seq *sseq = (struct sub_seq *)elt;
    >>> + u32 instance = *(u32 *)key;
    >>> +
    >>> + if (instance < sseq->lower)
    >>> + return -1;
    >>> + else if (instance > sseq->upper)
    >>> + return 1;
    >>> + return 0;
    >>> +}
    >>> +
    >>> /**
    >>> * nameseq_find_subseq - find sub-sequence (if any) matching a name instance
    >>> *
    >>> @@ -176,21 +189,8 @@ static struct name_seq *tipc_nameseq_create(u32 type, struct hlist_head *seq_hea
    >>> static struct sub_seq *nameseq_find_subseq(struct name_seq *nseq,
    >>> u32 instance)
    >>> {
    >>> - struct sub_seq *sseqs = nseq->sseqs;
    >>> - int low = 0;
    >>> - int high = nseq->first_free - 1;
    >>> - int mid;
    >>> -
    >>> - while (low <= high) {
    >>> - mid = (low + high) / 2;
    >>> - if (instance < sseqs[mid].lower)
    >>> - high = mid - 1;
    >>> - else if (instance > sseqs[mid].upper)
    >>> - low = mid + 1;
    >>> - else
    >>> - return &sseqs[mid];
    >>> - }
    >>> - return NULL;
    >>> + return bsearch(&instance, nseq->sseqs, nseq->first_free,
    >>> + sizeof(struct sub_seq), nameseq_find_subseq_cmp);
    >>> }
    >>>
    >>> /**
    >>>
    >

    \
     
     \ /
      Last update: 2017-09-16 11:39    [W:2.989 / U:0.356 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site