Integer based tags to avoid so many string comparions about mpc HOT 10 OPEN

I've only now notice that #31 mentions something like this. What are the status of any implementation of such a feature, if any?

from mpc.

Hi petermlm,

At the moment there is still no easy solution to this because different applications need to tag nodes in different ways and strings are the only good generic interface to this sort of thing.

Saying that there are a couple of simple things you can do.

You can declare your own ast type which uses integer tags and do a single pass to convert the mpc ast into your own ast which can be processed faster, or you can hack the mpc ast type and insert your own integer field - and again do a single pass which adds this integer tag to all the nodes by looking at the string tags.

An alternative option is to use the parser combinator approach instead of the grammar approach to specify your language. Here you can specify your own ast type and have complete control over how things get tagged.

Ideally mpc would let you use your own ast type along with the grammar specification by just having the user specify various operations such as how to create, tag, delete, join the custom ast type. This is what I proposed in #31 but never got around to doing it yet.

Your proposal sounds interesting though - I will have a think about it as it may be a practical way to solve this issue.

• Dan

from mpc.

The solutions you gave seem very good, thanks!

As to the more ideal solution, since I'll be working with MPC over the next few days I may end up thinking about something. If I do I'll propose it in here and we'll discuss it further!

from mpc.

Hi,

I've pushed up an experimental branch with integer flags (which can be used as tags): https://github.com/orangeduck/mpc/tree/flags

The flags are very easy to use - you just specify them when you create the parser with mpc_flag and then when the language gets parsed they get added into the flags field of mpc_ast_t. You should then be able to iterate over the tree as usual but instead just look at the flags field instead of the tag field. I also added a new option for mpca_lang to disable the string tags completely (for efficiency).

Here you can see I added some tests which basically shows how to set up the grammar to use the flags instead of the tags - I think it is pertty straight forward - ignore the complicated code used for testing the AST output:

https://github.com/orangeduck/mpc/blob/flags/tests/grammar.c#L270

Perhaps you can try it in your project and see if you encounter any issues? Tell me if you are unsure how to use them or if you have any questions.

• Dan

from mpc.

@orangeduck , just wanted to let you know that I've been extremely busy and haven't had time to look into this. But I'll be reviewing this over the next couple of days and will, hopefully, provide feedback.

from mpc.

@orangeduck , this seems very cool! Exactly what I had in mind. Might be cool to do a simple benchmark with and without the flags. I can work on one. Thinking about the example with the maths expressions, we could generate a random expression with 1000 or more values like:

432 + 754 - 3432 + 7654 / 423 * 6542 / 4312 + 432 ...

And run the parser several times to see how long it takes to do it with and without flags. I can work on that over the next following days.

from mpc.

Yeah that would be good. Perhaps something in the tests directory that can be run with make bench Actually I was intending to add some proper benchmarking code for #35 as I've just been doing some ad-hoc comparisons.

from mpc.

A benchmark directory separated from tests would be nice. I fell tests and benchmarks are different. Tests just specify if something is correct or not, while benchmarks are use to give insight into some part of some software.

I'll work on the benchmark like I spoke about. I'll try to have this before the weekend. I'll present it outside of the repository. We can come up with more benchmarks and eventually place them in the repository!

from mpc.

Yeah that works too. Sounds good - no hurry. Look forward to seeing if the integer tags improve performance.

from mpc.

@orangeduck I know it's been a while but... How did those experiments go?

I am looking at including mpc into my project, and I really like the declarative grammar approach - it just reads much better. But having all those string tags is both slow and inconvenient at times.

Integer tags seem nice but there's an obvious limit to how many tags one can have depending on the value that contains the flags.

Being able to specify custom ast nodes would be a killer feature for me but that as a more fundamental change.

from mpc.