​Static глобальные переменные

Начнем разбирать тонкие моменты применения static. В контексте глобальных переменных.

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

Первое, что стоит понимать - static обозначает определенный цикл жизни объекта. Например, цикл жизни объекта на стеке - от создания до выхода из скоупа. А для статических глобальных переменных их цикл жизни начинается до захода в main(причем порядок инициализации глобальных объектов не определен), сохраняется в течение всего времени существования программы и заканчивается после выхода из main.

Второе - static указывает на место хранения. Статические глобальные переменные хранятся в сегменте данных - .data segment. Это место в адресном пространстве, где находятся все глобальные и статические переменные. Также это Read-Write сегмент, поэтому мы спокойно можем изменять данные, которые в нем находятся(в отличие от .rodata segment).

Третье - это ключевое слово определяет тип линковки для сущности. В данном случае у объекта появляется внутреннее связывание. Это значит, что объект будет недоступным для других единиц трансляции. Никто другой его не увидит. И даже если такой объект будет определен в хэдере, который будет подключаться в разные единицы трансляции, то в каждой из них будет создаваться своя копия этого объекта и эти копии будут уникальными для своего юнита. И это будут именно копии, то есть несколько экземпляров. А значит памяти все это дело будет занимать больше.

Расскажу чуть подробнее про линковочный аспект. Каждая единица трансляции компилируется независимо от остальных. На этом этапе компилятору может не хватать данных(например у него есть только объявление сущности), поэтому он вставляет в такие места заглушки. Эти заглушки заменяет на ссылки на реальные символы уже линкер. Так вот. У каждой единицы трансляции создается свой .data segment и там лежат глобальные и статические переменные, определенные в этом юните. Когда вы в хэдере определяете статическую переменную, это ее определение попадает в ту единицу трансляции, куда этот хэдер был включен. Соотвественно, в каждом таком юните будет свой сегмент данных, каждый из которых будет содержать свою копию. И у каждой из них даже скорее всего имя будет одинаковым.

Но потом приходит компоновщик и объединяет все юниты трансляции в один исполняемый файл и, в том числе, он объединяет сегменты данных. Поэтому в объединенном .data segment у вас будут 2 объекта с потенциально одинаковым символьным представлением(хотя с чего они должны быть разными). Например, для целочисленной переменной с именем qwerty, ее внутреннее представление может иметь примерно такое имя - _ZL6qwerty. Разные могут быть варианты манглинга, но что-то похожее на это так или иначе будет. И вот такие экземпляров будет 2. Только у них разные адреса будут и каждая из них будет относится только к своему "модулю" программы. А конфликтовать они не будут, потому что линкер по очереди обрабатывает эти единицы трансляции и жестко привязывает символы к адресам в памяти.

Вроде довольно подробно рассказал. Задавайте вопросы, если что-то непонятно. Поправляйте, если что не так описал. В общем, ждем в комментах)

Stay based. Stay cool.

#compiler #cppcore #hardcore

​Пропуск конструкторов копирования и перемещения

Недавно был опубликован пост про RVO/NRVO. Какой еще можно сделать вывод из этой статьи?

Конструкторы копирования/перемещения не всегда могут быть вызваны! И если вы туда засовываете, например, какие-то счетчики, которые должны влиять на внешний код, то будьте готовы, что они могут остаться нетронуты.

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

Конечно же, такую оптимизацию можно отменить с помощью флага компиляции:

-fno-elide-constructors

Тогда всё всегда будет вызываться, но при этом с потерей производительности. С другой стороны, это в принципе кажется странным — конструкторы не должны менять ничего снаружи себя. Соблюдайте это правило, и всё будет хорошо!

#cppcore #algorithm #hardcore

​static inline

Мы с вами уже немного знаем про эти две вещи в отдельности. А сегодня мы разберем одну интересную вещь: что будет, если соединить эти два ключевых слова? Как изменится поведение сущностей в таком случае?

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

Рассмотрим static inline свободные функции. inline говорит компилятору, что эту функцию неплохо бы встроить, и это дает ей внешнее связывание. Теперь функцию можно определять во всех единицах трансляции единожды. И итоге код для всех этих определений объединится и будет один экземпляр функции в бинарнике. А вот static говорит, что у функции теперь внутреннее связывание и в каждой единице трансляции будет своя копия функции.

Нихера не клеится. Эти ключевые слова задают практически противоположное поведение. Как же они будут сочетаться?

static победит. И в каждой единице трансляции будет своя копия функции. inline здесь будет всего лишь подсказкой к встраиванию функции.
Однако здесь есть один интересный момент. Лишь для статической функции компилятор может попробовать встроить все ее вызовы и вообще не генерировать код для нее. Потому что static - гарантия того, что за пределами юнита трансляции никто не будет пробовать вызвать эту функцию. А значит, если получится в текущем юните встроить все вызовы, то и код функции вообще генерировать не нужно. Он просто никому не понадобиться. Для функций с внешней линковкой такой трюк не провернуть. Компилятор обязан для них генерировать код, потому что линкер потом может сослаться на вызов этой функции. И придется делать call, который должен перепрыгивать в тело функции.

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

К тому же это все справедливо и для хэдеров, и для цппшников.

Теперь про методы класса. Для них static не имеет того же значения, что и для предыдущих случаев. Статические методы - это по факту обычные свободные функции с внешним связыванием, которые имеют доступ ко всем полям класса. Поэтому в этом случае добавление inline просто будет явным намеком компилятору, что метод можно встроить. Хотя смысла от этого намека немного, ибо при этом всем, все статические методы, определенные внутри описания класса, неявно помечены inline, чтобы иметь возможность определять такие методы сразу в хэдерах и обходить odr.

И для полей класса. Мы кстати разбирали уже этот случай в этом посте. Пометив статическое поле inline, мы получаем возможность определять это поле внутри описания класса и не беспокоиться по поводу линкера и odr. Собственно, как и в случае с методами.

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

Combine things together. Stay cool.

#cpp17 #compiler #optimization

​inline constexpr

В прошлом мы уже обсуждали, что удобно определять константы в заголовочнике и помечать их inline constexpr. Я бы сегодня хотел поговорить в целом про два этих ключевых слова и рассмотреть, как они друг на друга влияют.

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

Теперь нужно посмотреть, какие особенности линковки у constexpr сущностей, чтобы понять, как они с inline взаимодействуют.

У нас опять куча вариантов, какие сущности мы можем пометить constexpr. Но в разрезе линковки их всего 2, поэтому будет полегче.

Первая группа - спецификатор используется при определении объектов. В этом случае подразумевается, что эти объекты помечены const. А это уже значит, что они базово имеют внутреннюю линковку. Кстати, константы можно помечать extern, чтобы у них сменился вид линковки с внутренней на внешнюю. А вот constexpr объекты - нельзя. Потому что связка объявления символа с его значением при внешнем связывании происходит на этапе линковки. А constexpr требует, чтобы значение было известно на этапе компиляции.

Вторая группа - функции и статические члены класса. В этом случае подразумевается, что они неявно помечены inline. На это есть весьма веские причины(по-другому и не делается). Функции, которые могут выполнять вычисления в compile-time, должны быть видны на этом самом этапе компиляции всем единицам трансляции. Так что extern мы сразу отбрасываем, такого не может быть. Они могли бы помечаться static, но тогда потенциально будет дублироваться код функции во всех единицах трансляции. А inline решает все проблемы. Функцию видно во всех единицах трансляции, куда она подключается. А код на этапе линковки объединяется в одно определение и никакого дублирования.

Для статических полей класса похожая схема. Раз их определение должно быть видно всем единицам трансляции, которые видят этот класс, то их нужно определять внутри описания класса. А это(за исключением пары случаев) можно сделать только, если пометить статический член как inline.

Получается, что нет смысла писать inline constexpr для любого рода функций(которые в принципе могут быть constexpr) и для статических поле классов. Это можно сделать, чтобы подсветить эту конкретную особенность и намерение(?), но, на самом деле, непонятно, что это изменит.

А вот глобальные объекты есть смысл помечать inline. Чтобы избежать издержек внутренней линковки объектов. Поэтому в примере из прошлого поста именно так и было сделано.

Продолжаем штудировать тему inline и линковки. Если вы устали от этой однотипной тематики, то ставьте реакцию🗿, постараемся разбавить эту духоту. Хочется просто сделать связный рассказ, чтобы вы из контекста не выпадали. Но если это мешает, то поменяем тактику.

Dig to the core. Stay cool.

#cpp11 #cpp17 #cppcore #compiler

​Ретроспектива

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

«Нормальные люди… считают, что если не сломано – не чини. Инженеры считают, что если не сломано – значит недостаточно улучшено» – Скотт Адамс.

Я глубоко убежден, что всё находится в вечной градации: либо развивается, либо деградирует. Причем, деградация – это неявно определенное поведение по умолчанию компилятором жизни 😅 В основном, потому что развивается что-то другое, более естественное, чем разработка ПО. Следовательно, необходимо явно определять поведение, влияющее на наше развитие в контексте коллективной разработки.

Одним из таких инструментов самоорганизации является ретроспектива. Какие преимущества она несёт?

• Улучшение процессов
Нет смысла тратить время зря, если это не является целью встречи. Возможно, это другое собрание.

• Укрепление команды
Общие психотравмы объединяют 🤣 На самом деле, открытое общение помогает лучше понимать друг друга и доверять. Так же, это помогает вовлечь в процесс новых сотрудников.

• Целеполагание
Умение четко формулировать цели и находить пути к их достижению - это двигатель развития людей.

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

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

В книге «То как мы работаем, – не работает» Tony Schwartz пишет, что умение экономить силы на работе и эффективно их восполнять во время отдыха НАПРЯМУЮ определяет вашу продуктивность. Я полностью согласен с этим утверждением.

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

А вы проводите ретро у себя в команде? Помогает ли вам это?

#goodpractice

static inline constexpr

Когда-то давно @Igorlamerger попросил нас рассказать про inline, static inline и static inline constexpr. Отчасти эта большая серия постов и была предназначена как ответ на просьбу подписчика. И хотя мы уже столько всего обсудили, что, в целом, вы и так можете сказать, когда и как можно писать inline static constexpr. Но на всякий случай сегодняшний пост будет про это.

Был у нас уже вчера пост про inline constexpr, поэтому нам осталось только добавить к этому всему немного статичности)

Как мы знаем, constexpr для статических методов и полей класса подразумевает inline. Следовательно в этих случаях static обозначает принадлежность свободной функции или глобальной переменной к классу, а не объекту, и внешнюю линковку. constexpr здесь отвечает за возможность использования сущности в вычислениях времени компиляции, а inline обеспечивает эту возможность. Чтобы все единицы трансляции получили определение сущности во время компиляции.

Далее свободные функции и методы класса. Для них constexpr тоже подразумевает inline. Если к методу класса приписать static, то он будет уже не методом, а статической функцией, кейс которой мы обсуждали выше. Если для свободной, по факту уже, inline constexpr функции дописать static, то static кинет на прогиб ваш inline и навяжет свои правила. Эту функцию также можно будет продолжать использовать для compile-time вычислений, но в каждой единице трансляции будет своя копия этой функции. То есть тип линковки изменится с внешней на внутренюю.

Ну и теперь глобальные переменные. С ними ситуация почти такая же, как и со свободными функциями. Только здесь constexpr раскрывается в просто const и дает внутреннее связывание. inline говорит, что нихера подобного, пусть все тебя видят. И дает внешнее связывание. Но приходит static и в честном, бесконтактном бою закидывает невидимыми энергоударами инлайн и побеждает его. Связывание будет внутренним.

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

Be a master of your specialty. Stay cool.

#cppcore #cpp11 #cpp17 #compiler

​Ретроспектива с подписчиками #1

Буквально вчера был опубликован пост про ретроспективу. Естественно, это был прогрев 😃 Мы бы хотели провести своё собственное открытое ретро с подписчиками, большая надежда на ваш отклик! 😌

Напомню цель: необходимо закрепить хорошее, выявить и исправить плохое. Желательно подкрепить замечания какими-то фактами или наблюдениями, чтобы нам была понятна мотивация. Это может быть готовое предложение, наблюдение или вопрос.

Это может касаться абсолютно всего, что связано с каналом. Например:
- Управление: время публикаций, частота публикаций;
- Наполненность: план публикаций, сложность материала, глубина погружения в тему, душность, объём публикаций;
- Общение: время отклика, качество ответов, живость, вежливость;
- Поиск материала: сложность поиска, группировка постов, подготовка гайдов (т.е. методичек, сборников статей по теме);

Голосовать за важность чьей либо идеи предлагаем просто пальцами: 👍или👎. Так мы поймем, что действительно важно для нас. Данный тред будет актуален до следующей ретроспективы. Погнали! 👨‍💻

#retro

Почему нельзя объявлять нестатические поля класса constexpr?

В прошлом посте мы задели особенности линковки constexpr сущностей. Однако я не упомянул про нестатические поля класса. И не зря. Потому что нельзя нестатические поля объявлять constexpr. Но почему?

Давайте немного подумаем, что значит constexpr. В глобальном смысле подразумевается, что мы что-то можем вычислить во время компиляции. Для это придуманы константы времени компиляции(constexpr variables) и функции, которые способны делать вычисления в compile-time.

Причем на константы времени компиляции накладываются жесткие ограничения. Их инициализатор должен быть известен во время компилятору на этом самом этапе компиляции(или конструктор класса помечен constexpr). Только тогда можно создать такой объект.

И теперь взглянем на поле класса. Когда оно инициализируется? Правильно, в конструкторе. То есть мы должны начать создавать объект, чтобы инициализировать поле. А создаются объекты во время исполнения. Получается, что наше constexpr поле принадлежит сущности, которой вообще не существует до момента создания экземпляра класса. И как оно тогда может быть константой времени компиляции? Ведь если constexpr variable и создается, то создается только в compile time. А это просто невозможно в таком случае.

На самом деле поле класса может быть constexpr. Но неявно. Когда объект, в котором содержится это поле, сам является constexpr.

Посмотрите на пример на картинке. Там определяется класс с constexpr конструкторами и затем создается constexpr экземпляр этого класса. Чтобы проверить, действительно ли поле a является константой времени компиляции, можно попробовать вызвать шаблонную функцию с интовым шаблонным параметром. Так как шаблонный параметр - часть типа, то его значение должно быть известно на этапе компиляции. Поэтому, если все получится, то это докажет, что a - константа времени компиляции. И действительно, все работает. constexpr объект делает его поля constexpr.

Если мы попробуем разрешить помечать поля класса constexpr, даже одно единственное поле, значит нам нужно гарантировать, чтобы все поля становились constexpr(если это будет делаться неявно, то это явно кринж), и все объекты данного класса могли создаваться только в compile-time. Зачем это нужно? Да вроде как не за чем. В этом очень мало смысла. Можно выделить constexpr интерфейс и жить себе прекрасно в compile-time. И пользоваться полноценным интерфейсом во время выполнения. Слишком много неуверенности в полезности этой фичи. Поэтому и не разрешают так делать.

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

Reach new levels. Stay cool.

#cpp11 #compiler

​Inline под капотом

Мы уже знаем, что inline позволяет находится определению одних и тех же сущностей в разных единицах трансляции. А потом на этапе линковки, компоновщик объединяет все эти определения в одно. Но как конкретно он это делает? Как устроен этот механизм в деталях? Сегодня будем в этом разбираться.

Вернемся к примерам из вот этого поста(продублирую его в прикрепленной картинке к этому посту), но только уберем constexpr, чтобы компилятор не просто вставлял значение переменной в место ее использования, а прям создал эту переменную в секции .data, чтобы ее можно было видеть. Ну и пометим их static, чтобы на нас линкер не ругался. Да, это глобальная переменная, так нельзя делать, и ля ля ля. Но пример учебный, просто для понимания.

Как будет выглядеть переменная light_speed в единице трансляции, соответствующей файлу first.cpp?

.data
.align 4
.type    _ZN9constantsL11light_speedE, @object
.size    _ZN9constantsL11light_speedE, 4
_ZN9constantsL11light_speedE:
.long    299792458

Рассмотрим по порядку, что здесь происходит. Начинается сегмент данных, которые выровнены на 4 байта. Говорим, что наш символ _ZN9constantsL11light_speedE - это объект с размером 4 байта. И определяем этом символ, говорим, что он типа long со значением 299792458.

И в результирующем бинарнике у нас будет 2 экземпляра семантически одной переменной в разных единицах трансляции.

0000000000004010 d _ZN9constantsL11light_speedE
0000000000004020 d _ZN9constantsL11light_speedE

Что конечно может хорошенько подпортить жизнь трудноотловимыми багами. Не нужно объявлять в хэдерах изменяющиеся переменные как static. Но повторю, что это только учебный пример, чтобы показать интересности линковки inline. Много циферок - виртуальный адрес символа, а d значит, что символ инициализирован.

Теперь, что будет, если мы static заменим на inline.

.weak    _ZN9constants11light_speedE
.section     .data._ZN9constants11light_speedE,"awG",@progbits,_ZN9constants11light_speedE,comdat
.align 4
.type    _ZN9constants11light_speedE, @gnu_unique_object
.size    _ZN9constants11light_speedE, 4
_ZN9constants11light_speedE:
    .long    299792458

Здесь определяется слабый символ _ZN9constants11light_speedE. Слабый символ может быть переписан другим определением. Дальше идет секция данных и очень много страшных букв, но нам важно только последнее слово "comdat". Оно значит: "Здарова братишка, компоновщик! Не в службу, а в дружбу, не конкатенируй определения для символа _ZN9constants11light_speedE, а просто выбери из них всех одно и вставь в финальный бинарь. Мое увожение!". Это и есть тот маркер, по которому линкер определяет inline сущности. Ну и это все идет с компании с типом @gnu_unique_object, который должен быть уникальным во всех программе и это предотвращает дупликацию кода.

Тогда в бинарнике будет только одна запись на эту переменную.

0000000000004018 u _ZN9constants11light_speedE

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

Кстати, можно заметить пару деталей. В первом случае символ имел имя _ZN9constantsL11light_speedE, а во втором случае _ZN9constants11light_speedE.

Их объединяет то, что в оба имя включено название их нэймспейса. В С++ каждый символ имеет свое замангленное имя, которое может включать много всяких интересностей. Такое имя сильно облегчает компилятору и линкеру работу по разрешению вызовов и сопоставлению символов. Так что имя неймспейса включено в это расширенное имя объекта.

Но можно заметить и разницу. После имени неймспейса в случае статических переменных мы имеем заглавную L. Так компилятор помечает символ с внутренним связыванием.

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

Stay hardcore. Stay cool.

#cppcore #hardcore #cpp17 #compiler

​Vector vs List

Знание алгоритмов и структур данных - критично для нашей профессии. Ведь в принципе все, что мы делаем - это берем какие-то явления реального мира, создаем их представления в программе и управляем ими. От нашего понимания эффективного представления данных в памяти компьютера и управления ими зависит количество ресурсов, которое требуется на предоставление какой-то услуги, а значит и доход заказчика. Чем лучше мы знаем эти вещи, тем дешевле предоставлять услугу и тем больше мы ценны как специалисты. И наши доходы растут. Но computer science намного обширнее, чем абстрактные вещи типа теории алгоритмов или архитектуры ПО. Это еще и знание и понимание работы конкретного железа, на котором наш софт выполняется. Что важнее - непонятно. Но только в синергии можно получить топовые результаты.

Согласно теории, проход по массиву и двунаправленному списку происходит за одинаковое алгоритмическое время. O(n). То есть время прохода линейно зависит от количества элементов в структуре. И без применения знаний о принципах работы железа, можно подумать, что они взаимозаменяемы. Просто в одном случае элементы лежат рядом, а в другом - связаны ссылками. А на практике получается, что не совсем линейно и совсем не взаимозаменяемы. Расскажу подробнее о последнем.

Дело в существовании кэша у процессора. Когда мы запрашиваем доступ к одной ячейке памяти, процессор верно предполагает, что нам скорее всего будут нужны и соседние ячейки тоже. Поэтому он копирует целый интервал в памяти, называемый кэш-строкой, в свой промежуточный буфер. А доступ к этому буферу происходит намного быстрее, чем к оперативной памяти. И процессору не нужно ходить за этими рядом лежащими данными в ОЗУ, он их просто берет из кэша.

Элементы же списка хранятся в разных участках памяти и связаны между собой ссылками. В общем виде нет никакой гарантии, что они будут лежать рядом. Если конечно вы не используете кастомный аллокатор. Поэтому за каждым элементом листа процессору приходится ходит в ОЗУ.

Вот и получается, что обработка элементов списка будет происходит медленнее, чем элементов массива.

Написал простенькую программку, которая проверит разницу во времени прохода.
Получилось, что для 100кк чисел в массиве и в листе, время отличается от 1.5 до 2 раз на разных машинах. Нихрена себе такая разница. И это без оптимизаций!
С ними разница вообще 6-8 раз. Это кстати еще один повод для того, чтобы понимать, как именно мы работаем на уровне железа и какие структуры данных хорошо ложатся на разные оптимизации.

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

Stay based. Stay cool.

#STL #algorithms #cppcore

​Cамая популярная задачка с собеседований

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

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

Формулировка.

Вы находитесь в кольцевом поезде. То есть как будто бы 2 конца одного поезда соединили и можно бесконечно теперь в нем гулять. Количество вагонов вам неизвестно. В каждом вагоне есть всего одна лампочка. Она имеет 2 состояния: вкл и выкл. По дефолту они в рандомном порядке включены во всех вагонах, то есть вы заранее не знаете, в каком порядке в вагонах зажжены лампочки. И у каждой лампочки есть выключатель, который исправно работает.

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

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

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

Решение сброшу завтра в комментах к отдельному посту, посвященному ответу.

Всем удачи!

Train your logic. Stay cool.

#fun

Задача про закольцованный поезд

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

​Сравнение решений задачи

Меня всегда восхищает, как люди доходят до разных решений одной задачи. Это расширяет мои рамки восприятия мира и я могу перенять эти паттерны мышления. Всем спасибо за ваши варианты решений. Даже читаерные. Скорее даже особенно читерные. Потому что редко у меня получается думать outside the box.

Но сегодня разберем кое-что другое. Увидел в комментах, что многие люди приходили к немного иному решению. Не по аналогии с маятником, а скорее со спидометром. От изначального вагона с включенным светом идем вправо и выключаем лампочку. Потом возвращаемся и проверяем лампочку в самом первом вагоне. Далее снова идем вправо, но уже на один вагон дальше, и выключаем там свет. Возвращаемся обратно и делаем проверку света в изначальном вагоне. Условие остановки - в изначальном вагоне погасла лампочка. И длина поезда - последнее количество вагонов на пути обратно.

Проще ли этот вариант? Думаю, что да. В голове нужно всего один счетчик хранить. А для маятника уже 2 нужно. Как говорят физики: "все, что больше одного - это уже много". После прохождения энного вагона я бы точно что-то перепутал.

Но вот вопрос: а для какого решения требуется пройти меньше вагонов? С первого взгляда, какая разница. И там и там ходим туда-сюда. Но если все хорошенько подсчитать, то разница есть и значительная. Я вот и посчитал. Результаты на картинке под постом.

Не преследовал целей принизить чье-то решение. Просто самому было интересно проверить. Еще раз: я восхищаюсь всеми вами, кто придумал решение. Потому что в свое время не смог этого сделать на собесе. Вы крутые)

Stay cool.

Мини-гайд по собеседованиям

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

В общем, особо не знаю, что сказать. Все в документе.

Share knowledge. Stay cool.

#guide

​Что значит, что фича устрела или удалена

Новые стандарты языка приносят нам кучу разных новых способов решать наши повседневные задачи. Но не только это. Комитет стандартизации думает не только о новом, но и заботится о прошлом. Как минимум примером является обратная совместимость языка при переходе на новый стандарт. Но это не совсем правда. Бывают случаи, когда ломают обратную совместимость в некоторых моментах. Через удаление определенных фичей. Зачем это делают?

Плюсы - довольно старый язык, который пытается сохранить, до определенной степени, совместимость в еще более старым языком - С. Такая большая история говорит о том, что в языке накапливается определенное количество "багов", то есть функциональности, которая уже устарела и/или вреди пользователю. На самом деле такие "баги" выделяют очень строго, когда есть реальная опасность в их использовании. Или все члены комитета согласятся, что от нее нет толку. А комитет состоит из сотен людей, которые непрерывно дебатируют по поводу будущего языка. И если уж они наконец договорились что-то удалить, то это должно сильно встревожить разрабов и воодушевить их на переход на более безопасные альтернативы, которые уже есть в языке.

Такой процесс происходил например с std::autoptr, std::randomshuffle, ключевым словом register, триграфами и прочим.

Их всех объединяет, что для них есть более предпочтительные альтернативы или в современных реалиях они полностью утратили значимость и просто вносят сложность в язык.

Теперь разберем процесс удаления сущности из стандарта.

Для начала она объявляется устаревшей или deprecated. При попытке компиляции с новым стандартом всплывет ворнинг. А в любой нормальной компании ворнинг роняет через бедро сборку проекта. Об этом подробнее здесь рассказывали. И люди просто вынуждены провести небольшой рефакторинг и заменить устаревшую функциональность, чтобы перейти на новый стандарт. Таким образом народ минимально преобразует код, но зато теперь есть возможность использовать фишки нового стандарта, которые могут быть вполне полезными. Ну или забить и не переходить на него. Так тоже иногда делают. Но я бы не хотел работать в такой компании)

После объявления устаревшей стандарт еще какое-то время поддерживает фичу. Но через 3-5-10 лет ее удалят. И больше ее упоминания в стандарте не будет.

Fix your flaws. Stay cool.

#commercial #cppcore

Снова сравниваем решения задачи с поездами

Кто забыл или не в теме, вот эта задача. В прошлом мы уже сравнивали два решения: условный маятник и спидометр. Лучше освежить в памяти контекст, чтобы понятнее был предмет разговора. Однако наша подписчица @tigrisVD сделала несколько улучшений алгоритма спидометра. Вот ее сообщение с пояснениями и кодом.

Первое - базовое улучшение. Вместо того, чтобы возвращаться назад на каждом шаге(что очень расточительно), мы возвращаемся назад, только, если встретили единичку и поменяли ее на ноль. Только в этом случае мы могли поменять самую первую лампочку.
Это уже улучшение уполовинило количество шагов. И сравняло его с маятником.

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

Там есть некоторые проблемы с тем, что оптимизированные алгоритмы спидометра зависят от входных данных. И в худшем случае, когда в поезде включены все лампочки, последний оптимизированный алгоритм работает лишь в 2 раза лучше базового спидометра. В лучшем случае, когда все лампочки выключены - сложность алгоритмов линейно зависит от количества вагонов, а не квадратично, как у базового спидометра. Базовое улучшение - нужно пройти всего х2 от количества вагонов. А оптимизированный вариант- х4(я там одну ошибочку нашел в коде при подсчете пройденных вагонов, поэтому не в 3, а в 4). Но в рандомных случаях оптимизированный вариант примерно в 2 раза быстрее базового улучшенного и в 4 раза быстрее оригинального спидометра.

Позапускать ее код и посмотреть на цифры можно тут

Спасибо вам, @tigrisVD, за такие интересные решения!

Но ваши улучшения натолкнули и меня на размышления и улучшения, о которых я расскажу завтра.

Impove yourself. Stay cool.

#fun #optimization

Линейное решение задачи с поездами

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

Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х2 от количества вагонов. И в среднем работает в 2 раза быстрее, чем оригинальный маятник, и примерно наравне с оптимизированным спидометром(чуточку хуже).

Но! Кажется на основе оптимизированного спидометра я придумал линейный алгоритм, дающий стабильно O(4n) для совершенно рандомных случаев и во всех особых случаях, когда все лампочки либо включены, либо выключены. И где-то О(8n) в худшем случае для конкретно этого алгоритма.

В чем суть. Для оптимизированного спидометра мы разрешали себе идти дальше, когда на очередном проходе на пути от начального вагона мы в первый раз встретили зажженную лампочку, но только до тех пор, пока не встретим еще одну единичку или не закончатся наши разрешенные шаги. А что если пойти дальше, даже после второй зажженной лампочки? Что если каждый раз когда мы встречаем такую лампочку, то разрешаем себе идти еще в 2 раза дальше? Прям каждый раз. Встретили зажженную лампочку - погасили и может идти дальше на столько же вагонов, сколько мы прошли от начала до только что погашенной нами лампочки. По факту, мы идем вперед всегда, пока нам встречаются зажженные лампочки и мы не уходим слишком далеко от последней погашенной нами. Тогда существует всего 2 варианта - рано или поздно мы погасим начальную лампочку или последняя погашенная не была начальной, но мы так и не дошли до следующей зажженной до того, как истекли наши разрешенные вагоны.

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

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

Таким образом, если зажженные лампочки достаточно часто встречаются, то мы идем в один проход до конца поезда, потом еще удвоенную его длину и обратно. Получается, что нам понадобится 4 длины поезда, чтобы посчитать количество вагонов.

Но есть у такого алгоритма худший случай. Тогда, когда зажженные лампочки стоят ровно на один вагон дальше, чем нам разрешено пройти. Пример: зажженная лампочка находится в 3-м вагоне. После того, как мы ее погасили, нам разрешается идти еще 2 вагона и искать там зажженные лампочки. То есть последний вагон, который мы можем посмотреть на этой итерации - 5-ый. А вот следующая зажженная лампочка будет в шестом. И мы могли бы всего на один вагончик вперед пройти и встретить ее, но согласно алгоритму мы должны вернуться к изначальному вагону. Если после шестого вагона лампочка будет в 12-м, то мы обязаны будем вернуться назад и снова пройти вперед до 12-ого. И так далее. Думаю, суть вы уловили.

Так вот на таких данных сложность повышается до примерно О(8n). Эту чиселку вывел совершенно экспериментально. Возможно знатоки математики и теории алгоритмов выведут более точную зависимость. Чему я очень буду рад)

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

Прикреплю в комменты полный файл со всеми сравнениями. Но вот ссылка на годболт кому будет так удобнее.

Критика и замечания приветствуются.

Improve yourself. Stay cool.

#fun #optimization

Inline namespace

В этом сообщении Михаил попросил нас сделать пост про inline namespace'ы. Это хорошо вписывается в контекст постинга в последние месяцы, когда мы много говорим о линковке и inline. Поэтому держите.

Ключевое слово inline используется либо как подсказка компилятору для встраивания кода функции в место ее вызова, либо как средство обхода ODR. Применять его можно и к функциям, и к переменным(с С++17). Но есть еще одно интересное применение inline. Им мы можем пометить пространство имен. Такая пометка неймспейсов доступна с С++11. Я бы сказал, что судя по названию и уже усвоенной инфе, мы можем понять, что это значит. Но нет. Нихрена не понятно. Поэтому будем разбираться.

Контекст и использование встроенных неймспейсов совсем простой, однако он отличается от поведения других inline сущностей. Все, что объявлено внутри такого пространства имен, считается также членом внешнего неймспейса, которое содержит в себе данный inline namespace. То есть

namespace trah {
   inline namespace tibidoh {
       template<typename T> class tibidoh{ /* ... */ };
   }
   template<typename T> void tenberg(T) { /* ... */ }
}

есть у нас вот такая иерархия. Неймспейс трах. У него есть шаблонная функция тенберг. И в него вложен встроеный неймспейс тибедох. В этом внутреннем неймспейсе шаблонный класс тибедох. И прикол в том, что вместо trah::tibidoh::tibidoh я могу написать просто trah::tibidoh и использовать вложенный класс наряду с функцией trah::tenberg.

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

Для чего это нужно? По сути эта фича призвана решить одну единственную проблему - версионирование библиотеки. Глянем на прошлый пример. Библиотека trah активно развивается и, начиная с какой-то версии, в ней появился класс tibedoh, которого не было в предыдущей версии библиотеки. До появления С++11 это выглядело бы примерно так:

namespace trah {
#  if __version == new
  using namespace tibidoh;
#  endif
    namespace tibidoh {
       template<typename T> class tibidoh{ /* ... */ };
   }
   template<typename T> void tenberg(T) { /* ... */ }
}

В этом случае нам недоступен класс tibidoh, если мы не используем новую версию либы. А если используем, то using помогает нам не писать оператор разрешения имен и пользоваться классом tibidoh, как если бы он был членом неймспейса trah. То есть вот так trah::tibidoh. Вроде все круто и нет проблем. Но не все так просто.

Мне, как пользователю библиотеки, не желательно что-то объявлять в пространстве имен trah, по аналогии с std. Однако мне разрешается делать полную специализацию для шаблонов непосредственно в trah без последствий. Я, как автор своих классов, лучше знаю, как ими нужно оперировать, чтобы достичь максимального перфоманса. Зная API библиотеки, я думаю, что класс tibedoh объявлен в trah. Окей, пишу:

namespace trah {
   template <>
  class tibidoh<AbraKadabra> {
      // ...
  };
}

Но вот проблема. Мне позволяется полностью специализировать шаблоны именно в том пространстве имен, в котором шаблон объявлен. А на самом деле он объявлен во вложенном неймспейсе. Предыдущий код мог бы сработать для неверсионированной либы, но в нашем случае будет просто ошибка компиляции.

Это не единственный пример, когда вложенное пространство имен становится видным пользовательскому коду. Например, ADL(кто знает, тот знает, раскрытие adl не влезет в этом пост) не следует директиве using и при поиске символа из вложенного неймспейса во внешнем. ADL будет очень стараться, но так и не найдет нужный символ, который на самом деле спрятан во вложенном namespace.

Продолжение в комментах

#cpp11 #cppcore

​Сколько весит объект пустого класса?

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

Самый очевидный и первый приходящий в голову ответ - 0. Просто 0. Пустой класс, 0. Все сходится. И это очень логично. Однако это не соответствует реальности.

Реальность в том, что пустые классы - такие же классы с точки зрения кода программы и с ними можно делать все то же самое, что и с обычными классами. Например, создать массив объектов пустого класса. Это опять же не имеет смысла. Но для компилятора объект неполиморфного класса с определенным набором методов - тоже пустой. Потому что адреса методов не хранятся в самом классе, они подставляются непосредственно в момент вызова этих методов. А вот такие объекты уже можно хранить. Они хоть что-то делать могут.

Так вот. Если бы объект пустого был размером 0 байт, его невозможно было бы проиндексировать в массиве. Порядковый номер элемента в массиве задает сдвиг этого элемента от начала. Любой сдвиг помноженный на ноль будет равен нулю. Хотя бы уже поэтому любой объект должен хоть сколько-нибудь весить.

Ну и следующий по логике ответ - 1 байт - будет верным. 1 байт это минимальный адресуемый размер памяти (даже тип bool занимает 1 байт), поэтому это довольно логично.

Stay reasonable. Stay cool.

#interview #cppcore

​anonymous namespace

Раз мы затрагиваем тему static и линковки, я не могу не рассказать про эту фичу. Есть такая штука, как безымянные или анонимные пространства имен. Они из себя представляют примерно следующее:

namespace {
    int int_var = 0;
    void foo() {...}
}

Как же можно получить доступ к содержимому этого неймспейса, если у него нет имени?

На самом деле имя есть. Его генерирует компилятор. Вот во что преобразуется пример выше внутри компилятора:

namespace unique{}
using namespace unique;
namespace unique{
    int int_var = 0;
    void foo() {...}
}

Будем разбирать по порядку, потому что здесь все непросто.

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

Во-вторых, все содержимое безымянных пространств видно из родительского пространства за счет дирекивы using. Благодаря этому мы можем пользоваться всеми членами unnamed namespace, как если бы они были в текущем неймспейсе.

В-третьих, на каждую единицу трансляции будет уникальное имя unique, которое больше никому не будет известно. Это значит, что ни одна другая единица трансляции не сможет получить доступ к intvar и foo, потому что не будет знать это уникальное имя.

И вот здесь ключевой момент. Хоть intvar и foo имеют внешнее связывание, но по сути к ним из другого юнита нельзя получить доступ. Значит они имеют эффект внутреннего связывания. Начиная вроде с 11-го стандарта там даже написано, что все члены безымянных неймспейсов имеют внутреннее связывание. Но это стандарт. Некоторые компиляторы типа VS2015/VS2017 считают все неконстантные переменные и свободные функции внутри безымянных пространств extern. На самом деле тут тонкий и не очень понятный момент, потому что именованные пространства имен содержат члены с внешним связыванием. А также в стандарте написано, что анонимное пространство раскрывается как именованое. Но теперь все объявления внутри почему-то имеют внутреннее связывание. Не эффект внутреннего связывания, а прям оно самое. Со всеми плюшками оптимизаций. Как это работает, мне не очень понятно. Знающие люди, отпишитесь в комментариях пожалуйста.

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

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

Следующий пост будет как раз про отличия unnamed namespace и static

Don't expose your secrets. Stay cool.

#cppcore #cpp11 #compiler