[clangd] Encode Line/Column as a 32-bits integer.

[hokein]

Summary

This would buy us more memory. Using a 32-bits integer is enough for
most human-readable source code (up to 1M lines and 4K columns).

Previsouly, we used 8 bytes for a position, now 4 bytes, it would save
us 8 bytes for each Ref and each Symbol instance.

For LLVM-project binary index file, we save ~13% memory.

Before	After
412MB	355MB

[sammccall]

(I think your math is off in the description: 20 bits should be 1M lines, not 4M)
I think this is a win, as I think truncation will be rare and not terrible. We should document the intentions around truncation though.

Incidentally, this means replacing just the StringRef in SymbolLocation::Position with a char* would save another 13%, because that's also 8 bytes.
(Obviously we'd probably replace the other StringRefs too, but it gives a lower bound).

clangd/index/Index.h

37

I think it's enough to say "position is packed into 32 bits to save space".

It'd be useful to spell out the consequences in a second line.

40–50

(not sure these constants are needed as it stands - YAML shouldn't use them, see below)

52

If we overflow the columns, it would be much easier to recognize if the result is always e.g. 255, rather than an essentially random number from 0-255 (from modulo 256 arithmetic).

This would mean replacing the raw fields with setters/getters, which is obviously a more invasive change. What about a compromise: add the setters, and call them from the most important codepaths: SymbolCollector and Serialization.

clangd/index/YAMLSerialization.cpp

108

I don't think there's any reason to pack the YAML encoding.

[hokein]

Address review comments:

• handle overflowed cases, and added tests
• add getter/setters for line/column and clear all call sides

[hokein]

In D53363#1267628, @sammccall wrote:

(I think your math is off in the description: 20 bits should be 1M lines, not 4M)

Oops...Update the desccription.

I think this is a win, as I think truncation will be rare and not terrible. We should document the intentions around truncation though.

Incidentally, this means replacing just the StringRef in SymbolLocation::Position with a char* would save another 13%, because that's also 8 bytes.

Yeah, I have a rough patch for it, using char* will save us ~50MB memory, which will lead to ~300 MB memory usage in total.

(Obviously we'd probably replace the other StringRefs too, but it gives a lower bound).

clangd/index/Index.h

40–50

I think we need, for testing, for setters, rather than using magic number.

52

It seems reasonable to use maximum value if we encounter overflows.

This would mean replacing the raw fields with setters/getters, which is obviously a more invasive change. What about a compromise: add the setters, and call them from the most important codepaths: SymbolCollector and Serialization.

Actually, there is not too much usage of the raw fields in the source code, I'd prefer to use all setters/getters in all places (and it would make the code consistent and more safe). How about this plan?

1. I update the patch to change all raw fields usage to getters/setters, and keep these raw fields public
2. do a cleanup internally
3. make these raw fields private

clangd/index/YAMLSerialization.cpp

108

The YAML here is a bit tricky, the previous code could not compile because we can not bind bit-field to Non-const references, I added another traits to keep the original YAML encoding (which is more readable).

[sammccall]

Nice, just nits!

In D53363#1267721, @hokein wrote:

Yeah, I have a rough patch for it, using char* will save us ~50MB memory, which will lead to ~300 MB memory usage in total.

For just the StringRef in SymbolLocation::Position, or for all our strings?
If the latter, that seems too low, as we should save strictly more than this patch (unless I'm missing something about alignment/padding)

clangd/index/Index.h

38

nit: no "is", overflow is a verb

40–50

In that case I'd suggest static constexpr MaxLine = 1 << 20 - 1, MaxColumn = 1 << 12 - 1, as that's what the tests (and potentially some warning checks in the code later?) need, so we encapsulate a little more detail. But up to you.

(Writing 20 twice a couple of lines apart seems fine to me)

41

nit: define the trivial getters here so the compiler can always inline them.
(Setters seem fine out-of-line)

52

SGTM!

66–67

Why only using the getters on one side?

clangd/index/YAMLSerialization.cpp

108

I don't think specializing the traits for pair<uint32,uint32> is OK, specializing for common types we don't own is asking for ODR violations.

prefer to define an custom struct for this (in fact you do, so just map that struct instead of struct->P?)

111–129

please document why this normalization (YamlIO can't directly map bitfields)

116

no need for this assert

[hokein]

Address review comments.

[hokein]

In D53363#1267721, @hokein wrote:

Yeah, I have a rough patch for it, using char* will save us ~50MB memory, which will lead to ~300 MB memory usage in total.

For just the StringRef in SymbolLocation::Position, or for all our strings?
If the latter, that seems too low, as we should save strictly more than this patch (unless I'm missing something about alignment/padding)

This is just for the StringRef in Position, I think it matches our estimation.

More details coming:

• 6.4 million refs, 6.4m * 40 bytes = ~250MB
• 0.3 million symbols, 0.3m * 248 bytes = ~70MB

The original size of Ref (before any space optimization) is 40 bytes, we save 8 bytes per refs, 8*6.5 = ~50 MB; If we change all StringRef in Symbol to char*, which will save 64 bytes (8*8) per sym, 64*0.3v = ~19 MB, which doesn't gain as much as refs, as refs contributes more than 70% memory.

clangd/index/Index.h

66–67

Oops, I mis-thought the type of the right side LSP position, fixed.

clangd/FindSymbols.cpp

if (!Path) {
       log("Workspace symbol: Could not resolve path for URI '{0}' for symbol "
           "'{1}'.",
           Uri->toString(), Sym.Name);
       return;
     }
     Location L;
     L.uri = URIForFile((*Path));
     Position Start, End;
-    Start.line = CD.Start.Line;
-    Start.character = CD.Start.Column;
-    End.line = CD.End.Line;
-    End.character = CD.End.Column;
+    Start.line = CD.Start.line();
+    Start.character = CD.Start.column();
+    End.line = CD.End.line();
+    End.character = CD.End.column();
     L.range = {Start, End};
     SymbolKind SK = indexSymbolKindToSymbolKind(Sym.SymInfo.Kind);
     std::string Scope = Sym.Scope;
     StringRef ScopeRef = Scope;
     ScopeRef.consume_back("::");
     SymbolInformation Info = {Sym.Name, SK, L, ScopeRef};
 
     SymbolQualitySignals Quality;

clangd/XRefs.cpp

llvm::Optional<Location> toLSPLocation(const SymbolLocation &Loc,
   }
   auto Path = URI::resolve(*Uri, HintPath);
   if (!Path) {
     log("Could not resolve URI: {0}", Loc.FileURI);
     return llvm::None;
   }
   Location LSPLoc;
   LSPLoc.uri = URIForFile(*Path);
-  LSPLoc.range.start.line = Loc.Start.Line;
-  LSPLoc.range.start.character = Loc.Start.Column;
-  LSPLoc.range.end.line = Loc.End.Line;
-  LSPLoc.range.end.character = Loc.End.Column;
+  LSPLoc.range.start.line = Loc.Start.line();
+  LSPLoc.range.start.character = Loc.Start.column();
+  LSPLoc.range.end.line = Loc.End.line();
+  LSPLoc.range.end.character = Loc.End.column();
   return LSPLoc;
 }
 
 struct MacroDecl {
   StringRef Name;
   const MacroInfo *Info;
 };
 

clangd/index/Index.h

 #include <tuple>
 
 namespace clang {
 namespace clangd {
 
 struct SymbolLocation {
   // Specify a position (Line, Column) of symbol. Using Line/Column allows us to
   // build LSP responses without reading the file content.
+  //
+  // Position is encoded into 32 bits to save space.
+  // If Line/Column overflow, the value will be their maximum value.
   struct Position {
-    uint32_t Line = 0; // 0-based
+    void setLine(uint32_t Line);
+    uint32_t line() const { return Line; }
+    void setColumn(uint32_t Column);
+    uint32_t column() const { return Column; }
+
+    static constexpr uint32_t MaxLine = (1 << 20) - 1;
+    static constexpr uint32_t MaxColumn = (1 << 12) - 1;
+
+    // Clients should use getters and setters to access these members.
+    // FIXME: hide these members.
+    uint32_t Line : 20; // 0-based
     // Using UTF-16 code units.
-    uint32_t Column = 0; // 0-based
+    uint32_t Column : 12; // 0-based
   };
 
   // The URI of the source file where a symbol occurs.
   llvm::StringRef FileURI;
 
   /// The symbol range, using half-open range [Start, End).
   Position Start;
   Position End;
 
   explicit operator bool() const { return !FileURI.empty(); }
 };
 inline bool operator==(const SymbolLocation::Position &L,
                        const SymbolLocation::Position &R) {
-  return std::tie(L.Line, L.Column) == std::tie(R.Line, R.Column);
+  return std::make_tuple(L.line(), L.column()) ==
+         std::make_tuple(R.line(), R.column());
 }
 inline bool operator<(const SymbolLocation::Position &L,
                       const SymbolLocation::Position &R) {
-  return std::tie(L.Line, L.Column) < std::tie(R.Line, R.Column);
+  return std::make_tuple(L.line(), L.column()) <
+         std::make_tuple(R.line(), R.column());
 }
 inline bool operator==(const SymbolLocation &L, const SymbolLocation &R) {
   return std::tie(L.FileURI, L.Start, L.End) ==
          std::tie(R.FileURI, R.Start, R.End);
 }
 inline bool operator<(const SymbolLocation &L, const SymbolLocation &R) {
   return std::tie(L.FileURI, L.Start, L.End) <
          std::tie(R.FileURI, R.Start, R.End);

clangd/index/Index.cpp

 //===--- Index.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Index.h"
+#include "Logger.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
+constexpr uint32_t SymbolLocation::Position::MaxLine;
+constexpr uint32_t SymbolLocation::Position::MaxColumn;
+void SymbolLocation::Position::setLine(uint32_t L) {
+  if (L > MaxLine) {
+    log("Set an overflowed Line {0}", L);
+    Line = MaxLine;
+    return;
+  }
+  Line = L;
+}
+void SymbolLocation::Position::setColumn(uint32_t Col) {
+  if (Col > MaxColumn) {
+    log("Set an overflowed Column {0}", Col);
+    Column = MaxColumn;
+    return;
+  }
+  Column = Col;
+}
+
 raw_ostream &operator<<(raw_ostream &OS, const SymbolLocation &L) {
   if (!L)
     return OS << "(none)";
-  return OS << L.FileURI << "[" << L.Start.Line << ":" << L.Start.Column << "-"
-            << L.End.Line << ":" << L.End.Column << ")";
+  return OS << L.FileURI << "[" << L.Start.line() << ":" << L.Start.column()
+            << "-" << L.End.line() << ":" << L.End.column() << ")";
 }
 
 SymbolID::SymbolID(StringRef USR)
     : HashValue(SHA1::hash(arrayRefFromStringRef(USR))) {}
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolID &ID) {
   return OS << toHex(ID.raw());
 }

clangd/index/Serialization.cpp

 //  - StringRef fields encode as varint (index into the string table)
 //  - enums encode as the underlying type
 //  - most numbers encode as varint
 
 void writeLocation(const SymbolLocation &Loc, const StringTableOut &Strings,
                    raw_ostream &OS) {
   writeVar(Strings.index(Loc.FileURI), OS);
   for (const auto &Endpoint : {Loc.Start, Loc.End}) {
-    writeVar(Endpoint.Line, OS);
-    writeVar(Endpoint.Column, OS);
+    writeVar(Endpoint.line(), OS);
+    writeVar(Endpoint.column(), OS);
   }
 }
 
 SymbolLocation readLocation(Reader &Data, ArrayRef<StringRef> Strings) {
   SymbolLocation Loc;
   Loc.FileURI = Data.consumeString(Strings);
   for (auto *Endpoint : {&Loc.Start, &Loc.End}) {
-    Endpoint->Line = Data.consumeVar();
-    Endpoint->Column = Data.consumeVar();
+    Endpoint->setLine(Data.consumeVar());
+    Endpoint->setColumn(Data.consumeVar());
   }
   return Loc;
 }
 
 void writeSymbol(const Symbol &Sym, const StringTableOut &Strings,
                  raw_ostream &OS) {
   OS << Sym.ID.raw(); // TODO: once we start writing xrefs and posting lists,
                       // symbol IDs should probably be in a string table.

clangd/index/SymbolCollector.cpp

 
 // Return the symbol range of the token at \p TokLoc.
 std::pair<SymbolLocation::Position, SymbolLocation::Position>
 getTokenRange(SourceLocation TokLoc, const SourceManager &SM,
               const LangOptions &LangOpts) {
   auto CreatePosition = [&SM](SourceLocation Loc) {
     auto LSPLoc = sourceLocToPosition(SM, Loc);
     SymbolLocation::Position Pos;
-    Pos.Line = LSPLoc.line;
-    Pos.Column = LSPLoc.character;
+    Pos.setLine(LSPLoc.line);
+    Pos.setColumn(LSPLoc.character);
     return Pos;
   };
 
   auto TokenLength = clang::Lexer::MeasureTokenLength(TokLoc, SM, LangOpts);
   return {CreatePosition(TokLoc),
           CreatePosition(TokLoc.getLocWithOffset(TokenLength))};
 }
 

clangd/index/YAMLSerialization.cpp

 //===----------------------------------------------------------------------===//
 
 #include "Index.h"
 #include "Serialization.h"
 #include "Trace.h"
 #include "dex/Dex.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/YAMLTraits.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdint>
 
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Symbol::IncludeHeaderWithReferences)
 LLVM_YAML_IS_SEQUENCE_VECTOR(clang::clangd::Ref)
 
 namespace {
 using RefBundle =
     std::pair<clang::clangd::SymbolID, std::vector<clang::clangd::Ref>>;
 // This is a pale imitation of std::variant<Symbol, RefBundle>
 struct VariantEntry {
   llvm::Optional<clang::clangd::Symbol> Symbol;
   llvm::Optional<RefBundle> Refs;
 };
+// A class helps YAML to serialize the 32-bit encoded position (Line&Column),
+// as YAMLIO can't directly map bitfields.
+struct YPosition {
+  uint32_t Line;
+  uint32_t Column;
+};
+
 } // namespace
 namespace llvm {
 namespace yaml {
 
 using clang::clangd::Ref;
 using clang::clangd::RefKind;
 using clang::clangd::Symbol;
 using clang::clangd::SymbolID;
NormalizedSymbolOrigin(IO &, SymbolOrigin O) {
     Origin = static_cast<uint8_t>(O);
   }
 
   SymbolOrigin denormalize(IO &) { return static_cast<SymbolOrigin>(Origin); }
 
   uint8_t Origin = 0;
 };
 
-template <> struct MappingTraits<SymbolLocation::Position> {
-  static void mapping(IO &IO, SymbolLocation::Position &Value) {
+template <> struct MappingTraits<YPosition> {
+  static void mapping(IO &IO, YPosition &Value) {
     IO.mapRequired("Line", Value.Line);
     IO.mapRequired("Column", Value.Column);
   }
 };
 
+struct NormalizedPosition {
+  using Position = clang::clangd::SymbolLocation::Position;
+  NormalizedPosition(IO &) {}
+  NormalizedPosition(IO &, const Position &Pos) {
+    P.Line = Pos.line();
+    P.Column = Pos.column();
+  }
+
+  Position denormalize(IO &) {
+    Position Pos;
+    Pos.setLine(P.Line);
+    Pos.setColumn(P.Column);
+    return Pos;
+  }
+  YPosition P;
+};
+
 template <> struct MappingTraits<SymbolLocation> {
   static void mapping(IO &IO, SymbolLocation &Value) {
     IO.mapRequired("FileURI", Value.FileURI);
-    IO.mapRequired("Start", Value.Start);
-    IO.mapRequired("End", Value.End);
+    MappingNormalization<NormalizedPosition, SymbolLocation::Position> NStart(
+        IO, Value.Start);
+    IO.mapRequired("Start", NStart->P);
+    MappingNormalization<NormalizedPosition, SymbolLocation::Position> NEnd(
+        IO, Value.End);
+    IO.mapRequired("End", NEnd->P);
   }
 };
 
 template <> struct MappingTraits<SymbolInfo> {
   static void mapping(IO &io, SymbolInfo &SymInfo) {
     // FIXME: expose other fields?
     io.mapRequired("Kind", SymInfo.Kind);
     io.mapRequired("Lang", SymInfo.Lang);

unittests/clangd/FileIndexTests.cpp

 using testing::AllOf;
 using testing::Contains;
 using testing::ElementsAre;
 using testing::IsEmpty;
 using testing::Pair;
 using testing::UnorderedElementsAre;
 
 MATCHER_P(RefRange, Range, "") {
-  return std::tie(arg.Location.Start.Line, arg.Location.Start.Column,
-                  arg.Location.End.Line, arg.Location.End.Column) ==
-         std::tie(Range.start.line, Range.start.character, Range.end.line,
-                  Range.end.character);
+  return std::make_tuple(arg.Location.Start.line(), arg.Location.Start.column(),
+                         arg.Location.End.line(), arg.Location.End.column()) ==
+         std::make_tuple(Range.start.line, Range.start.character,
+                         Range.end.line, Range.end.character);
 }
 MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
 MATCHER_P(DeclURI, U, "") { return arg.CanonicalDeclaration.FileURI == U; }
 MATCHER_P(QName, N, "") { return (arg.Scope + arg.Name).str() == N; }
 
 namespace clang {
 namespace clangd {
 namespace {

unittests/clangd/IndexTests.cpp

 using namespace llvm;
 
 namespace clang {
 namespace clangd {
 namespace {
 
 MATCHER_P(Named, N, "") { return arg.Name == N; }
 MATCHER_P(RefRange, Range, "") {
-  return std::tie(arg.Location.Start.Line, arg.Location.Start.Column,
-                  arg.Location.End.Line, arg.Location.End.Column) ==
-         std::tie(Range.start.line, Range.start.character, Range.end.line,
-                  Range.end.character);
+  return std::make_tuple(arg.Location.Start.line(), arg.Location.Start.column(),
+                         arg.Location.End.line(), arg.Location.End.column()) ==
+         std::make_tuple(Range.start.line, Range.start.character,
+                         Range.end.line, Range.end.character);
 }
 MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
 
+TEST(SymbolLocation, Position) {
+  using Position = SymbolLocation::Position;
+  Position Pos;
+
+  Pos.setLine(1);
+  EXPECT_EQ(1u, Pos.line());
+  Pos.setColumn(2);
+  EXPECT_EQ(2u, Pos.column());
+
+  Pos.setLine(Position::MaxLine + 1); // overflow
+  EXPECT_EQ(Pos.line(), Position::MaxLine);
+  Pos.setColumn(Position::MaxColumn + 1); // overflow
+  EXPECT_EQ(Pos.column(), Position::MaxColumn);
+}
+
 TEST(SymbolSlab, FindAndIterate) {
   SymbolSlab::Builder B;
   B.insert(symbol("Z"));
   B.insert(symbol("Y"));
   B.insert(symbol("X"));
   EXPECT_EQ(nullptr, B.find(SymbolID("W")));
   for (const char *Sym : {"X", "Y", "Z"})
     EXPECT_THAT(B.find(SymbolID(Sym)), Pointee(Named(Sym)));

unittests/clangd/SymbolCollectorTests.cpp

 MATCHER_P(IncludeHeader, P, "") {
   return (arg.IncludeHeaders.size() == 1) &&
          (arg.IncludeHeaders.begin()->IncludeHeader == P);
 }
 MATCHER_P2(IncludeHeaderWithRef, IncludeHeader, References,  "") {
   return (arg.IncludeHeader == IncludeHeader) && (arg.References == References);
 }
 MATCHER_P(DeclRange, Pos, "") {
-  return std::tie(arg.CanonicalDeclaration.Start.Line,
-                  arg.CanonicalDeclaration.Start.Column,
-                  arg.CanonicalDeclaration.End.Line,
-                  arg.CanonicalDeclaration.End.Column) ==
-         std::tie(Pos.start.line, Pos.start.character, Pos.end.line,
+  return std::make_tuple(arg.CanonicalDeclaration.Start.line(),
+                         arg.CanonicalDeclaration.Start.column(),
+                         arg.CanonicalDeclaration.End.line(),
+                         arg.CanonicalDeclaration.End.column()) ==
+         std::make_tuple(Pos.start.line, Pos.start.character, Pos.end.line,
                          Pos.end.character);
 }
 MATCHER_P(DefRange, Pos, "") {
-  return std::tie(arg.Definition.Start.Line,
-                  arg.Definition.Start.Column, arg.Definition.End.Line,
-                  arg.Definition.End.Column) ==
-         std::tie(Pos.start.line, Pos.start.character, Pos.end.line,
+  return std::make_tuple(
+             arg.Definition.Start.line(), arg.Definition.Start.column(),
+             arg.Definition.End.line(), arg.Definition.End.column()) ==
+         std::make_tuple(Pos.start.line, Pos.start.character, Pos.end.line,
                          Pos.end.character);
 }
 MATCHER_P(RefCount, R, "") { return int(arg.References) == R; }
 MATCHER_P(ForCodeCompletion, IsIndexedForCodeCompletion, "") {
   return static_cast<bool>(arg.Flags & Symbol::IndexedForCodeCompletion) ==
          IsIndexedForCodeCompletion;
 }
 MATCHER(Deprecated, "") { return arg.Flags & Symbol::Deprecated; }
 MATCHER(RefRange, "") {
   const Ref &Pos = testing::get<0>(arg);
   const Range &Range = testing::get<1>(arg);
-  return std::tie(Pos.Location.Start.Line, Pos.Location.Start.Column,
-                  Pos.Location.End.Line, Pos.Location.End.Column) ==
-         std::tie(Range.start.line, Range.start.character, Range.end.line,
-                  Range.end.character);
+  return std::make_tuple(Pos.Location.Start.line(), Pos.Location.Start.column(),
+                         Pos.Location.End.line(), Pos.Location.End.column()) ==
+         std::make_tuple(Range.start.line, Range.start.character,
+                         Range.end.line, Range.end.character);
 }
 testing::Matcher<const std::vector<Ref> &>
 HaveRanges(const std::vector<Range> Ranges) {
   return testing::UnorderedPointwise(RefRange(), Ranges);
 }
 
 class ShouldCollectSymbolTest : public ::testing::Test {
 public: