Optimize lld::elf::ScriptLexer::getLineNumber by avoiding repeated work

[ccross]

Summary

getLineNumber() was counting the number of line feeds from the start
of the buffer to the current token. For large linker scripts this
became a performance bottleneck. For one 4MB linker script over 4
minutes was spent in getLineNumber's StringRef::count.

Store the line number from the last token, and only count the additional
line feeds since the last token.

[MaskRay]

lld/ELF/ScriptLexer.cpp

65

the prevailing style is compact. You can move tokOffset immediately below StringRef tok and delete the extra empty lines

// For the first token, or when going backwards, start from the beginning of
// the buffer. If this token is after the previous token start from the previous token.
size_t line = 1;
size_t start = 0;
if (lastLineNumberOffset > 0 && tokOffset >= lastLineNumberOffset) {

[MaskRay]

Looks great!

[ccross]

Reorder variable definitions to reduce line count

[MaskRay]

I can commit this on your behalf:)

For one 4MB linker script over 4 minutes was spent in getLineNumber's StringRef::count.

Hmm... A 4MB linker script is weird.

[MaskRay]

@ccross How did you end up with a 4MB linker script? Something like .text : { input0(.text) input1(.text) input2(.text) } to reorder sections?

[ccross]

In D104137#2834729, @MaskRay wrote:

@ccross How did you end up with a 4MB linker script? Something like .text : { input0(.text) input1(.text) input2(.text) } to reorder sections?

I was experimenting with embedding a binary into another binary by converting the loadable sections into blocks of .WORD(0x....) in a linker script. I ended up needing an extra .s file to set the writable/executable flags on the resulting sections, so I moved the data back into the .s file and no longer have a 4MB linker script. If I could set the flags on sections created from a linker script I could handle the embedding entirely in the linker script.

lld/ELF/ScriptLexer.h

public:
   bool consumeLabel(StringRef tok);
   std::string getCurrentLocation();
 
   std::vector<MemoryBufferRef> mbs;
   std::vector<StringRef> tokens;
   bool inExpr = false;
   size_t pos = 0;
 
+  size_t lastLineNumber = 0;
+  size_t lastLineNumberOffset = 0;
+
 protected:
   MemoryBufferRef getCurrentMB();
 
 private:
   void maybeSplitExpr();
   StringRef getLine();
   size_t getLineNumber();
   size_t getColumnNumber();
 };
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/ScriptLexer.cpp

 }
 
 // Returns 1-based line number of the current token.
 size_t ScriptLexer::getLineNumber() {
   if (pos == 0)
     return 1;
   StringRef s = getCurrentMB().getBuffer();
   StringRef tok = tokens[pos - 1];
-  return s.substr(0, tok.data() - s.data()).count('\n') + 1;
+  const size_t tokOffset = tok.data() - s.data();
+
+  // For the first token, or when going backwards, start from the beginning of
+  // the buffer. If this token is after the previous token, start from the
+  // previous token.
+  size_t line = 1;
+  size_t start = 0;
+  if (lastLineNumberOffset > 0 && tokOffset >= lastLineNumberOffset) {
+    start = lastLineNumberOffset;
+    line = lastLineNumber;
+  }
+
+  line += s.substr(start, tokOffset - start).count('\n');
+
+  // Store the line number of this token for reuse.
+  lastLineNumberOffset = tokOffset;
+  lastLineNumber = line;
+
+  return line;
 }
 
 // Returns 0-based column number of the current token.
 size_t ScriptLexer::getColumnNumber() {
   StringRef tok = tokens[pos - 1];
   return tok.data() - getLine().data();
 }