Author rhettinger
Recipients amaury.forgeotdarc, collinwinter, eric.smith, mark.dickinson, pitrou, rhettinger, stutzbach, terry.reedy, tim.peters
Date 2010-12-02.00:38:49
SpamBayes Score 9.25393e-05
Marked as misclassified No
Message-id <1291250331.44.0.20647116632.issue9915@psf.upfronthosting.co.za>
In-reply-to
Content
Just for the record, I wanted to highlight how little room there is for optimization here.  The sort wrapper is *very* thin:

sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)
{
    if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) {
        PyErr_SetString(PyExc_TypeError,
            "expected a sortwrapperobject");
        return NULL;
    }
    return PyObject_RichCompare(a->key, b->key, op);
}

When a key function is defined, this is all you can possibly shave off the time for a comparison.  When a key function is not defined, there was no overhead at all.

With the patch, we're relying on branch prediction to minimize the cost to the regular case and adding a little indirection in the form of lo variables becoming lo.keys, etc.  And the number of memmoves is doubled.

To me, the main advantage of the patch is that it saves a little memory for each key:

   typedef struct {
       PyObject_HEAD
       PyObject *key;
       PyObject *value;
   } sortwrapperobject;

Just wanted to post this so there weren't any illusions about the patch being a big win.
History
Date User Action Args
2010-12-02 00:38:51rhettingersetrecipients: + rhettinger, tim.peters, collinwinter, terry.reedy, amaury.forgeotdarc, mark.dickinson, pitrou, eric.smith, stutzbach
2010-12-02 00:38:51rhettingersetmessageid: <1291250331.44.0.20647116632.issue9915@psf.upfronthosting.co.za>
2010-12-02 00:38:49rhettingerlinkissue9915 messages
2010-12-02 00:38:49rhettingercreate