Update the Angle parser - #1050

So just to be clear, is this supposed to be merged only into the 0.2.x branch, or this should be merged into master before #1006 ?

I think this can be merged to master, but before #1006 and @iguananaut's merge-finding script should pull this over to 0.2.x.

Haven't looked over the code changes yet but sounds fine in principle.

Also, 👍 to using pyparsing as it makes the code more readable - though I'd be interested to know if there is a big performance impact?

pyparsing is by no means the fastest tool out there. But when I last looked (when I started working on the units package) it was the only one I could find that:

a] was pure Python, thereby not adding another C dependency
b] works on Python 2 and 3
c] uses a well-understood parsing model

There's newer/faster/cooler things, (pyPEG, Parsely), but none seem to meet all of these criteria.

As for performance impact, I can try to measure it...

It's hundreds of times slower.

from astropy.coordinates import Angle

def parse_angle():
    x = Angle("52d34m29s")

import timeit
print timeit.timeit(parse_angle, number=1000)

Gives me 1.08s vs. 0.0349s. It's not an entirely fair comparison, since the pyparsing-based parser supports more things, and more correctly. There might be some speedups in there for the pyparsing-based parser. I'd love to use a faster parsing framework, but, as I said, I'm not sure any of them are practical and fit all our needs.

That's way too slow. I'd opt to not use that.

I can't believe this could possible be this slow. Is it regenerating the parser on each loop or something? I've never used pyparsing so I don't know but that just seems extreme. I wonder if putting this in a profiler would be at all illuminating.

@demitri: Just because something is much slower than something else doesn't make it "way too slow". How many of these angles can we expect to parse during an average application? Does that dominate? Again, this isn't an apples to apples comparison because the regex parser was incorrect, and making it correct would add a lot of implementation complexity that would be hard to debug. We're using Python and not C++ here because we all understand that implementation efficiency can in many cases beat computational efficiency.

@iguananaut: It is not regenerating the parser on each loop.

I've used pyparsing for years as part of matplotlib, and it has never been a speed demon. I think you have to use a code-generation approach of, e.g. Parsely, to really get speed improvements (but that doesn't support Python 3). pyparsing merely builds a tree of objects that form an interpreter of sorts.

I'd rather put this in now because it's correct but slow, and track other parsing projects with an eye to moving to them once they become practical.

In any event, I was able to get a 3x speedup by reorganizing the parser clauses a little bit.

So if I'm interpreting the numbers correctly (feel free to correct me if not, @mdboom). I consider 1 sec to be roughly the threshold for "noticeably" slow... so this means you now get a "noticeable" slowdown at 1000 angles vs. 10000 angles, is that right?

Also, would there be any significant speedup for array/list Angles? That is, if you know ahead of time that you have a list of angles instead of a single string, will pyparsing process that faster?

@mdboom Yes, I get that it's not C++. I just think that 1000 coordinates to parse is not an unusual number; nor would 10K be. I'm all about avoiding preoptimization, but long coordinates lists are common. I'm working with one list of 250K - that's high, but not crazy.

Ok -- I might spend a bit of time today re-exploring parser libraries. This is a simple enough grammar, it should be easy enough to reimplement in various ways and do a shoot-off.

See http://github.com/mdboom/parser-shootout

I've taken the existing pyparsing-based parser and reimplemented it in PLY.

Results (for 11,000 angle parses):

test_pyparsing: 5.29625892639s
test_ply: 2.03879404068s

See the README file for other projects that I rejected outright. The only other possible candidate found is parsing, but I'm on the verge of rejecting it for having such minimal documentation.

I guess a few seconds for 11,000 angles doesn't seem that bad to me. And I agree a factor-of-a-few hit in the name of code clarity and correctness is fine. (Although all that is pretty subjective.) Thanks for doing the tests, @mdboom - that's useful information for a variety of other contexts, as well!

So I think it makes sense to use one of these (ply or pyparsing) now and if we get complaints that it's just too slow we can have someone work on optimizing more down the road.

Yes, thanks. That's a great improvement!

Ok -- I've moved everything over to PLY. This includes the existing pyparsing-based units parsers.

Is this ready to merge, @mdboom ? I would say it's important enough to push it into 0.2.2...

As far as I know, yes. It's sort of a bigger change than I would usually like for a minor point release (changing the underlying parser library used), but it is passing all tests...

I agree in principal, but I think this is mostly "under the hood", and after all it was wrong behavior before.

@iguananaut - I'll leave this open for now in case there anyone wants to take a last-minute look, but how about you merge this for 0.2.2 ?

Okay. I'll leave it open for now but once I've gone through merging other work for 0.2.2 I'll come back around to this and merge it.