std.mem.findScalarLast is a scalar loop while it's counterpart std.mem.findScalarPos is vectorized.
The logic from findScalarPos prettiemuch maps 1:1 to findScalarLast
Implementation
pubfnfindScalarLast(comptimeT:type,slice:[]constT,value:T)?usize{varend=slice.len;if(use_vectors_for_comparisonand!std.debug.inValgrind()and!@inComptime()and(@typeInfo(T)==.intor@typeInfo(T)==.float)andstd.math.isPowerOfTwo(@bitSizeOf(T))){if(std.simd.suggestVectorLength(T))|block_len|{// See std.mem.findScalarPos for discussion of alignment and unrolling.constBlock=@Vector(block_len,T);if(2*block_len<=end){constmask:Block=@splat(value);while(true){inlinefor(0..2)|_|{end-=block_len;constblock:Block=slice[end..][0..block_len].*;constmatches=block==mask;if(@reduce(.Or,matches)){returnend+std.simd.lastTrue(matches).?;}}if(2*block_len>end)break;}}// {block_len, block_len / 2} checkinlinefor(0..2)|j|{constblock_x_len=block_len/(1<<j);comptimeif(block_x_len<4)break;constBlockX=@Vector(block_x_len,T);if(block_x_len<=end){end-=block_x_len;constmask:BlockX=@splat(value);constblock:BlockX=slice[end..][0..block_x_len].*;constmatches=block==mask;if(@reduce(.Or,matches)){returnend+std.simd.lastTrue(matches).?;}}}}}while(end!=0){end-=1;if(slice[end]==value)returnend;}returnnull;}Note that this uses <=, > and <= respectively for if (2 * block_len <= end) {, if (2 * block_len > end) break; and if (block_x_len <= end) {
findScalarLast uses <, >= and < which seems like a mistake since we can loop once more if size is divisible by block sizes exactly. I think findScalarLast should also be changed to have if (i + 2 * block_len <= slice.len) {, if (i + 2 * block_len > slice.len) break; and if (i + block_x_len <= slice.len) {
Implementation
pubfnfindScalarPos(comptimeT:type,slice:[]constT,start_index:usize,value:T)?usize{if(start_index>=slice.len)returnnull;vari:usize=start_index;if(use_vectors_for_comparisonand!std.debug.inValgrind()and// https://github.com/ziglang/zig/issues/17717!@inComptime()and(@typeInfo(T)==.intor@typeInfo(T)==.float)andstd.math.isPowerOfTwo(@bitSizeOf(T))){if(std.simd.suggestVectorLength(T))|block_len|{// For Intel Nehalem (2009) and AMD Bulldozer (2012) or later, unaligned loads on aligned data result// in the same execution as aligned loads. We ignore older arch's here and don't bother pre-aligning.//// Use `std.simd.suggestVectorLength(T)` to get the same alignment as used in this function// however this usually isn't necessary unless your arch has a performance penalty due to this.//// This may differ for other arch's. Arm for example costs a cycle when loading across a cache// line so explicit alignment prologues may be worth exploration.// Unrolling here is ~10% improvement. We can then do one bounds check every 2 blocks// instead of one which adds up.constBlock=@Vector(block_len,T);if(i+2*block_len<=slice.len){constmask:Block=@splat(value);while(true){inlinefor(0..2)|_|{constblock:Block=slice[i..][0..block_len].*;constmatches=block==mask;if(@reduce(.Or,matches)){returni+std.simd.firstTrue(matches).?;}i+=block_len;}if(i+2*block_len>slice.len)break;}}// {block_len, block_len / 2} checkinlinefor(0..2)|j|{constblock_x_len=block_len/(1<<j);comptimeif(block_x_len<4)break;constBlockX=@Vector(block_x_len,T);if(i+block_x_len<=slice.len){constmask:BlockX=@splat(value);constblock:BlockX=slice[i..][0..block_x_len].*;constmatches=block==mask;if(@reduce(.Or,matches)){returni+std.simd.firstTrue(matches).?;}i+=block_x_len;}}}}for(slice[i..],i..)|c,j|{if(c==value)returnj;}returnnull;}The test for findScalarPos may also be mirrored
Implementation
testfindScalarLast{constTypes=[_]type{u8,u16,u32,u64};inlinefor(Types)|T|{varmemory:[64/@sizeOf(T)]T=undefined;@memset(&memory,0xaa);memory[0]=0;for(1..memory.len+1)|i|{constslice=memory[0..i];trytesting.expectEqual(@as(usize,0),findScalarLast(T,slice,0).?);}}}The above function passes these tests; and the modified findScalarPos version passes it's tests too.
_std.mem.findScalarLast_ is a scalar loop while it's counterpart _std.mem.findScalarPos_ is vectorized.
The logic from _findScalarPos_ prettiemuch maps 1:1 to _findScalarLast_
<details>
<summary>Implementation</summary>
```zig
pub fn findScalarLast(comptime T: type, slice: []const T, value: T) ?usize {
var end = slice.len;
if (use_vectors_for_comparison and
!std.debug.inValgrind() and
!@inComptime() and
(@typeInfo(T) == .int or @typeInfo(T) == .float) and
std.math.isPowerOfTwo(@bitSizeOf(T)))
{
if (std.simd.suggestVectorLength(T)) |block_len| {
// See std.mem.findScalarPos for discussion of alignment and unrolling.
const Block = @Vector(block_len, T);
if (2 * block_len <= end) {
const mask: Block = @splat(value);
while (true) {
inline for (0..2) |_| {
end -= block_len;
const block: Block = slice[end..][0..block_len].*;
const matches = block == mask;
if (@reduce(.Or, matches)) {
return end + std.simd.lastTrue(matches).?;
}
}
if (2 * block_len > end) break;
}
}
// {block_len, block_len / 2} check
inline for (0..2) |j| {
const block_x_len = block_len / (1 << j);
comptime if (block_x_len < 4) break;
const BlockX = @Vector(block_x_len, T);
if (block_x_len <= end) {
end -= block_x_len;
const mask: BlockX = @splat(value);
const block: BlockX = slice[end..][0..block_x_len].*;
const matches = block == mask;
if (@reduce(.Or, matches)) {
return end + std.simd.lastTrue(matches).?;
}
}
}
}
}
while (end != 0) {
end -= 1;
if (slice[end] == value) return end;
}
return null;
}
```
</details>
Note that this uses `<=`, `>` and `<=` respectively for `if (2 * block_len <= end) {`, `if (2 * block_len > end) break;` and `if (block_x_len <= end) {`
_findScalarLast_ uses `<`, `>=` and `<` which seems like a mistake since we can loop once more if size is divisible by block sizes exactly. I think _findScalarLast_ should also be changed to have `if (i + 2 * block_len <= slice.len) {`, `if (i + 2 * block_len > slice.len) break;` and `if (i + block_x_len <= slice.len) {`
<details>
<Summary>Implementation</summary>
```zig
pub fn findScalarPos(comptime T: type, slice: []const T, start_index: usize, value: T) ?usize {
if (start_index >= slice.len) return null;
var i: usize = start_index;
if (use_vectors_for_comparison and
!std.debug.inValgrind() and // https://github.com/ziglang/zig/issues/17717
!@inComptime() and
(@typeInfo(T) == .int or @typeInfo(T) == .float) and std.math.isPowerOfTwo(@bitSizeOf(T)))
{
if (std.simd.suggestVectorLength(T)) |block_len| {
// For Intel Nehalem (2009) and AMD Bulldozer (2012) or later, unaligned loads on aligned data result
// in the same execution as aligned loads. We ignore older arch's here and don't bother pre-aligning.
//
// Use `std.simd.suggestVectorLength(T)` to get the same alignment as used in this function
// however this usually isn't necessary unless your arch has a performance penalty due to this.
//
// This may differ for other arch's. Arm for example costs a cycle when loading across a cache
// line so explicit alignment prologues may be worth exploration.
// Unrolling here is ~10% improvement. We can then do one bounds check every 2 blocks
// instead of one which adds up.
const Block = @Vector(block_len, T);
if (i + 2 * block_len <= slice.len) {
const mask: Block = @splat(value);
while (true) {
inline for (0..2) |_| {
const block: Block = slice[i..][0..block_len].*;
const matches = block == mask;
if (@reduce(.Or, matches)) {
return i + std.simd.firstTrue(matches).?;
}
i += block_len;
}
if (i + 2 * block_len > slice.len) break;
}
}
// {block_len, block_len / 2} check
inline for (0..2) |j| {
const block_x_len = block_len / (1 << j);
comptime if (block_x_len < 4) break;
const BlockX = @Vector(block_x_len, T);
if (i + block_x_len <= slice.len) {
const mask: BlockX = @splat(value);
const block: BlockX = slice[i..][0..block_x_len].*;
const matches = block == mask;
if (@reduce(.Or, matches)) {
return i + std.simd.firstTrue(matches).?;
}
i += block_x_len;
}
}
}
}
for (slice[i..], i..) |c, j| {
if (c == value) return j;
}
return null;
}
```
</details>
The test for _findScalarPos_ may also be mirrored
<details>
<summary>Implementation</summary>
```zig
test findScalarLast {
const Types = [_]type{ u8, u16, u32, u64 };
inline for (Types) |T| {
var memory: [64 / @sizeOf(T)]T = undefined;
@memset(&memory, 0xaa);
memory[0] = 0;
for (1..memory.len + 1) |i| {
const slice = memory[0..i];
try testing.expectEqual(@as(usize, 0), findScalarLast(T, slice, 0).?);
}
}
}
```
</details>
The above function passes these tests; and the modified _findScalarPos_ version passes it's tests too.