{"action":"created","issue":{"url":"https://api.github.com/repos/swenson/sort/issues/50","repository_url":"https://api.github.com/repos/swenson/sort","labels_url":"https://api.github.com/repos/swenson/sort/issues/50/labels{/name}","comments_url":"https://api.github.com/repos/swenson/sort/issues/50/comments","events_url":"https://api.github.com/repos/swenson/sort/issues/50/events","html_url":"https://github.com/swenson/sort/pull/50","id":375386519,"node_id":"MDExOlB1bGxSZXF1ZXN0MjI2ODQxNzc1","number":50,"title":"Implement gallop mode in timsort (#49)","user":{"login":"liwt31","id":22628546,"node_id":"MDQ6VXNlcjIyNjI4NTQ2","avatar_url":"https://avatars3.githubusercontent.com/u/22628546?v=4","gravatar_id":"","url":"https://api.github.com/users/liwt31","html_url":"https://github.com/liwt31","followers_url":"https://api.github.com/users/liwt31/followers","following_url":"https://api.github.com/users/liwt31/following{/other_user}","gists_url":"https://api.github.com/users/liwt31/gists{/gist_id}","starred_url":"https://api.github.com/users/liwt31/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liwt31/subscriptions","organizations_url":"https://api.github.com/users/liwt31/orgs","repos_url":"https://api.github.com/users/liwt31/repos","events_url":"https://api.github.com/users/liwt31/events{/privacy}","received_events_url":"https://api.github.com/users/liwt31/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-10-30T09:11:31Z","updated_at":"2018-10-30T09:41:46Z","closed_at":null,"author_association":"NONE","pull_request":{"url":"https://api.github.com/repos/swenson/sort/pulls/50","html_url":"https://github.com/swenson/sort/pull/50","diff_url":"https://github.com/swenson/sort/pull/50.diff","patch_url":"https://github.com/swenson/sort/pull/50.patch"},"body":"This PR implements gallop mode in timsort according to the [CPython code](https://github.com/python/cpython/blob/master/Objects/fileobject.c). Benchmark between this implementation and the original timsort (`otim sort` or `osortertim_sort`) is shown below (array size 1600, averaged over 1000 tests):\r\n```\r\n             tim sort -- stable\r\n            otim sort -- stable\r\n-------\r\nRunning tests with random numbers:\r\n-------\r\nsort.h sortertim_sort         - ok,    61202.0 usec\r\nsort.h osortertim_sort        - ok,    50822.0 usec\r\n-------\r\nRunning tests with same number:\r\n-------\r\nsort.h sortertim_sort         - ok,      511.0 usec\r\nsort.h osortertim_sort        - ok,      478.0 usec\r\n-------\r\nRunning tests with sorted numbers:\r\n-------\r\nsort.h sortertim_sort         - ok,      560.0 usec\r\nsort.h osortertim_sort        - ok,      487.0 usec\r\n-------\r\nRunning tests with sorted blocks of length 10:\r\n-------\r\nsort.h sortertim_sort         - ok,    41630.0 usec\r\nsort.h osortertim_sort        - ok,    42016.0 usec\r\n-------\r\nRunning tests with sorted blocks of length 100:\r\n-------\r\nsort.h sortertim_sort         - ok,    13310.0 usec\r\nsort.h osortertim_sort        - ok,    14273.0 usec\r\n-------\r\nRunning tests with sorted blocks of length 10000:\r\n-------\r\nsort.h sortertim_sort         - ok,      494.0 usec\r\nsort.h osortertim_sort        - ok,      479.0 usec\r\n-------\r\nRunning tests with swapped size/2 pairs:\r\n-------\r\nsort.h sortertim_sort         - ok,     1012.0 usec\r\nsort.h osortertim_sort        - ok,     1617.0 usec\r\n-------\r\nRunning tests with swapped size/8 pairs:\r\n-------\r\nsort.h sortertim_sort         - ok,      997.0 usec\r\nsort.h osortertim_sort        - ok,     1636.0 usec\r\n```\r\nThe overhead is significant for random numbers, while gain from nearly sorted numbers (last 2 tests) is pretty decent.\r\nIf the size of the array is multiplied by 10 (to 16000), smaller overhead is expected:\r\n```\r\n             tim sort -- stable\r\n            otim sort -- stable\r\n-------\r\nRunning tests with random numbers:\r\n-------\r\nsort.h sortertim_sort         - ok,   618967.0 usec\r\nsort.h osortertim_sort        - ok,   663787.0 usec\r\n-------\r\nRunning tests with same number:\r\n-------\r\nsort.h sortertim_sort         - ok,     5541.0 usec\r\nsort.h osortertim_sort        - ok,     5740.0 usec\r\n-------\r\nRunning tests with sorted numbers:\r\n-------\r\nsort.h sortertim_sort         - ok,     5491.0 usec\r\nsort.h osortertim_sort        - ok,     5549.0 usec\r\n-------\r\nRunning tests with sorted blocks of length 10:\r\n-------\r\nsort.h sortertim_sort         - ok,   645361.0 usec\r\nsort.h osortertim_sort        - ok,   657122.0 usec\r\n-------\r\nRunning tests with sorted blocks of length 100:\r\n-------\r\nsort.h sortertim_sort         - ok,   302787.0 usec\r\nsort.h osortertim_sort        - ok,   308961.0 usec\r\n-------\r\nRunning tests with sorted blocks of length 10000:\r\n-------\r\nsort.h sortertim_sort         - ok,    18291.0 usec\r\nsort.h osortertim_sort        - ok,    21772.0 usec\r\n-------\r\nRunning tests with swapped size/2 pairs:\r\n-------\r\nsort.h sortertim_sort         - ok,     6765.0 usec\r\nsort.h osortertim_sort        - ok,    14864.0 usec\r\n-------\r\nRunning tests with swapped size/8 pairs:\r\n-------\r\nsort.h sortertim_sort         - ok,     6765.0 usec\r\nsort.h osortertim_sort        - ok,    14566.0 usec\r\n```\r\nI don't quite understand why with larger array gallop mode enabled timsort performs better even in cases such as random numbers. Maybe some fluctuation in my environment? Still, the gallop mode proves to be a reasonable improvement.\r\n\r\nThis [cmp.c](https://gist.github.com/liwt31/da9fb67e5c98c60a661ce73f55ff805e) is the benchmark file I used, modified from `stresstest.c`. Put this `sort.h` and the original `sort.h` as `osort.h` in the same directory with `cmp.c` then it's ready to go."},"comment":{"url":"https://api.github.com/repos/swenson/sort/issues/comments/434233709","html_url":"https://github.com/swenson/sort/pull/50#issuecomment-434233709","issue_url":"https://api.github.com/repos/swenson/sort/issues/50","id":434233709,"node_id":"MDEyOklzc3VlQ29tbWVudDQzNDIzMzcwOQ==","user":{"login":"liwt31","id":22628546,"node_id":"MDQ6VXNlcjIyNjI4NTQ2","avatar_url":"https://avatars3.githubusercontent.com/u/22628546?v=4","gravatar_id":"","url":"https://api.github.com/users/liwt31","html_url":"https://github.com/liwt31","followers_url":"https://api.github.com/users/liwt31/followers","following_url":"https://api.github.com/users/liwt31/following{/other_user}","gists_url":"https://api.github.com/users/liwt31/gists{/gist_id}","starred_url":"https://api.github.com/users/liwt31/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/liwt31/subscriptions","organizations_url":"https://api.github.com/users/liwt31/orgs","repos_url":"https://api.github.com/users/liwt31/repos","events_url":"https://api.github.com/users/liwt31/events{/privacy}","received_events_url":"https://api.github.com/users/liwt31/received_events","type":"User","site_admin":false},"created_at":"2018-10-30T09:41:46Z","updated_at":"2018-10-30T09:41:46Z","author_association":"NONE","body":"CI failed - but I can't reproduce the error for now. Might need some time."}}
{"actor":{"display_login":"liwt31"}}