On Wed, Oct 12, 2016 at 5:36 AM Paul Moore <p.f.moore@gmail.com> wrote:

On 12 October 2016 at 11:16, Steven D'Aprano <steve@pearwood.info> wrote:

> On Wed, Oct 12, 2016 at 12:25:16AM +0000, Elliot Gorokhovsky wrote:

>

>> Regarding generalization: the general technique for special-casing is you

>> just substitute all type checks with 1 or 0 by applying the type assumption

>> you're making. That's the only way to guarantee it's safe and compliant.

>

> I'm confused -- I don't understand how *removing* type checks can

> possible guarantee the code is safe and compliant.

>

> It's all very well and good when you are running tests that meet your

> type assumption, but what happens if they don't? If I sort a list made

> up of (say) mixed int and float (possibly including subclasses), does

> your "all type checks are 1 or 0" sort segfault? If not, why not?

> Where's the safety coming from?

My understanding is that the code does a pre-check that all the

elements of the list are the same type (float, for example). This is a

relatively quick test (O(n) pointer comparisons).

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.

The code for this is really very simple:

int keys_are_all_same_type = 1;

PyTypeObject* key_type = lo.keys[0]->ob_type;

for (i=0; i< saved_ob_size; i++){

if (lo.keys[i]->ob_type != key_type){

keys_are_all_same_type = 0;

break;

}

}

if (keys_are_all_same_type){

if (key_type == &PyUnicode_Type)

compare_function = unsafe_unicode_compare;

if (key_type == &PyLong_Type)

compare_function = unsafe_long_compare;

if (key_type == &PyFloat_Type)

compare_function = unsafe_float_compare;

else

compare_function = key_type->tp_richcompare;

} else {

compare_function = PyObject_RichCompare;

}

PyTypeObject* key_type = lo.keys[0]->ob_type;

for (i=0; i< saved_ob_size; i++){

if (lo.keys[i]->ob_type != key_type){

keys_are_all_same_type = 0;

break;

}

}

if (keys_are_all_same_type){

if (key_type == &PyUnicode_Type)

compare_function = unsafe_unicode_compare;

if (key_type == &PyLong_Type)

compare_function = unsafe_long_compare;

if (key_type == &PyFloat_Type)

compare_function = unsafe_float_compare;

else

compare_function = key_type->tp_richcompare;

} else {

compare_function = PyObject_RichCompare;

}

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.

Hope everything is clear now!

Elliot