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

• Добавить свою публикацию
для этого требуется регистрация

Для чего нужна локальность по обращению

Локальность (обращений в память) (locality) - общее предположение о свойстве работы программ с данными. Заключается в том, что при обращении к некоторым данным велика вероятность, что в скором времени произойдет повторное обращение к тем же или расположенным рядом данным.

Локальность по обращению существенно влияет на скорость вычислений, особенно в циклах. Причина в cache компьютера. Кеш компьютера имеет наиболее быстрое время доступа из имеющихся вариантов. Поэтому следует писать алгоритмы с учётом кеша.

Где это может использоваться?

При расчётах вариантов себестоимости,  при расчётах загрузки многономенклатурного производства (Теория расписаний), в эвристических алгоритмах, в переборных задачах. Данные могут обрабатываться из файла в формате Extensible markup language последовательным чтением с диска, увеличивая время на постоянное дочитывание.

Что такое cache

 В сфере вычислительной обработки данных кэш – это высокоскоростной уровень хранения, на котором требуемый набор данных, как правило, временного характера. Доступ к данным на этом уровне осуществляется значительно быстрее, чем к основному месту их хранения.

Как устроена память компьютера:

1. Внутренняя память
   1. Уровень центрального процессора
      1. Регистры (хранение команд, время доступа меньше 0.1 нс)
      2. Кеш-память L1 (хранение блоков, время доступа 0.5-1 нс)
      3. Кеш-память L2 (хранение блоков, время доступа 2-7 нс)
   2. Уровень сетевой платы
      1. Кеш-память L3 (хранение блоков, время доступа 10-30 нс)
      2. Основная память (хранение страниц, время доступа 60-100 нс)
2. Внешняя память
   1. Остальная часть системы
      1. Дисковая кеш-память (хранение страниц, время доступа 50-100 мкс)
      2. Магнитные диски HDD (файлы, время доступа 50 мкс-20 мс)
      3. Оптические диски (файлы, время доступа >50 мс)
      4. Дискеты (файлы, время доступа в секундах)
      5. Магнитные ленты (файлы, время доступ в минутах)

Как работает локальность по обращению

Рассмотрим на примере такой структуры данных как многомерный массив. Ячейки массива хранятся в ОЗУ последовательно рядом. Строки многомерного массива могут находиться где угодно в ОЗУ, соотвественно ячейки одной строки хранятся рядом.
Так как работает локальность по обращению? Компьютер загружает соседние ячейки читаемой ячейки ОЗУ в кеш процессора. Далее следует вопрос: А как этим пользоваться? Ответ: Правильно работать с рассматриваемой структурой данных (многомерным массивом).

Пример работы с кешем и многомерным массивом, замеры производительности

Примечание. На результат влияет набор исходных данных.

Замер времени для 10 элементов

Замер времени для 100 элементов

Разница: 6 секунд.

Замер времени для 500 элементов

Разница: 2 минуты 3 секунды.

Замер времени для 1000 элементов

Разница: 10 минут.

Замер времени для 5000 элементов

Разница: около часа.

Замер времени для 100000 элементов

Разница: более трёх часов.

&НаКлиенте
Процедура Вариант1(Команда)
    
    Вычисления()
     
КонецПроцедуры

&НаСервереБезКонтекста
Процедура Вычисления()
    
    Перем ДеталиВСпецификациях, ЦеныПоставщиков, Итоговая, МаксимальныйИндекс, КоличествоЭлементов, ы, ё, я;
    
    КоличествоЭлементов = 1000;
    МаксимальныйИндекс = КоличествоЭлементов - 1;
    
     ДеталиВСпецификациях = Новый Массив(КоличествоЭлементов, КоличествоЭлементов);
     ЦеныПоставщиков = Новый Массив(КоличествоЭлементов, КоличествоЭлементов);
     Итоговая1 = Новый Массив(КоличествоЭлементов, КоличествоЭлементов);
     Итоговая2 = Новый Массив(КоличествоЭлементов, КоличествоЭлементов);
     
     Генератор = Новый ГенераторСлучайныхЧисел(100000);
     
     Для ё = 0 По МаксимальныйИндекс Цикл
         Для ы = 0 По МаксимальныйИндекс Цикл
            ДеталиВСпецификациях[ё][ы] = Генератор.СлучайноеЧисло(0, 50);
            ЦеныПоставщиков[ё][ы] = Генератор.СлучайноеЧисло(0, 999999) / Генератор.СлучайноеЧисло(1, 5);
             Итоговая1[ё][ы]  = 0;
             Итоговая2[ё][ы]  = 0
        КонецЦикла
    КонецЦикла;
    
    Вычисления1(Итоговая1, ДеталиВСпецификациях, ЦеныПоставщиков, МаксимальныйИндекс);
    Вычисления2(Итоговая2, ДеталиВСпецификациях, ЦеныПоставщиков, МаксимальныйИндекс)
     
КонецПроцедуры

&НаСервереБезКонтекста
Процедура Вычисления1(Итоговая, ДеталиВСпецификациях, ЦеныПоставщиков, МаксимальныйИндекс)
    
    Перем ы, ё, я;
     
     Для ы = 0 По МаксимальныйИндекс Цикл
         Для ё = 0 По МаксимальныйИндекс Цикл
             Для я = 0 По МаксимальныйИндекс Цикл
                 Итоговая[ы][я] = Итоговая[ы][я] + ДеталиВСпецификациях[ы][я] * ЦеныПоставщиков[ы][я] ;
            КонецЦикла
        КонецЦикла
    КонецЦикла
     
КонецПроцедуры

&НаСервереБезКонтекста
Процедура Вычисления2(Итоговая, ДеталиВСпецификациях, ЦеныПоставщиков, МаксимальныйИндекс)
    
    Перем  ы, ё, я;
     
     Для я = 0 По МаксимальныйИндекс Цикл
         Для ё = 0 По МаксимальныйИндекс Цикл
             Для ы = 0 По МаксимальныйИндекс Цикл
                 Итоговая[ы][я] = Итоговая[ы][я] + ДеталиВСпецификациях[ы][я] * ЦеныПоставщиков[ы][я] ;
            КонецЦикла
        КонецЦикла
    КонецЦикла
     
КонецПроцедуры