[perf] investigate performance issue in `convolution`

[harry0000]

Summary

When using the convolution function on Scala Native in problems from the AtCoder Library Practice Contest, some test cases result in an MLE (Memory Limit Exceeded). This issue does not occur on Dotty.

Observed Behavior

Environment:

AtCoder 2023/1 Language Update - Google スプレッドシート

• Scala 3.3.0 (Scala Native 0.4.14)
• openjdk-20-jdk-headless

Contest tasks

• F - Convolution

Submissions

https://atcoder.jp/contests/practice2/submissions/70192779

2024 ms / 1,086,252 KiB

case	result	time	memory
fft_killer_00	MLE	2024 ms	1086064 KiB
fft_killer_01	MLE	1985 ms	1086252 KiB
max_ans_zero_00	MLE	1990 ms	1086044 KiB
max_random_00	MLE	1988 ms	1086100 KiB
max_random_01	MLE	1982 ms	1086116 KiB
random_00	MLE	1851 ms	1079012 KiB
random_01	MLE	1900 ms	1064780 KiB

Hypotheses

• Memory leak in Scala Native generated code

Steps to Reproduce

Tasks

• Reproduce and confirm the issue
• Run profiling (JMH, async-profiler, etc.)
• Identify bottleneck
• Propose optimization approach
• Benchmark optimized version
• Create pull request

Related

• [math] convolution() #17
• [math] convolution() #17 (comment)
• [perf] investigate performance issue in LazySegtree with ModInt #20
• Runtime / Garbage Collector Settings — Scala Native 0.5.9 documentation
• 新ジャッジ運用開始のお知らせ - AtCoder
• AtCoder言語アップデート2024-2025 - Google スプレッドシート

Notes

Previously, the AtCoder administrators uploaded the test cases for the AtCoder Library Practice Contest to Dropbox for me, but the public access has been temporarily suspended, so the test data is currently unavailable.

• https://atcoder.jp/posts/1376
• https://atcoder.jp/posts/20

[harry0000]

#20 (comment)

Using FastScanner allows AC, but memory consumption persisted almost until the very end of MLE.

Scala 3.3.0 (Scala Native 0.4.14)

• https://atcoder.jp/contests/practice2/submissions/70284459
• 1720 ms / 1010812 KiB

[harry0000]

Excluding ModInt issues, the following changes are expected to yield improvements.

https://atcoder.jp/contests/practice2/submissions/70309343

1682 ms / 856984 KiB

private def convolutionFft[M <: Int](
  a: Array[ModInt[M]],
  b: Array[ModInt[M]]
)(using Modulus[M]): collection.IndexedSeq[ModInt[M]] = {
  val n = a.length
  val m = b.length
  val z = 1 << internal.ceilPow2(n + m - 1)

- val _a = java.util.Arrays.copyOf(a, z)
- foreach(n until z)(i => { _a(i) = ModInt() })
+ // a.resize(z);
+ val _a = Array.fill(z)(ModInt())
+ Array.copy(src = a, srcPos = 0, dest = _a, destPos = 0, length = n)
  butterfly(_a)

- val _b = java.util.Arrays.copyOf(b, z)
- foreach(m until z)(i => { _b(i) = ModInt() })
+ // b.resize(z);
+ val _b = Array.fill(z)(ModInt())
+ Array.copy(src = b, srcPos = 0, dest = _b, destPos = 0, length = m)
  butterfly(_b)

  foreach(0 until z)(i => { _a(i) *= _b(i) })
  butterflyInv(_a)

- val ans = java.util.Arrays.copyOf(_a, n + m - 1)
- foreach(z until (n + m - 1))(i => { ans(i) = ModInt() })
+ // a.resize(n + m - 1);
+ // for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
  val iz = ModInt(z).inv
- foreach(0 until (n + m - 1))(i => { ans(i) *= iz })
- ans
+ Array.tabulate(n + m - 1)(i => _a(i) * iz)
}