Refactor and speed up HV3D by nabenabe0928 · Pull Request #6124 · optuna/optuna

nabenabe0928 · 2025-06-03T22:30:59Z

Note

This branch completed the script below in 31.02 seconds while the latest HEAD completed it in 36.84 seconds, resulting in 15.8% speedup.

Motivation

This PR is a followup of:

Add _compute_3d for hypervolume computation #6112

Description of the changes

Replace inline comments by # with """
Use more NumPy vectorization to speed up

In essence, here:

z_delta[np.arange(n), y_indices] = reference_point[2] - sorted_pareto_sols[:, 2]

Tweak a bit to reduce NumPy method calls to speed up

In essence, here:

z_delta = np.maximum.accumulate(np.maximum.accumulate(z_delta, axis=0), axis=1)

and here:

x_delta = np.concatenate([x_vals[1:], reference_point[:1]]) - x_vals
y_delta = np.concatenate([y_vals[1:], reference_point[1:2]]) - y_vals

Use more efficient NumPy methods, i.e., np.vdot(A, B) instead of np.sum(A * B) and np.concatenate instead of np.append.

Benchmarking Code

import optuna


def objective(trial: optuna.Trial) -> tuple[float, float, float]:
    x = trial.suggest_float("x", -5, 5)
    y = trial.suggest_float("y", -5, 5)
    return x**2 + y**2, (x - 2)**2 + (y - 2)**2, (x + 2)**2 + (y + 2)**2


sampler = optuna.samplers.TPESampler(seed=42)
study = optuna.create_study(sampler=sampler, directions=["minimize"]*3)
study.optimize(objective, n_trials=1000)
trials = study.trials
print((trials[-1].datetime_complete - trials[0].datetime_start).total_seconds())

y0z · 2025-06-04T04:12:25Z

@not522 @kAIto47802 Could you review this PR?

nabenabe0928 · 2025-06-04T04:29:41Z

optuna/_hypervolume/wfg.py

+    x_delta = np.concatenate([x_vals[1:], reference_point[:1]]) - x_vals
+    y_delta = np.concatenate([y_vals[1:], reference_point[1:2]]) - y_vals
+    # NOTE(nabenabe): `np.vdot(A, B)` is a faster calculation of `np.sum(A * B)`.
+    return np.vdot(x_delta[:, np.newaxis] * y_delta, z_delta)


It seems sorted_pareto_sols.shape[0] is < 25 due to the default_gamma.

In [1]: import numpy as np ...: ...: A = np.random.random((30, 30)) ...: %timeit np.sum(A * A) ...: %timeit np.vdot(A, A) 2.08 μs ± 32.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) 479 ns ± 6.95 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

nabenabe0928 · 2025-06-04T04:34:47Z

optuna/_hypervolume/wfg.py

+    y_indices, y_vals = _compress_coordinate(sorted_pareto_sols[:, 1])
+    z_delta = np.zeros((n, n), dtype=float)
+    z_delta[np.arange(n), y_indices] = reference_point[2] - sorted_pareto_sols[:, 2]
+    z_delta = np.maximum.accumulate(np.maximum.accumulate(z_delta, axis=0), axis=1)


In [2]: import numpy as np ...: ...: ...: A = np.random.random((30, 30)) ...: %timeit 1.0 - np.minimum.accumulate(np.minimum.accumulate(A, axis=0), axis=1 ...: ) ...: %timeit np.maximum.accumulate(np.maximum.accumulate(A, axis=0), axis=1) 7.16 μs ± 52.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) 6.61 μs ± 54.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

nabenabe0928 · 2025-06-04T04:40:29Z

optuna/_hypervolume/wfg.py

+    z_delta = np.zeros((n, n), dtype=float)
+    z_delta[np.arange(n), y_indices] = reference_point[2] - sorted_pareto_sols[:, 2]


In [4]: import numpy as np ...: ...: ...: n = 30 ...: a = np.random.random(n) ...: ...: def original(): ...: A = np.full((n, n), 1.0) ...: for i in range(n): ...: A[i, i] = a[i] ...: A = 1.0 - A ...: ...: def this_pr(): ...: inds = np.arange(n) ...: A = np.zeros((n, n), dtype=float) ...: A[inds, inds] = 1.0 - a ...: ...: %timeit original() ...: %timeit this_pr() 4.26 μs ± 41 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each) 1.63 μs ± 17.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

nabenabe0928 · 2025-06-04T04:50:18Z

optuna/_hypervolume/wfg.py

+    z_delta = np.maximum.accumulate(np.maximum.accumulate(z_delta, axis=0), axis=1)
+    # The x axis is already sorted, so no need to compress this coordinate.
+    x_vals = sorted_pareto_sols[:, 0]
+    x_delta = np.concatenate([x_vals[1:], reference_point[:1]]) - x_vals


This change makes only a slight speedup (2%).

In [5]: import numpy as np ...: ...: ...: a = np.random.random(30) ...: ...: def original(): ...: b = np.concatenate([a, [1.0]]) ...: b[1:] - b[:-1] ...: ...: def this_pr(): ...: np.concatenate([a[1:], [1.0]]) - a ...: ...: %timeit original() ...: %timeit this_pr() 972 ns ± 13.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) 952 ns ± 6.55 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

not522

Could you check my comments? They will improve the speed performance.

optuna/_hypervolume/wfg.py

Co-authored-by: Naoto Mizuno <naotomizuno@preferred.jp>

nabenabe0928 · 2025-06-04T05:52:33Z

optuna/_hypervolume/wfg.py

+    x_delta = np.concatenate([x_vals[1:], reference_point[:1]]) - x_vals
+    y_delta = np.concatenate([y_vals[1:], reference_point[1:2]]) - y_vals
+    # NOTE(nabenabe): Below is a faster calculation of `np.sum(A * B)`.
+    return np.dot(np.dot(z_delta, y_delta), x_delta)


In [3]: import numpy as np ...: ...: ...: a = np.random.random(30) ...: b = np.random.random(30) ...: C = np.random.random((30, 30)) ...: %timeit np.dot(np.dot(C, b), a) ...: %timeit np.vdot(a[:, None] * b, C) ...: %timeit np.sum(C * a[:, None] * b[None, :], axis=(0, 1)) 761 ns ± 13.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) 1.99 μs ± 28.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) 4.31 μs ± 4.69 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

not522

LGTM!

…-hv-3d

kAIto47802 · 2025-06-06T10:55:51Z

Thank you for your PR!
I've confirmed that this PR, along with the original one:

Add _compute_3d for hypervolume computation #6112,

indeed improves the benchmarking time.

I used the same objective function as you described in the initial comment.
The benchmarking result is as follows:

The result of the benchmarking. "Original Master" refers to the master branch before any changes, "Latest Master" refers to the current master branch including #6112, and "This PR" refers to the branch introduced in this pull request. The solid lines denote the mean, and the translucent areas denote the standard error, both computed over five independent runs with different random seeds.

kAIto47802

LGTM!

nabenabe0928 added 2 commits June 3, 2025 18:22

Refactor and speed up HV3D

68c1964

Refactor

bebeb82

nabenabe0928 marked this pull request as ready for review June 3, 2025 22:31

nabenabe0928 added 4 commits June 4, 2025 00:47

Add a note

c183c3b

Apply formatter

e05a034

Use vdot

fb3339c

Add note about vdot

2902bad

y0z assigned not522, sawa3030 and kAIto47802 and unassigned sawa3030 Jun 4, 2025

y0z added the enhancement Change that does not break compatibility and not affect public interfaces, but improves performance. label Jun 4, 2025

nabenabe0928 commented Jun 4, 2025

View reviewed changes

not522 reviewed Jun 4, 2025

View reviewed changes

optuna/_hypervolume/wfg.py Outdated Show resolved Hide resolved

optuna/_hypervolume/wfg.py Outdated Show resolved Hide resolved

nabenabe0928 and others added 4 commits June 4, 2025 07:23

Update optuna/_hypervolume/wfg.py

627cfe9

Co-authored-by: Naoto Mizuno <naotomizuno@preferred.jp>

Update optuna/_hypervolume/wfg.py

9fe7b4f

Co-authored-by: Naoto Mizuno <naotomizuno@preferred.jp>

Remove compression

d385b5e

Refactor

c3f714a

nabenabe0928 commented Jun 4, 2025

View reviewed changes

Refactor

3978db1

not522 approved these changes Jun 4, 2025

View reviewed changes

not522 removed their assignment Jun 4, 2025

Merge remote-tracking branch 'upstream/master' into code-fix/refactor…

0b43c33

…-hv-3d

kAIto47802 approved these changes Jun 6, 2025

View reviewed changes

nabenabe0928 merged commit 7228f77 into optuna:master Jun 6, 2025
14 checks passed

nabenabe0928 added this to the v4.4.0 milestone Jun 9, 2025

kAIto47802 removed their assignment Jun 11, 2025

nabenabe0928 mentioned this pull request Oct 16, 2025

Speedup of TPESampler in Optuna nabenabe0928/my-skills#4

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Refactor and speed up HV3D#6124

Refactor and speed up HV3D#6124
nabenabe0928 merged 12 commits intooptuna:masterfrom
nabenabe0928:code-fix/refactor-hv-3d

nabenabe0928 commented Jun 3, 2025 •

edited

Loading

Uh oh!

y0z commented Jun 4, 2025

Uh oh!

nabenabe0928 Jun 4, 2025 •

edited

Loading

Uh oh!

nabenabe0928 Jun 4, 2025

Uh oh!

nabenabe0928 Jun 4, 2025

Uh oh!

nabenabe0928 Jun 4, 2025 •

edited

Loading

Uh oh!

not522 left a comment

Uh oh!

Uh oh!

Uh oh!

nabenabe0928 Jun 4, 2025

Uh oh!

not522 left a comment

Uh oh!

kAIto47802 commented Jun 6, 2025 •

edited

Loading

Uh oh!

kAIto47802 left a comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

		z_delta = np.zeros((n, n), dtype=float)
		z_delta[np.arange(n), y_indices] = reference_point[2] - sorted_pareto_sols[:, 2]

Uh oh!

Conversation

nabenabe0928 commented Jun 3, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Motivation

Description of the changes

Uh oh!

y0z commented Jun 4, 2025

Uh oh!

nabenabe0928 Jun 4, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

nabenabe0928 Jun 4, 2025

Choose a reason for hiding this comment

Uh oh!

nabenabe0928 Jun 4, 2025

Choose a reason for hiding this comment

Uh oh!

nabenabe0928 Jun 4, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

not522 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

nabenabe0928 Jun 4, 2025

Choose a reason for hiding this comment

Uh oh!

not522 left a comment

Choose a reason for hiding this comment

Uh oh!

kAIto47802 commented Jun 6, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kAIto47802 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

nabenabe0928 commented Jun 3, 2025 •

edited

Loading

nabenabe0928 Jun 4, 2025 •

edited

Loading

nabenabe0928 Jun 4, 2025 •

edited

Loading

kAIto47802 commented Jun 6, 2025 •

edited

Loading