{"action":"created","issue":{"url":"https://api.github.com/repos/gap-system/gap/issues/609","repository_url":"https://api.github.com/repos/gap-system/gap","labels_url":"https://api.github.com/repos/gap-system/gap/issues/609/labels{/name}","comments_url":"https://api.github.com/repos/gap-system/gap/issues/609/comments","events_url":"https://api.github.com/repos/gap-system/gap/issues/609/events","html_url":"https://github.com/gap-system/gap/pull/609","id":132720660,"number":609,"title":"[WIP] Improve GAP's sort functions","user":{"login":"ChrisJefferson","id":811527,"avatar_url":"https://avatars.githubusercontent.com/u/811527?v=3","gravatar_id":"","url":"https://api.github.com/users/ChrisJefferson","html_url":"https://github.com/ChrisJefferson","followers_url":"https://api.github.com/users/ChrisJefferson/followers","following_url":"https://api.github.com/users/ChrisJefferson/following{/other_user}","gists_url":"https://api.github.com/users/ChrisJefferson/gists{/gist_id}","starred_url":"https://api.github.com/users/ChrisJefferson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ChrisJefferson/subscriptions","organizations_url":"https://api.github.com/users/ChrisJefferson/orgs","repos_url":"https://api.github.com/users/ChrisJefferson/repos","events_url":"https://api.github.com/users/ChrisJefferson/events{/privacy}","received_events_url":"https://api.github.com/users/ChrisJefferson/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":15,"created_at":"2016-02-10T14:57:18Z","updated_at":"2016-02-11T13:33:47Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/gap-system/gap/pulls/609","html_url":"https://github.com/gap-system/gap/pull/609","diff_url":"https://github.com/gap-system/gap/pull/609.diff","patch_url":"https://github.com/gap-system/gap/pull/609.patch"},"body":"Before looking at this patch, look at these soothing benchmarks. These each show a list, and how long it takes to show to sort it in master, and in this branch.\r\n\r\n```\r\nList([1..10000000], x -> Random([1..10000000])) : 4467 -> 1324\r\nList([1..10000000], x -> Random([1..2]));; : 736 -> 200\r\nList([1..10000000], x -> -x) : 895 -> 175\r\nConcatenation([1..10000000], [50]) : 639 -> 383\r\nl := [1..100000000] * 0;; : 6245 -> 1412\r\n```\r\n\r\nThis patch aims to do 2 things:\r\n\r\n1) Using some reasonably horrid C macros, remove the fact we have 8 cut+pasted copy of our sort routine.\r\n\r\nThe 8 sorts are all combinations of:\r\n\r\n* Sorting a plist and any list\r\n* Sorting with a predicate, or without\r\n* Sort and SortParallel\r\n\r\n\r\n2) Replace the shell sort (which has served us well) with a more modern search, in this case 'pdqsort' which is a variant of introsort (which is a variant of quicksort), designed to make use of sorted sub-sequences fairly cheaply.\r\n\r\nThe way this works is we define a small language of macro functions which must be implemented to instantiate our sort. \r\n\r\nThe main question is, do people consider the macros worth the reduction in code duplication, or does anyone have a suggestion on how to handle this differently, before I apply final spit+polish? (The  answer \"turn the GAP kernel in C++\" seems like too huge a step right now)."},"comment":{"url":"https://api.github.com/repos/gap-system/gap/issues/comments/182864032","html_url":"https://github.com/gap-system/gap/pull/609#issuecomment-182864032","issue_url":"https://api.github.com/repos/gap-system/gap/issues/609","id":182864032,"user":{"login":"ChrisJefferson","id":811527,"avatar_url":"https://avatars.githubusercontent.com/u/811527?v=3","gravatar_id":"","url":"https://api.github.com/users/ChrisJefferson","html_url":"https://github.com/ChrisJefferson","followers_url":"https://api.github.com/users/ChrisJefferson/followers","following_url":"https://api.github.com/users/ChrisJefferson/following{/other_user}","gists_url":"https://api.github.com/users/ChrisJefferson/gists{/gist_id}","starred_url":"https://api.github.com/users/ChrisJefferson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ChrisJefferson/subscriptions","organizations_url":"https://api.github.com/users/ChrisJefferson/orgs","repos_url":"https://api.github.com/users/ChrisJefferson/repos","events_url":"https://api.github.com/users/ChrisJefferson/events{/privacy}","received_events_url":"https://api.github.com/users/ChrisJefferson/received_events","type":"User","site_admin":false},"created_at":"2016-02-11T13:33:47Z","updated_at":"2016-02-11T13:33:47Z","body":"Now featuring `StableSort`, `StableSortBy` and `StableSortParallel`, just missing documentation.\r\n\r\nThese methods are (not unexpectedly) lower than `Sort` by varying amounts, but still (usually) faster than @frankluebeck 's mapping to an array of pairs.\r\n\r\nTo get the speed higher, one could implement one of the modern stable sorts which is similar in design to  pdqsort, such as timsort (used in Python, among other places). I leave such an implementation to anyone who wants to volunteer :)"}}