Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: Parallel lexers by chunking the input
Date: Fri, 25 Mar 2022 17:47:56 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 34
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-03-067@comp.compilers>
References: <22-03-058@comp.compilers> <22-03-064@comp.compilers> <22-03-065@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="2187"; mail-complaints-to="abuse@iecc.com"
Keywords: lex, parallel, comment
Posted-Date: 25 Mar 2022 15:05:13 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:2961

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
...
>[Experiments would be useful here.  Yes, you can do this, but do you
>end up throwing away so much work that it's not worth it? -John]

There is no throwing away, but there are two parallelized passes
through the input (compared to one for the sequential version), plus
the sequential component (should be comparatively small if the chunks
are large), plus maybe some additional overhead for the interface to
the parser.  Still, if you run the scanner on an 8-core CPU, I would
expect a nice real-time speedup (but CPU-time slowdown) for scanning a single input.

However, for typical C/C++ compilation jobs, there often is enough
parallelism from "make -j", so you don't want a scanner that takes
more CPU time.

For load-and-go systems, this kind of parallelization may be more
appropriate, but often there is some interleaving with semantic stuff
that may prevent having the complete scanner run before the rest, and
thus prevent parallelizing the scanner.

@gah4: I don't think that the Aho-Corasick algorithm is particularly
relevant.  It seems to be a less general variant of what lex/flex
does, and is completely sequential in any case.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[I don't understand where you get only two passes.  If you divide the input
into arbitrary sized chunks, you could potentially start at any state in the
scanner and while most of those states would quickly fail, that's a lot of
startup overhead for each block. -John]