Форум TeamX
   Home   Members  
Pages: [1] |   Go Down
 
Author Topic: Проверка границ массива. Вопрос не по фолу.  (Read 913 times)
Jordan
Пользователь
Posts: 416

476228895
Проверка границ массива. Вопрос не по фолу.
« on: 10 January 2011, 16:32:07 »

Так как на форуме, есть программисты вопрос адресую к ним.

У меня тут вопрос о границах массива в программировании.

К примеру язык си не проверяет границы массива. Паскаль проверяет.

Я подхожу к вопросу, так ли падает производительность с проверкой?

Я как понял.

int Array[100];

Присваиваем (массив нумерауется с нуля.)

Array[0] = 5; всё нормально.

Array[239] = 5; ошибка и пошли пляски

Проверка происходит так

if (index < 0) and (index > 100) then
  Print(ошибка выхода за границ массива)
else
  Array[index] = 5;

Так вот на асме выглядит так(псевдо асм)

index = 5
IF index < 0   
IF index > 100 goto L2 4 инструкции 2 сравнения AND и JMP

То есть производительность падает в 4 раза. 400%

В инете пишут что в десятки раз падает производительность
Другие пишут, что проверки тормозять на несколько процентов

Как выяснить? Объясните.

Это не холивар. Просто хочется разобраться.

Воспрянет Россия, из праха отцов
Расправятся крылья, миллионов сердец
Поднимут все головы и грудью вздохнут
И громка скажут, что пришли
Мы пришли, со столетней войны
Jordan
Пользователь
Posts: 416

476228895
Re: Проверка границ массива. Вопрос не по фолу.
« Reply #1 on: 10 January 2011, 17:00:54 »

Немного разобрался.

Вот код

Quote

{$mode delphi}
program pidigits_example;

 function RDTSC: UInt64; register;
 asm
   rdtsc
 end;

var
 count : UInt64;
 A: array[1..100] of integer;
 i: integer;
 Start  : UInt64;
 Finish : UInt64;
 
 
begin

{$R+}
  Start := RDTSC;
    for i := 1 to 100 do
    begin
    A := 5;
    end;
  Finish := RDTSC;
WriteLn('count = ', Finish - Start);


{$R-}

  Start := RDTSC;
    for i := 1 to 100 do
    begin
    A := 5;
    end;
  Finish := RDTSC;
WriteLn('count = ', Finish - Start);
end.


Microsoft Windows XP [Версия 5.1.2600]
(С) Корпорация Майкрософт, 1985-2001.

D:\FPC\2.4.0\1>1
count = 1990  с проверкой
count = 1644  без проверки

D:\FPC\2.4.0\1>1
count = 2611  с проверкой
count = 1794  без проверки

D:\FPC\2.4.0\1>1
count = 2760  с проверкой
count = 2358  без проверки

D:\FPC\2.4.0\1>
D:\FPC\2.4.0\1>1
count = 2714  с проверкой
count = 1690  без проверки

D:\FPC\2.4.0\1>1
count = 2565  с проверкой
count = 1633  без проверки

D:\FPC\2.4.0\1>1
count = 2461  с проверкой
count = 1736  без проверки

D:\FPC\2.4.0\1>1
count = 2450 с проверкой
count = 1771  без проверки

D:\FPC\2.4.0\1>1
count = 2495  с проверкой
count = 1702  без проверки

D:\FPC\2.4.0\1>1
count = 1989  с проверкой
count = 1702  без проверки

D:\FPC\2.4.0\1>
D:\FPC\2.4.0\1>1
count = 2438  с проверкой
count = 1702  без проверки

D:\FPC\2.4.0\1>1
count = 2783  с проверкой
count = 1748  без проверки


Если округлить то 2 раза медленне. Либо это так, либо я не правильно измерю.

Воспрянет Россия, из праха отцов
Расправятся крылья, миллионов сердец
Поднимут все головы и грудью вздохнут
И громка скажут, что пришли
Мы пришли, со столетней войны
Jordan
Пользователь
Posts: 416

476228895
Re: Проверка границ массива. Вопрос не по фолу.
« Reply #2 on: 10 January 2011, 18:47:36 »

Удалите тему. Тема ни к месту и я разобрался.

Воспрянет Россия, из праха отцов
Расправятся крылья, миллионов сердец
Поднимут все головы и грудью вздохнут
И громка скажут, что пришли
Мы пришли, со столетней войны
KLIMaka
Пользователь
Posts: 72


Re: Проверка границ массива. Вопрос не по фолу.
« Reply #3 on: 10 January 2011, 19:10:41 »

Во-первых не совсем корректный тест. 100 элементов - это слишком мало для современных компьютеров. Эта программа выполняется слишком быстро и слишком многое может повлиять на время ее выполнения. Да и к тому же 20% отклонение от среднего значения - признак того, что эти данные скорее случайны. Но даже увеличение количества элементов массива ничего полезного тебе не даст. Этому есть как минимум две причины:
1) Компилятор. Не знаю как в паскале, но в С++ такой код вполне может дать count по нулям в обоих случаях. Все потому, что циклы не влияют на поток выполнения и они просто будут выброшены. Но даже если добавить в конец программы вывод на печать всего массива, то компилятор циклы вполне сможет заменить на вызов memset, часто усиленный SSE инструкциями, и как следствие выполняться они будут одинаково быстро, т.к. границы массивов заданы статически.
2) Архитектура же тоже может сыграть важную роль. Существует множество техник, сводящих на нет различия между проверяемым и не проверяемым доступом. Это и трэйс-кеши, и статическое предсказывание переходов, и дополнительные конвейеры.

Так что толку что то мерить, тем более на таких синтетических примерах ровно ноль. В каждом конкретном случае будет свой конкретный результат. Но очевидно, что проверка границ требует неких затрат, но эти затраты могу быть настолько ничтожны, что их можно игнорировать.
Wasteland Ghost
Администратор
Posts: 869

Маленькое Злое Привидение


Re: Проверка границ массива. Вопрос не по фолу.
« Reply #4 on: 10 January 2011, 23:16:12 »

На сях есть такая вещь как assert.
Ray
Глобальный модератор
Posts: 220

336150559
Re: Проверка границ массива. Вопрос не по фолу.
« Reply #5 on: 11 January 2011, 00:14:23 »

Я вам больше скажу. Когда писал патч для передвижения по карте мира, натолкнулся на всем известный факт (но не мне тогда), что системный таймер в винде может давать погрешность до 20 милисекунд. Ну там были нюансы между TimeGetTime и GetTickCount, но это не суть важно... Погрешности есть и они много где задокументированы. На таком синтетическом тесте и с таким количеством элементов - это всё не имеет ни малейшего смысла.
Jordan
Пользователь
Posts: 416

476228895
Re: Проверка границ массива. Вопрос не по фолу.
« Reply #6 on: 11 January 2011, 00:46:44 »

Так я не время считал, а количество тактов.

Из вики

rdtsc (англ. Read Time Stamp Counter) — ассемблерная инструкция для платформы x86, читающая счётчик TSC (Time Stamp Counter) и возвращающая в регистрах EDX:EAX 64-битное количество тактов с момента последнего сброса процессора.

В современных процессорах Intel, счетчик TSC не зависит от использования технологий энергосбережения и увеличивается на 1 каждый такт, вне зависимости от того, работал ли процессор или находился в состоянии сна.

rdtsc чаще всего используется:
для точного измерения временных интервалов;
в антиотладочных приёмах;
как источник энтропии для генераторов псевдослучайных чисел.

Воспрянет Россия, из праха отцов
Расправятся крылья, миллионов сердец
Поднимут все головы и грудью вздохнут
И громка скажут, что пришли
Мы пришли, со столетней войны
KLIMaka
Пользователь
Posts: 72


Re: Проверка границ массива. Вопрос не по фолу.
« Reply #7 on: 11 January 2011, 01:12:19 »

Ну дело в том, что нет никакой гарантии, что все эти такты были потрачены именно на выполнение твоего кода, вытесняющая многозадачность делает свое темное дело...
Jordan
Пользователь
Posts: 416

476228895
Re: Проверка границ массива. Вопрос не по фолу.
« Reply #8 on: 11 January 2011, 01:22:02 »

Ясно. Но ведь даже без оптимизаций компилятора, разница с проверкой небольшая. По тестам максимум в 2 раза. Просто сколько не читал статей по си, пишут что код с проверкой выполняется намного дольше и так далее. Мне было интересно узнать.

Спасибо всем за ответы.

Воспрянет Россия, из праха отцов
Расправятся крылья, миллионов сердец
Поднимут все головы и грудью вздохнут
И громка скажут, что пришли
Мы пришли, со столетней войны
Pages: [1] |   Go Up