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

[Haojian Wu via Phabricator via cfe-commits]

hokein created this revision.
hokein added a reviewer: sammccall.
Herald added subscribers: kadircet, arphaman, jkorous, MaskRay, ioeric, 
ilya-biryukov.

This would buy us more memory. Using a 32-bits integer is enough for
most human-readable source code (up to 4M 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 |


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D53363

Files:
  clangd/index/Index.h
  clangd/index/YAMLSerialization.cpp
  unittests/clangd/FileIndexTests.cpp
  unittests/clangd/SerializationTests.cpp


Index: unittests/clangd/SerializationTests.cpp
===================================================================
--- unittests/clangd/SerializationTests.cpp
+++ unittests/clangd/SerializationTests.cpp
@@ -33,12 +33,8 @@
   Lang:            Cpp
 CanonicalDeclaration:
   FileURI:        file:///path/foo.h
-  Start:
-    Line: 1
-    Column: 0
-  End:
-    Line: 1
-    Column: 1
+  Start: 4096 # Line 1, Column 0
+  End: 4097 # Line 1, Column 1
 Origin:    4
 Flags:    1
 Documentation:    'Foo doc'
@@ -59,12 +55,8 @@
   Lang:            Cpp
 CanonicalDeclaration:
   FileURI:        file:///path/bar.h
-  Start:
-    Line: 1
-    Column: 0
-  End:
-    Line: 1
-    Column: 1
+  Start: 4096 # Line 1, Column 0
+  End: 4097 # Line 1, Column 1
 Flags:    2
 Signature:    '-sig'
 CompletionSnippetSuffix:    '-snippet'
@@ -75,12 +67,8 @@
   - Kind: 4
     Location:
       FileURI:    file:///path/foo.cc
-      Start:
-        Line: 5
-        Column: 3
-      End:
-        Line: 5
-        Column: 8
+      Start: 20483 # Line 5, Column 3
+      End: 20485 # Line5, Column 8
 )";
 
 MATCHER_P(ID, I, "") { return arg.ID == cantFail(SymbolID::fromStr(I)); }
Index: unittests/clangd/FileIndexTests.cpp
===================================================================
--- unittests/clangd/FileIndexTests.cpp
+++ unittests/clangd/FileIndexTests.cpp
@@ -32,10 +32,10 @@
 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 arg.Location.Start.Line == Range.start.line &&
+         arg.Location.Start.Column == Range.start.character &&
+         arg.Location.End.Line == Range.end.line &&
+         arg.Location.End.Column == Range.end.character;
 }
 MATCHER_P(FileURI, F, "") { return arg.Location.FileURI == F; }
 MATCHER_P(DeclURI, U, "") { return arg.CanonicalDeclaration.FileURI == U; }
Index: clangd/index/YAMLSerialization.cpp
===================================================================
--- clangd/index/YAMLSerialization.cpp
+++ clangd/index/YAMLSerialization.cpp
@@ -94,18 +94,37 @@
   uint8_t Origin = 0;
 };
 
-template <> struct MappingTraits<SymbolLocation::Position> {
-  static void mapping(IO &IO, SymbolLocation::Position &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) {
+    static_assert(
+        sizeof(Position) == sizeof(uint32_t),
+        "SymbolLocation::Position structure can not fit into a uint32_t.");
+    value = (Pos.Line << Position::ColumnBits) + Pos.Column;
   }
+
+  Position denormalize(IO &) {
+    Position Pos;
+    Pos.Line = value >> Position::ColumnBits;
+    Pos.Column = value & ((1 << Position::ColumnBits) - 1);
+    return Pos;
+  }
+
+  // Encode the SymbolLocation::Position:
+  // |  Line  | Column |
+  uint32_t value;
 };
 
 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->value);
+    MappingNormalization<NormalizedPosition, SymbolLocation::Position> NEnd(
+        IO, Value.End);
+    IO.mapRequired("End", NEnd->value);
   }
 };
 
Index: clangd/index/Index.h
===================================================================
--- clangd/index/Index.h
+++ clangd/index/Index.h
@@ -33,10 +33,17 @@
 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 as a 32-bits integer like below:
+  // |<--- 20 bits --->|<-12 bits->|
+  // |<---  Line   --->|<- Column->|
   struct Position {
-    uint32_t Line = 0; // 0-based
+    static constexpr int LineBits = 20;
+    static constexpr int ColumnBits = 12;
+
+    uint32_t Line : LineBits; // 0-based
     // Using UTF-16 code units.
-    uint32_t Column = 0; // 0-based
+    uint32_t Column : ColumnBits; // 0-based
   };
 
   // The URI of the source file where a symbol occurs.

_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits