<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Wed, Oct 12, 2016 at 5:36 AM Paul Moore <<a href="mailto:p.f.moore@gmail.com">p.f.moore@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 12 October 2016 at 11:16, Steven D'Aprano <<a href="mailto:steve@pearwood.info" class="gmail_msg" target="_blank">steve@pearwood.info</a>> wrote:<br class="gmail_msg">
> On Wed, Oct 12, 2016 at 12:25:16AM +0000, Elliot Gorokhovsky wrote:<br class="gmail_msg">
><br class="gmail_msg">
>> Regarding generalization: the general technique for special-casing is you<br class="gmail_msg">
>> just substitute all type checks with 1 or 0 by applying the type assumption<br class="gmail_msg">
>> you're making. That's the only way to guarantee it's safe and compliant.<br class="gmail_msg">
><br class="gmail_msg">
> I'm confused -- I don't understand how *removing* type checks can<br class="gmail_msg">
> possible guarantee the code is safe and compliant.<br class="gmail_msg">
><br class="gmail_msg">
> It's all very well and good when you are running tests that meet your<br class="gmail_msg">
> type assumption, but what happens if they don't? If I sort a list made<br class="gmail_msg">
> up of (say) mixed int and float (possibly including subclasses), does<br class="gmail_msg">
> your "all type checks are 1 or 0" sort segfault? If not, why not?<br class="gmail_msg">
> Where's the safety coming from?<br class="gmail_msg">
<br class="gmail_msg">
My understanding is that the code does a pre-check that all the<br class="gmail_msg">
elements of the list are the same type (float, for example). This is a<br class="gmail_msg">
relatively quick test (O(n) pointer comparisons). </blockquote><div><br></div><div>Yes, that's correct. I'd like to emphasize that I'm not "*removing* type checks" -- I'm checking them in advance, and then substituting in the values I already know are correct. To put it rigorously: there are expressions of the form PyWhatever_Check. I can be eager or lazy about how I calculate these. The current implementation is lazy: it waits until the values are actually called for before calculating them. This is expensive, because they are called for many, many times. My implementation is eager: I calculate all the values in advance, and then if they all happen to be the same, I plug in that  value (1 or 0 as the case may be) wherever it appears in the code. If they don't happen to all be the same, like for "mixed int and float", then I just don't change anything and use the default implementation.<br><br></div><div>The code for this is really very simple:<br><table class="inbox-inbox-highlight inbox-inbox-tab-size inbox-inbox-js-file-line-container"><tbody><tr><td id="inbox-inbox-LC124" class="inbox-inbox-blob-code inbox-inbox-blob-code-inner inbox-inbox-js-file-line"><br></td>
      </tr>
      <tr>
        </tr></tbody></table>int keys_are_all_same_type = 1;<br>    PyTypeObject* key_type = lo.keys[0]->ob_type;<br>    for (i=0; i< saved_ob_size; i++){<br>      if (lo.keys[i]->ob_type != key_type){<br>        keys_are_all_same_type = 0;<br>        break;<br>      }<br>    }<br>    <br>    if (keys_are_all_same_type){<br>      if (key_type == &PyUnicode_Type)<br>        compare_function = unsafe_unicode_compare;<br>      if (key_type == &PyLong_Type)<br>        compare_function = unsafe_long_compare;<br>      if (key_type == &PyFloat_Type)<br>        compare_function = unsafe_float_compare;<br>      else<br>        compare_function = key_type->tp_richcompare;<br>    } else {<br>      compare_function = PyObject_RichCompare;<br>    }<br><br></div><div>Those unsafe_whatever* functions are derived by substituting in, like I said, the known values for the typechecks (known since keys_are_all_same_type=1 and key_type = whatever) in the existing implementations of the compare functions.<br><br></div><div>Hope everything is clear now!<br><br></div><div>Elliot</div></div></div>