Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

#28 Speed improvements can be made by removing a lot of strcats

v2.4.0
closed-accepted
7
2007-12-20
2007-11-30
Chris Behrens
No

dkim_dstring_cat() can be made more efficient by replacing the use of 'sm_strlcat' with memcpy() as you already know:

1) The size of the old string, so you can memcpy directly onto the end
2) You know the size of the string being added (from a previous strlen() to figure out if you needed to grow the buffer)
3) And you also know that the buffer is large enough, because it was already expanded if needed

On very large strings where you are dkim_dstring_cat()ing something onto the end, this can be a decent performance improvement.

There are other cases throughout the libdkim code that can be made more efficient similarly:

in dkim_key_granok():

995 if (sm_strlcat(restr, "$", sizeof restr) >= sizeof restr)
996 return FALSE;

It looks like that can be converted into "*q = '$'" if 'q' is not pointing past the end of 'restr'.

1921 snprintf(tmp, sizeof tmp, ";%sbh=%s", delim,
1922 b64hash);
1923 sm_strlcat(tmphdr, tmp, sizeof tmphdr);

The return from 'snprintf' can be cached there and used to replace strlcat with a strlcpy.

Etc..

Discussion

    • assigned_to: nobody --> sm-msk
     
    • priority: 5 --> 7
     
  • Chris Behrens
    Chris Behrens
    2007-12-06

     
  • Chris Behrens
    Chris Behrens
    2007-12-06

    Logged In: YES
    user_id=627199
    Originator: YES

    I've attached a patch which does:

    1) Adds dkim_strtoul and dkim_strtoull which are optimized for base 10
    2) Adds 3 members to struct dkim_header:
    a) hdr_text_len == Full length of ->hdr_text
    b) hdr_name_len == Length of ->hdr_text header name (not including
    any spaces between end of header name and colon). Ie,
    "From : Foo" results in hdr_name_len = 4
    Also, if a colon is missing, hdr_name_len == hdr_text_len
    c) hdr_colon == Position of colon in hdr_text if it exists,
    otherwise NULL
    3) Added a 'name_len' argument to dkim_get_header
    4) Added DKIM_DATEHEADER like DKIM_FROMHEADER, etc, and changed
    occurance of "Date" to use it
    5) Added DKIM_FROMHEADER_LEN, DKIM_SIGNHEADER_LEN, DKIM_DATEHEADER_LEN
    etc so they could be used as constants instead of having to
    do strlen()s
    6) dkim_canon_header() modified to:
    a) buffer up data for passing to dkim_dstring_catn() instead of
    calling dkim_dstring_cat1() for every byte
    b) use 3 separate loops for RELAXED instead of 1 big loop with
    extra state checking... This also allows the call to
    dkim_lowerhdr() to be removed by doing the tolower() in
    the first loop. (3 loops are: before colon, spaces after
    colon, and then the remaining part of header)
    7) Made dkim_strdup() use memcpy instead of sm_strlcpy()
    8) Made dkim_dstring_copy() use memcpy instead of sm_strlcpy()
    9) Made dkim_dstring_cat() use memcpy instead of strlcat()
    10) Added dkim_dstring_catn() for use when you already know the
    length of the string you will be appending
    11) Made dkim_canon_runheaders() buffer data for passing to
    dkim_dstring_catn() instead of using dkim_dstring_cat1()

    All of the above cuts _verifying_ a signed+pass message in about 1/2, using
    gprof for reference. I've not attempted to optimize signing (yet) and
    I should look to see if there's further things that can be optimized for
    signed+failed (policy checking)

    The strtoul* change saved over 20%

    The changes for util routines to use memcpy(), the addition of dstring_catn
    and buffering of dkim_canon_header() saved about 15% total

    The change to split dkim_canon_header() into multiple loops for relaxed
    mode saved 10%

    The hdr_ changes saved the remaining 5%

    While I optimized the use of dkim_get_header(), it appears it isn't really
    used by the verifying routines...at least with my test message.

    File Added: perf-improvement.patch

     
  • Chris Behrens
    Chris Behrens
    2007-12-15

    Logged In: YES
    user_id=627199
    Originator: YES

    File Added: libdkim-perf-patches.tar

     
  • Chris Behrens
    Chris Behrens
    2007-12-15

    tar file of the patches individually

     
  • Logged In: YES
    user_id=1048957
    Originator: NO

    Massaging these into the 2.4.1 release which will begin a short beta series early next week. Thanks for splitting them up for me!

     
    • status: open --> closed-accepted
     
  • Logged In: YES
    user_id=1048957
    Originator: NO

    Your performance patches have been merged into the 2.4.1 release. Thank you!