[compiler] Make the scheduler faster [v8/v8 : main]

0 views
Skip to first unread message

Sam Parker-Haynes (Gerrit)

unread,
Oct 17, 2025, 5:50:46 AM (6 days ago) Oct 17
to Nico Hartmann, V8 LUCI CQ, dmercadi...@chromium.org, v8-re...@googlegroups.com
Attention needed from Nico Hartmann

Sam Parker-Haynes voted Commit-Queue+1

Commit-Queue+1
Open in Gerrit

Related details

Attention is currently required from:
  • Nico Hartmann
Submit Requirements:
  • requirement is not satisfiedCode-Owners
  • requirement is not satisfiedCode-Review
  • requirement is not satisfiedReview-Enforcement
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
Gerrit-MessageType: comment
Gerrit-Project: v8/v8
Gerrit-Branch: main
Gerrit-Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
Gerrit-Change-Number: 7053404
Gerrit-PatchSet: 2
Gerrit-Owner: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Reviewer: Nico Hartmann <nicoha...@chromium.org>
Gerrit-Reviewer: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Attention: Nico Hartmann <nicoha...@chromium.org>
Gerrit-Comment-Date: Fri, 17 Oct 2025 09:50:40 +0000
Gerrit-HasComments: No
Gerrit-Has-Labels: Yes
unsatisfied_requirement
open
diffy

Nico Hartmann (Gerrit)

unread,
Oct 21, 2025, 10:50:01 AM (2 days ago) Oct 21
to Sam Parker-Haynes, V8 LUCI CQ, dmercadi...@chromium.org, v8-re...@googlegroups.com
Attention needed from Sam Parker-Haynes

Nico Hartmann added 1 comment

Patchset-level comments
File-level comment, Patchset 2 (Latest):
Nico Hartmann . resolved

Hey Sam: I'm sorry I haven't managed to review this CL yet. Will take a look tomorrow!

Open in Gerrit

Related details

Attention is currently required from:
  • Sam Parker-Haynes
Submit Requirements:
  • requirement is not satisfiedCode-Owners
  • requirement is not satisfiedCode-Review
  • requirement is not satisfiedReview-Enforcement
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
Gerrit-MessageType: comment
Gerrit-Project: v8/v8
Gerrit-Branch: main
Gerrit-Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
Gerrit-Change-Number: 7053404
Gerrit-PatchSet: 2
Gerrit-Owner: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Reviewer: Nico Hartmann <nicoha...@chromium.org>
Gerrit-Reviewer: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Attention: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Comment-Date: Tue, 21 Oct 2025 14:49:56 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: No
unsatisfied_requirement
open
diffy

Sam Parker-Haynes (Gerrit)

unread,
Oct 21, 2025, 11:05:39 AM (2 days ago) Oct 21
to Nico Hartmann, V8 LUCI CQ, dmercadi...@chromium.org, v8-re...@googlegroups.com
Attention needed from Nico Hartmann

Sam Parker-Haynes added 1 comment

Patchset-level comments
Nico Hartmann . resolved

Hey Sam: I'm sorry I haven't managed to review this CL yet. Will take a look tomorrow!

Sam Parker-Haynes

Okay, thanks! And just for context, it now seems fast enough to use at runtime and I'm seeing ~1.5% geomean improvement on my personal suite.

Open in Gerrit

Related details

Attention is currently required from:
  • Nico Hartmann
Submit Requirements:
  • requirement is not satisfiedCode-Owners
  • requirement is not satisfiedCode-Review
  • requirement is not satisfiedReview-Enforcement
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
Gerrit-MessageType: comment
Gerrit-Project: v8/v8
Gerrit-Branch: main
Gerrit-Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
Gerrit-Change-Number: 7053404
Gerrit-PatchSet: 2
Gerrit-Owner: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Reviewer: Nico Hartmann <nicoha...@chromium.org>
Gerrit-Reviewer: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Attention: Nico Hartmann <nicoha...@chromium.org>
Gerrit-Comment-Date: Tue, 21 Oct 2025 15:05:34 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: No
Comment-In-Reply-To: Nico Hartmann <nicoha...@chromium.org>
unsatisfied_requirement
open
diffy

Nico Hartmann (Gerrit)

unread,
Oct 22, 2025, 8:02:21 AM (yesterday) Oct 22
to Sam Parker-Haynes, V8 LUCI CQ, dmercadi...@chromium.org, v8-re...@googlegroups.com
Attention needed from Nico Hartmann

Nico Hartmann voted and added 4 comments

Votes added by Nico Hartmann

Code-Review+1

4 comments

Patchset-level comments
Nico Hartmann . resolved

LGTM except for a few nits

File src/compiler/backend/instruction-scheduler.cc
Line 21, Patchset 2 (Latest): std::optional<base::RandomNumberGenerator>(v8_flags.random_seed)) {}
Nico Hartmann . unresolved

nit: I think we don't need this, but we can just initialize it with the generator.

Line 32, Patchset 2 (Latest): auto it = waiting_.begin();
while (it != waiting_.end()) {
if (cycle >= (*it)->start_cycle()) {
ready_.push_back(*it);
it = waiting_.erase(it);
} else {
++it;
}
}
Nico Hartmann . unresolved

nit: Do you think it would make sense to write this in terms of standard algorithms? E.g.
```
auto IsReady = [cycle](ScheduleGraphNode* n) { return cycle >= n->start_cycle(); };
auto it = std::partition(waiting_.begin(), waiting_.end(), IsReady);
ready_.insert(ready_.end(), waiting_.begin(), it);
waiting_.erase(waiting_.begin(), it);
```
I'm not decided what's the better choice.

Line 62, Patchset 2 (Latest): int max_latency = 0;
auto best_candidate = ready_.begin();
for (auto it = ready_.begin(); it != ready_.end(); ++it) {
if ((*it)->total_latency() > max_latency) {
max_latency = (*it)->total_latency();
best_candidate = it;
}
}
Nico Hartmann . unresolved
nit:
```
auto best_candidate = std::max_element(ready_.begin(), ready_.end(),
[](auto l, auto r) { return l->total_latency() < r->total_latency(); });
```
Open in Gerrit

Related details

Attention is currently required from:
  • Nico Hartmann
Submit Requirements:
  • requirement satisfiedCode-Owners
  • requirement satisfiedCode-Review
  • requirement is not satisfiedNo-Unresolved-Comments
  • requirement satisfiedReview-Enforcement
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
Gerrit-MessageType: comment
Gerrit-Project: v8/v8
Gerrit-Branch: main
Gerrit-Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
Gerrit-Change-Number: 7053404
Gerrit-PatchSet: 2
Gerrit-Owner: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Reviewer: Nico Hartmann <nicoha...@chromium.org>
Gerrit-Reviewer: Sam Parker-Haynes <sam.p...@arm.com>
Gerrit-Attention: Nico Hartmann <nicoha...@chromium.org>
Gerrit-Comment-Date: Wed, 22 Oct 2025 12:02:16 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: Yes
satisfied_requirement
unsatisfied_requirement
open
diffy

Sam Parker-Haynes (Gerrit)

unread,
Oct 22, 2025, 8:57:40 AM (yesterday) Oct 22
to Nico Hartmann, V8 LUCI CQ, dmercadi...@chromium.org, v8-re...@googlegroups.com
Attention needed from Nico Hartmann

Sam Parker-Haynes added 3 comments

File src/compiler/backend/instruction-scheduler.cc
Line 21, Patchset 2: std::optional<base::RandomNumberGenerator>(v8_flags.random_seed)) {}
Nico Hartmann . resolved

nit: I think we don't need this, but we can just initialize it with the generator.

Sam Parker-Haynes

Done

Line 32, Patchset 2: auto it = waiting_.begin();

while (it != waiting_.end()) {
if (cycle >= (*it)->start_cycle()) {
ready_.push_back(*it);
it = waiting_.erase(it);
} else {
++it;
}
}
Nico Hartmann . resolved

nit: Do you think it would make sense to write this in terms of standard algorithms? E.g.
```
auto IsReady = [cycle](ScheduleGraphNode* n) { return cycle >= n->start_cycle(); };
auto it = std::partition(waiting_.begin(), waiting_.end(), IsReady);
ready_.insert(ready_.end(), waiting_.begin(), it);
waiting_.erase(waiting_.begin(), it);
```
I'm not decided what's the better choice.

Sam Parker-Haynes

Considering the pain I always encounter with iterators, this SGTM!

Line 62, Patchset 2: int max_latency = 0;

auto best_candidate = ready_.begin();
for (auto it = ready_.begin(); it != ready_.end(); ++it) {
if ((*it)->total_latency() > max_latency) {
max_latency = (*it)->total_latency();
best_candidate = it;
}
}
Nico Hartmann . resolved
nit:
```
auto best_candidate = std::max_element(ready_.begin(), ready_.end(),
[](auto l, auto r) { return l->total_latency() < r->total_latency(); });
```
Sam Parker-Haynes

Thanks.

Open in Gerrit

Related details

Attention is currently required from:
  • Nico Hartmann
Submit Requirements:
    • requirement satisfiedCode-Owners
    • requirement satisfiedCode-Review
    • requirement satisfiedReview-Enforcement
    Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
    Gerrit-MessageType: comment
    Gerrit-Project: v8/v8
    Gerrit-Branch: main
    Gerrit-Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
    Gerrit-Change-Number: 7053404
    Gerrit-PatchSet: 2
    Gerrit-Owner: Sam Parker-Haynes <sam.p...@arm.com>
    Gerrit-Reviewer: Nico Hartmann <nicoha...@chromium.org>
    Gerrit-Reviewer: Sam Parker-Haynes <sam.p...@arm.com>
    Gerrit-Attention: Nico Hartmann <nicoha...@chromium.org>
    Gerrit-Comment-Date: Wed, 22 Oct 2025 12:57:35 +0000
    satisfied_requirement
    open
    diffy

    Sam Parker-Haynes (Gerrit)

    unread,
    Oct 22, 2025, 10:21:17 AM (yesterday) Oct 22
    to Nico Hartmann, V8 LUCI CQ, dmercadi...@chromium.org, v8-re...@googlegroups.com
    Attention needed from Nico Hartmann

    Sam Parker-Haynes voted Commit-Queue+2

    Commit-Queue+2
    Open in Gerrit

    Related details

    Attention is currently required from:
    • Nico Hartmann
    Submit Requirements:
    • requirement satisfiedCode-Owners
    • requirement satisfiedCode-Review
    • requirement satisfiedReview-Enforcement
    Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
    Gerrit-MessageType: comment
    Gerrit-Project: v8/v8
    Gerrit-Branch: main
    Gerrit-Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
    Gerrit-Change-Number: 7053404
    Gerrit-PatchSet: 3
    Gerrit-Owner: Sam Parker-Haynes <sam.p...@arm.com>
    Gerrit-Reviewer: Nico Hartmann <nicoha...@chromium.org>
    Gerrit-Reviewer: Sam Parker-Haynes <sam.p...@arm.com>
    Gerrit-Attention: Nico Hartmann <nicoha...@chromium.org>
    Gerrit-Comment-Date: Wed, 22 Oct 2025 14:21:12 +0000
    Gerrit-HasComments: No
    Gerrit-Has-Labels: Yes
    satisfied_requirement
    open
    diffy

    V8 LUCI CQ (Gerrit)

    unread,
    Oct 22, 2025, 10:22:49 AM (yesterday) Oct 22
    to Sam Parker-Haynes, Nico Hartmann, dmercadi...@chromium.org, v8-re...@googlegroups.com

    V8 LUCI CQ submitted the change with unreviewed changes

    Unreviewed changes

    2 is the latest approved patch-set.
    The change was submitted with unreviewed changes in the following files:

    ```
    The name of the file: src/compiler/backend/instruction-scheduler.cc
    Insertions: 10, Deletions: 18.

    The diff is too large to show. Please review the diff.
    ```

    Change information

    Commit message:
    [compiler] Make the scheduler faster

    Fixup the instruction scheduler to be (~an order of magnitude) faster.
    This is achieved in several ways, mainly changing data structures:
    - Split nodes into two lists: waiting and ready.
    - We don't keep waiting or ready sorted, we just iterate through the
    ready list to find the longest latency.
    - Using an ZoneUnorderedMap, instead of ZoneMap, for operands_map.
    - Use a SmallZoneVector, instead of ZoneDeque, for successors which
    reduces the overhead of resizing.
    - Reserving enough space when constructing the graph.

    Other structural changes are:
    - Caching the result from GetInstructionFlags, as this was taking a
    significant amount of time, after being called many times for each
    instruction.
    - We no longer add the terminator to the graph as this caused far too
    many unnecessary edges. We want the terminator to be the last
    instruction, so we just append it to the, almost, final sequence.
    - The two SchedulingQueues have been combined and we just construct one
    per scheduler, not per call to Schedule.
    Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
    Reviewed-by: Nico Hartmann <nicoha...@chromium.org>
    Commit-Queue: Sam Parker-Haynes <sam.p...@arm.com>
    Cr-Commit-Position: refs/heads/main@{#103295}
    Files:
    • M src/compiler/backend/instruction-scheduler.cc
    • M src/compiler/backend/instruction-scheduler.h
    • M src/compiler/backend/instruction-selector.cc
    • M src/compiler/backend/instruction-selector.h
    • M src/compiler/backend/instruction.cc
    • M src/compiler/backend/instruction.h
    • M test/cctest/compiler/test-instruction-scheduler.cc
    Change size: L
    Delta: 7 files changed, 101 insertions(+), 162 deletions(-)
    Branch: refs/heads/main
    Submit Requirements:
    • requirement satisfiedCode-Review: +1 by Nico Hartmann
    Open in Gerrit
    Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. DiffyGerrit
    Gerrit-MessageType: merged
    Gerrit-Project: v8/v8
    Gerrit-Branch: main
    Gerrit-Change-Id: I8fa436589182a50cdbd5f600725b653e7cf05acc
    Gerrit-Change-Number: 7053404
    Gerrit-PatchSet: 4
    Gerrit-Owner: Sam Parker-Haynes <sam.p...@arm.com>
    Gerrit-Reviewer: Nico Hartmann <nicoha...@chromium.org>
    Gerrit-Reviewer: Sam Parker-Haynes <sam.p...@arm.com>
    open
    diffy
    satisfied_requirement
    Reply all
    Reply to author
    Forward
    0 new messages