From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001
From: Charles Kerr <charles@charleskerr.com>
Date: Mon, 26 Oct 2020 16:53:25 -0500
Subject: perf: make GetPositionInfoSlow() faster
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Halve the number of lookups in ExtractLocationForJSFunction() by calling
GetPositionInfo() directly instead of making separate calls for column
and line number.

Improve the efficiency of position lookups in slow mode. The current
code does a linear walk through the source by calling String::Get() for
each character. This PR also does a linear walk, but avoids the overhead
of multiple Get() calls by pulling the String's flat content into a
local vector and walking through that.

Downstream Electron discussion of this can be found at
https://github.com/electron/electron/issues/24509

Change-Id: I22b034dc1bfe967164d2f8515a9a0c1d7f043c83
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2496065
Commit-Queue: Simon Zünd <szuend@chromium.org>
Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
Reviewed-by: Simon Zünd <szuend@chromium.org>
Cr-Commit-Position: refs/heads/master@{#70783}

diff --git a/AUTHORS b/AUTHORS
index 36abcfba774a448723a7fafd08ae2349bd2a045c..054e2bee4b6e2a5ee99cb3229c98095fce52f0a5 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -72,6 +72,7 @@ Bert Belder <bertbelder@gmail.com>
 Burcu Dogan <burcujdogan@gmail.com>
 Caitlin Potter <caitpotter88@gmail.com>
 Craig Schlenter <craig.schlenter@gmail.com>
+Charles Kerr <charles@charleskerr.com>
 Chengzhong Wu <legendecas@gmail.com>
 Choongwoo Han <cwhan.tunz@gmail.com>
 Chris Nardi <hichris123@gmail.com>
diff --git a/src/objects/objects.cc b/src/objects/objects.cc
index bb33b5d097afccd758b199cc335d45cb3d743faf..51b9caef8b3531804f8aa615a4c612c1c2bdf34d 100644
--- a/src/objects/objects.cc
+++ b/src/objects/objects.cc
@@ -4781,30 +4781,43 @@ bool Script::ContainsAsmModule() {
 }
 
 namespace {
-bool GetPositionInfoSlow(const Script script, int position,
-                         Script::PositionInfo* info) {
-  if (!script.source().IsString()) return false;
-  if (position < 0) position = 0;
 
-  String source_string = String::cast(script.source());
+template <typename Char>
+bool GetPositionInfoSlowImpl(const Vector<Char>& source, int position,
+                             Script::PositionInfo* info) {
+  if (position < 0) {
+    position = 0;
+  }
   int line = 0;
-  int line_start = 0;
-  int len = source_string.length();
-  for (int pos = 0; pos <= len; ++pos) {
-    if (pos == len || source_string.Get(pos) == '\n') {
-      if (position <= pos) {
-        info->line = line;
-        info->column = position - line_start;
-        info->line_start = line_start;
-        info->line_end = pos;
-        return true;
-      }
-      line++;
-      line_start = pos + 1;
+  const auto begin = std::cbegin(source);
+  const auto end = std::cend(source);
+  for (auto line_begin = begin; line_begin < end;) {
+    const auto line_end = std::find(line_begin, end, '\n');
+    if (position <= (line_end - begin)) {
+      info->line = line;
+      info->column = static_cast<int>((begin + position) - line_begin);
+      info->line_start = static_cast<int>(line_begin - begin);
+      info->line_end = static_cast<int>(line_end - begin);
+      return true;
     }
+    ++line;
+    line_begin = line_end + 1;
   }
   return false;
 }
+bool GetPositionInfoSlow(const Script script, int position,
+                         const DisallowHeapAllocation& no_gc,
+                         Script::PositionInfo* info) {
+  if (!script.source().IsString()) {
+    return false;
+  }
+  auto source = String::cast(script.source());
+  const auto flat = source.GetFlatContent(no_gc);
+  return flat.IsOneByte()
+             ? GetPositionInfoSlowImpl(flat.ToOneByteVector(), position, info)
+             : GetPositionInfoSlowImpl(flat.ToUC16Vector(), position, info);
+}
+
 }  // namespace
 
 bool Script::GetPositionInfo(int position, PositionInfo* info,
@@ -4826,7 +4839,9 @@ bool Script::GetPositionInfo(int position, PositionInfo* info,
 
   if (line_ends().IsUndefined()) {
     // Slow mode: we do not have line_ends. We have to iterate through source.
-    if (!GetPositionInfoSlow(*this, position, info)) return false;
+    if (!GetPositionInfoSlow(*this, position, no_allocation, info)) {
+      return false;
+    }
   } else {
     DCHECK(line_ends().IsFixedArray());
     FixedArray ends = FixedArray::cast(line_ends());
diff --git a/src/profiler/heap-snapshot-generator.cc b/src/profiler/heap-snapshot-generator.cc
index 0c5af20b017fe641ce3503357f4de19ee4e49632..b505bdab8102f238e53296b1ef86c7253ab3a731 100644
--- a/src/profiler/heap-snapshot-generator.cc
+++ b/src/profiler/heap-snapshot-generator.cc
@@ -578,9 +578,9 @@ void V8HeapExplorer::ExtractLocationForJSFunction(HeapEntry* entry,
   Script script = Script::cast(func.shared().script());
   int scriptId = script.id();
   int start = func.shared().StartPosition();
-  int line = script.GetLineNumber(start);
-  int col = script.GetColumnNumber(start);
-  snapshot_->AddLocation(entry, scriptId, line, col);
+  Script::PositionInfo info;
+  script.GetPositionInfo(start, &info, Script::WITH_OFFSET);
+  snapshot_->AddLocation(entry, scriptId, info.line, info.column);
 }
 
 HeapEntry* V8HeapExplorer::AddEntry(HeapObject object) {
