News for hackers. Stuff that matters.
Re:Strategies for Fast Lexers by SnowflakeOnIce on Monday July 14, 2025 @03:30PM (#44564311)
A simple hello world in C++ can pull in dozens of megabytes of header files.

Years back I worked at a C++ shop with a big codebase (hundreds of millions of LOC when you included vendored dependencies). Compile times there were sometimes dominated by parsing speed! Now, I don't remember the exact breakdown of lexing vs parsing, but I did look at it under a profiler.

It's very easy in C++ projects to structure your code such that you inadvertently cause hundreds of megabytes of sources to be parsed by each single #include. In such a case, lexing and parsing costs can dominate build times. Precompiled headers help, but not enough...

Re:Strategies for Fast Lexers by adev_ on Monday July 14, 2025 @03:46PM (#44564478)
> Now, I don't remember the exact breakdown of lexing vs parsing, but I did look at it under a profiler.

Lexing, parsing and even type checking are interleaved in most C++ compilers due to the ambiguous nature of many construct in the language.

It is very hard to profile only one of these in isolation. And even with compiler built-in instrumentation, the results are not very representative of the work done behind.

C++ compilers are amazing machines. They are blazing fast at parsing a language which is a nightmare of ambiguities. And they are like that mainly because how stupidly verbose and inefficient the C++ include system is.

Re:Strategies for Fast Lexers by SnowflakeOnIce on Monday July 14, 2025 @10:15PM (#44567241)
> Lexing, parsing and even type checking are interleaved in most C++ compilers due to the ambiguous nature of many construct in the language. > > It is very hard to profile only one of these in isolation. And even with compiler built-in instrumentation, the results are not very representative of the work done behind.

Indeed, precise cost attribution is difficult or impossible due to how the nature of the language imposes structure on industrial computers. But that aside, you still end up easily with hundreds of megabytes of source to deal with in each translation unit. I have so many scars from dealing with that...

Re:Strategies for Fast Lexers by viega on Tuesday July 15, 2025 @09:58AM (#44571239)
The computational complexity for lexing C++ is linear, but for parsing C++ it's super-linear, as will be many analyses. In practice, the lexing is in the noise for almost all compliers.
Re:Strategies for Fast Lexers by adev_ on Wednesday July 16, 2025 @02:04AM (#44579186)
Even the lexing is not strictly linear.

Good luck to naively differentiate if '>' is effectively a chevron operator or a shift operator '>>' in a random nested template expression like : 'set<vector<int>>'.