On Tue, Oct 11, 2016 at 2:29 PM, Elliot Gorokhovsky <elliot.gorokhovsky@gmail.com> wrote:

Ya, I think this may be a good approach for floats: if the list is all floats, just copy all the floats into a seperate array, use the standard library quicksort, and then construct a sorted PyObject* array. Like maybe set up a struct { PyObject* payload, float key } type of deal.

Not quite sure what you mean here. What is payload, what is key? Are you implying that the original float objects could be destroyed and replaced with others of equal value? Python (unlike insurance claims) guarantees that you get back the exact same object as you started with. ChrisA

On Mon, Oct 10, 2016 at 11:30 PM Elliot Gorokhovsky < elliot.gorokhovsky@gmail.com> wrote:

- I expect tuples will also be worth specializing (complex sort keys are often implemented as tuples).

I'm not sure what you mean here... I'm looking at the types of lo.keys, not of saved_ob_item (I think I said that earlier in this thread by mistake actually). So if someone is passing tuples and using itemgetter to extract ints or strings or whatever, the current code will work fine; lo.keys will be scalar types. Unless I misunderstand you here. I mean, when would lo.keys actually be tuples?

If someone wanted to sort, e.g., a table (likely a list of tuples) by multiple columns at once, they might pass the key function as `itemgetter(3, 4, 5)`, meaning to sort by "column" (actually item) 3, then columns 4 and then 5 as tiebreakers. This itemgetter will return a new tuple of three items, that tuple being the key to sort by. Since tuples sort by the first different item, in this theoretical example the result of sort() will be exactly what the user wanted: a table sorted by three columns at once. A practical example of such a use case is sorting by last name first and then by first name where two people have the same last name. Assuming a list of dicts in this case, the key function passed to sort() would simply be `itemgetter('lastname", "firstname")`, which returns a tuple of two items to use as the key. So yes, there are perfectly valid use cases for tuples as keys.

On Mon, Oct 10, 2016 at 11:29 PM, Elliot Gorokhovsky <elliot.gorokhovsky@gmail.com> wrote:

...

Note that when Python's current sort was adopted in Java, they still kept a quicksort variant for "unboxed" builtin types. The adaptive merge sort incurs many overheads that often cost more than they save unless comparisons are in fact very expensive compared to the cost of pointer copying (and in Java comparison of unboxed types is cheap). Indeed, for native numeric types, where comparison is dirt cheap, quicksort generally runs faster than mergesort despite that the former does _more_ comparisons (because mergesort does so much more pointer-copying).

Ya, I think this may be a good approach for floats: if the list is all floats, just copy all the floats into a seperate array, use the standard library quicksort, and then construct a sorted PyObject* array. Like maybe set up a struct { PyObject* payload, float key } type of deal. This wouldn't work for strings (unicode is scary), and probably not for ints (one would have to check that all the ints are within C long bounds). Though on the other hand perhaps this would be too expensive?

I happened onto a page talking about float radix sort, and thought of this thread. Here it is: http://stereopsis.com/radix.html The author claimed an 8x speedup, though the test was done nearly fifteen years ago. I was unsure about posting publicly, because it's not as if an even faster float sort would help decide whether specialized sorts are worth adding to CPython. I'm posting for history.

On Tue, Oct 11, 2016 at 2:29 PM, Elliot Gorokhovsky <elliot.gorokhovsky@gmail.com> wrote:

Ya, I think this may be a good approach for floats: if the list is all floats, just copy all the floats into a seperate array, use the standard library quicksort, and then construct a sorted PyObject* array. Like maybe set up a struct { PyObject* payload, float key } type of deal.

Not quite sure what you mean here. What is payload, what is key? Are you implying that the original float objects could be destroyed and replaced with others of equal value? Python (unlike insurance claims) guarantees that you get back the exact same object as you started with. ChrisA

On Mon, Oct 10, 2016 at 11:30 PM Elliot Gorokhovsky < elliot.gorokhovsky@gmail.com> wrote:

- I expect tuples will also be worth specializing (complex sort keys are often implemented as tuples).

I'm not sure what you mean here... I'm looking at the types of lo.keys, not of saved_ob_item (I think I said that earlier in this thread by mistake actually). So if someone is passing tuples and using itemgetter to extract ints or strings or whatever, the current code will work fine; lo.keys will be scalar types. Unless I misunderstand you here. I mean, when would lo.keys actually be tuples?

If someone wanted to sort, e.g., a table (likely a list of tuples) by multiple columns at once, they might pass the key function as `itemgetter(3, 4, 5)`, meaning to sort by "column" (actually item) 3, then columns 4 and then 5 as tiebreakers. This itemgetter will return a new tuple of three items, that tuple being the key to sort by. Since tuples sort by the first different item, in this theoretical example the result of sort() will be exactly what the user wanted: a table sorted by three columns at once. A practical example of such a use case is sorting by last name first and then by first name where two people have the same last name. Assuming a list of dicts in this case, the key function passed to sort() would simply be `itemgetter('lastname", "firstname")`, which returns a tuple of two items to use as the key. So yes, there are perfectly valid use cases for tuples as keys.

On Mon, Oct 10, 2016 at 11:29 PM, Elliot Gorokhovsky <elliot.gorokhovsky@gmail.com> wrote:

...

Note that when Python's current sort was adopted in Java, they still kept a quicksort variant for "unboxed" builtin types. The adaptive merge sort incurs many overheads that often cost more than they save unless comparisons are in fact very expensive compared to the cost of pointer copying (and in Java comparison of unboxed types is cheap). Indeed, for native numeric types, where comparison is dirt cheap, quicksort generally runs faster than mergesort despite that the former does _more_ comparisons (because mergesort does so much more pointer-copying).

Ya, I think this may be a good approach for floats: if the list is all floats, just copy all the floats into a seperate array, use the standard library quicksort, and then construct a sorted PyObject* array. Like maybe set up a struct { PyObject* payload, float key } type of deal. This wouldn't work for strings (unicode is scary), and probably not for ints (one would have to check that all the ints are within C long bounds). Though on the other hand perhaps this would be too expensive?

I happened onto a page talking about float radix sort, and thought of this thread. Here it is: http://stereopsis.com/radix.html The author claimed an 8x speedup, though the test was done nearly fifteen years ago. I was unsure about posting publicly, because it's not as if an even faster float sort would help decide whether specialized sorts are worth adding to CPython. I'm posting for history.