[Python-checkins] r46230 - python/trunk/Objects/stringobject.c

[Neal Norwitz]

See my previous comments on this code in unicodeobject.c.  In
particular, count needs to be a Py_ssize_t.  If you've already fixed,
sorry, I'm trying to catch up on mail. :-(

n
--

On 5/25/06, fredrik.lundh <python-checkins at python.org> wrote:
> Author: fredrik.lundh
> Date: Thu May 25 19:55:31 2006
> New Revision: 46230
>
> Modified:
>    python/trunk/Objects/stringobject.c
> Log:
> needforspeed: use "fastsearch" for count.  this results in a 3x speedup
> for the related stringbench tests.
>
>
>
> Modified: python/trunk/Objects/stringobject.c
> ==============================================================================
> --- python/trunk/Objects/stringobject.c (original)
> +++ python/trunk/Objects/stringobject.c Thu May 25 19:55:31 2006
> @@ -5,6 +5,18 @@
>
>  #include <ctype.h>
>
> +#undef USE_INLINE /* XXX - set via configure? */
> +
> +#if defined(_MSC_VER) /* this is taken from _sre.c */
> +#pragma warning(disable: 4710)
> +/* fastest possible local call under MSVC */
> +#define LOCAL(type) static __inline type __fastcall
> +#elif defined(USE_INLINE)
> +#define LOCAL(type) static inline type
> +#else
> +#define LOCAL(type) static type
> +#endif
> +
>  #ifdef COUNT_ALLOCS
>  int null_strings, one_strings;
>  #endif
> @@ -763,6 +775,108 @@
>         return 0;
>  }
>
> +/* -------------------------------------------------------------------- */
> +/* Helpers */
> +
> +#define USE_FAST /* experimental fast search implementation */
> +
> +/* XXX - this code is copied from unicodeobject.c.  we really should
> +   refactor the core implementations (see _sre.c for how this can be
> +   done), but that'll have to wait -- fredrik */
> +
> +/* fast search/count implementation, based on a mix between boyer-
> +   moore and horspool, with a few more bells and whistles on the top.
> +   for some more background, see: http://effbot.org/stringlib */
> +
> +/* note: fastsearch may access s[n], which isn't a problem when using
> +   Python's ordinary string types, but may cause problems if you're
> +   using this code in other contexts.  also, the count mode returns -1
> +   if there cannot possible be a match in the target string, and 0 if
> +   it has actually checked for matches, but didn't find any.  callers
> +   beware! */
> +
> +#define FAST_COUNT 0
> +#define FAST_SEARCH 1
> +
> +LOCAL(Py_ssize_t)
> +       fastsearch(const unsigned char* s, Py_ssize_t n, const unsigned char* p,
> +                  Py_ssize_t m, int mode)
> +{
> +       long mask;
> +       int skip, count = 0;
> +       Py_ssize_t i, j, mlast, w;
> +
> +       w = n - m;
> +
> +       if (w < 0)
> +               return -1;
> +
> +       /* look for special cases */
> +       if (m <= 1) {
> +               if (m <= 0)
> +                       return -1;
> +               /* use special case for 1-character strings */
> +               if (mode == FAST_COUNT) {
> +                       for (i = 0; i < n; i++)
> +                               if (s[i] == p[0])
> +                                       count++;
> +                       return count;
> +               } else {
> +                       for (i = 0; i < n; i++)
> +                               if (s[i] == p[0])
> +                                       return i;
> +               }
> +               return -1;
> +       }
> +
> +       mlast = m - 1;
> +
> +       /* create compressed boyer-moore delta 1 table */
> +       skip = mlast - 1;
> +       /* process pattern[:-1] */
> +       for (mask = i = 0; i < mlast; i++) {
> +               mask |= (1 << (p[i] & 0x1F));
> +               if (p[i] == p[mlast])
> +                       skip = mlast - i - 1;
> +       }
> +       /* process pattern[-1] outside the loop */
> +       mask |= (1 << (p[mlast] & 0x1F));
> +
> +       for (i = 0; i <= w; i++) {
> +               /* note: using mlast in the skip path slows things down on x86 */
> +               if (s[i+m-1] == p[m-1]) {
> +                       /* candidate match */
> +                       for (j = 0; j < mlast; j++)
> +                               if (s[i+j] != p[j])
> +                                       break;
> +                       if (j == mlast) {
> +                               /* got a match! */
> +                               if (mode != FAST_COUNT)
> +                                       return i;
> +                               count++;
> +                               i = i + mlast;
> +                               continue;
> +                       }
> +                       /* miss: check if next character is part of pattern */
> +                       if (!(mask & (1 << (s[i+m] & 0x1F))))
> +                               i = i + m;
> +                       else {
> +                               i = i + skip;
> +                               continue;
> +                       }
> +               } else {
> +                       /* skip: check if next character is part of pattern */
> +                       if (!(mask & (1 << (s[i+m] & 0x1F))))
> +                               i = i + m;
> +               }
> +       }
> +
> +       if (mode != FAST_COUNT)
> +               return -1;
> +       return count;
> +}
> +
> +/* -------------------------------------------------------------------- */
>  /* Methods */
>
>  static int
> @@ -2177,7 +2291,7 @@
>  static PyObject *
>  string_count(PyStringObject *self, PyObject *args)
>  {
> -       const char *s = PyString_AS_STRING(self), *sub, *t;
> +       const char *s = PyString_AS_STRING(self), *sub;
>         Py_ssize_t len = PyString_GET_SIZE(self), n;
>         Py_ssize_t i = 0, last = PY_SSIZE_T_MAX;
>         Py_ssize_t m, r;
> @@ -2210,8 +2324,14 @@
>         if (n == 0)
>                 return PyInt_FromSsize_t(m-i);
>
> +#ifdef USE_FAST
> +       r = fastsearch(s + i, last - i, sub, n, FAST_COUNT);
> +       if (r < 0)
> +               r = 0; /* no match */
> +#else
>         r = 0;
>         while (i < m) {
> +               const char *t
>                 if (!memcmp(s+i, sub, n)) {
>                         r++;
>                         i += n;
> @@ -2225,6 +2345,7 @@
>                         break;
>                 i = t - s;
>         }
> +#endif
>         return PyInt_FromSsize_t(r);
>  }
>
> _______________________________________________
> Python-checkins mailing list
> Python-checkins at python.org
> http://mail.python.org/mailman/listinfo/python-checkins
>