C ++ Производительность структур, используемых в качестве безопасной упаковки массивов

Question

В C или C ++ нет проверки массивов за пределами. Один из способов обойти это - упаковать его в структуру:

struct array_of_foo{
  int length;
  foo *arr; //array with variable length.
};

Затем его можно инициализировать:

array_of_foo *ar(int length){
  array_of_foo *out = (array_of_foo*) malloc(sizeof(array_of_foo));
  out->arr = (foo*) malloc(length*sizeof(foo));
}

А затем получили доступ:

foo I(array_of_foo *ar, int ix){ //may need to be foo* I(...
   if(ix>ar->length-1){printf("out of range!\n")} //error
   return ar->arr[ix];
}

И наконец освободился:

void freeFoo(array_of_foo *ar){ //is it nessessary to free both ar->arr and ar?
  free(ar->arr); free(ar);
}

Таким образом, он может предупреждать программистов о выходе за пределы. Но существенно ли замедлит эту упаковку предварительное исполнение?

Answer 1

Вы можете протестировать его самостоятельно, но на некоторых машинах у вас могут возникнуть серьезные проблемы с производительностью при разных сценариях. Если вы зацикливаетесь на миллионах элементов, то проверка границ каждый раз приведет к многочисленным ошибкам кэша. Какое влияние это окажет, зависит от того, что делает ваш код. Опять же, вы можете проверить это довольно быстро.

Answer 2

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

Если у вас естьC-код, который вы хотели бы сделать более безопасным, вас может заинтересовать Cyclone .

Answer 3

В C ++ нет необходимости придумывать собственную неполную версию vector.(Чтобы проверить границы на vector, используйте .at() вместо []. Если вы выйдете за пределы, будет выброшено исключение.)

В C это не обязательно плохоидея, но я бы отбросил указатель в вашей функции инициализации и просто возвратил бы структуру.У него есть int и указатель, и он не будет очень большим, обычно не более чем в два раза больше указателя.Вы, вероятно, в любом случае не хотите, чтобы в ваших функциях доступа были случайные printf s, так как если вы выйдете за пределы, вы получите случайные сообщения, которые не будут очень полезны, даже если вы их ищите.

Answer 4

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

И просто ради этого:
- Вы также должны инициализировать поле длины в ar()
- Вы должны проверить ix < 0 в I()

Answer 5

Я согласен с рекомендацией std::vector.Кроме того, вы можете попробовать библиотеки boost :: array, которые включают полную (и протестированную) реализацию контейнеров массивов фиксированного размера:

http://svn.boost.org/svn/boost/trunk/boost/array.hpp