Select comparison function for sorting based on type information

Question

So I'm working on a patch for the python interpreter where you go through the list and look at the types of the elements and try to use optimized special-case comparison functions that are much cheaper than the default comparison function. This is the code that goes through and checks the list elements and then assigns the comparison function. I put a lot of thought into the design, refactoring it many times; I really want this to be readable. Is it? How can I improve the form of this? I'm not looking for performance fixes, this just executes once per sort so performance isn't a big deal... I'm looking more for style/refactoring feedback.

/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = (lo.keys[0]->ob_type == &PyTuple_Type &&
                          Py_SIZE(lo.keys[0]) > 0);

PyTypeObject* key_type = (keys_are_in_tuples ?
                          PyTuple_GET_ITEM(lo.keys[0],0)->ob_type :
                          lo.keys[0]->ob_type);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples &&
      (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  PyObject* key = (keys_are_in_tuples ?
                   PyTuple_GET_ITEM(lo.keys[i],0) :
                   lo.keys[i]);

  if (key->ob_type != key_type) {
      keys_are_all_same_type = 0;
      break;
  }

  else if (key_type == &PyLong_Type && ints_are_bounded &&
             Py_ABS(Py_SIZE(key)) > 1)
    ints_are_bounded = 0;

  else if (key_type == &PyUnicode_Type && strings_are_latin &&
             PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND)
    strings_are_latin = 0;
}

/* Set compare_function appropriately based on values of the above bools */
if (keys_are_all_same_type) {

  if (key_type == &PyUnicode_Type && strings_are_latin)
    compare_function = unsafe_unicode_compare;

  else if (key_type == &PyLong_Type && ints_are_bounded)
    compare_function = unsafe_long_compare;

  else if (key_type == &PyFloat_Type)
    compare_function = unsafe_float_compare;

  else if ((richcompare_function = key_type->tp_richcompare) != NULL)
    compare_function = unsafe_object_compare;

} else {
  compare_function = safe_object_compare;
}

if (keys_are_in_tuples) {
  tuple_elem_compare = compare_function;
  compare_function = unsafe_tuple_compare;
}
/* End of type-checking stuff! */

Answer 1

Bug

I don't know anything about the python interpreter, but this if statement:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){

should be:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[i]) == 0)){

where keys[0] was changed to keys[i] in the size check. Otherwise the size check will always be false, since Py_SIZE(lo.keys[0]) was already determined to be nonzero if keys_are_in_tuples is true.

Suggestion for simplification

If you created static inline functions like these:

static inline bool key_is_in_tuple(PyObject *obj)
{
    return obj->ob_type == &PyTuple_Type && Py_SIZE(obj) > 0;
}

static inline PyTypeObject *get_key_type(PyObject *obj)
{
    return key_is_in_tuple(obj) ?
               PyTuple_GET_ITEM(obj,0)->ob_type :
               obj->ob_type);
}

Then your code would read easier:

/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = key_is_in_tuple(lo.keys[0]);

PyTypeObject* key_type = get_key_type(lo.keys[0]);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples && !key_is_in_tuple(lo.keys[i]) {
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  if (get_key_type(lo.keys[i]) != key_type) {
      keys_are_all_same_type = 0;
      break;
  }
  // ...