Performance degradation when initializing arrays in loops

[kostya]

Describe the bug

In this benchmark: https://kostya.github.io/LangArena/
The AStarPathfinder benchmark executes in ~60s on:

I found that changing the init_scores function to an unsafe version reduces time to 3.3s (20x faster).

Here are the slow and fast functions from the source: https://github.com/kostya/LangArena/blob/d2e12f2e643ca69e93e635c5e0a8d13fad3722d3/v/astar_pathfinder.v#L169

// Slow version (~60s)
fn (mut b AStarPathfinder) init_scores(size int) {
    for i in 0 .. size {
        b.g_scores[i] = inf
        b.came_from[i] = -1
    }
}

// Fast version (~3.3s) - 20x faster
// fn (mut b AStarPathfinder) init_scores(size int) {
//     unsafe {
//         // Fill g_scores with inf
//         mut g_ptr := &b.g_scores[0]
//         for i in 0 .. size {
//             g_ptr[i] = inf
//         }
//
//         // Fill came_from with -1
//         mut c_ptr := &b.came_from[0]
//         for i in 0 .. size {
//             c_ptr[i] = -1
//         }
//     }
// }

I'm pretty sure this is unexpected behavior - the safe version shouldn't be 20x slower than the unsafe one for simple array initialization.

Reproduction Steps

git clone https://github.com/kostya/LangArena.git
cd LangArena/v
v install
./run AStarPathfinder

Expected Behavior

Fast version (~3.3s)

Current Behavior

Slow execution (~60s)

Possible Solution

use unsafe initialization

Additional Information/Context

No response

V version

V 0.5.0 6be2fbb

Environment details (OS name and version, etc.)

• MacOS
• Apple clang version 15.0.0 (clang-1500.3.9.4)

Note

You can use the 👍 reaction to increase the issue's priority for developers.

Please note that only the 👍 reaction to the issue itself counts as a vote.
Other reactions and those to comments will not be taken into account.

[JalonSolov]

Did you test using V regular syntax?

Instead of

fn (mut b AStarPathfinder) init_scores(size int) {
    for i in 0 .. size {
        b.g_scores[i] = inf
        b.came_from[i] = -1
    }
}

for those fields, use

fn (mut b AStarPathfinder) init_scores(size int) {
    b.g_scores = []int{len: size, init: inf}
    b.came_from = []int{len: size, init: -1}
}

No "Hacks" or special compiler flags needed.

[spytheman]

@kostya tag the slower function (that does not use unsafe{}), with:
@[direct_array_access] above it to speed it up.

V code that is not tagged that way, and is not inside unsafe, does bounds checking on each a[i] access, which can be heavy in tight loops.

TLDR: it is not a bug, the language just has chosen safety by default, and a way to opt out, where it matters (and the code was reviewed/validated before that).

[spytheman]

@JalonSolov b.g_scores = []int{len: size, init: inf} allocates a new array, which may or may not be what is needed

given that the question is about a program in a benchmark, probably not - it is better to be as close as possible to what other languages there are doing, and if they only do assignments in a loop for that case, adding an allocation would be counterproductive and misleading

[spytheman]

@kostya on my m1, before/after:

[spytheman]

a previous run was even faster:

start: 1770107383459
AStarPathfinder: OK in 3.954s
Summary: 3.9543s, 1, 1, 0
CPU: 98% 9.59s	Real: 10.28s	Elapsed: 0:10.28	RAM: 536560KB	./run AStarPathfinder

but I am not sure if it was because of the choosen seed, or because of some unrelated system load factor

[JalonSolov]

@kostya tag the slower function (that does not use unsafe{}), with: @[direct_array_access] above it to speed it up.

I specifically didn't mention the @[direct_array_access] attribute because of this line in the README for that repo:

"No "Hacks": Low-level tricks, impractical compiler flags (e.g., bounds check disabling), or non-standard libraries are intentionally avoided."

[kostya]

@kostya tag the slower function (that does not use unsafe{}), with: @[direct_array_access] above it to speed it up.

I specifically didn't mention the @[direct_array_access] attribute because of this line in the README for that repo:

"No "Hacks": Low-level tricks, impractical compiler flags (e.g., bounds check disabling), or non-standard libraries are intentionally avoided."

Yes, this is the preferred approach.

TLDR: it is not a bug, the language just has chosen safety by default, and a way to opt out, where it matters (and the code was reviewed/validated before that).

By the way, this behavior is still somewhat unexpected for me. Here's a suggestion:
Since V knows that i is within bounds in this loop, could it apply @[direct_array_access] automatically?

	for i in 0 .. size {
		b.g_scores[i] = inf
		b.came_from[i] = -1
	}

[kostya]

fixed by, thanks

fn (mut b AStarPathfinder) init_scores(size int) {
	b.g_scores = []int{len: size, init: inf}
	b.came_from = []int{len: size, init: -1}
}

closing if it is expected.