Remove usages of cons

[chriseidhof]

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).

There 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.

public func many<In, Out, Outs: RangeReplaceableCollectionType where Outs.Generator.Element == Out>(p: Parser<In, Out>) -> Parser<In, Outs>
{
    return Parser { input in
        var result = Outs()
        var remainder = input
        while true {
            switch parse(p, remainder) {
            case .Done(let input, let out):
                result.append(out)
                remainder = input
            case .Fail(_, _, _): return .Done(remainder, result)
            }
        }
    }
}

This makes it twice as fast on my machine! I think some other cases are manyTill, sepBy1, count, etc.

[chriseidhof]

Another way would be to have a data structure that can do an O(1) append at the front (e.g. a reversed array). But I think that might be confusing as well...

[norio-nomura]

@chriseidhof Oh, my local experimental build became much faster by this approach! I'll create branch that we can test that.

[chriseidhof]

Awesome! I also would think that removing the mutual recursion in functions like skipMany/skipMany1 and replacing one of their implementations with a for loop could improve the speed (although I'm not sure about this, so we should test it).

[norio-nomura]

I have included this approach in the TryParsecExperiment target on https://github.com/tryswift/TryParsec/tree/nn/experiment that twice faster than original.
As I tested, rewriting inside logic of cons to using append() approach does not gain performance improvement.
So, I think that the performance gaining on the heading case of this issue is caused by inlining cons into many and others.

[chriseidhof]

Did you push those commits? I can't seem to find them!

[norio-nomura]

Sorry, I did not include that. 🙇

[norio-nomura]

And I apologize that I misunderstood approach of this issue.
Now, c7f44f7 is 1.359sec (original is 7.427sec on same mac)!

[chriseidhof]

By the way, I just wrote my code in the quickest and dirtiest way possible, I totally think there's a lot of room for writing it in a more functional way. For example, I really don't like the while true loop...

[norio-nomura]

Sorry, I found bug on my TryParsecExperiment by making functional test pass, then the duration back to 5.595sec. 😞

[chriseidhof]

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? =)

[norio-nomura]

Yes, your change made faster.
Sorry, I should not post here about my experiments. 🙇

[norio-nomura]

I wrote about nn/experiment branch on #10.