{"action":"created","issue":{"url":"https://api.github.com/repos/fscheck/FsCheck/issues/237","repository_url":"https://api.github.com/repos/fscheck/FsCheck","labels_url":"https://api.github.com/repos/fscheck/FsCheck/issues/237/labels{/name}","comments_url":"https://api.github.com/repos/fscheck/FsCheck/issues/237/comments","events_url":"https://api.github.com/repos/fscheck/FsCheck/issues/237/events","html_url":"https://github.com/fscheck/FsCheck/pull/237","id":152528889,"number":237,"title":"FsList shrinker","user":{"login":"MarcoMaar","id":4059205,"avatar_url":"https://avatars.githubusercontent.com/u/4059205?v=3","gravatar_id":"","url":"https://api.github.com/users/MarcoMaar","html_url":"https://github.com/MarcoMaar","followers_url":"https://api.github.com/users/MarcoMaar/followers","following_url":"https://api.github.com/users/MarcoMaar/following{/other_user}","gists_url":"https://api.github.com/users/MarcoMaar/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcoMaar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcoMaar/subscriptions","organizations_url":"https://api.github.com/users/MarcoMaar/orgs","repos_url":"https://api.github.com/users/MarcoMaar/repos","events_url":"https://api.github.com/users/MarcoMaar/events{/privacy}","received_events_url":"https://api.github.com/users/MarcoMaar/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-05-02T10:35:21Z","updated_at":"2016-05-03T10:00:58Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/fscheck/FsCheck/pulls/237","html_url":"https://github.com/fscheck/FsCheck/pull/237","diff_url":"https://github.com/fscheck/FsCheck/pull/237.diff","patch_url":"https://github.com/fscheck/FsCheck/pull/237.patch"},"body":"Following PR for #234\r\n\r\nI did a performance comparison for three versions of the FsList shrinker:\r\n1) old one\r\n2)\r\n```fsharp\r\n        static member FsList() = \r\n            { new Arbitrary<list<'a>>() with\r\n                override __.Generator = Gen.listOf generate\r\n                override __.Shrinker (l:'a list) =\r\n                    let skipOne (l:list<_>) =\r\n                        seq { for i in 0..l.Length-1 do \r\n                              yield List.foldBack (fun e (c,r) -> c+1, if i <> c then e::r else r) l (0,[]) |> snd\r\n                            }\r\n                    let rec shrinks cl pre = \r\n                        match cl with\r\n                        | [] -> Seq.empty\r\n                        | [x] -> seq { for x' in shrink x -> x'::pre |> List.rev}\r\n                        | x::xs -> seq { for x' in shrink x -> pre @ (x'::xs)\r\n                                         yield! shrinks xs (x::pre |> List.rev) }\r\n                    seq { yield! skipOne l; yield! shrinks l []}\r\n```\r\n3) the one in this PR\r\n\r\nI did the performance check with three configurations. The small configuration uses startsize 0 and endsize 100 medium uses 200,200 and large uses 400,400. I ran each test 5 times and used the average. I did not use a stopwatch and simply looked at the time a testcase needed. The small configurations were quite similar due to the startup time of VS's test runner.\r\n```fsharp\r\n    [<Fact>]\r\n    let ``performance_medium``() =\r\n        let config = { Config.Quick with StartSize = 200; EndSize = 200 }\r\n        let prop l = \r\n            let shrunk = Arb.Default.FsList().Shrinker l\r\n            l.Length = 0 || (shrunk |> Seq.forall (fun s -> s.Length = l.Length || s.Length = l.Length - 1))\r\n        Check.One(config, prop) \r\n```\r\nHere are the results:\r\n-- | ---S--- | --M-- | --L--\r\n1 | 370ms | 5.5s | 40s\r\n2 | 370ms | 2.8s | 19s\r\n3 | 350ms | 2.0s | 14s\r\n\r\nThere is a difference between 3 and 1,2 we should consider. The shrunk values that skip one element are at the beginning of the sequence in 1 and 2. They are not in 3. It may make sense to use Implementation 2 if we want to have the skips at the beginning."},"comment":{"url":"https://api.github.com/repos/fscheck/FsCheck/issues/comments/216484967","html_url":"https://github.com/fscheck/FsCheck/pull/237#issuecomment-216484967","issue_url":"https://api.github.com/repos/fscheck/FsCheck/issues/237","id":216484967,"user":{"login":"kurtschelfthout","id":164917,"avatar_url":"https://avatars.githubusercontent.com/u/164917?v=3","gravatar_id":"","url":"https://api.github.com/users/kurtschelfthout","html_url":"https://github.com/kurtschelfthout","followers_url":"https://api.github.com/users/kurtschelfthout/followers","following_url":"https://api.github.com/users/kurtschelfthout/following{/other_user}","gists_url":"https://api.github.com/users/kurtschelfthout/gists{/gist_id}","starred_url":"https://api.github.com/users/kurtschelfthout/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kurtschelfthout/subscriptions","organizations_url":"https://api.github.com/users/kurtschelfthout/orgs","repos_url":"https://api.github.com/users/kurtschelfthout/repos","events_url":"https://api.github.com/users/kurtschelfthout/events{/privacy}","received_events_url":"https://api.github.com/users/kurtschelfthout/received_events","type":"User","site_admin":false},"created_at":"2016-05-03T10:00:58Z","updated_at":"2016-05-03T10:00:58Z","body":"Cool. Initial impressions for now.\r\n\r\nI prefer not to change the semantics  - although we don't have a test case for it, it may affect the eventual counter-example in some cases and I consider that a \"slightly breaking\" change ;) \r\n\r\nAlso the perf difference between 2 and 3 seems pretty small. Shrinking is not a frequent operation so doesn't look like it would be really worth it. (As a tangent, the real meat of where perf matters I think is in generation.)\r\n\r\nI'll try to take a look at this in more detail soon...\r\n"}}