Оптимизация программ

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

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

Нужно помнить, что он вообще есть

И вот я помню, что у процессора есть кэш. Как мне учитывать это, кроме как не оценками «влезет/не влезет»?

Вот именно проблема в том, что кэши везде разного размера, поэтому подстраиваться под какое-то значение нельзя.

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

Можно постараться не раздувать размеры структур и эффективно оперировать памятью, потому что иначе кэш забит и профит падает.

Ориентироваться на самое быстрое железо и рядом с ним а на тормозном старом уг выдавать предупреждение.

Если под оптимизацией понимать не изменение алгоритма, а трансляцию в GAS и замену команд, то да.

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

Почему нельзя? Что мешает написать универсальный код который чекает модель процессора и выполняет оптимизированный под эту модель код?

Ну вот я допустим сортирую массив. Если знаю что кэшь процессора 1MB я сортирую блоками <1MB, если меньше то меньшими.
Такая оптимизация будет работать?

Ага, эта чекающая программа называется компилятором, и представь себе - код для компилятора можно писать «универсально».

А можно название этого компилятора волшебного?

этот универсальный код придётся писать на ассемблере :)

А почему не на java?

Называется cc.

Я после этого твоего сообщения додумался прочитать твои теги и твои темы. Не парься об оптимизациях, зачем тебе это?

Возьми да проверь, это же не сложно.

точно высчитывать вмещаемость переменных в кэш это глупо

Иногда стараются выравнивать данные на начало кеш-линий.

вы параметры кэша процессора учитываете при оптимизации

Обычно нет. А какие «параметры кэша» ты хочешь учитывать?

Размер кэша.

Полный размер кэша?

Выравнивание по размеру это немножко не то, о чём я речь вёл. Но да, его иногда учитывают.

Да у тебя по ходу вся речь «немножко не о том». xD

Прости, но не хочется такое выслушивать от человека, который думает, что сможет производить низкоуровневые оптимизации на java.

Давно ли оптимизация алгоритма сортировки стала «низкоуровневой»?

В софте от адоби можно указать кеш цпу и гпу, и выбрать уровень оптимизации

gcc точно умеет в некоторые специфичные оптимизации. з.ы. и да - думается мне, за исключением компиляторов есть очень мало применений, где это оправдано. Всё же это усложняет поддержку и добавяляет зависимость от конкретных железок (что. впрочем, может быть приемлемо).

Количество моделей процессоров.

Какого кстати? Он не один.

Это так и работает. А мешает то, что кто это будет писать? Писать некому. Это есть в глибц, но даже для глибц это некому писать и реализации там так себе.

Ты же выше толкал, что конпелятор должен собирать под 386-й и не париться? Ты уж определись.

Да и брехня всё это - конпелятор ничего не умеет.

gcc точно умеет в некоторые специфичные оптимизации.

Собирать-то надо под 386-й - какие ещё оптимизации?

думается мне, за исключением компиляторов есть очень мало применений, где это оправдано

А пацаны-то не знали. Во всё коде, который сложнее хелворда используется, но вдруг «не оправданно» у пацана на лоре случилось - бывает.

Всё же это усложняет поддержку и добавяляет зависимость от конкретных железок

Не добавляет. И к поддержке это не имеет никакого отношения - рядовой адепт просто это не напишет.

Любой таргет-специфик добавляется поверх общего - это специализация. Т.е. для всех не поддерживаемых ничего не поменяется.

Для справки:

Какое отношение модель имеет к микроархитектуре? За последние 10лет микроархитектур от интела было 4 + ещё столько же от амд. нехалем+сандик+хасвел+скайлайк/бульдозер+шмульдозер+экскаватор - я не шарю. Ну где-то то же 4. И то нехалем считай тот же кора2, а скайлайк хасвел. Т.е. реально надо 1) последние коры+нехалем - на это окаменелое дерьмо можно уже нассать, 2) vex_sse + avx_fp - это всё до хасвела, 3) vex_avx - это хасвел/скайлайк. У амд та же фигня.

Товарищ выше именно про модели говорит. Потолкуй с ним.

Всё после санди заменить на санди+ и всё после бульдозера на бульдозер+.

Всё после санди заменить на санди+

Что за херня? Каким образом можно приравнять друг к другу хасвел и сандик? Это совершенно разные вещи.

бульдозер+.

Понятия не имеют что там у амд - возможно.

Нет, не будет. man ассоциативность кэша.

А можно узнать у уважаемых знатаков: Какое отношение ассоциативность имеет к обращению внутри блока длинную с кеш? Подсказка - она никогда не закольцуется.

Да, особенно когда фабрики билдеров декораторов прокси для синглтонов пишу.

Отношение самое прямое: блок не влезет целиком в кэш, это имеет смысл только для кэш-линии

До оптимизации под кеш еще дойти нужно. Это, можно сказать, последняя инстанция.

Вы бы ЯП указали, а то если у вас не C/C++/Rust - то о кеше можно не беспокоится.

На самом деле, я неправ: непрерывный блок размером в кэш в него таки влезет. Тем не менее, бить данные на такие куски всё равно плохая идея: во-первых, не очень понятно, о каком кэше речь — ЕМНИП L1 на многих микроархитектурах кэширует только код, а на более высоких уровнях уже возникнут проблемы с влезанием в него; во-вторых, в памяти могут случайно оказаться используемые при сортировке переменные.

Чё? Хотя ладно - спрашивать что-то со знатаков глупо, но раз я социализируюсь - объясню тебе нормально.

Кеш-линия никакого отношения ни к чему не имеет - это просто те части, которыми «адресуется» кеш и собственно ассоциативность работает для них.

Далее - ассоциативность - это просто кольцевое отображение на кеш, но отражения не байтов, а блоков, которые называются кеш-лайнами. Это значит, что если кеш 32кб с блоками по 64байта - память просто отображается теми же самыми блоками на 512 этими же самыми блоками.

Это значит то, что в рамках любых последовательных 512 елеметов их mod 512 будет УНИКАЛЕН ВСЕГДА. И никак они перекрывать друг друга не будут - кеш будет вмещать в себя ровно 32кб.

Ассоциативность работает против ёмкости кеша на обращение к памяти выше этого окна - т.е. когда мы обращается к блокам с шагом 512, то кеш может хранить 1блок * на его n-way - т.е. его ёмкость 64 * n-way байт. И ты слышал именно про эти все случаи.

Поэтому перед тем как рассуждать - надо научиться понимать то, о чём рассуждаешь, а не ретранслировать какой-то звон, если ты не знаешь где он.

Естественно ты не прав.

Тем не менее, бить данные на такие куски всё равно плохая идея: во-первых, не очень понятно, о каком кэше речь man sysconf()

на многих микроархитектурах кэширует только код

Никого не интересуют эти архитектуры. В прикладном мире существует одна архитектура - х86. В мире мейнфремов ещё 2, которые почти такие же.

Остальные недомобилки с жабкой и прочая херня - никого не волнует.

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

опять же man sysconf - используй блок чуть меньше объёма кеша. Всё это считается.

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

Всё учитывается и всё спокойно используется. Естественно всё это делается осознанно, поэтому никаких проблем с этим нет.

используй блок чуть меньше объёма кеша

Чёрт, я не распарсил «<» во фразе «Если знаю, что кэш процессора 1MB, я сортирую блоками <1MB» и думал, что чувак берёт ровно такие куски, сколько у него кэша. Посыпаю голову пеплом.

В прикладном мире существует одна архитектура - х86

x86 — архитектура набора инструкций, разве она как-то регламентирует кэши и прочие микроархитектурные вещи? Или в прикладном программировании существует одна микроархитектура — та, которая в последнем поколении интеловских процов?

Посыпаю голову пеплом.

Чувак просто предполагает - зачем искать неточности в его предположениях? Его предположение верно - в деталях оно чуть сложнее, чем просто взять кусок, но из этого ничего не следует.

x86 — архитектура набора инструкций, разве она как-то регламентирует кэши и прочие микроархитектурные вещи?

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

При этом это никакого отношения к делу не имеет, ибо я уже сказал про sysconf() - всё это очень просто получается.

Или в прикладном программировании существует одна микроархитектура — та, которая в последнем поколении интеловских процов?

Да, существует набор микроахитектур, актуальных настоящему времени. Общее описание вида l1/lcc - работает для всех. А если не работает - ничего страшного:

if(смоглось) supersort; else sort; - всё просто и понятно. Дефолтное днище у тебя всегда есть и даунгрейднуться на него можно в любой момент и никаких проблем это не вызывает.

Подскажите вот те кто оптимизацией программ занимается, вы параметры кэша процессора учитываете при оптимизации?

Просто чумовая книга Криса Касперски «Техника оптимизации программ. Эффективное использование памяти» поможет найти ответы на твои вопросы.

Год: 2003

Год: 2003

Работа с памятью внутри и снаружи процессора показана примерами на Си без привязки к компилятору. Жаль, что Крис написал книгу только с прицелом на семейство процессоров «Интел х86», наверное, в те времена об исполнении программ на других процессорах особо не думали. Так что книга вполне годная, если кому любопытен практический исследовательский взгляд компьютерного взломщика.

Глуп ты. А размер cache line при оптимизации важнейший параметр.