В преддверии очередной конференции C++ Siberia, я решил выложить на всеобщее обоЗачастую, знакомство с алиасингом в C++ у многих программистов начинается и заканчивается одинаково:
В докладе сделана попытка заглянуть под капот компилятора и понять, что же там, внутри? Что такое alias analysis, где он может быть полезен, в чем его преимущества и недостатки. Тема рассмотрена и со стороны программиста и со стороны разработчика компилятора. А по сему, вопрос «зачем?» был центральным.
В докладе вы найдете:
- Код Quake3 и стандарт IEEE754
- Магическую константу 0x5F3759DF
- Много ассемблера x86
- Много IR кода LLVM
- Rust, Java и даже Fortran
Поэтому прошу вас концентрироваться на докладе, а не на моей печальной физиономии
Комментарии (36)
red75prim
24.07.2016 17:51Если очень очень очень коротко:
float as_float(int* p_i) {
float * p_f = (float*) p_i;
return *p_f;
}
этот код, скомпилированный без -fno-strict-aliasing, приводит к неопределенному поведению, так как компилятор имеет право считать, что p_f и p_i никогда не указывают на одну и ту же область памяти.DistortNeo
24.07.2016 19:20Можно ли как-нибудь лицезреть данный эффект в современных компиляторах?
Я прекрасно понимаю ситуацию с вычислением суммы или максимума, когда out-параметр указывает куда-то в область в обрабатываемых данных. Но это просто алиасинг, не связанный с strict-aliasing.
При этом я не понимаю, почему в указанном примере должно присутствовать неопределённое поведение, кроме как неоднозначного машинного представления чисел. Правильно ли я понимаю, что по стандарту компилятор должен вернуть мусор, т.к. предполагается, что p_f и p_i указывают на разные области памяти, а программист использовать «безопасные» способы, например, union?
Halt
24.07.2016 19:51Правильно ли я понимаю, что по стандарту компилятор должен вернуть мусор, т.к. предполагается, что p_f и p_i указывают на разные области памяти, а программист использовать «безопасные» способы, например, union?
Нет, не совсем так. Компилятор ничего не обязан сверх того, что предписано стандартом. Неопределенное поведение потому и опасно, что оно не определено. На вашей машине и вашем компиляторе все может сработать «как надо».
С точки зрения strict aliasing-а, значения существенно разных типов не могут алиаситься, то есть в программе не должно быть мест, где указатели, типированные несовместимыми типами будут указывать на один адрес.
Например, если у нас в программе есть IR код вида:
%float_ptr = alloca float
%int_ptr = alloca i32
; ...
store float 3.14, float* %float_ptr, !tbaa !1
store i32 42, i32* %int_ptr, !tbaa !0
; ...
%float_value = load float* %float_ptr, !tbaa !1
; ...
!0 = metadata !{ metadata !"int32" }
!1 = metadata !{ metadata !"float" }
…то при включенном strict aliasing-е, оптипизатор имеет полное право протолкнуть константу 3.14 в загружаемое значение %float_value минуя операцию load, поскольку операции тэгированы типами, которые с точки зрения семантики языка являются несовместимыми.
Тем самым мы экономим одно обращение в память в локальном контексте, которое может привести к большим последствиям, если окажется внутри цикла и позволит инлайнить или векторизовать весь участок.
Все ужасы которые выполняет оптимизатор направлены в конечном итоге на производительность и достигаются ценой определенных уступок. Поскольку отказываться от оптимизаций никто не хочет, имеем что имеем.firsttimecxx
24.07.2016 23:48-1>>то при включенном strict aliasing-е, оптипизатор имеет полное право протолкнуть константу 3.14 в загружаемое значение %float_value минуя операцию load, поскольку операции тэгированы типами, которые с точки зрения семантики языка являются несовместимыми.
Оптимизатор чего? В том же шланге на уровне фронтенда? Да и в любом другом компиляторе.
Сама по себе логика оптимизацией основанная на семантики языка не имеет смысла, вернее имеет мало смысла. Оптимизация на то и потимизация, чтобы выйти за семантику языка. Код должен делать что от него требуется, но не должен следовать семантики написанного кода.
Поэтому какой-то алиасинг на уровне вменяемого компилятора в данном случае не имеет смысла, ибо компилятор итак знает есть там алиасинг или нет. Нахрен это впилили в стандарт С++, когда как С++ без сильного компилятора не имеет смысла к существованию — мне так неведомо.
В конечном итоге и банальная логика, и банальное устройство компиляторов говорит за то, что стрикт алиасинг не имеет смысла и не должен использоваться. Собственно все сменяемые компиляторы этого придерживаются и ни разу я его не видел.
>>Все ужасы которые выполняет оптимизатор направлены в конечном итоге на производительность и достигаются ценой определенных уступок.
Стрикталиасинг не имеет никакого отношения к оптимизациям на том уровне оптимизаторов, которые в эту оптимизацию вообще могут. Там где нет алиасинга — компилятор об этом знает, а там где он есть — это нарушает поведение на которое надеялся тот, кто его писал. Кому нужен профит, если он ломает код, при этом пусть и ломает в рамках стандарта?Halt
25.07.2016 06:46+1Спасибо за развернутый комментарий!
Оптимизатор чего? В том же шланге на уровне фронтенда? Да и в любом другом компиляторе.
В данном случае речь про проход SimpleTBAA.
Сама по себе логика оптимизацией основанная на семантики языка не имеет смысла, вернее имеет мало смысла. Оптимизация на то и потимизация, чтобы выйти за семантику языка. Код должен делать что от него требуется, но не должен следовать семантики написанного кода.
Вы говорите про наблюдаемое поведение, я говорю про соответстве стандарту.
К слову, интересный момент заключается в том, что в отличие от языков C/C++, компилятор Rust может позволить себе использовать strict aliasing без ущерба для программиста. Но там это достигается как побочный результат системы типов языка, поскольку Rust на этапе компиляции обеспечивает отсутствие алиасинга читающих и модифицирующих указателей. Можно почитать например эти старые, но интересные статьи: раз и два.
Поэтому какой-то алиасинг на уровне вменяемого компилятора в данном случае не имеет смысла, ибо компилятор итак знает есть там алиасинг или нет. Нахрен это впилили в стандарт С++, когда как С++ без сильного компилятора не имеет смысла к существованию — мне так неведомо.
Компилятор далеко не всегда знает, есть или нет. Может оказаться так, что единственное что есть на руках у компилятора, это прототип функции которую надо вызывать, или прототип функции откуда она получила два значения. В этом смысле strict aliasing работает как последняя способ для компилятора.
Но вы правы в том, что современные компиляторы стараются проводить честный data flow анализ, вместо того, чтобы слепо следовать стандарту.
Стрикталиасинг не имеет никакого отношения к оптимизациям на том уровне оптимизаторов, которые в эту оптимизацию вообще могут. Там где нет алиасинга — компилятор об этом знает, а там где он есть — это нарушает поведение на которое надеялся тот, кто его писал. Кому нужен профит, если он ломает код, при этом пусть и ломает в рамках стандарта?
Вы сами себе противоречите. Сначала вы говорите про выход за семантику языка, потом что код перестает соответствовать тому, что задумал программист. Зачастую люди сами не знают, что они тут написали, а вы хотите чтобы компилятор это понимал. Именно так и происходит, что «код должен делать что от него требуется, но не должен следовать семантики написанного кода».
В конечном итоге и банальная логика, и банальное устройство компиляторов говорит за то, что стрикт алиасинг не имеет смысла и не должен использоваться. Собственно все сменяемые компиляторы этого придерживаются и ни разу я его не видел.
Устройство компиляторов далеко не банально, как и логика, за ними стоящая. Давайте все же не будем обсуждать личные качества разработчиков стандарта/компиляторов а сконцентрируемся на описании того что есть. Я не ставлю себе целью защитить strict aliasing, я стараюсь всего лишь донести информацию.firsttimecxx
25.07.2016 22:19-3>>В данном случае речь про проход SimpleTBAA.
Это обычный поиск алиасов, о котором я говорил. Где именно логика из крестов/с с их стрикталиасингом?
>>Вы говорите про наблюдаемое поведение, я говорю про соответстве стандарту.
Я говорю про ожидаемое поведением, про вменяемое поведение и банальную логику. Я критикую стандарт — с чего вдруг я должен ему следовать? Я где-то писал иное?
>>К слову, интересный момент заключается в том, что в отличие от языков C/C++, компилятор Rust может позволить себе использовать strict aliasing без ущерба для программиста.
Не может — это невозможно.
>>Но там это достигается как побочный результат системы типов языка, поскольку Rust на этапе компиляции обеспечивает отсутствие алиасинга читающих и модифицирующих указателей.
В конечном итоге всё так хорошо начиналось, но свелось к решению проблемы «болит голова» отрубанием головы.
>>The simplest rule is that raw pointers (*T and *mut T) may alias with anything and everything.
А далее тупо нельзя писать в не уникальную ссылку. При этом опять же в ансейфе это работать не может, при работе с биндингами так же. Ну и делается это руками, а не компилятором. Зачем мне использовать не читаемое нагромождение синтаксиса лишь потому, что авторы раста не смогли это сделать на уровне компилятора, при этом сравнивают с языками, в которых это делать не надо.
>>fn curry<A: Copy + 'static, B: 'static, C: 'static>(f: Box<Fn(A,B) -> C>, a: A) -> Box<Fn(B) -> C> {
Box::new(move|b: B| {f(a,b)})
}
И прочие страшилки.
Да и что за мода сравнивать поведение того, чего нет и поведение того, что есть.
>>Компилятор далеко не всегда знает, есть или нет. Может оказаться так, что единственное что есть на руках у компилятора, это прототип функции которую надо вызывать, или прототип функции откуда она получила два значения.
Ну это уже зависит от того как писать. Входит и выход указателей с разными типами довольной редкий юзкейс, а в случае с одинаковыми оно не может. Хотел написать ремарку про аргументы недоступных функций, но подумал, что это итак ясно.
>>В этом смысле strict aliasing работает как последняя способ для компилятора.
Опять же — на каком уровне ему работать в рамках того же шланга? Я не эксперт, но вроде вся работа с ир — это прерогатива ллвм, а там они должны быть обобщенными. Впиливать какие-то проходы в сам шланг? Хотя возможно там они и есть.
В конечном итоге есть рестрикт, который должен решать эту проблему. Его итак надо использовать в более общем юзкейсе — если к этому добавится и более редки — ничего сложного. Это решит все проблемы без создания новых.
>>Вы сами себе противоречите. Сначала вы говорите про выход за семантику языка, потом что код перестает соответствовать тому, что задумал программист.
Нет. На уровне семантики есть только поведение кода. Компилятор меняет поведение того, что написал я. Т.е. код не соотносится с семантикой тех контрукций, что написал я.
А то, что задумал программист как результат — это не семантика языка — это уже левая логика и строится она уже на результатах, а не на самих конструкциях.
И да, оптимизатор ломает то, что написал программист. Я написал «крутить цикл» — он его не крутит и прочие проблемы стана «бенчмаркеров».
>>Зачастую люди сами не знают, что они тут написали, а вы хотите чтобы компилятор это понимал.
Я ничего не хочу — эти лишь ваши попытки меня на чём-то поймать и как-то интерпретировать мои слова в свою пользу выдёргивая их из контекта.
В данном случае компилятор знает что хотел программист и используя стрикт-алиасинг — он ломает код. Такое поведение, даже если оно соответствует стандарту, не очень приемлемо.
>> Именно так и происходит, что «код должен делать что от него требуется, но не должен следовать семантики написанного кода».
Но он не делает, при этом это невалидная оптимизация, которую без пункта стандарта «руби с плеча» компилятор бы никогда не сделал.
>>Устройство компиляторов далеко не банально
Ну это спорный вопрос банальный ли компилятор того уровня на котором он сейчас находится, вернее является ли он менее банальным в сравнением с любым другим проектом того же класса.
Но я об этом не писал — банальным я назвал не устройство компилятора, а причину. «банальная причина — устройство компилятора» — это допущение можно легко интерпретировать верно уже из того, что уточнение «какое именно устройство» у компилятора в данном контексте не имеет смысла.
>>Давайте все же не будем обсуждать личные качества разработчиков стандарта/компиляторов а сконцентрируемся на описании того что есть.
Никому не интересны личные качества каких-то там разработчиков и я их не обсуждаю — мне они не интересны. Я обсуждаю их творения. Я написал почему стрикт-алиасинг не имеет смысла и привносить больше проблем чем пользы, а для получения той же пользы — уже давно в языке есть средства.
Хорошо — то что есть. Я не видел ни одного(не протухшего, не убогого) компилятора, который бы следовал стрикт-алиасингу. Ни шланг, ни гцц ему не следуют, либо я этого не видел, а видел я много.
Зачем же тогда обсуждать то, чего нет? Надо определиться. Зачем решить те проблемы, которые решать не надо? Надо просто выкинуть убогое решение, которое их создаёт и не даёт профит.
>>Я не ставлю себе целью защитить strict aliasing, я стараюсь всего лишь донести информацию.
Я видел ваш доклад. Он строится на невнятной критике и «фи» в адрес код, который перестал работать, либо не работает из-за стрикт-алиасинга. Тем более нигде не указывается, что «может авторы его выкинули», «может авторам не нужно ничего кроме 1/2компиляторов и ни один компилятор этого код не ломает», «может код собирается вообще с другим стандартов, в котором нет стрикт-алиасинга», да и вообще с чего вдруг код плох — плохо тут стрикт-алиасинг, а не код.
Если вы его не защищаете и внятно оцениваете, но при этом хотите людям донести сам факт его наличия и что он может сделать — дак так и делайте.
Да и сама аргументация «не просто так», про юнион и прочее. Про разработчиков ОС, который к синшным биндингам из glibc не имеют никакого отношения. Про магию с transparent_union, которая нужна не для стрикт-алиасинга, а для того, чтобы компилятор не ругался на несовместимые типы указателей. В функцию передаются юнион — один тип. Указатели спокойно накладываются в юнионе, а атрибут к этому не имеет никакого отношения — он лишь позволяет кастовать в него те типы, которые в нём есть.
Тем боле опять же — это не «системый кастыль» — это гнуц. Тем более всё это к теме не имеет никакого отношения.
Тем более всё это нужно для тайпсейфа, а не для реализации. Для реализации там достаточно void *.
Всё это глумление смотрится глупо и отбивает всё желание это смотреть. Зачем это? Произвести вауэффект на зелёных?
red75prim
26.07.2016 00:52+2Насчёт страшного Rust кода. Если бы вы внимательнее посмотрели мои ответы на LOR'е, то могли бы заметить, что был предложен и более компактный вариант, а также объяснено почему необходимы лайфтаймы и trait bounds.
firsttimecxx
27.07.2016 10:19-4Очередное враньё ради плюсиков. Можно ссылку на ответ, где описывается «более компактные», либо «почему необходимы лайфтаймы»? Не на уровне «Нужно потому что нужно».
По поводу раста и его лайфтаймов. Я с каждым разом всё больше и больше удивляюсь как можно людей дурить и как под новой обёрткой им можно впаривать всё, что угодно.
Было время, когда все боролись с ручным управлением памятью. Все орали — С/С++ говно, ибо надо руками — нужны средства без рук. Появилась жава и прочие языки с гц.
Теперь же появился раст и впаривает то же самое ручное управление памятью, только не уровня «убить кусок», а на уровне хинтов при его передаче «жив, жив, мёртв» — это ещё больше действий.
Далее, пропаганда везде орёт, что в расте сила земли(компилятора) и он что-то сам, хотя на самом деле руками и нихрена не сам(ну максимум он может сказать, что «ты сказал „мёртв“, а передал дальше — ошибка»).
Синтаксис же просто «без слёз не взглянешь» — каждый раз адепты и пропагандисты тебе расскажут, что вот-вот он поменяется и будет вменяемым, но ничего не происходит. Раньше то же самое орали про «у нас свой синтаксис — кресты дерьмо — ко-ко-ко», а после все свои попытки над синтаксисом выкинули и взяли крестовый.
А потом пойдут оправдания «да как мы хотим невозможно сделать не руками», а на вопрос «а с чего это должно быть так, как вы хотите?» — ответа нет.
А далее тайлшлангер ниже пытался поспорить с крестовиком опять и опять слился. Со мною конечно он спорить не будет, ибо его я раскатаю как и раскатывал до этого, но опять же — почему все адепты раста такие ограниченные?
Почему про «троллейбус из буханки», раст, llvm, стрикт-алиасинг, кресты — мне рассказывают всегда нули? Потому что кто-то более шарящий не купится на такую херню? Потому что ему надо работать, а не онанировать на раст/смалтак и прочие куллстори?
Если бы, если бы. Смешно. Надоело уже с вами играться. Есть что ответить — отвечай. Нету? Минусуй в крысу и проходи мимо.Halt
27.07.2016 10:45+3Я выложил доклад ради обсуждения, в том числе чтобы вы написали свое мнение и прокомментировали моменты, которые вам показались откровенно неверными. Чтобы хоть в одном месте можно было бы нормально поговорить на русском языке по интересующим темам и обсудить сильные и слабые стороны.
Откуда в вас столько ненависти? Никогда не думал что в дискуссии о компиляторах будут переходить на личности и кидаться грязью. Впрочем, дискутировать на эту тему действительно скучно.firsttimecxx
27.07.2016 13:59-5Я выложил доклад ради обсуждения
И где же это обсуждение? Его нету. Единственный тут человек, который что-то обсуждал по теме — это я. Но по теме дискутировать никто не хочет, ибо ваша привычная аудитория — это те, кто смотрят в рот и перед кем можно бахвалится примитивными и неверными познаниями.
Чтобы хоть в одном месте можно было бы нормально поговорить на русском языке по интересующим темам и обсудить сильные и слабые стороны.
Поговорили, обсудили? Ведь именно того, кто может говорить вы(аудитория подобная вам) минусуете, а почему минусуете? Ну мотивация «бессилие» понятна, но всё же.
Я вам написал основной минус — убогое бахвальство. Это свойственно всем в рамках слабой аудитории. Убогое противопоставление себя другим с реакция мамки во имя защиты своей темы. Как только я начал говорить плохо про стрикт-алиасинг — я сразу стал плохим, сразу начались попытки сменить тему и прочее. Зачем?
>>Откуда в вас столько ненависти?
У меня нет ненависти — у меня есть вменяемая оценка действительности. Вам же не 5лет, чтобы сюсюкать, либо почему я кому-то должен лизать жопу? Почему вы должны?
Я с чем-то несогласен — говорю прямо. Я не собираюсь писать обтекаемо, аля «ну ты тоже прав, мы все правы, но я считаю, что надо иначе — я не настаиваю, ты прям, прости меня, что вообще заикнулся об этом — молю, послушай меня, ответь мне — я буду молится на тебя во имя ответа твоего».
>>Никогда не думал что в дискуссии о компиляторах будут переходить на личности и кидаться грязью.
Я уже писал в другой теме — повторю. У вас, как и большинства банальная брешь в восприятии. Вы всю критику в адрес чего-то экстраполируете на себя. Ругаю я жабку при жабисте — он воспринимает это так, буд-то я перехожу на личности. Ругаю я доклад и отношение — я перехожу на личности. Естественно умение внятно оценивать критику в адрес своей работы — это сложно и мало кому доступно, но обвинение меня во имя оправдания себя — фу.
Критика, несогласие, отсутствие порывов лизать жопу — это не кидание грязью. Если вы не согласны с тем, что то, что вы мне пишете является непотребством — надо объяснить почему и доказать.
Да, как и все верующие вы очень ранимые когда кто-то что-то без благоговения и возвеличивания говорит в адрес объекта ваших верований, но такова жизнь. Без разницы во что верить — в раст, в го, в ллвм, в смалток и прочее. Вера отличается от вменяемости(осознаного выбора) отличается тем, и потому она такую попоболь вызывает у верующих, что вера — это вера и аргументировать за выбор, за свои утверждения верующий не может. Если бы это был осознанный выбор — у вас бы никаких проблем отстоять свою ТЗ не возникло бы, как это не возникает у меня.
firsttimecxx
27.07.2016 14:05-2Если вам нужно по теме вашего доклада — я сделаю вам разбор с таймингами. И да, они не показались мне «не верными» — они и есть не верные. Не согласны — опровергните.
red75prim
27.07.2016 14:57+1Очередное враньё ради плюсиков. Можно ссылку на ответ, где описывается «более компактные», либо «почему необходимы лайфтаймы»?
Почему в функции curry необходимо указать лайфтаймы и trait bounds
Причесанный вариант функции из поста с более компактной записью функции curryfirsttimecxx
27.07.2016 16:04-1Ну уже двое скооперировались и в 2-х минусуют и друг друга плюсуют. Бывает.
>>Почему в функции curry необходимо указать лайфтаймы и trait bounds
Враньё. Конкретную цитату где объясняется «также объяснено почему необходимы лайфтаймы»? Хотя уже поплыл, уже поплыл и начал «необходимо указывать», нет, нет — такое не прокатит.
>>Причесанный вариант функции из поста с более компактной записью функции curry
Опять же враньё — никакой компактности там нет.
fn curry<'a, A: Copy + 'a, B: 'a, C: 'a>(f: Box<Fn(A,B) -> C + 'a>, a: A) -> Box<Fn(B) -> C + 'a> {
Box::new(move|b: B| {f(a,b)})
}
fn curry<A: Copy + 'static, B: 'static, C: 'static>(f: Box<Fn(A,B) -> C>, a: A) -> Box<Fn(B) -> C> {
Box::new(move|b: B| {f(a,b)})
}
Длинна портянки уменьшилась на пол символа — такая себе компактность.
Ну в целом в очередной раз убеждаемся в уровне аргументации адептов руста, да и в целом в их вменяемости. Вам же, конечно, доказывать что-то бесполезно, но авось кого-то я спасу от вашей участи.
Halt
24.07.2016 20:07Вообще, рекомендую прочитать отличную серию статей в блоге LLVM на эту тему:
- What Every C Programmer Should Know About Undefined Behavior, часть 1
- What Every C Programmer Should Know About Undefined Behavior, часть 2
- What Every C Programmer Should Know About Undefined Behavior, часть 3
Antervis
24.07.2016 21:18когда компилятор с++ видит const-ссылку на объект, он предполагает, что значение иммутабельно в контексте блока?
Halt
24.07.2016 21:26Если коротко, то константность заканчивается на уровне семантики языка. На уровне IR она выглядит как спецификаторы readonly, readnone, но они являются рекомендацией для проходов.
Насколько я помню, неверно проставленный спецификатор не приведет к ошибке компиляции, но может спровоцировать UB, если по этому адресу память все же будут писать.
Выдержка из документацииreadnone
On a function, this attribute indicates that the function computes its result (or decides to unwind an exception) based strictly on its arguments, without dereferencing any pointer arguments or otherwise accessing any mutable state (e.g. memory, control registers, etc) visible to caller functions. It does not write through any pointer arguments (including byval arguments) and never changes any state visible to callers. This means that it cannot unwind exceptions by calling the C++ exception throwing methods.
On an argument, this attribute indicates that the function does not dereference that pointer argument, even though it may read or write the memory that the pointer points to if accessed through other pointers.
readonly
On a function, this attribute indicates that the function does not write through any pointer arguments (including byval arguments) or otherwise modify any state (e.g. memory, control registers, etc) visible to caller functions. It may dereference pointer arguments and read state that may be set in the caller. A readonly function always returns the same value (or unwinds an exception identically) when called with the same set of arguments and global state. It cannot unwind an exception by calling the C++ exception throwing methods.
On an argument, this attribute indicates that the function does not write through this pointer argument, even though it may write to the memory that the pointer points to.
DmitryShm
25.07.2016 06:47Похоже на ещё одну тему, которую мало кто затрагивает на практике. Зато сейчас начитаются википедий и вовсю будут спрашивать на собеседованиях.
Halt
25.07.2016 06:48+1То, что ее «мало затрагивают на практике», не означает, что в один прекрасный момент оно не выстрелит. Как я уже писал выше, я стараюсь донести информацию, а не защищать какую-либо из сторон.
Про горе интервьюеров однако же я с вами соглашусь :) Но на моей практике они мгновенно сливались, когда начинаешь их самих выводить на чистую воду.
entomolog
25.07.2016 07:37+1Не совсем по теме strict aliasing, но все же. Насколько умным компилятор может быть, чтобы вывести что указатели не имеют aliasing?
Дело в том, что имею такую привычку, когда все возможные оптимизации в tight loop'е заканчиваются, лепить restrict везде, где только можно. Не редко неплохо помогает. Хотелось бы знать кейсы где этого делать нету необходимости, а где все же желательно.
Вот например, представим такой класс:
struct bar { int Summation(const float* input, int n) { sum = 0; for (int i = 0; i < n; ++i) { sum += input[i]; } }; float sum; }
С одной стороны здесь нету out параметра и все хорошо, но с другой стороны, обращение к sum происходит через указатель this и компилятору никто не дает гарантий что указатель на sum не будет иметь aliasing с input.
По сути, компилятор будет вынужден на каждом прибавлении к sum делать store.
Я как то наблюдал aliasing в этом случае с MSVC, с тех пор, предпочитаю в случае с tight loop'fми копировать содержимое членов класса в локальные переменные перед входом в цикл, а затем копировать обратно после выхода.
Но это в случае с MSVC, где нету strict aliasing. Что будет делать в этом случае LLVM?
Или другой пример:
struct bar { int Summation(const float* input, int n) { *sum = 0; for (int i = 0; i < n; ++i) { *sum += input[i]; } }; bar() { sum = new float; }; ~bar() { delete sum; }; private: float* sum; }
В этом случае, компилятор мог бы вывести, что указатель sum не может иметь aliasing с input. Указатель sum в приватной секции и мы аллокейтим память, которая априори не может пересечся с input. Поэтому кажется, что компилятор может опустить store в *sum внутри цикла, а сделать store только по выходу.
Но что-то не уверен компилятор может так рассуждать. В конце концов мы могли перегрузить new, нужно еще запретить копирование, да и приватная секция ничего не значит, мы могли бы положить туда указатель на любой участок памяти.
Вопрос в том, что действительно все так плохо и пару лишних restrict + копирование в локальные переменные не помешают, или это паранойя?
Спасибо.Halt
25.07.2016 09:09Если коротко, то все сильно зависит от контекста. Компилятор выполняет сложный data flow анализ, чтобы понять откуда берутся значения. В этом смысле он заглядывает гораздо глубже чем просто определения поле/параметр.
Можете поиграться с вашим кодом в онлайн компиляторе. Попробуйте раскомментировать другой вариант и посмотреть, как изменится листинг. IR код можно посмотреть добавив ключ -emit-llvm в строку параметров компилятора.
Вообще, советую не ударяться в преждевременную оптимизацию без весомых на то причин. Принимать решения о реорганизации кода в угоду скорости стоит тогда, когда без этого уже совершенно точно не обойтись.
Грамотная архитектура, правильная расстановка const и использование алгоритмов стандартной библиотеки как правило позволяют достичь неплохих результатов и без черной магии. Если же код такой, что и человек в нем еле разбирается, то было бы наивно полагать, что «компилятор все оптимизирует».entomolog
25.07.2016 11:31+1Спасибо за ссылку
Да, когда в качестве аргументов используются константы, все кончено оптимизируется на ура и компилятор просто вычисляет сумму заранее. Попробовал второй вариант, где аргументы приходят из вне, вот тут интереснее:
Вот такой кодstruct foo { int get_sum(const float* input, int size) { sum = 0; // try uncomment this for (int i = 0; i < size; ++i) { sum += input[i]; } return sum; }; float sum; }; foo* get_foo(); float* get_floats(); int main(int argc, char** argv) { float* floats = get_floats(); foo* foo = get_foo(); return foo->get_sum(floats, 10); }Halt
25.07.2016 12:01В данном примере, с get_floats() и get_foo() у компилятора нет ни малейшого шанса что либо проверить, поэтому предпологается худший вариант. Что будет происходить в реальном случае я без понятия.
Да, вы верно поняли. Нелокальная переменная индукции без представления о времени жизни объекта не может быть оптимизирована.
Может компилятор сможет отследить все вызовы и все таки догадается, что там нету aliasing? А что если там полиморфизм замешан, и таблица указателей на виртуальные функции, что тогда?
Современные компиляторы очень умные.
Если компилятор, после выполнения dataflow analysis поймет, что объект порождается и используется в локальном контексте, что указатель на него не утекает вовне, а функции объекта не имеют побочных эффектов за пределами контекста, то в таком случае он может и положить переменную индукции/свертки «поближе», а то и затолкать в регистр (например выполнить оптимизацию mem2reg).
Если анализ стоимости цикла покажет, что его выгодно векторизовать, то будут произведены разворачивание цикла и его векторизация. Обратите внимание, насколько сложные конструкции могут быть векторизованы.
Виртуальные вызовы могут быть девиртуализованы, если компилятор обладает достаточными сведениями об иерархии классов и контексте вызова. Это очень активно применяет мой JIT компилятор llst, о котором я уже писал.
К слову, даже после генерации объектного файла данной единицы трансляции остается возможность для оптимизации. Если компилятор поддерживает LTO, то после линковки модулей могут быть выполнены дополнительные проходы оптимизации. В вашем примере, если на этапе линковки выяснится, что get_foo() и get_floats() выплывают из такого локального контекста, компилятор (линкер?) может произвести инлайнинг и оптимизацию кода. Разумеется, если будет доказана безопасность такого маневра.
Gumanoid
25.07.2016 15:39Вместо restrict и локальных переменных можно писать #pragma omp simd перед циклом.
Antervis
25.07.2016 14:04+1кстати, вот еще интересный вопрос. А компилятор может решить, что ему выгоднее проверить алиасинг в рантайме и в зависимости от этого выполнять MustAlias/NoAlias ветки, нежели генерировать код для MayAlias?
Halt
25.07.2016 14:44+2До сих пор в компиляторах я видел только статический алиас анализ. Однако существуют научные работы, изучающие динамический анализ, например: 1, 2, 3.
Например в первой работе получают интересные результаты:
The experiments yielded that for several programs the statically retrieved data is enormously worse. An example proves that feedback-directed compilers сould greatly enhance program performance for the expected subset of pointers. Also the data can provide an optimistic up to optimal estimate of the points-to sets, which can be used if the statically obtained data is too coarse to be useful.
6opoDuJIo
можно будет потом в текстовом виде это узреть?
Halt
Да, конечно. Я давно хотел оформить эту тему в виде статьи, но последние 4 месяца писал код вывода типов для llst.
Я планирую оформить очередную статью про llst по результатам работы, добавив к ней материалы из февральского доклада.
Halt
Пока могу предложить только слайды в виде pdf.
Gitkan
Странно, мой провайдер сообщает, что ссылка ведёт на запрещённый ресурс
Halt
Действительно странно. Вот прямая несокращенная ссылка: тык.
Vjatcheslav3345
Приложите текст речи, пожалуйста — из неё получится хороший конспект.
Halt
Пожалуйста. Вот тут можно найти опорные фразы в pdf. А полного текста речи у меня не бывает.
Halt
Кстати, на Хабре есть хорошая статья «Про C++ алиасинг, ловкие оптимизации и подлые баги» за авторством shodan.