1
\$\begingroup\$

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! */
\$\endgroup\$
2
\$\begingroup\$

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;
  }
  // ...
\$\endgroup\$
  • \$\begingroup\$ You're right about [0], I caught that myself after posting. Will edit \$\endgroup\$ – Elliot Gorokhovsky Nov 12 '16 at 9:55
  • \$\begingroup\$ Also: should I use static inlines or macros? \$\endgroup\$ – Elliot Gorokhovsky Nov 12 '16 at 9:55
  • \$\begingroup\$ Good suggestion either way, though, will use! \$\endgroup\$ – Elliot Gorokhovsky Nov 12 '16 at 9:56
  • \$\begingroup\$ It's a matter of preference but I would use static inlines. \$\endgroup\$ – JS1 Nov 12 '16 at 9:56
  • \$\begingroup\$ Does it make sense to mark them inline though? Because the compiler will try to inline anyway \$\endgroup\$ – Elliot Gorokhovsky Nov 12 '16 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.