{"action":"created","issue":{"url":"https://api.github.com/repos/tryswift/TryParsec/issues/5","repository_url":"https://api.github.com/repos/tryswift/TryParsec","labels_url":"https://api.github.com/repos/tryswift/TryParsec/issues/5/labels{/name}","comments_url":"https://api.github.com/repos/tryswift/TryParsec/issues/5/comments","events_url":"https://api.github.com/repos/tryswift/TryParsec/issues/5/events","html_url":"https://github.com/tryswift/TryParsec/issues/5","id":139783001,"number":5,"title":"Remove usages of `cons`","user":{"login":"chriseidhof","id":5382,"avatar_url":"https://avatars.githubusercontent.com/u/5382?v=3","gravatar_id":"","url":"https://api.github.com/users/chriseidhof","html_url":"https://github.com/chriseidhof","followers_url":"https://api.github.com/users/chriseidhof/followers","following_url":"https://api.github.com/users/chriseidhof/following{/other_user}","gists_url":"https://api.github.com/users/chriseidhof/gists{/gist_id}","starred_url":"https://api.github.com/users/chriseidhof/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chriseidhof/subscriptions","organizations_url":"https://api.github.com/users/chriseidhof/orgs","repos_url":"https://api.github.com/users/chriseidhof/repos","events_url":"https://api.github.com/users/chriseidhof/events{/privacy}","received_events_url":"https://api.github.com/users/chriseidhof/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":10,"created_at":"2016-03-10T04:45:35Z","updated_at":"2016-03-11T16:11:58Z","closed_at":null,"body":"When we use a lot of `cons` (e.g. in `many`) this will slow down the code, because a copy of the array has to be made and inserting at index 0 is O(n).\r\n\r\nThere are a couple of workarounds. The most \"brute-force\" one would be to rewrite `many` (and other combinators). I'm sorry, the code is quite ugly, but I think many parts can be factored out nicely to keep everything in a functional style. The key trick is to have one `result` array that's not shared, so the compiler can modify it without making copies.\r\n\r\n```swift\r\npublic func many<In, Out, Outs: RangeReplaceableCollectionType where Outs.Generator.Element == Out>(p: Parser<In, Out>) -> Parser<In, Outs>\r\n{\r\n    return Parser { input in\r\n        var result = Outs()\r\n        var remainder = input\r\n        while true {\r\n            switch parse(p, remainder) {\r\n            case .Done(let input, let out):\r\n                result.append(out)\r\n                remainder = input\r\n            case .Fail(_, _, _): return .Done(remainder, result)\r\n            }\r\n        }\r\n    }\r\n}\r\n```\r\n\r\nThis makes it twice as fast on my machine! I think some other cases are `manyTill`, `sepBy1`, `count`, etc."},"comment":{"url":"https://api.github.com/repos/tryswift/TryParsec/issues/comments/195431294","html_url":"https://github.com/tryswift/TryParsec/issues/5#issuecomment-195431294","issue_url":"https://api.github.com/repos/tryswift/TryParsec/issues/5","id":195431294,"user":{"login":"chriseidhof","id":5382,"avatar_url":"https://avatars.githubusercontent.com/u/5382?v=3","gravatar_id":"","url":"https://api.github.com/users/chriseidhof","html_url":"https://github.com/chriseidhof","followers_url":"https://api.github.com/users/chriseidhof/followers","following_url":"https://api.github.com/users/chriseidhof/following{/other_user}","gists_url":"https://api.github.com/users/chriseidhof/gists{/gist_id}","starred_url":"https://api.github.com/users/chriseidhof/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chriseidhof/subscriptions","organizations_url":"https://api.github.com/users/chriseidhof/orgs","repos_url":"https://api.github.com/users/chriseidhof/repos","events_url":"https://api.github.com/users/chriseidhof/events{/privacy}","received_events_url":"https://api.github.com/users/chriseidhof/received_events","type":"User","site_admin":false},"created_at":"2016-03-11T16:11:58Z","updated_at":"2016-03-11T16:11:58Z","body":"I'm not sure what exactly changed in your branch, but I'm pretty sure that my change made everything a lot faster! So maybe we should separate the two things so we can clearly see the differences? =)"}}