title: The behavior of string.split for short strings when maxsplit is supplied
body: <p>I recently ran across some intriguing behavior of the string.split method in python2.7, particularly with respect to short stings (less than around 25 chars, see below), that involves contrasting the behavior of:</p>
  
  <pre><code># Without maxplsit
  my_string.split('A')
  </code></pre>
  
  <p>to</p>
  
  <pre><code># With maxsplit=1
  my_string.split('A', 1)
  </code></pre>
  
  <p>The second method is actually slower for short strings, and I'm quite curious as to why.</p>
  
  <h2>The Test</h2>
  
  <p>This first came about from a small call to timeit that my co-worker discovered:</p>
  
  <pre><code># Without maxsplit
  $ python -m timeit -s "json_line='a|b|c'" "part_one='|'.split(json_line)[0]"
  1000000 loops, best of 3: 0.274 usec per loop
  # With maxsplit
  $ python -m timeit -s "json_line='a|b|c'" "part_one='|'.split(json_line,1)[0]"
  1000000 loops, best of 3: 0.461 usec per loop
  </code></pre>
  
  <p>I thought this was certainly curious, so I put together a more detailed test.  First I wrote the following small function that generates random strings of a specified length consisting of the first ten capital letters:</p>
  
  <pre><code>from random import choice
  
  # 'A' through 'J'
  choices = map(chr, range(65, 75))
  
  def make_random_string(length):
      return ''.join(choice(choices) for i in xrange(length))
  </code></pre>
  
  <p>Then I wrote a couple tester functions to repeatedly split and time randomly generated strings of a specified length:</p>
  
  <pre><code>from timeit import timeit
  
  def time_split_of_size(str_length, n_strs_to_split):
      times = []
      data = [make_random_string(str_length) for i in xrange(n_strs_to_split)]
      for s in data:
          t = timeit("'{s}'.split('A')".format(s=s),
                     setup="from __main__ import make_random_string",
                     number=1000)
          times.append(t)
      return times
  
  def time_split_of_size_with_maxcount(str_length, n_strs_to_split):
      times = []
      data = [make_random_string(str_length) for i in xrange(n_strs_to_split)]
      for s in data:
          t = timeit("'{s}'.split('A', 1)".format(s=s),
                     setup="from __main__ import make_random_string",
                     number=1000)
          times.append(t)
      return times
  </code></pre>
  
  <p>I then ran these testing methods over strings of varying sizes:</p>
  
  <pre><code>from collections import OrderedDict
  d = OrderedDict({})
  for str_length in xrange(10, 10*1000, 25):
      no_maxcount = mean(time_split_of_size(str_length, 20))
      with_maxcount = mean(time_split_of_size_with_maxcount(str_length, 20))
      d[str_length] = [no_maxcount, with_maxcount]
  </code></pre>
  
  <p>This gives you the behavior you would expect, O(1) for the method with maxsplit=1 and O(n) for splitting all the way.  Here's a plot of the time by the length of the string, the barely visible green curve is with <code>maxsplit=1</code> and the blue curve is without:</p>
  
  <p><img src="https://i.stack.imgur.com/p5ywq.png" alt="StringSplitTiming"></p>
  
  <p>None the less, the behavior my co-worker discovered for small stings is real.  Here's some code that times many splits of short stings:</p>
  
  <pre><code>from collections import OrderedDict
  d = OrderedDict({})
  for str_length in xrange(1, 50, 2):
      no_maxcount = mean(time_split_of_size(str_length, 500))
      with_maxcount = mean(time_split_of_size_with_maxcount(str_length, 500))
      d[str_length] = [no_maxcount, with_maxcount]
  </code></pre>
  
  <p>With the following results:</p>
  
  <p><img src="https://i.stack.imgur.com/5i0YL.png" alt="StringSplitShortString"></p>
  
  <p>It seems like there is some overhead for strings less than 25 or so characters in length.  The shape of the green curve is also quite curious, how it increases parallel to the blue before leveling off permenantly.</p>
  
  <p>I took a look at the source code, which you may find here:</p>
  
  <p><a href="https://github.com/certik/python-2.7/blob/master/Objects/stringobject.c" rel="nofollow noreferrer">stringobject.c</a> (line 1449)
  <a href="https://github.com/certik/python-2.7/blob/master/Objects/stringlib/split.h" rel="nofollow noreferrer">stringlib/split.h</a> (line 105)</p>
  
  <p>but nothing obvious jumped out at me.</p>
  
  <p>Any idea what is causing the overhead when maxsplit is passed for the short strings?  </p>