News for hackers. Stuff that matters.
Re:Increasing the D Compiler Speed by Over 75% by shasta on Thursday July 25, 2013 @03:15PM (#6104359)
Walter, could you explain why lexing was a bottleneck? That's very surprising to me. You don't re-lex template instantiations do you?
Re:Increasing the D Compiler Speed by Over 75% by WalterBright on Thursday July 25, 2013 @03:29PM (#6104456)
Lexing has been a bottleneck in every compiler I've built. The only answer I have is that ASTs are a lot smaller than source code.

Templates are stored as ASTs. They are not re-lexed.

Re:Increasing the D Compiler Speed by Over 75% by acqq on Thursday July 25, 2013 @04:03PM (#6104613)
Do you consider lexing only "reading the file, finding out if the sequence of characters is the keyword of the literal or the comment" or something more? I admit I lex the source which is already in memory, and there lexing takes less than all other processing (in CPU use). Also in my case the source is always smaller in memory than any AST.
Re:Increasing the D Compiler Speed by Over 75% by WalterBright on Thursday July 25, 2013 @04:22PM (#6104725)
Lexing is converting the source text into a token stream.

If lexing takes relatively smaller times for you, perhaps you have bottlenecks in the later passes?

Re:Increasing the D Compiler Speed by Over 75% by shasta on Thursday July 25, 2013 @04:35PM (#6104803)
I'm just having a hard time understanding how you could be having complaints about the compile times if you have a fast lexer and that lexer is a significant percentage of the total time. Can't your lexer handle a million lines of code in a few seconds? How big are these code bases?
Re:Increasing the D Compiler Speed by Over 75% by WalterBright on Thursday July 25, 2013 @04:54PM (#6104908)
It does handle a million lines in a few seconds - it's just that the rest of the compiler's work goes even faster.

The top cycle sucker is Lexer::scan(). Here's the source:

https://github.com/D-Programming-Language/dmd/blob/master/sr...

See line 440. It's entirely possible I've missed something glaringly obvious - have a go at it and see if you spot anything.

Oh, and "complaints" is a relative term. DMD is incredibly fast at compiling compared to other compilers - it's just that I want it to go even faster. Anything less than instantaneous I regard as "needs improvement." When D gets a design win at a company, I'll often ask what put D out in front of the competition. "Compile speed" is usually mentioned. Compile speed has a huge effect on programmer productivity.

Re:Increasing the D Compiler Speed by Over 75% by marshray on Thursday July 25, 2013 @08:22PM (#6105871)
Note: I like the way you think!

You might eliminate a few per-token function calls and cache thrashing by making it less of a 'pull' tokenizer interface. I.e., instead of the (elegant) method having Lexer::scan(&t) scan and produce just one token, scan a batch of them at once and fill a contiguous array.

Also, your Token class looks like it might be 7 or 8 pointers big. Seems like that could probably slim down a bit.

Re:Increasing the D Compiler Speed by Over 75% by jeremiep on Thursday July 25, 2013 @05:52PM (#6105250)
Looks like the same kind of problem that plagues interpreter loops: that top-level switch statement is causing a branch misprediction on almost every hit.

The solution i've seen was to have each opcode handler determine what the next handler would be and directly jump there.

Re:Increasing the D Compiler Speed by Over 75% by acqq on Thursday July 25, 2013 @06:02PM (#6105277)
The problem is that most of the time the main switch of lex isn't entered in the loop, instead it is called from the many different points in the parser (a token is considered, something is done, then there's a call for a next token). The only case I see at the moment where there's loop over the switch is when doing the whitespaces, that can maybe be slightly improved.

The whole topic of lexing turning out to be slow is really a thing that should be measured. Really intriguing.

Re:Increasing the D Compiler Speed by Over 75% by nkurz on Thursday July 25, 2013 @07:59PM (#6105770)
Glancing at the source, I think the whitespace parsing could be improved. Since whitespace will rarely if ever (?) be followed by more whitespace, and since most other things are likely to be followed by whitespace, just having both "parse_expecting_whitespace()" and "parse_probably_not_whitespace()" should improve the prediction.

Other tokens probably have similar but less strong "preferences". It's possible that a smart enough branch predictor will learn these on its own, but changing things so that each token ends with its own predicted branch would likely be a win.

Since the branch predictor uses the address of the branch as the 'key', the general goal is to have a separate branch instruction (if, switch) in each place where the probabilities are different enough to favor a different prediction. A wrong prediction costs about 15 cycles, but a correctly predicted branch costs less than 1, so you can put in quite a lot of these and still come out ahead.

Perhaps just ending every token handler with a best guess at what comes next?

  if (T->ptr[0] == most_likely_next) 
    handle_most_likely_next(T);
  else scan(T);
I don't have the syntax in my head, by I think you can use 'perf' to record mispredicted indirect branches and then display that sorted by caller.
Re:Increasing the D Compiler Speed by Over 75% by acqq on Thursday July 25, 2013 @08:21PM (#6105867)
In every line there are more consecutive whitespaces at the begining unless the code isn't indented.
Re:Increasing the D Compiler Speed by Over 75% by nkurz on Thursday July 25, 2013 @09:37PM (#6106117)
Great, that sounds like a fine opportunity for a "best guess": if newline, expect whitespace. Currently, I'd guess that 'whitespace except newline' is the default prediction for the switch() at line 451. I'd also guess that if not followed by a space or tab, a newline is frequently followed by another newline.

Maybe you could combine the case statements for space and newline, and do a branchless 'cmov' to increment loc.linenum if the match was a newline? This could be combined with loop to grab all the whitespace/newlines in one if you think whitespace is occurs in clumps.

Re:Increasing the D Compiler Speed by Over 75% by acqq on Friday July 26, 2013 @02:12AM (#6106872)
FWIW I'd never do a CPU dependent asm code in the lex.
Re:Increasing the D Compiler Speed by Over 75% by nkurz on Friday July 26, 2013 @08:13AM (#6107746)
I played with how to phrase that. You don't need to actually use a CMOV, just write code that allows your compiler to use one if supported.

  int tmp = real;
  if (foo == bar) {
    tmp = newval;
  }
  real = tmp;
I've seen it referred to as a 'hammock'[1], and at least for GCC and ICC it usually is a strong enough hint.

[1] http://people.engr.ncsu.edu/ericro/publications/conference_M...

Re:Increasing the D Compiler Speed by Over 75% by jeremiep on Thursday July 25, 2013 @06:35PM (#6105416)
Indeed. At the very least, that scan() function could be broken down into smaller parts to be individually profiled.
Re:Increasing the D Compiler Speed by Over 75% by acqq on Friday July 26, 2013 @09:48AM (#6108156)
I did the small statistics of the lexer.c and considered it an example of the input. You have there some 3050 lines 90KB, inside of the file there are 44K space (chr(32)) characters, giving on average more than 10 spaces per line. To process the indentation spaces faster I'd try reading them in the loop after the nl something like:

    case '\n':
       char* t = p + 1; // skip the nl
       while ( *t == ' ' ) // skip the indent spaces
           t++;            // while avoiding the big switch
       p = t; 
       continue;
I don't know if it's worth, but seems a good compromise.
Re:Increasing the D Compiler Speed by Over 75% by shasta on Thursday July 25, 2013 @10:45PM (#6106283)
This sounds like a good problem to have! Your compiler must be blazing fast. Does it remain so fast with full optimizations turned on? Thanks for the answers.
Re:Increasing the D Compiler Speed by Over 75% by acqq on Thursday July 25, 2013 @05:18PM (#6105064)
Please excuse me for even asking, did you propagate your bump-the-pointer greedy allocator to the lexer (that is, what's behind "mem.malloc" in the code you linked to)? And do you have some idea why would lexing otherwise take so much time for you to notice?
Re:Increasing the D Compiler Speed by Over 75% by WalterBright on Thursday July 25, 2013 @05:52PM (#6105249)
Yes, but the lexer doesn't do too much allocating. I try to avoid allocing in the lexer because of speed issues.