Это перевод Computing the size of a directory is more than just adding file sizes. Автор: Реймонд Чен.
Кто-то может подумать, что вычисление размера каталога есть простое суммирование размера всех файлов, хранящихся в нём.
Ах, если бы это было так просто.
...when altering one's mind becomes as easy as programming a computer, what does it mean to be human?..
понедельник, 28 декабря 2009 г.
воскресенье, 27 декабря 2009 г.
Вы можете создать бесконечное рекурсивное дерево каталогов
Это перевод You can create an infinitely recursive directory tree. Автор: Реймонд Чен.
Возможно создать бесконечное рекурсивное дерево каталогов. Это приведёт к хаосу во многих функциях просмотра структуры каталогов. Вот, как вы можете это сделать (примечание: требует NTFS).
Возможно создать бесконечное рекурсивное дерево каталогов. Это приведёт к хаосу во многих функциях просмотра структуры каталогов. Вот, как вы можете это сделать (примечание: требует NTFS).
суббота, 26 декабря 2009 г.
Почему система конвертирует TEMP в короткое имя?
Это перевод Why does the system convert TEMP to a short file name? Автор: Реймонд Чен.
Когда вы устанавливаете переменные окружения в апплете Система Панели Управления, переменные TEMP и TMP неявно конвертируются в свои короткие эквиваленты (если это возможно). Почему это так?
Когда вы устанавливаете переменные окружения в апплете Система Панели Управления, переменные TEMP и TMP неявно конвертируются в свои короткие эквиваленты (если это возможно). Почему это так?
пятница, 25 декабря 2009 г.
Нужно ли вам закрывать описатели "одноразовых" таймеров?
Это перевод Do you need clean up one-shot timers? Автор: Реймонд Чен.
Функция CreateTimerQueueTimer позволяет вам создавать "одноразовый" таймер, передавая флаг WT_EXECUTEONLYONCE. Документация говорит, что вам нужно вызвать функцию DeleteTimerQueueTimer, когда вам больше не нужен таймер.
Но почему вам нужно закрывать одноразовые таймеры?
Чтобы ответить на это, я хотел бы представить вам один из моих любимых риторических вопросов, которые я использую при решении головоломок с API: "на что был бы похож мир, если бы это было так?".
Представьте, на что был бы похож мир, если бы вы могли не закрывать описатели одноразовых таймеров.
Ну, для начала, это означает, что поведение функции может быть запутанным. Вызывающий функцию CreateTimerQueueTimer теперь должен отслеживать, какие таймеры были одноразовыми, а такие - нет, чтобы знать, надо ли ему закрывать описатели или нет.
Но намного, намного более плохой вещью будут авто-закрывающиеся таймеры, потому что правильно использовать их будет практически невозможно.
Предположим, что у вас есть объект, который создаёт одноразовый таймер, и вы хотите удалить таймер в деструкторе, если он не успел сработать. Если бы одноразовые таймеры были бы самоудаляющимися, то вы не смогли бы написать такой объект.
Только теперь у вас условие гонки.
Это условие гонки нельзя обойти, потому что гонка происходит до того, как хотя бы одна инструкция вашего кода получит шанс на выполнение.
Так что будьте благодарны, что вам нужно закрывать описатели одноразовых таймеров.
Функция CreateTimerQueueTimer позволяет вам создавать "одноразовый" таймер, передавая флаг WT_EXECUTEONLYONCE. Документация говорит, что вам нужно вызвать функцию DeleteTimerQueueTimer, когда вам больше не нужен таймер.
Но почему вам нужно закрывать одноразовые таймеры?
Чтобы ответить на это, я хотел бы представить вам один из моих любимых риторических вопросов, которые я использую при решении головоломок с API: "на что был бы похож мир, если бы это было так?".
Представьте, на что был бы похож мир, если бы вы могли не закрывать описатели одноразовых таймеров.
Ну, для начала, это означает, что поведение функции может быть запутанным. Вызывающий функцию CreateTimerQueueTimer теперь должен отслеживать, какие таймеры были одноразовыми, а такие - нет, чтобы знать, надо ли ему закрывать описатели или нет.
Но намного, намного более плохой вещью будут авто-закрывающиеся таймеры, потому что правильно использовать их будет практически невозможно.
Предположим, что у вас есть объект, который создаёт одноразовый таймер, и вы хотите удалить таймер в деструкторе, если он не успел сработать. Если бы одноразовые таймеры были бы самоудаляющимися, то вы не смогли бы написать такой объект.
typeВы можете сказать: ну я могу обнулить поле m_hTimer в callback-ке таймера. Таким образом, деструктор будет знать, когда таймер сработал".
TSample = class
private
m_hTimer: THandle;
// ...
public
constructor Create;
destructor Destroy; override;
end;
constructor TSample.Create;
begin
inherited;
CreateTimerQueueTimer(m_hTimer, ...);
end;
destructor TSample.Destroy;
begin
// что написать тут?
inherited;
end;
Только теперь у вас условие гонки.
class procedure TSample.Callback(const Context: Pointer); stdcall; static;Если callback будет вытеснен во время выполнения окна (до обнуления поля), и тут же запустится деструктор объекта, то объект попытается использовать неверный описатель, поскольку таймер уже закрыт.
begin
// ОКНО ДЛЯ ГОНКИ:
TSample(Context).m_hTimer := 0;
// ...
end;
Это условие гонки нельзя обойти, потому что гонка происходит до того, как хотя бы одна инструкция вашего кода получит шанс на выполнение.
Так что будьте благодарны, что вам нужно закрывать описатели одноразовых таймеров.
четверг, 24 декабря 2009 г.
Иногда людям не нравится, когда вы соблюдаете стандарт
Это перевод Sometimes people don't like it when you enforce a standard. Автор: Реймонд Чен.
Средний пользователь компьютера не признает документы стандартов, даже если вы швырнёте их ему в лицо.
Я вспомнил о баг-отчёте в 1996-м, касающегося того, как Outlook Express (тогда он назывался "Microsoft Internet Mail and News") обрабатывал знак процента в e-mail адресах (мне кажется). Способ, которым Outlook Express работал с ними, был согласованным со стандартом, поэтому я отправил соответствующую часть RFC человеку, который сообщил об ошибке. Вот что я получил в ответ:
Есть много "странностей" в том, как Internet Explorer обрабатывает определённые аспекты HTML, когда он не запущен в строгом режиме. Например, замечали ли вы, что шрифт, который вы ставите через CSS для вашего тэга BODY, не применяется к таблицам? Или что вызов метода submit на форме не приводит к генерации события onsubmit? Это всё потому что Netscape тоже этого не делал, а Internet Explorer был вынужден быть баг-к-багу совместимым с Netscape, потому что все web сайты рассчитывали на такое поведение.
Последний параграф в ответе особенно занимателен. Человек использует "RFC" как волшебное слово, не зная, что оно значит. Очевидно, что если вы хотите сказать, что что-то не работает, как вы ожидаете, вы говорите, что оно не согласуется с RFC. Согласуются ли сами ваши ожидания с RFC тут не важно (человек, сообщивший о баге, по своему собственному признанию, не читал RFC).
Средний пользователь компьютера не признает документы стандартов, даже если вы швырнёте их ему в лицо.
Я вспомнил о баг-отчёте в 1996-м, касающегося того, как Outlook Express (тогда он назывался "Microsoft Internet Mail and News") обрабатывал знак процента в e-mail адресах (мне кажется). Способ, которым Outlook Express работал с ними, был согласованным со стандартом, поэтому я отправил соответствующую часть RFC человеку, который сообщил об ошибке. Вот что я получил в ответ:
Я никогда не читал ваши RFC (я уверен, что большинство людей тоже), но я знаю, когда что-то РАБОТАЕТ в одной почтовой программе (Netscape) и НЕ РАБОТАЕТ в другой (MSIMN).Первое предложение очень хорошо передаёт отношение всего мира к документам стандартов: они бесполезны. Если Outlook Express не ведёт вебя так, как Netscape - то это баг в Outlook Express, вне зависимости от того, что говорят стандарты.
Проблема, переформулированная в согласии с вашим RFC:
MS Internet Mail and News НЕ ОБРАБАТЫВАЮТ ЗНАКИ ПРОЦЕНТА, как говорит RFC.
Есть много "странностей" в том, как Internet Explorer обрабатывает определённые аспекты HTML, когда он не запущен в строгом режиме. Например, замечали ли вы, что шрифт, который вы ставите через CSS для вашего тэга BODY, не применяется к таблицам? Или что вызов метода submit на форме не приводит к генерации события onsubmit? Это всё потому что Netscape тоже этого не делал, а Internet Explorer был вынужден быть баг-к-багу совместимым с Netscape, потому что все web сайты рассчитывали на такое поведение.
Последний параграф в ответе особенно занимателен. Человек использует "RFC" как волшебное слово, не зная, что оно значит. Очевидно, что если вы хотите сказать, что что-то не работает, как вы ожидаете, вы говорите, что оно не согласуется с RFC. Согласуются ли сами ваши ожидания с RFC тут не важно (человек, сообщивший о баге, по своему собственному признанию, не читал RFC).
среда, 23 декабря 2009 г.
Не сохраняйте ничего, что вы можете пересчитать
Это перевод Don't save anything you can recalculate. Автор: Реймонд Чен.
В настоящее время основным ограничением производительности для многих классов программ является подкачка. Мы видели в начале этого года, что подкачка может убить сервер. Сегодня еще один пример того, как производительность стала привязана к подкачке.
Принцип - "не сохраняй ничего, что ты можешь заново рассчитать". Это, конечно же, кажется оптимизацией против интуиции: разве вам не следовало бы сохранить ответ, чтобы не тратить время на повторное вычисление?
Ответ: "это зависит от разных причин".
Если вычисление заново не очень затратно и имеет хорошую локализованность по данным, то вам бы лучше вычислять ответ заново, чем сохранять его - особенно, если его сохранение уменьшает локализуемость данных. Например, если результат сохраняется в отдельном объекте, то теперь вы рискуете page fault-ом при чтении сохранённого ответа, т.к. вам надо сперва получить ссылку на объект, а потом прочитать у него сам ответ.
В последний раз, мы видели, как этот принцип применяется к Windows 95 - так что перебазирование DLL не ставило на колени вашу машину. Мне сказали, что команда Access использовала этот принцип для значительного улучшения производительности. Вместо кэширования результатов они просто выкидывали их и вычисляли заново, когда они добавлялись в дальнейшем.
Будет ли эта техника работать для вас - предсказать сложно. Если ваша программа ограничивается процессором, то кэширование результатов может быть хорошей идеей. Но если ваша программа ограничивается памятью, то вам лучше бы избавиться от кэша, потому что он создаёт большее давление на память.
В настоящее время основным ограничением производительности для многих классов программ является подкачка. Мы видели в начале этого года, что подкачка может убить сервер. Сегодня еще один пример того, как производительность стала привязана к подкачке.
Принцип - "не сохраняй ничего, что ты можешь заново рассчитать". Это, конечно же, кажется оптимизацией против интуиции: разве вам не следовало бы сохранить ответ, чтобы не тратить время на повторное вычисление?
Ответ: "это зависит от разных причин".
Если вычисление заново не очень затратно и имеет хорошую локализованность по данным, то вам бы лучше вычислять ответ заново, чем сохранять его - особенно, если его сохранение уменьшает локализуемость данных. Например, если результат сохраняется в отдельном объекте, то теперь вы рискуете page fault-ом при чтении сохранённого ответа, т.к. вам надо сперва получить ссылку на объект, а потом прочитать у него сам ответ.
В последний раз, мы видели, как этот принцип применяется к Windows 95 - так что перебазирование DLL не ставило на колени вашу машину. Мне сказали, что команда Access использовала этот принцип для значительного улучшения производительности. Вместо кэширования результатов они просто выкидывали их и вычисляли заново, когда они добавлялись в дальнейшем.
Будет ли эта техника работать для вас - предсказать сложно. Если ваша программа ограничивается процессором, то кэширование результатов может быть хорошей идеей. Но если ваша программа ограничивается памятью, то вам лучше бы избавиться от кэша, потому что он создаёт большее давление на память.
вторник, 22 декабря 2009 г.
Как Windows 95 меняла базовый адрес DLL?
Это перевод How did Windows 95 rebase DLLs? Автор: Реймонд Чен.
Windows 95 обрабатывала смену базового адреса DLL (DLL-rebasing) совершенно другим способом, нежели в Windows NT.
Когда Windows NT определяла, что DLL нужно загрузить по адресу, отличному от предпочтительного базового адреса, она проецировала всю DLL с флагом copy-on-write, правила её адреса (что приводило к выгрузке всех страниц с правками (fix up) в файл подкачки), после чего восстанавливала флаг read-only/read-write на страницы (Ларри Остерман в этом году подробно это разбирал).
Windows 95, с другой стороны, перебазировала DLL последовательно. Это было ещё одной уступкой Windows 95 из-за очень сильных ограничений на требования к памяти. Вспомните, что она должна была работать на машине с 4 Мб оперативной памяти. Если бы она обрабатывала перебазирование DLL тем же способом, что и Windows NT, то загрузка 4-х мегабайтной DLL и её исправление заняло бы всю память машины, приводя к выгрузке в файл подкачки всей памяти, которую лучше было бы придержать в памяти!
Когда DLL нуждалась в смене базового адреса, Windows 95 просто делала отметку о новом базовом адресе DLL, не делая ничего сверх этого. Настоящая работа случалась, когда страницы этой DLL подгружались в память. Когда сырая страница загружалась с диска в память, то все правки (fix up) применялись к странице на лету, производя её перемещение. Эти правки проецировались в адресное пространство процесса, и программа могла продолжать своё выполнение.
Этот метод имел преимущество в том, что стоимость исправления страницы не платилась до тех пор, пока страница не начинала использоваться, что было значительным выигрышем для огромных DLL с кучей мёртвого кода (т.е. кода, который никогда не вызывался приложением - прим. пер.). Более того, когда исправленная страница нуждалсь в выгрузке из памяти - она просто отбрасывалась, без сохранения в файл подкачки, потому что все правки могли быть повторно применены при следующей её загрузке в память.
И вот, пожалуйста: перебазирование DLL по-странично по требованию вместо перебазирования DLL целиком при загрузке. Что могло тут пойти не так?
Подсказка: это проблема, которая свойственна только для x86.
Проблема тут в том, что правки могут пересекать границы страниц. Это происходит только на x86, потому что архитектура x86 - очень странная, с инструкциями переменного размера, которые могут начинаться с любого адреса. Если страница содержит правку, которая частично пересекает начало страницы, то вы не можете сделать правку точно, пока вы не узнаете, не создала ли правка, которую вы не видите, перенос единички (carry). Если да - то вам надо добавить перенос к своей частичной правке.
Чтобы сохранить эту информацию, менеджер памяти ассоциирует с каждой страницей перемещаемой DLL флаг, который показывает, создала ли страница перенос на своём конце. Флаг может иметь один из следующих состояний:
Но что, если флаг говорит "Я не знаю"?
Если вы не знаете, то вам нужно это выяснить. Потрогайте предыдущую страницу, чтобы загрузить её и сделайте в ней правки. Как часть вычисления поправок, будет установлен флаг, говорящий, есть ли перенос на конце. Когда предыдущая страница исправлена, вы теперь можете проверить флаг (который теперь не будет в состоянии "Я не знаю"), и он сообщит вам, надо ли вам добавлять единичку.
И вот, пожалуйста: перебазирование DLL по-странично по требованию вместо перебазирования DLL целиком при загрузке. Даже в присутствии правок через границу страниц. Что могло тут пойти не так?
Подсказка: что может пойти не так с рекурсией?
Проблема в том, что предыдущая страница в свою очередь может иметь правку, пересекающую начало страницы, а флаг для предыдущей предыдущей страницы может также быть в состоянии "Я не знаю". Теперь вам надо обработать третью страницу.
К счастью, на практике редко бывают случаи правки больше трёх страниц за раз. Три страницы исправлений по цепочке были рекордом.
(Конечно же, другим способом остановить рекурсию было бы выполнение только части правок на предыдущей странице - только минимум, необходимый для вычисления нужен ли перенос на конце или нет, без попыток исправить всю страницу. Но Windows 95 шла вперёд и исправляла всю страницу, потому что она считала: "эй, я тут столько заплатила за эту страницу, почему бы мне её не использовать").
В чём была мораль сегодняшней истории? Не думаю, что она у меня была. Это была просто историческая закавырка, которая, как я надеюсь, будет кому-то интересной.
Читать далее.
Windows 95 обрабатывала смену базового адреса DLL (DLL-rebasing) совершенно другим способом, нежели в Windows NT.
Когда Windows NT определяла, что DLL нужно загрузить по адресу, отличному от предпочтительного базового адреса, она проецировала всю DLL с флагом copy-on-write, правила её адреса (что приводило к выгрузке всех страниц с правками (fix up) в файл подкачки), после чего восстанавливала флаг read-only/read-write на страницы (Ларри Остерман в этом году подробно это разбирал).
Windows 95, с другой стороны, перебазировала DLL последовательно. Это было ещё одной уступкой Windows 95 из-за очень сильных ограничений на требования к памяти. Вспомните, что она должна была работать на машине с 4 Мб оперативной памяти. Если бы она обрабатывала перебазирование DLL тем же способом, что и Windows NT, то загрузка 4-х мегабайтной DLL и её исправление заняло бы всю память машины, приводя к выгрузке в файл подкачки всей памяти, которую лучше было бы придержать в памяти!
Когда DLL нуждалась в смене базового адреса, Windows 95 просто делала отметку о новом базовом адресе DLL, не делая ничего сверх этого. Настоящая работа случалась, когда страницы этой DLL подгружались в память. Когда сырая страница загружалась с диска в память, то все правки (fix up) применялись к странице на лету, производя её перемещение. Эти правки проецировались в адресное пространство процесса, и программа могла продолжать своё выполнение.
Этот метод имел преимущество в том, что стоимость исправления страницы не платилась до тех пор, пока страница не начинала использоваться, что было значительным выигрышем для огромных DLL с кучей мёртвого кода (т.е. кода, который никогда не вызывался приложением - прим. пер.). Более того, когда исправленная страница нуждалсь в выгрузке из памяти - она просто отбрасывалась, без сохранения в файл подкачки, потому что все правки могли быть повторно применены при следующей её загрузке в память.
И вот, пожалуйста: перебазирование DLL по-странично по требованию вместо перебазирования DLL целиком при загрузке. Что могло тут пойти не так?
Подсказка: это проблема, которая свойственна только для x86.
Проблема тут в том, что правки могут пересекать границы страниц. Это происходит только на x86, потому что архитектура x86 - очень странная, с инструкциями переменного размера, которые могут начинаться с любого адреса. Если страница содержит правку, которая частично пересекает начало страницы, то вы не можете сделать правку точно, пока вы не узнаете, не создала ли правка, которую вы не видите, перенос единички (carry). Если да - то вам надо добавить перенос к своей частичной правке.
Чтобы сохранить эту информацию, менеджер памяти ассоциирует с каждой страницей перемещаемой DLL флаг, который показывает, создала ли страница перенос на своём конце. Флаг может иметь один из следующих состояний:
- Да, есть перенос на конце.
- Нет, на конце переноса нет.
- Я не знаю, был ли перенос на конце.
Но что, если флаг говорит "Я не знаю"?
Если вы не знаете, то вам нужно это выяснить. Потрогайте предыдущую страницу, чтобы загрузить её и сделайте в ней правки. Как часть вычисления поправок, будет установлен флаг, говорящий, есть ли перенос на конце. Когда предыдущая страница исправлена, вы теперь можете проверить флаг (который теперь не будет в состоянии "Я не знаю"), и он сообщит вам, надо ли вам добавлять единичку.
И вот, пожалуйста: перебазирование DLL по-странично по требованию вместо перебазирования DLL целиком при загрузке. Даже в присутствии правок через границу страниц. Что могло тут пойти не так?
Подсказка: что может пойти не так с рекурсией?
Проблема в том, что предыдущая страница в свою очередь может иметь правку, пересекающую начало страницы, а флаг для предыдущей предыдущей страницы может также быть в состоянии "Я не знаю". Теперь вам надо обработать третью страницу.
К счастью, на практике редко бывают случаи правки больше трёх страниц за раз. Три страницы исправлений по цепочке были рекордом.
(Конечно же, другим способом остановить рекурсию было бы выполнение только части правок на предыдущей странице - только минимум, необходимый для вычисления нужен ли перенос на конце или нет, без попыток исправить всю страницу. Но Windows 95 шла вперёд и исправляла всю страницу, потому что она считала: "эй, я тут столько заплатила за эту страницу, почему бы мне её не использовать").
В чём была мораль сегодняшней истории? Не думаю, что она у меня была. Это была просто историческая закавырка, которая, как я надеюсь, будет кому-то интересной.
Читать далее.
понедельник, 21 декабря 2009 г.
Но кто такие KnownDLLs?
Это перевод What are KnownDLLs anyway? Автор: Ларри Остерман.
В моём предыдущем посте о DLL и их работе, я упомянул, что winmm.dll была KnownDLL ("Известные DLL") в Longhorn. Кажется, это баг в существующих KnownDLL. Но что, чёрт возьми, такое, эти Known DLLs?
В моём предыдущем посте о DLL и их работе, я упомянул, что winmm.dll была KnownDLL ("Известные DLL") в Longhorn. Кажется, это баг в существующих KnownDLL. Но что, чёрт возьми, такое, эти Known DLLs?
воскресенье, 20 декабря 2009 г.
Почему я должен волноваться об использовании DLL в моей системе?
Это перевод Why should I bother to use DLL's in my system? Автор: Ларри Остерман.
В конце этого поста я упомянул, что когда я компилирую новую версию winmm.dll на мою машину, мне нужно сделать перезагрузку. Cesar Eduardo Barros спросил:
В конце этого поста я упомянул, что когда я компилирую новую версию winmm.dll на мою машину, мне нужно сделать перезагрузку. Cesar Eduardo Barros спросил:
Зачем нужна перезагрузка? Разве нельзя перезапустить все приложения, которые используют DLL, или перезапустить службу, которая использует её?
суббота, 19 декабря 2009 г.
Зачастую оптимизация противоречит интуиции
Это перевод Optimization is often counter-intuitive. Автор: Реймонд Чен.
Любой человек, который много занимался оптимизацией программ, знает, что зачастую оптимизация идёт вразрез с интуитивным представлением. Вещи, которые вам кажутся быстрее, в действительности такими не являются.
Рассмотрим, например, упражнение по получению указателя на текущую выполняемую инструкцию. Вот наивное решение:
Но если вы сядете и запустите оба фрагмента, вы можете обнаружить, что первый вариант с вызовом функций быстрее в два раза! Как такое может быть?
Причина - влияние "скрытых переменных" внутри процессора. Все современные процессоры отслеживают гораздо больше состояний, чем вы можете видеть в последовательности инструкций. Например: TLB, кэши L1 и L2 - всё это вещи, которых вы не видите. Скрытым состоянием, которое важно в нашем примере, является предсказание адреса возврата.
Современные процессоры Pentium (и я думаю, что Athlon тоже) отслеживают внутренний стек, который обновляется каждой командой CALL и RET. Когда выполняется команда CALL, адрес возврата заносится как в программный стек (на который указывает регистр ESP), а также во внутренний стек предсказателя переходов; инструкция RET выталкивает адрес возврата из стека предсказателя переходов и из программного стека.
Стек предсказателя переходов используется, когда процессор декодирует команду RET. Он смотрит на вершину стека предсказателя переходов и говорит: "ставлю на то, что эта команда RET собирается вернуть управление на этот адрес". После чего он заранее выполняет инструкцию по этому адресу ("спекулятивное выполнение"). Поскольку программы редко балуются с адресов возврата в стеке, это предсказание обычно бывает очень точным.
Вот почему наша "оптимизация" стала работать ещё медленнее. Предположим, что в момент выполнения инструкции CALL L1 стек адресов возврата предсказателя переходов выглядел так:
Тут, caller1 - вызывающий функции, caller2 - вызывающий вызывающего функцию и т.д. Пока стек предсказателя переходов соответствует действительности (я нарисовал действующий стек под стеком предсказателя переходов, чтобы вы могли увидеть, что они соответствуют друг другу).
Теперь вы выполняете инструкцию CALL. Стек предсказателя переходов и программный стек теперь выглядят вот так:
Но вместо выполнения инструкции RET, вы просто выталкиваете (pop) из стека адрес возврата. Это удаляет адрес возврата из программного стека, но не удаляет его из стека предсказателя переходов.
Думаю вы видите, к чему я клоню.
Потом ваша функция возвращает управление. Процессор декодирует вашу команду RET, он смотрит на адрес в стеке предсказателя переходов и говорит: "что-то подсказывает мне, что эта команда RET вернёт управление на L1. Я начну предварительное выполнение команд оттуда".
Но - ах нет! - значение в программном стеке вовсе не L1. Это - caller1. Предсказатель переходов процессора предсказал неверный адрес возврата, в результате чего процессор потратил время на изучение ненужного кода!
Но эффект от этого не заканчивается тут. После инструкции RET, стеки выглядят вот так:
Затем ваш вызывающий вернёт управление. И снова, процессор проконсультируется со стеком предсказателя переходов и начнёт спекулятивное выполнение инструкций по адресу caller1. Но вы возвращаетесь не туда - на самом деле вы вернётесь к caller2.
И так далее. Вводя дисбаланс в последовательность инструкций CALL и RET, вы сумели сделать так, что теперь каждое предсказание адреса перехода в стеке будет неверным. Заметьте на диаграмме, что если никто больше не будет играться со стеком так, как мы сделали изначально для создания проблемы, то ни одно предсказание по стеку адресов возврата предсказателя перехода не будет верным. Ни один из адресов в стеке предсказателя переходов теперь не соответствует адресам в программном стеке.
Ваша оптимизация "через щель" оказалась недальновидной.
Некоторые процессоры раскрывают это предсказание более явно. К примеру, Alpha AXP, имеет несколько типов инструкций по контролю потока выполнения, которые имеют одинаковый логический эффект, но содержат различные подсказки процессору по управлению внутренним стеком предсказаний переходов. Например, инструкция BR говорит: "перепрыгни на этот адрес, но не заноси старый адрес в стек предсказаний". С другой стороны, инструкция JSR говорит: "перейди на этот адрес и занеси старый адрес в стек предсказателя переходов". Есть также и инструкция RET, которая говорит: "перепрыгни на этот адрес и извлеки адрес из стека предсказателя" (имеется и четвёртый тип, который, впрочем, довольно редко используется).
Мораль истории: просто потому, что что-то выглядит лучше, не означает, что оно действительно лучше.
Любой человек, который много занимался оптимизацией программ, знает, что зачастую оптимизация идёт вразрез с интуитивным представлением. Вещи, которые вам кажутся быстрее, в действительности такими не являются.
Рассмотрим, например, упражнение по получению указателя на текущую выполняемую инструкцию. Вот наивное решение:
function GetCurrentAddress: Pointer;Если вы посмотрите на ассемблерный листинг, вы увидите что-то такое:
asm
mov eax, [esp]
end;
// ...
var
CurrentInstruction: Pointer;
begin
// ...
CurrentInstruction := GetCurrentAddress;
GetCurrentAddress:"Хах" - скажете вы, - "вы только посмотрите, как это не эффективно. Я могу сделать это всего в две инструкции. Следи за руками:"
mov eax, [esp]
ret
...
call GetCurrentAddress
mov [CurrentInstruction], eax
var"Тут вдвое меньше инструкций, чем в вашем раздутом girly-code!"
CurrentInstruction: Pointer;
label
L1;
begin
// ...
asm
call L1
L1: pop CurrentInstruction
end;
Но если вы сядете и запустите оба фрагмента, вы можете обнаружить, что первый вариант с вызовом функций быстрее в два раза! Как такое может быть?
Причина - влияние "скрытых переменных" внутри процессора. Все современные процессоры отслеживают гораздо больше состояний, чем вы можете видеть в последовательности инструкций. Например: TLB, кэши L1 и L2 - всё это вещи, которых вы не видите. Скрытым состоянием, которое важно в нашем примере, является предсказание адреса возврата.
Современные процессоры Pentium (и я думаю, что Athlon тоже) отслеживают внутренний стек, который обновляется каждой командой CALL и RET. Когда выполняется команда CALL, адрес возврата заносится как в программный стек (на который указывает регистр ESP), а также во внутренний стек предсказателя переходов; инструкция RET выталкивает адрес возврата из стека предсказателя переходов и из программного стека.
Стек предсказателя переходов используется, когда процессор декодирует команду RET. Он смотрит на вершину стека предсказателя переходов и говорит: "ставлю на то, что эта команда RET собирается вернуть управление на этот адрес". После чего он заранее выполняет инструкцию по этому адресу ("спекулятивное выполнение"). Поскольку программы редко балуются с адресов возврата в стеке, это предсказание обычно бывает очень точным.
Вот почему наша "оптимизация" стала работать ещё медленнее. Предположим, что в момент выполнения инструкции CALL L1 стек адресов возврата предсказателя переходов выглядел так:
| Адрес возврата Стек предсказателя: | caller1 | -> | caller2 | -> | caller3 | -> | ... | |
|---|---|---|---|---|---|---|---|---|
| Действительный стек: | caller1 | -> | caller2 | -> | caller3 | -> | ... |
Тут, caller1 - вызывающий функции, caller2 - вызывающий вызывающего функцию и т.д. Пока стек предсказателя переходов соответствует действительности (я нарисовал действующий стек под стеком предсказателя переходов, чтобы вы могли увидеть, что они соответствуют друг другу).
Теперь вы выполняете инструкцию CALL. Стек предсказателя переходов и программный стек теперь выглядят вот так:
| Адрес возврата Стек предсказателя: | L1 | -> | caller1 | -> | caller2 | -> | caller3 | -> | ... | |
|---|---|---|---|---|---|---|---|---|---|---|
| Действительный стек: | L1 | -> | caller1 | -> | caller2 | -> | caller3 | -> | ... |
Но вместо выполнения инструкции RET, вы просто выталкиваете (pop) из стека адрес возврата. Это удаляет адрес возврата из программного стека, но не удаляет его из стека предсказателя переходов.
| Адрес возврата Стек предсказателя: | L1 | -> | caller1 | -> | caller2 | -> | caller3 | -> | ... | |
|---|---|---|---|---|---|---|---|---|---|---|
| Действительный стек: | caller1 | -> | caller2 | -> | caller3 | -> | caller4 | -> | ... |
Думаю вы видите, к чему я клоню.
Потом ваша функция возвращает управление. Процессор декодирует вашу команду RET, он смотрит на адрес в стеке предсказателя переходов и говорит: "что-то подсказывает мне, что эта команда RET вернёт управление на L1. Я начну предварительное выполнение команд оттуда".
Но - ах нет! - значение в программном стеке вовсе не L1. Это - caller1. Предсказатель переходов процессора предсказал неверный адрес возврата, в результате чего процессор потратил время на изучение ненужного кода!
Но эффект от этого не заканчивается тут. После инструкции RET, стеки выглядят вот так:
| Адрес возврата Стек предсказателя: | caller1 | -> | caller2 | -> | caller3 | -> | ... | |
|---|---|---|---|---|---|---|---|---|
| Действительный стек: | caller2 | -> | caller3 | -> | caller4 | -> | ... |
Затем ваш вызывающий вернёт управление. И снова, процессор проконсультируется со стеком предсказателя переходов и начнёт спекулятивное выполнение инструкций по адресу caller1. Но вы возвращаетесь не туда - на самом деле вы вернётесь к caller2.
И так далее. Вводя дисбаланс в последовательность инструкций CALL и RET, вы сумели сделать так, что теперь каждое предсказание адреса перехода в стеке будет неверным. Заметьте на диаграмме, что если никто больше не будет играться со стеком так, как мы сделали изначально для создания проблемы, то ни одно предсказание по стеку адресов возврата предсказателя перехода не будет верным. Ни один из адресов в стеке предсказателя переходов теперь не соответствует адресам в программном стеке.
Ваша оптимизация "через щель" оказалась недальновидной.
Некоторые процессоры раскрывают это предсказание более явно. К примеру, Alpha AXP, имеет несколько типов инструкций по контролю потока выполнения, которые имеют одинаковый логический эффект, но содержат различные подсказки процессору по управлению внутренним стеком предсказаний переходов. Например, инструкция BR говорит: "перепрыгни на этот адрес, но не заноси старый адрес в стек предсказаний". С другой стороны, инструкция JSR говорит: "перейди на этот адрес и занеси старый адрес в стек предсказателя переходов". Есть также и инструкция RET, которая говорит: "перепрыгни на этот адрес и извлеки адрес из стека предсказателя" (имеется и четвёртый тип, который, впрочем, довольно редко используется).
Мораль истории: просто потому, что что-то выглядит лучше, не означает, что оно действительно лучше.
Подписаться на:
Сообщения (Atom)