Почему не хорошо использовать рекурсивное наследование для реализаций std::tuple?
В этом вопросе Говард Хиннант сказал
Некоторые реализации std::tuple используют рекурсивное наследование. Но хорошие не делают.;-)
Может кто-нибудь, пожалуйста, пролить свет на это?
3 ответа
Нерекурсивная реализация имеет лучшую производительность во время компиляции. Верьте или нет, в интенсивно используемом библиотечном средстве, таком как std::tupleТо, как это реализовано, может повлиять (к лучшему или худшему) на время компиляции, которое видит клиент. Рекурсивные реализации имеют тенденцию производить время компиляции, которое является линейным по глубине рекурсии (или может быть даже хуже).
Это влияет не только на создание самого кортежа. std::get<I>(tuple) например, для одной реализации потребуется линейное количество времени компиляции и постоянное количество времени компиляции для другой реализации. Это воздействие может быстро ухудшаться (или нет) при работе с кортежами кортежей. Т.е. рекурсивная реализация может привести к O(N^2) времени компиляции, в то время как нерекурсивная реализация все еще O (1).
Fwiw, реализация libC++ размещает объекты в порядке, указанном клиентом, но оптимизирует свободное место для пустых компонентов, используя средство оптимизации пустого базового класса компилятора.
Я не помню точно, что говорил Андрей Александреску на GoingNative 2012, но он говорил об этом, и одним из моментов, которые он упомянул, была схема памяти. Если у меня есть std::tuple<int, short, char, char>будет в памяти как char, short, int и этот макет займет (в моей системе) на 4 байта больше, чем если бы они были выложены как int, short, char, Р. Мартиньо Фернандес напомнил мне, что лучше всего было бы упорядочить их в памяти в порядке, который сводит к минимуму заполнение, что не является ни порядком передачи, ни обратным порядком. (Наивное наследование делает обратный порядок).
Если я напишу std::tuple<int, char, short, char>, кортеж, который работает наивным наследованием, поместил бы их в порядок char, short, int в памяти, используя 3 байта заполнения, когда оптимальное имеет нулевые байты заполнения. (Или int, short, char, char или же char, char, short, int).
Предполагая, что я прав, что речь идет о дополнении, Р. Мартиньо Фернандес сказал: "[мой аргумент] не исключает использование рекурсивного наследования для фактической реализации в оптимальном порядке", поэтому я и задаю это наивное наследование. плохо.
(Порядок в памяти не означает, что get<0> даст другой объект, и Р. Мартиньо Фернандес правильно отмечает, что порядок должен быть невидим для пользователя. Тем не менее, это были те моменты, о которых мне напомнило событие GoingNative.)
Видео находится по адресу http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Variadic-Templates-are-Funadic а слайды - по адресу http://ecn.channel9.msdn.com/events/GoingNative12/GN12VariadicTemplatesAreFunadic.pdf.
Одна из причин не использовать цепочку базовых классов заключается в том, что цепочка конструкторов не задействована: аргументы напрямую передаются соответствующему подобъекту. Кроме того, кажется, что нерекурсивная реализация создает намного меньшую нагрузку на компилятор и создает намного меньше [внутренних] символов. Не говоря уже о том, что на самом деле проще не цепочку базовых классов.