And I forgot to attach the relevant code (though it is also in my fork)...<br><br><div class="gmail_quote">On Sun, May 13, 2012 at 6:28 PM, Anthony Scopatz <span dir="ltr"><<a href="mailto:scopatz@gmail.com" target="_blank">scopatz@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello All, <div><br></div><div>This week, while doing some optimization, I found that np.fromstring()</div><div>is significantly slower than many alternatives out there.  This function</div>

<div>basically does two things: (1) it splits the string and (2) it converts the</div>

<div>data to the desired type.</div><div><br></div><div>There isn't much we can do about the conversion/casting so what I </div><div>mean is that the <b>string splitting implementation is slow</b>.  </div><div><br></div>



<div>To simplify the discussion, I will just talk about string to 1d float64 arrays.</div><div>I have also issued pull request #279 [1] to numpy with some sample code.</div><div>Timings can be seen in the ipython notebook here.</div>



<div><br></div><div>It turns out that using str.split() and np.array() are 20 - 35% faster, which </div><div>was non-intuitive to me.  That is to say:</div><div><span style="color:rgb(51,51,51);margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;border-top-width:0px;border-right-width:0px;border-bottom-width:0px;border-left-width:0px;border-style:initial;border-color:initial;font:inherit"><br>



</span></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px">rawdata = s.split()<br>data = np.array(rawdata, dtype=float)</blockquote><div><span style="color:rgb(51,51,51);margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;border-top-width:0px;border-right-width:0px;border-bottom-width:0px;border-left-width:0px;border-style:initial;border-color:initial;font:inherit"><br>



</span></div>is faster than<div><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px">data = np.fromstring(s, sep=" ", dtype=float)</blockquote><div><font color="#333333" face="'Bitstream Vera Sans Mono', 'Courier New', monospace"><span style="line-height:16px;white-space:pre-wrap"><br>



</span></font></div><div>The next thing to try, naturally, was Cython.  This did not change the </div><div>timings much for these two  strategies.  However, being in Cython </div><div>allows us to call atof() directly.  My implementation is based on a previous </div>



<div>thread on this topic [2].   However, in the example in [2], the string was </div><div>hard coded, contained only one data value, and did not need to be split.</div><div>Thus they saw a dramatic 10x speed boost.   To deal with the more </div>



<div>realistic case, I first just continued to use str.split().  This took 35 - 50%</div><div>less time than np.fromstring().</div><div><br></div><div>Finally, using the strtok() function in the C standard library to call atof() </div>



<div>while we tokenize the string further reduces the speed 50 - 60% of the </div><div>baseline np.fromstring() time.  </div><div><br></div><div>Timings</div><div>------------</div><div><div>In [1]: import fromstr        </div>



<div><br></div><div>In [2]: s = "100.0 " * 100000</div><div><br></div><div>In [3]: timeit fromstr.fromstring(s)</div><div>10 loops, best of 3: 20.7 ms per loop</div><div><br></div><div>In [4]: timeit fromstr.split_and_array(s)</div>



<div>100 loops, best of 3: 16.1 ms per loop</div><div><br></div><div>In [6]: timeit fromstr.split_atof(s)</div><div>100 loops, best of 3: 13.5 ms per loop</div><div><br></div><div>In [7]: timeit fromstr.token_atof(s)</div>



<div>100 loops, best of 3: 8.35 ms per loop</div></div><div><br></div><div><div>Possible Explanation</div><div>----------------------------------</div><div>Numpy's fromstring() function may be found here [3].  However, this code </div>



<div>is a bit hard to follow but it uses the array_from_text() function [4].  On the </div><div>other hand str.split() [5] uses a macro function SPLIT_ADD().   The difference</div><div>between these is that I believe that str.split() over-allocates the size of the</div>



</div><div>list in a more aggressive way than array_from_text().  This leads to fewer </div><div>resizes and thus fewer memory copies.</div><div><br></div><div>This would also explain why the tokenize implementation is the fastest since </div>



<div>this pre-allocates the maximum possible array size and then slices it down. </div><div>No resizes are present in this function, though it requires more memory up </div><div>front.</div><div><br></div><div>Summary (tl;dr)</div>



<div>------------------------</div><div>The np.fromstring() is slow in the mechanism it chooses to split strings by.  </div><div>This is likely due to how many resize operations it must perform.  While it </div><div>need not be the<b> *fastest* </b>thing out there, it should probably be at least as</div>



<div>fast at Python string splitting.   </div><div><br></div><div>No pull-request 'fixing' this issue was provided because I wanted to see </div><div>what people thought and if / which option is worth pursuing.</div>



<div><br></div><div>Be Well</div><div>Anthony</div><div><br></div><div>[1] <a href="https://github.com/numpy/numpy/pull/279" target="_blank">https://github.com/numpy/numpy/pull/279</a></div></div><div>[2] <a href="http://comments.gmane.org/gmane.comp.python.numeric.general/41504" target="_blank">http://comments.gmane.org/gmane.comp.python.numeric.general/41504</a></div>



<div>[3] <a href="https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L3699" target="_blank">https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L3699</a></div><div>[4] <a href="https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L3418" target="_blank">https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.c#L3418</a></div>



<div>[5] <a href="http://svn.python.org/view/python/tags/r271/Objects/stringlib/split.h?view=markup" target="_blank">http://svn.python.org/view/python/tags/r271/Objects/stringlib/split.h?view=markup</a></div>
</blockquote></div><br>