4 ms·

Can anyone recommend pointers to find out more about creating programming languages / markup languages that would be more parallel friendly for parsing? Or may

by floxy 2y ago

Can anyone recommend pointers to find out more about creating programming languages / markup languages that would be more parallel friendly for parsing? Or maybe even embarrassingly parallel? How does that affect the grammar, etc.. Maybe you need a different formalism rather than BNF do describe it, and you don't use regex to tokenize, and there is no recursive descent, or state machines in parsing, etc..

dzaima 2y ago
There's not really that much specific to change I think; the general thing is just reducing the number of rules, as in a parallel thing you'll be applying every rule to every part versus just the rules given preceding context (there is the option of filtering parts to process if there are a bunch of rules applying to the same small subset of the input, but that requires such cont). All I can point at is from the array language world, with the notable thing of Co-dfns from Aaron Hsu, an APL compiler capable of running on the GPU (pointless as that may be): https://github.com/Co-dfns/Co-dfns/tree/master https://github.com/Co-dfns/Co-dfns/tree/master; and a 284-page dissertation: https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-bd95-40aff99e8c7a https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-... And Marshall Lochbaum following (https://mlochbaum.github.io/BQN/implementation/codfns.html https://mlochbaum.github.io/BQN/implementation/codfns.html) that work, and covering some basics of parsing expressions of infix & prefix ops to stack-based/RPN at the bottom of https://mlochbaum.github.io/BQN/implementation/index.html https://mlochbaum.github.io/BQN/implementation/index.html, though the code is in BQN. From that same author, parsers written in BQN, that I think should have sub-linear critical paths: Markdown: https://github.com/mlochbaum/BQN/blob/master/md.bqn https://github.com/mlochbaum/BQN/blob/master/md.bqn XML: https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn and a compiler of BQN itself: https://github.com/mlochbaum/BQN/blob/master/src/c.bqn https://github.com/mlochbaum/BQN/blob/master/src/c.bqn (outputs stack-based bytecode).
- floxy 2y ago
  Are you still operating on a single stream of characters? I was wondering about something more radical, like you start in the middle of the stream, and one thread parses the forward to the end, and the other parses backwards towards the beginning.
  - dzaima 2y ago
    That's an option for a potential 2x boost, which I suppose could be good enough in certain contexts, but that's it. In particular, if you have a parser system able to utilize SIMD for all parsing, that'll get arbitrary parallelizability for "free" (at the cost of some log(n) increase in total operations across all threads).

by floxy 2y ago

dzaima 2y ago

There's not really that much specific to change I think; the general thing is just reducing the number of rules, as in a parallel thing you'll be applying every rule to every part versus just the rules given preceding context (there is the option of filtering parts to process if there are a bunch of rules applying to the same small subset of the input, but that requires such cont). All I can point at is from the array language world, with the notable thing of Co-dfns from Aaron Hsu, an APL compiler capable of running on the GPU (pointless as that may be): https://github.com/Co-dfns/Co-dfns/tree/master https://github.com/Co-dfns/Co-dfns/tree/master; and a 284-page dissertation: https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-bd95-40aff99e8c7a https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-... And Marshall Lochbaum following (https://mlochbaum.github.io/BQN/implementation/codfns.html https://mlochbaum.github.io/BQN/implementation/codfns.html) that work, and covering some basics of parsing expressions of infix & prefix ops to stack-based/RPN at the bottom of https://mlochbaum.github.io/BQN/implementation/index.html https://mlochbaum.github.io/BQN/implementation/index.html, though the code is in BQN. From that same author, parsers written in BQN, that I think should have sub-linear critical paths: Markdown: https://github.com/mlochbaum/BQN/blob/master/md.bqn https://github.com/mlochbaum/BQN/blob/master/md.bqn XML: https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn and a compiler of BQN itself: https://github.com/mlochbaum/BQN/blob/master/src/c.bqn https://github.com/mlochbaum/BQN/blob/master/src/c.bqn (outputs stack-based bytecode).

floxy 2y ago
Are you still operating on a single stream of characters? I was wondering about something more radical, like you start in the middle of the stream, and one thread parses the forward to the end, and the other parses backwards towards the beginning.
- dzaima 2y ago
  That's an option for a potential 2x boost, which I suppose could be good enough in certain contexts, but that's it. In particular, if you have a parser system able to utilize SIMD for all parsing, that'll get arbitrary parallelizability for "free" (at the cost of some log(n) increase in total operations across all threads).