Alex Lexer Performance Issues
Hi Cafe, In one of my projects I have a lexer that seems to be taking an inordinate amount of time and space. The lexer is generated by Alex using the lazy ByteString (with position information) template. I compiled and ran with profiling enabled and I get a report like this: ------------------------------------------------------------------------------- Tue Jun 21 16:56 2011 Time and Allocation Profiling Report (Final) ViewCallGraph +RTS -p -RTS gnutls.bc total time = 51.80 secs (2590 ticks @ 20 ms) total alloc = 9,482,333,244 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc alexScanTokens Data.LLVM.Private.Lexer 24.1 4.5 alex_scan_tkn Data.LLVM.Private.Lexer 21.2 32.7 tokenAs Data.LLVM.Private.Parser.Primitive 6.7 2.9 alexGetChar Data.LLVM.Private.Lexer 6.5 22.7 ------------------------------------------------------------------------------- The entries below these four are marginal. The third entry is from my code and isn't a big deal (yet), but the other three seem to indicate that the lexer is responsible for about 50% of my runtime and memory allocation. For reference, this particular input is about 18M of text, though the ratios are just as bad for smaller inputs. My uneducated suspicion is that Alex is constructing separate ByteStrings that it passes to each of my token constructors, and that this is responsible for a large part of this allocation. Most of my token constructors just ignore this ByteString - assuming there really is an allocation for each token, is there any way to avoid it? I was looking at alexScanTokens, alex_scan_tkn, and alexGetChar but didn't see any obvious ways to improve them. Alternatively, does any one have lexing performance tips that might help? Thanks
How fast is good old String rather than ByteString? For lexing, String is a good fit (cheap deconstruction at the head / front). For your particular case, maybe it loses due to the large file size, maybe it doesn't...
On Wed, Jun 22, 2011 at 07:48:40AM +0100, Stephen Tetley wrote:
How fast is good old String rather than ByteString?
For lexing, String is a good fit (cheap deconstruction at the head / front). For your particular case, maybe it loses due to the large file size, maybe it doesn't...
I gave it a shot and the percentages in the profile are approximately the same (and peak memory usage was about double). I might end up having to parse the original binary format instead of the text format.
On 22 Jun 2011, at 15:53, Tristan Ravitch wrote:
On Wed, Jun 22, 2011 at 07:48:40AM +0100, Stephen Tetley wrote:
How fast is good old String rather than ByteString?
For lexing, String is a good fit (cheap deconstruction at the head / front). For your particular case, maybe it loses due to the large file size, maybe it doesn't...
I gave it a shot and the percentages in the profile are approximately the same (and peak memory usage was about double). I might end up having to parse the original binary format instead of the text format.
There is an old folklore that lexing is usually the most expensive phase of any compiler-like traversal. 50% of time and space expended on lexing was pretty common twenty years ago. Regards, Malcolm
On 26/06/2011, at 10:19 PM, Malcolm Wallace wrote:
There is an old folklore that lexing is usually the most expensive phase of any compiler-like traversal. 50% of time and space expended on lexing was pretty common twenty years ago.
Indeed it is old, but no, it isn't folklore, you'll find actual measurements in Per Brinch Hansen, and no, what was pretty common twenty years ago is not necessarily valid today. Depending on what you are compiling into what, you could be spending a lot of time reading, a lot of time writing, or a lot of time doing semantic analysis and optimisation. For example, lexing C++ is clearly a linear time operation, but type checking C++ is Turing complete (any computable function can be expressed as a C++ type checking problem). There's a Scheme compiler I know of where semantic analysis is at least O(N**3), N being the number of nodes in the AST. Also, much depends on the level at which you are doing I/O. Stuff layered on top of C stdio can be amazingly slow (thanks in part to libraries that acquire and release a lock for every call to getc() or putc()).
participants (4)
-
Malcolm Wallace -
Richard O'Keefe -
Stephen Tetley -
Tristan Ravitch