Bug 5077 – std.algorithm.schwartzSort is slow

Here are few benchmarks that show that schwartzSort() is much slower than sort(). (While in Python the usage of the 'key' argumement, analogous to a Schwartz sort, usually leads to faster code. But Python and D have very different compilation structure, so comparisons are hazardous at best.) Timings 2.1 GHz CPU, , DATA_LEN=1_000_000, best of 4, seconds: none: 0.3 sort: 4.1 sort: 3.4 (alternative) schwartz: 17.9 I have no idea why the "alternative" sort is faster than the normal sort, I was expecting the opposite. ----------------------------------------- import std.stdio: writeln; import std.algorithm: schwartzSort, sort; import std.random: Random, uniform; import std.typecons: Tuple; enum SortType { none, sort, schwartz } enum DATA_LEN = 1_000_000; enum sort_type = SortType.sort; alias Tuple!(double, "x", double, "y") P; void main() { auto data = new P[DATA_LEN]; auto rnd = Random(1); foreach (ref el; data) { double x = uniform(0.0, 1.0, rnd); double y = uniform(0.0, 1.0, rnd); el = P(x, y); } if (data.length < 50) writeln(data); static if (sort_type == SortType.schwartz) { schwartzSort!((p) { return p.y; })(data); schwartzSort!((p) { return p.x; })(data); schwartzSort!((p) { return p.y; })(data); } static if (sort_type == SortType.sort) { sort!q{ a.y < b.y }(data); sort!q{ a.x < b.x }(data); sort!q{ a.y < b.y }(data); /* // alternative sort!((P a, P b) { return a.y < b.y; })(data); sort!((P a, P b) { return a.x < b.x; })(data); sort!((P a, P b) { return a.y < b.y; })(data); */ } if (data.length < 50) writeln(data); }

I get quite similar timings: sort: 3.8 alt. sort: 3.4 schwartz: 25.8 This is with -inline -O -release.

This is a misunderstanding of Schwartz sort is supposed to do. D's equivalent of Python's key argument is not Schwartz sort, but instead: sort!q{p.x < p.y}(data); i.e. the keys are not copied but instead a projection is used for the comparison. That's your "alt" sort. Schwartz sort is meant for usage when the key computation (in this case a simple member access) is too expensive to be done more than once. To avoid that, schwartzSort creates an array of the computed keys and then sorts the keys and the original arrays in lockstep. It is expected that schwartzSort is considerably slower than sort for cheap keys. It is also expected that "alt" sort is the best of the breed because it has the fastest key computation. I'm leaving this open in case you have new experiments that do reveal a problem. Otherwise, feel free to close it.

(In reply to comment #2) Thank you for your answers. > This is a misunderstanding of Schwartz sort is supposed to do. D's equivalent > of Python's key argument is not Schwartz sort, but instead: > > sort!q{p.x < p.y}(data); > > i.e. the keys are not copied but instead a projection is used for the > comparison. That's your "alt" sort. In that D benchmark there are 3 kinds of sort, two use the normal sort() the other uses schwartzSort. The "alternative" version is still a normal sort. The only difference is that it uses a delegate, as you see from the code: (P a, P b) { return a.y < b.y; } instead of a "template lambda": q{ a.y < b.y } Regarding Python, years ago Python2 used to have just a sort like this, with the "cmp" argument: s.sort(cmp) From the docs: http://docs.python.org/library/stdtypes.html#mutable-sequence-types cmp specifies a custom comparison function of two arguments (list items) which should return a negative, zero or positive number depending on whether the first argument is considered smaller than, equal to, or larger than the second argument: cmp=lambda x,y: cmp(x.lower(), y.lower()). The default value is None. Recent Python2 versions use have a more complex sort signature: s.sort([cmp[, key[, reverse]]]) Where beside the "cmp" that's still present, there is the "key" function: key specifies a function of one argument that is used to extract a comparison key from each list element: key=str.lower. The default value is None. Python3 has removed the cmp argument. In the bug report I was referring to "key" that's a function that takes a single argument and return a single transformed item. So in Python if you use the "key" you are performing a Schwartz sort. C source code of CPython is available online, if you use "key" CPython builds a temporary array of the transformed data, that is used to sort the true data. > I'm leaving this open in case you have new experiments that do reveal a > problem. Otherwise, feel free to close it. The performance of schwartzSort is too much low, so in my opinion the bug report needs to be open still.

Sorry, I have forgotten a Python version of the code: from random import random, seed from operator import itemgetter SortType_none = 0 SortType_sort = 1 SortType_schwartz = 2 DATA_LEN = 1000 # ********** sort_type = SortType_schwartz def main(): seed(1) data = [(random(), random()) for _ in xrange(DATA_LEN)] if len(data) < 50: print data if sort_type == SortType_schwartz: data.sort(key=itemgetter(1)) data.sort(key=itemgetter(0)) data.sort(key=itemgetter(1)) if sort_type == SortType_sort: data.sort(cmp=lambda a, b: cmp(a[1], b[1])) data.sort(cmp=lambda a, b: cmp(a[0], b[0])) data.sort(cmp=lambda a, b: cmp(a[1], b[1])) if len(data) < 50: print data main()

See bug 6192 for more

Still reproducible in 2017. FWIW, with LDC, the difference is smaller: only schwartzSort is slower than regular sort only by about one third rather than being about twice as slow.

(In reply to Vladimir Panteleev from comment #6) > Still reproducible in 2017. > > FWIW, with LDC, the difference is smaller: only schwartzSort is slower than > regular sort only by about one third rather than being about twice as slow. Sounds like typical poor performance of using DMD with ranges (i.e. std.range.zip used by schwartzSwort.) Possible duplicate of: #14943 & #16120 Aside: Stripping out dynamic stopping policies from std.range.zip led to a few % improvement on LDC, nothing big though.

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/phobos/issues/9891 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB