Реализация проверки границ цикла через прерывание переполнения - PullRequest
Новая
       43

Реализация проверки границ цикла через прерывание переполнения

1 голос
/ 10 ноября 2019

Сегодня у меня была идея, что можно реализовать цикл проверки границ для массива, создав счетчик итераций, который будет переполнен при последнем приращении и остановит выполнение на основе созданного прерывания переполнения.

Итак, предположим,у вас есть массив, например 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 делает что-то подобное, чтобы избежать нулевых проверок в сгенерированном во время выполнения коде. Как вы думаете, это будет выполнимо или это когда-либо рассматривалось / испытывалось какой-либо языковой средой исполнения?

1 Ответ

2 голосов
/ 10 ноября 2019

Принимая исключение очень медленно ;массив должен быть огромный , чтобы амортизировать дополнительные затраты на выход из цикла из-за сбоя, даже если вы можете сохранить инструкцию внутри цикла.

То, о чем вы, вероятно, читали, так это Проверка границ массива на 64-битном оборудовании с использованием аппаратной защиты памяти : завершение массива в конце виртуальной страницы и оставление следующей страницы без отображения . Виртуальная машина перехватывает SIGSEGV и доставляет исключение для гостевого кода, если когда-либо возникает исключение за пределами допустимого. Это устраняет необходимость проверки границ для случайных обращений, а не в цикле.

Этот метод вызывает только недопустимую ошибку страницы (segfault), когдагостевой код фактически принимает исключение границ массива, не для обычного случая выхода из цикла над массивом.

Давайте посмотрим, как ваша идея будет (не)работа:

Я думаю, что вы говорите о MIPS, где есть инструкция addi, которая перехватывает переполнение со знаком. (Вместо обычного addiu, который делает сложение без условной ловушки).

Большинство других ISA не имеют эффективного способа вызвать сбой при подписанном переполнении. x86 имеет into (прерывание OF установлено), но это отдельная инструкция от add, которая может устанавливать флаги. Вы могли бы также использовать условную ветвь вместо того, чтобы вызывать исключение и перехватывать его. Или просто используйте dec ecx / jnz в качестве счетчика цикла или подсчитайте отрицательный индекс до нуля и индекс с конца массива.

Я думаю, что MIPS потребует дополнительных addi внутри цикл для выделенного счетчика: единственный режим адресации MIPS reg+16_bit_constant.

Так что, если вы хотите перебрать массив, вам нужно увеличить указатель, иначе вам понадобится дополнительный add tmp, base, index внутриloop.

Цикл нуждается в инструкции перехода или перехода внизу, и это может быть условная ветвь без каких-либо дополнительных затрат . Таким образом, в 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], вы поднимаете проверку границ из цикла, чтобы поддерживать его таким образом. .

...