Content of the patch:
 - removed code duplication between bytearray/string/unicode
 - new header "stringlib/split.h" with common methods:
    stringlib_split/_rsplit/_splitlines
 - added "maxcount" argument to "stringlib_count"
 - better performance for split/replace unicode methods

Benchmark coming soon...

The "split.h" file is missing from your patch.

You're right. Oups.

The patch looks wrong for bytearrays. They are mutable, so you shouldn't return the original object as an optimization. Here is the current (unpatched) behaviour:

>>> a = bytearray(b"abc")
>>> b, = a.split()
>>> b is a
False

On the other hand, you aren't doing this optimization at all in the general case of stringlib_split() and stringlib_rsplit(), while it could be done.

Mutable methods split() splitlines() and partition() fixed.
And added optimization for all immutables methods.

added "Makefile.pre.in".

There's some reference leaking somewhere...
Will investigate.

~ $ ./python Lib/test/regrtest.py -R 2:3: test_unicode
test_unicode leaked [7, 7, 7] references, sum=21

Refleak fixed in PyUnicode_Splitlines.

A few comments on coding style:

 * please keep the existing argument formats as they are, e.g.

    count = countstring(self_s, self_len,
                        from_s, from_len,
                        0, self_len, FORWARD, maxcount);

   or

  /* helper macro to fixup start/end slice values */
  -#define FIX_START_END(obj)                      \
  -    if (start < 0)                              \
  -        start += (obj)->length;                 \
  -    if (start < 0)                              \
  -        start = 0;                              \
  -    if (end > (obj)->length)                    \
  -        end = (obj)->length;                    \
  -    if (end < 0)                                \
  -        end += (obj)->length;                   \
  -    if (end < 0)                                \
  -        end = 0;
  +#define ADJUST_INDICES(start, end, len)                         \
  +    if (end > len) end = len;                                   \
  +    else if (end < 0) { end += len; if (end < 0) end = 0; }     \
  +    if (start < 0) { start += len; if (start < 0) start = 0; }



   and use similar formatting for the replacement function
   calls/macros

 * make sure that the name of a symbol matches the value, e.g.

   #define LONG_BITMASK (LONG_BIT-1)
   #define BLOOM(mask, ch) ((mask & (1 << ((ch) & LONG_BITMASK))))

   LONG_BITMASK has a value of 0x1f (31) - that's a single byte, not
   a long value. In this case, 0x1f is an implementation detail of
   the simplified Bloom filter used for set membership tests in the
   Unicode implementation.

   When adjusting the value to be platform dependent, please check
   that the implementation does work for platforms that have
   more than 31 bits available for (signed) longs.

   Note that you don't need to expose that value separately if
   you stick to using BLOOM() directly.

 * use BLOOM() macro in fastsearch.c

 * when declaring variables with initial values, keep these on separate lines, e.g. don't use this style:

    Py_ssize_t i, j, count=0;
    PyObject *list = PyList_New(PREALLOC_SIZE(maxcount)), *sub;

   instead, write:

    Py_ssize_t i, j;
    Py_ssize_t count=0;
    PyObject *list = PyList_New(PREALLOC_SIZE(maxcount))
    PyObject *sub;

 * always place variable declarations at the top of a function, not into the function body:

  +stringlib_split(
  +    PyObject* str_obj, const STRINGLIB_CHAR* str, Py_ssize_t str_len,
  +    const STRINGLIB_CHAR* sep, Py_ssize_t sep_len, Py_ssize_t  maxcount
  +    )
  +{
  +    if (sep_len == 0) {
  +        PyErr_SetString(PyExc_ValueError, "empty separator");
  +        return NULL;
  +    }
  +    else if (sep_len == 1)
  +        return stringlib_split_char(str_obj, str, str_len, sep[0],   maxcount);
  +
  +    Py_ssize_t i, j, pos, count=0;
  +    PyObject *list = PyList_New(PREALLOC_SIZE(maxcount)), *sub;
  +    if (list == NULL)
  +        return NULL;
   
 * function declarations should not put parameters on new lines:

  +stringlib_splitlines(
  +    PyObject* str_obj, const STRINGLIB_CHAR* str, Py_ssize_t str_len,
  +    int keepends
  +    )
  +{

 instead use this style:

  -static
  -PyObject *rsplit_substring(PyUnicodeObject *self,
  -                           PyObject *list,
  -                           PyUnicodeObject *substring,
  -                           Py_ssize_t maxcount)
  -{

> A few comments on coding style:

Thank you for your remarks. I will update the patch accordingly.

> * make sure that the name of a symbol matches the value, e.g.
>
>   #define LONG_BITMASK (LONG_BIT-1)
>   #define BLOOM(mask, ch) ((mask & (1 << ((ch) & LONG_BITMASK))))
>
>   LONG_BITMASK has a value of 0x1f (31) - that's a single byte, not
>   a long value. In this case, 0x1f is an implementation detail of
>   the simplified Bloom filter used for set membership tests in the
>   Unicode implementation.
>
>   When adjusting the value to be platform dependent, please check
>   that the implementation does work for platforms that have
>   more than 31 bits available for (signed) longs.
>
>   Note that you don't need to expose that value separately if
>   you stick to using BLOOM() directly.

Since the same value is used to build the mask, I assume it's better to keep the value around (or use (LONG_BIT-1) directly?).
    mask |= (1 << (ptr[i] & LONG_BITMASK));

s/LONG_BITMASK/BLOOM_BITMASK/ is not confusing?

> * function declarations should not put parameters on new lines:
>
>  +stringlib_splitlines(
>  +    PyObject* str_obj, const STRINGLIB_CHAR* str, Py_ssize_t str_len,
>  +    int keepends
>  +    )
>  +{

I copied the style of "stringlib/partition.h" for this part.
Should I update style of "partition.h" too?

> I copied the style of "stringlib/partition.h" for this part.
> Should I update style of "partition.h" too?

No, it's ok for stringlib to have its own consistent style and there's no reason to change it IMO.

More interesting would be benchmark results showing how much this improves the various methods :-)

Patch updated:
 * coding style
 * added macros BLOOM_ADD to unicodeobject.c and fastsearch.h
   (and removed LONG_BITMASK)

And now, the figures.

There's no gain for the string methods.
Some unicode methods are faster: split/rsplit/replace:


Most significant results:

--- bench_slow.log  Trunk
+++ bench_fast.log  Patched

 string unicode
 (ms)   (ms)    comment

 ========== late match, 100 characters
-13.30  20.51   s="ABC"*33; ("E"+s+("D"+s)*500).rsplit("E"+s, 1) (*100)
-16.12  29.88   s="ABC"*33; ((s+"D")*500+s+"E").split(s+"E", 1) (*100)
+13.27  14.38   s="ABC"*33; ("E"+s+("D"+s)*500).rsplit("E"+s, 1) (*100)
+16.19  17.61   s="ABC"*33; ((s+"D")*500+s+"E").split(s+"E", 1) (*100)

 ========== quick replace multiple character match
-4.51   159.78  ("A" + ("Z"*128*1024)).replace("AZZ", "BBZZ", 1) (*100)
+3.67   7.30    ("A" + ("Z"*128*1024)).replace("AZZ", "BBZZ", 1) (*100)

 ========== quick replace single character match
-3.73   50.61   ("A" + ("Z"*128*1024)).replace("A", "BB", 1) (*100)
+3.72   7.18    ("A" + ("Z"*128*1024)).replace("A", "BB", 1) (*100)

(full benchmark diff is attached)

And we save 1000 lines of code cumulated
(stringobject.c/unicodeobject.c/bytearrayobject.c)

I don't think you should remove such blocks:

-/*
-  Local variables:
-  c-basic-offset: 4
-  indent-tabs-mode: nil
-  End:
-*/

There probably are people relying on them :-)

Florent Xicluna wrote:
> > 
> > Florent Xicluna <laxyf@yahoo.fr> added the comment:
> > 
>> >> * function declarations should not put parameters on new lines:
>> >>
>> >>  +stringlib_splitlines(
>> >>  +    PyObject* str_obj, const STRINGLIB_CHAR* str, Py_ssize_t str_len,
>> >>  +    int keepends
>> >>  +    )
>> >>  +{
> > 
> > I copied the style of "stringlib/partition.h" for this part.
> > Should I update style of "partition.h" too?

I'd prefer if you change the coding style to what we use elsewhere
in Python C code.

See http://www.python.org/dev/peps/pep-0007/ for more C coding
style suggestions.

I think we should use whatever style is currently being used in the code. If we want to go back through this code (or any other code) and PEP7-ify it, that should be a separate task.

Alternately, we could PEP7-ify it first, then apply these changes.

Eric Smith wrote:
> > 
> > Eric Smith <eric@trueblade.com> added the comment:
> > 
> > I think we should use whatever style is currently being used in the code. If we want to go back through this code (or any other code) and PEP7-ify it, that should be a separate task.
> > 
> > Alternately, we could PEP7-ify it first, then apply these changes.

For any new files added, PEP 7 should always be used.

For PEP7-ifying the existing code, we could open a separate ticket or just apply the change as separate patch.

Fixed a problem with the splitlines optimization: use PyList_Append instead of PyList_SET_ITEM because there's no preallocated list
in this case.

The test case for the previous issue.

This looks generally good. Can you produce a separate patch for py3k? stringobject.c has been replaced with bytesobject.c there.

Slight update:
 * Objects/unicodeobject.c
   - moved STRINGLIB_ISLINEBREAK to unicodedefs.h
   - removed FROM_UNICODE: use STRINGLIB_IS_UNICODE instead
 * Objects/stringlib/find.h
   - use STRINGLIB_WANT_CONTAINS_OBJ in find.h
     (similar to current py3k impl.)

And the Py3k patch.

(note: previous update v4b -> v4c minimize the differences
       between Py2 and Py3 implementations)

Committed in r77461 (trunk), r77462 (py3k). Thank you very much!