ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничные кеши
15 сообщений из 15, страница 1 из 1
Тяпничные кеши
    #39510770
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Привет друзья!

Илья. Сова. Дима. И все-все другие!

В продолжение топика Cache miss/hit detector in Java .

Ввиду зафлуженности и различных противоречий я решил поднять отдельный топик с
вполне себе конкретными вопросами.

1) Кто из вас когда и как использовал оптимизации нацеленные на использование CPU Caches (L1/L2/L3) ?
2) Какое API вы при этом использовали?
3) Какое было железо?
4) Был ли полезный эффект?

Приветствуются не только истории разработки но и истории админские, оптимизации БД и истории
сетей и протоколов.

Ассемблер и С/С++ приветствуется. Хардкод! Moar хардкода!

Thnx & Go! Go!
...
Рейтинг: 0 / 0
25.08.2017, 20:40
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39510955
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Никого нет. Ну ладно.

Из Intel-овской документации по Performance. Существуют 4 инструкции
- prefetchnta
- prefetch0
- prefetch1
- prefetch2

полезные для сабж.

Дока у меня старая. И описывает архитектуру до Pentium III. Но новее никак не могу найти.
Так что если кто-то найдет - thnx.
...
Рейтинг: 0 / 0
26.08.2017, 17:18
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39510958
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Лет десять-двенадцать назад рассказывали мне историю про то, как после замены пень-четыре на экстремальный пень-четыре расчёт "одной важной задачи" стал выполняться за три с половиной часа вместо двадцати.
Правда, аналогичных "историй успеха" мне слышать не приходилось.
С другой стороны, исходя из своего сисадминского опыта, могу обоснованно утверждать, что не надо браться за тонкую оптимизацию, если у вас нет доступа ко всему целевому железу. Глупо профилировать код на MacBook Pro, если целевая система - какой-нибудь Intel Phi.
...
Рейтинг: 0 / 0
26.08.2017, 17:26
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39510964
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Basil A. Sidorov, ценное замечание. Но мы здесь поскипаем MacBook и Java.
...
Рейтинг: 0 / 0
26.08.2017, 17:45
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511015
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я раз в 2-3 года меняю железяку, которая несколько раз в сутки сначала качает несколько Гб, затем парсит и на основании результата генерит некие отчеты. Все это на фокспро x32
В эпоху XP было непонятно как 8 Гб задействовать, в итоге линукс, в нем XEN в нем виртуалка с XP и просунутым в нее рамдрайвом на 4 Гб. С появлением 7-ки x64 линукс стал ненужен, фокспро x32 нынче уже внутри десятки, а тормозит инет, поэтому переписывать смысла нет.

А прелести кэша проца только в баловстве удалось почувствовать: Эратосфен и акторы.
...
Рейтинг: 0 / 0
26.08.2017, 21:04
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511017
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, +1 Эратосфен классная тема была. Может как нибудь еще поднимем.
Я-то свой pbfa так и не закончил. Ну по крайней мере дифференциальные
кеши так и не сделал.

А по сабжу реально документации мало. Чуть позже я пристегну к форуму
те документы которые смотрел из своего офлайного архива Intel.
Сейчас на сайте у них как-то запутано все. Много левого шлака
а полезных доков не видать.

И еще чуть позже посмотрю на сайте AMD. Куксенко кст. очень сильно хвалил
AMD в части конвейера инструкций.
...
Рейтинг: 0 / 0
26.08.2017, 21:13
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511043
petalvik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
petalvik
Участник
mayton,

небольшая статейка про кэш и данные, там в конце про управление кэшем пара слов и ссылки на доки.

Описанные в статье правильное умножение матриц и hold/cold data splitting реально дают полезный эффект. Это не прямое управление кэшем, а косвенное, но не суть.

Также, в многопоточке даёт реальный эффект избавление от false sharing . Несколько раз сталкивался с этим при программировании на C#.

Ещё сталкивался со следующим. Код, часто вставляющий и удаляющий элементы из коллекции, как в начале, так и в середине, так и в конце. Казалось бы, связный список будет очень эффективен, за счёт того, что не нужно сдвигать остаток коллекции после удаления элементов в начале. Однако, применение вектора (List<T> в C#) неожиданно оказывалось эффективнее. Причина в том, что данные из RAM копируются в кэш линиями. В итоге с одним элементом списка тянется мусор, а из вектора вся линия - нужные данные.

Отвечая на вопросы. Какие оптимизации использовались: правильный выбор алгоритмов и структур данных. Полезный эффект: есть.
...
Рейтинг: 0 / 0
26.08.2017, 22:58
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511064
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petalvik, спасибо. Хорошая статья. Запишу себе в mindmap про MSVC

Код: plaintext
1.
void _mm_prefetch(char * p , int hint );



Еще нашел про GCC.

https://gcc.gnu.org/projects/prefetch.html
...
Рейтинг: 0 / 0
26.08.2017, 23:49
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511068
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Есть мысль которую я думаю уже второй день. Это в разрезе той задачки где парень ищет уникальные
слова в справочнике 150Гиг.

Фрагмент Hadoop-овской ориниальной библиотеки для работы с Map<String,Boolean>
как с нечетким множеством.

Код на Java но тут не суть. Он херово будет работать в любом ЯП в силу реализации.
алгоритма.

Я прокомментирую. Создаем мапу размером в 1.6 млрд бит. Как я вычислил
этот размер - отдельная история но он тоже важен. Это соотв. 206 мегабайтам.

Код: java
1.
2.
// 1 649 813 008 bits = 206 226 626
BloomFilter bloomFilter = new BloomFilter(1_649_813_008, 13, Hash.MURMUR_HASH);



Второй аргумент тоже важен. Число 13 - это количество хеш функций типа Мур-Мур
(что это за хрень Мур-мур я не знаю но не суть. Нам важно что их 13 и все они дают разные
значения для хеша нашего ключа). 13 также вычисляется как особая функция зависящая
от наших требований (false positive propability, amount keys).

В теле конструктора - ничего интересного. Просто создается биткарта нужного размера.

Далее добавление ключа в нечеткое множество. Здесь интереснее.
org/apache/hadoop/util/bloom/BloomFilter
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
  public void add(Key key) {
    if(key == null) {
      throw new NullPointerException("key cannot be null");
    }

    int[] h = hash.hash(key);
    hash.clear();

    for(int i = 0; i < nbHash; i++) {
      bits.set(h[i]);
    }
  }


В цикле (13 итераций) видно что сетятся биты по нашей биткарте. Алгоритм гарантирует
что на каждый ключ мы установим через логическое OR битик в той позиции которую
вернут нам Мур-мурки.

Я не трассировал код но убежден что в силу алгоритмической особенности фильтра
все 13 функций дают СОВЕРШЕННО линейное распределение вероятности по всему
диапазону битсета. К примеру я сделал
Код: java
1.
bloomFilter.add(new Key("mayton"));


и 13 битиков зажглись на всем диапазоне.

Как быть с точки зрения кеша? Если мне проверки принадлежности ключей
сейчас не очень нужны - то я мог-бы буферизировать этот поток в массив
и потом как-то сортировать и накатывать на весь битсет.
...
Рейтинг: 0 / 0
27.08.2017, 00:15
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511081
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
mayton1) Кто из вас когда и как использовал оптимизации нацеленные на использование CPU Caches (L1/L2/L3) ?
2) Какое API вы при этом использовали?
3) Какое было железо?
4) Был ли полезный эффект?
1) Да, использовал. Во время учебы в классе ...... забыл название. В общем, был у меня в студенческие времена специальный класс по проектированию процессоров.
2) Ассемблер вестимо. Уж если хочешь быть увереным что процессор сделает то что ты хочешь - компиляторы идут на UI. :)
3) Какой-то ARM, толи седьмой, толи еще более древний.
4) Да, когда внимательно просчитываешь порядок ассемблерных инструкций и расположение данных в памяти - можно четко увидеть выигрыш. Иногда до 180% доходило (или падало до 70%, что бывало чаще). Но компиляция Си кода в gnuc с точно указаной целевой платформой и включеной оптимизацией давала стабильные 120%. Это все по отношению к тому-же Си коду собранного для абстрактного x86 и без оптимизации.
...
Рейтинг: 0 / 0
27.08.2017, 04:56
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511108
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
petalvikmayton,
небольшая статейка про кэш и данные, там в конце про управление кэшем пара слов и ссылки на доки.

Еще про статью. Канонический пример с умножением матриц я встречал в книгах по Параллелизму.
Забавно но в них кеши вообще не берутся в расчет. Просто ведется разговор о том как удобнее
порезать матрицу на слои (как торт) вертикально и горизонтально чтобы перемножить
эти слои в 1,2,4 и более потока или процесса.
...
Рейтинг: 0 / 0
27.08.2017, 09:57
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39511234
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
По поводу книжек. Вот что у меня локально на ноуте лежало.

 
Код: plaintext
1.
2.
3.
4.
5.
6.
f4dc218bd2ee865ccde9efe931536154 *6th.Generation.Intel.Processor.Families.4.S-Platforms(Vol-1).pdf
d5de1afa4185bad34ba452d4e7222994 *Intel.64.and.IA-32.Architectures.Optimization.Ref.Man.pdf
f6ffd0edfb77482a2cc921d1527608cc *Intel.64.and.IA-32.Architectures.Soft.Dev.Man(Vol-2a).pdf
41e43fea8a6293a5cd28aeace9079758 *Intel.64.and.IA-32.Architectures.Soft.Dev.Man(Vol-2b).pdf
03774bee25a9b26770e346fbbb47c2b3 *Intel.Architecture.Optimization.Manual.1997.pdf
3a36d995bf7dd198a36e1e720569bf34 *Intel.Architecture.Optimization.Ref.Man.pdf



Две из них кажется я уже видел в библиографическом списке той статьи которую дал petalvik.
...
Рейтинг: 0 / 0
27.08.2017, 16:36
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39514721
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
http://www.sql.ru/forum/858632-1/processornyy-kesh?hl=%ea%e5%f8]:[|||||||||]:

)
...
Рейтинг: 0 / 0
03.09.2017, 18:09
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39514773
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мда... Athlon я уже куда-то сплавил. Хорошая машинка была.
...
Рейтинг: 0 / 0
03.09.2017, 21:05
| Ответить | Цитировать | Написать  
Тяпничные кеши
    #39514795
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
maytonМда... Athlon я уже куда-то сплавил. Хорошая машинка была.

Насколько я знаю, с того времени крадинально ничего не поменялось,
и никаких новых инструментов не появилось.
...
Рейтинг: 0 / 0
03.09.2017, 22:30
| Ответить | Цитировать | Написать  
15 сообщений из 15, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничные кеши
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]