1

我今天有一个想法，可以通过构造一个迭代计数器来在数组上实现边界检查循环，该计数器将在最后一个增量时溢出并根据生成的溢出中断停止执行。

所以假设你有一个数组，例如int[32]，你想迭代它。为了避免每次循环运行中的边界检查，您现在可以做的是为溢出中断注册一个中断处理程序并为该值分配一个寄存器MAX - 32。该寄存器在每次循环迭代运行时递增，最后一次迭代运行将溢出，即触发中断处理程序。假设中断处理程序可以增加原始函数的程序计数器，这种机制可以用来避免边界检查。

所以像这样的代码

for (int i = 0; i < array.length; i++) {
  // do something
}

可以像这样实现

// setup interrupt somehow
SOME_REGISTER = MAX - array.length;
while (true) {
  // do something
  SOME_REGISTER++;
}

我不知道这是否可行，但我听说 Java 正在做类似的事情来避免在运行时生成的代码中进行空检查。您认为这是可行的还是任何语言运行时都考虑过/尝试过？

4

1 回答 1

2

处理异常非常慢；即使您可以在循环中保存一条指令，数组也必须很大才能分摊因故障而离开循环的额外成本。

您可能已经读到的是使用硬件内存保护对 64 位硬件进行数组边界检查：使数组在虚拟页面的末尾结束，并让下一页未映射。如果发生越界异常，VM 会捕获 SIGSEGV 并将异常传递给来宾代码。 这消除了对随机访问的边界检查的需要，而不是循环检查。

此技术仅在来宾代码实际发生数组边界异常时导致无效页面错误（segfault），而不是在退出数组循环的正常情况下。

让我们看看您的想法将如何（不）起作用：

我认为您在谈论 MIPS，其中有一条addi指令可以捕获有符号溢出。addiu（而不是在没有条件陷阱的情况下进行加法的法线）。

大多数其他 ISA 没有任何有效的方法来解决签名溢出问题。x86 具有（设置了 OF 的中断），但这是与可能设置标志into的单独指令。add您不妨使用条件分支，而不是引发异常并捕获它。或者只是dec ecx / jnz用作循环计数器，或者将负索引向上计数到零并从数组末尾开始索引。

我认为 MIPS 需要一个额外的循环addi 内部用于专用计数器：MIPS 唯一的寻址模式是reg+16_bit_constant.

所以如果你想迭代一个数组，你需要一个指针增量，否则你需要一个额外add tmp, base, index的循环内部。

循环在底部需要跳转或分支指令，它可以是一个条件分支，基本上没有额外的成本。所以在 MIPS 中，你会在循环外计算数组的结尾，然后编写一个普通循环，如

    addu   $t5, $t0, $t4     ; t5 = int *endp = start + byte_length
.loop:                       ; do{
    addiu  $t0, $t0, 4         ;  p++
    lw     $t1, ($t0)          ; *p
    ...
    bne    $t0, $t5, .loop    ; }while(p != endp)

循环内没有浪费的指令。任何数组边界检查都可以在循环外完成，方法是检查endp数组末尾不超过一个。

（在现代 x86 上，cmp/jne等效地工作，解码为单个比较和分支微指令。许多其他 ISA 具有递减和分支或类似指令，允许计数器循环条件只有一个开销指令。）

i < array.length因为循环条件不仅仅是数组边界检查。

正如我上面所说，在一个简单的迭代循环中arr[i]，你将边界检查提升到循环之外，以保持它的效率。

于 2019-11-10T17:39:03.430 回答