{"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":25,"created_at":"2016-02-10T14:57:18Z","updated_at":"2016-02-18T20:52:18Z","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/185914077","html_url":"https://github.com/gap-system/gap/pull/609#issuecomment-185914077","issue_url":"https://api.github.com/repos/gap-system/gap/issues/609","id":185914077,"user":{"login":"markuspf","id":3589190,"avatar_url":"https://avatars.githubusercontent.com/u/3589190?v=3","gravatar_id":"","url":"https://api.github.com/users/markuspf","html_url":"https://github.com/markuspf","followers_url":"https://api.github.com/users/markuspf/followers","following_url":"https://api.github.com/users/markuspf/following{/other_user}","gists_url":"https://api.github.com/users/markuspf/gists{/gist_id}","starred_url":"https://api.github.com/users/markuspf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/markuspf/subscriptions","organizations_url":"https://api.github.com/users/markuspf/orgs","repos_url":"https://api.github.com/users/markuspf/repos","events_url":"https://api.github.com/users/markuspf/events{/privacy}","received_events_url":"https://api.github.com/users/markuspf/received_events","type":"User","site_admin":false},"created_at":"2016-02-18T20:52:18Z","updated_at":"2016-02-18T20:52:18Z","body":"On Thu, Feb 18, 2016 at 12:13:35PM -0800, hungaborhorvath wrote:\n> Offtopic:\n> @markuspf Actually, no. I discussed my ideas with @Stefan-Kohl as he is the\n> maintainer of grpnames.g*, and some discussion has been started at e.g. #160.\n> There are already some PRs along making it more efficient, e.g. #379, #561, #\n> 563.\n> \n> What would be the proper forum to open a discussion about this? To open an\n> issue?\n\nIf you are planning to make major changes to the GAP system the best way to go\nabout probably is to send an email to gap@gap-system.org (the open development\nmailing list) and make people aware of your plans.\n\nWe hope that this way you will get early feedback on your project and (hopefully)\ndon't end up in a situation where you invested a lot of time into a project\nand you're then turned down because people don't agree with what you have\nbeen doing.\n\nIf you have code, the best thing to do is open a pull-request.\n\nI don't think that discussions about design decisions are well-placed in the\nissue tracker.\n"}}