< 返回版块

chuqingq 发表于 2022-05-26 12:45

Tags:迭代器,边界检查

评论区

写评论
作者 chuqingq 2022-05-26 19:42

明白了,多谢多谢!

--
👇
Aya0wind: 迭代器不是避免边界检查,是避免额外的边界检查。
例如我们用C写一个程序遍历数组

for(int i = 0;i<length;i++)
    arr[i] = 0;

这里边界检查只有在for循环每次检查循环条件时对i是到达length的一个检查,这种检查是必须的。而对于arr[i]是没有检查的,直接按偏移量访问。
而如果我们在rust里写相同的代码

for i in 0..length{
    arr[i] = 0;
}

由于arr的长度并不一定真的是length,在C里我们是靠约定,如果arr不是length长度,那程序就会越界访问。而rust要求安全,在length并不等于arr长度的时候,也要能导致程序panic,所以在arr[i]时也要进行一次边界检查来查看i是否超出arr的长度。
这样在rust里就变成了对for循环变量是否到达length进行一次检查,然后对循环变量索引是否对于arr越界进行一次边界检查,就有了两次检查,如果我们能保证length就是arr的length,那这次多余的检查就是无必要的。
那迭代器是怎么避免的,rust迭代器是这么写的

for e in arr.iter_mut(){
    *e = 0;
}

因为迭代器是由arr创建的,那么就能保证只要在next中进行一次检查,如果返回的是Some(&e)就是必然有效的,那么第二次边界检查就可以省掉。
当然,第一种写法是可能被编译器优化掉的,例如编译器可以判定length就是arr的长度,不过这在代码复杂的时候并不够可靠,所以还是需要用迭代器来保证进行这种优化,这也是官方推荐使用迭代器来避免边界检查的原因。

Aya0wind 2022-05-26 16:19

迭代器不是避免边界检查,是避免额外的边界检查。
例如我们用C写一个程序遍历数组

for(int i = 0;i<length;i++)
    arr[i] = 0;

这里边界检查只有在for循环每次检查循环条件时对i是到达length的一个检查,这种检查是必须的。而对于arr[i]是没有检查的,直接按偏移量访问。
而如果我们在rust里写相同的代码

for i in 0..length{
    arr[i] = 0;
}

由于arr的长度并不一定真的是length,在C里我们是靠约定,如果arr不是length长度,那程序就会越界访问。而rust要求安全,在length并不等于arr长度的时候,也要能导致程序panic,所以在arr[i]时也要进行一次边界检查来查看i是否超出arr的长度。
这样在rust里就变成了对for循环变量是否到达length进行一次检查,然后对循环变量索引是否对于arr越界进行一次边界检查,就有了两次检查,如果我们能保证length就是arr的length,那这次多余的检查就是无必要的。
那迭代器是怎么避免的,rust迭代器是这么写的

for e in arr.iter_mut(){
    *e = 0;
}

因为迭代器是由arr创建的,那么就能保证只要在next中进行一次检查,如果返回的是Some(&e)就是必然有效的,那么第二次边界检查就可以省掉。
当然,第一种写法是可能被编译器优化掉的,例如编译器可以判定length就是arr的长度,不过这在代码复杂的时候并不够可靠,所以还是需要用迭代器来保证进行这种优化,这也是官方推荐使用迭代器来避免边界检查的原因。

作者 chuqingq 2022-05-26 14:48

谢谢! 可能是我没说清楚,我想问的不是迭代器是否可以无限或无界。

看到其他的书和帖子有说,index的访问方式要做bounds check,会有性能损失,而迭代器有针对性的优化,可以避免bounds check。 想学习一下迭代器是怎么做到的避免bounds check的?越具体越好,比如迭代器是不是内联了相关操作,是否还依赖了LLVM的优化,等等。

--
👇
苦瓜小仔: 假设你说的迭代器是指 Iterator trait,那么显然:

实现 Iterator trait 的类型可以是无界的 Infinity

在其唯一手动实现的 next 方法中,你想怎么进行边界检查都可以,当然,因为可以无界,所以你可以无需检查边界。

总而言之,Iterator trait 没有规定有边界。

此外标准库里抽象了“边界”的 trait 有:ExactSizeIteratorTrustedLen

但无论如何,边界检查的逻辑视类型而定,与什么 trait 无关 —— trait 只是逻辑抽象。

比如,对于 Range 系列的迭代器,看源码会发现一些私有 trait:

/// Specialization implementations for `Range`.
trait RangeIteratorImpl {
    type Item;

    // Iterator
    fn spec_next(&mut self) -> Option<Self::Item>;
    fn spec_nth(&mut self, n: usize) -> Option<Self::Item>;
    fn spec_advance_by(&mut self, n: usize) -> Result<(), usize>;

    // DoubleEndedIterator
    fn spec_next_back(&mut self) -> Option<Self::Item>;
    fn spec_nth_back(&mut self, n: usize) -> Option<Self::Item>;
    fn spec_advance_back_by(&mut self, n: usize) -> Result<(), usize>;
}

实际的边界检查就在这些私有 trait 的实现上。

苦瓜小仔 2022-05-26 13:30

假设你说的迭代器是指 Iterator trait,那么显然:

实现 Iterator trait 的类型可以是无界的 Infinity

在其唯一手动实现的 next 方法中,你想怎么进行边界检查都可以,当然,因为可以无界,所以你可以无需检查边界。

总而言之,Iterator trait 没有规定有边界。

此外标准库里抽象了“边界”的 trait 有:ExactSizeIteratorTrustedLen

但无论如何,边界检查的逻辑视类型而定,与什么 trait 无关 —— trait 只是逻辑抽象。

比如,对于 Range 系列的迭代器,看源码会发现一些私有 trait:

/// Specialization implementations for `Range`.
trait RangeIteratorImpl {
    type Item;

    // Iterator
    fn spec_next(&mut self) -> Option<Self::Item>;
    fn spec_nth(&mut self, n: usize) -> Option<Self::Item>;
    fn spec_advance_by(&mut self, n: usize) -> Result<(), usize>;

    // DoubleEndedIterator
    fn spec_next_back(&mut self) -> Option<Self::Item>;
    fn spec_nth_back(&mut self, n: usize) -> Option<Self::Item>;
    fn spec_advance_back_by(&mut self, n: usize) -> Result<(), usize>;
}

实际的边界检查就在这些私有 trait 的实现上。

1 共 4 条评论, 1 页