Почему не хорошо использовать рекурсивное наследование для реализаций std :: tuple? - PullRequest
23 голосов
/ 10 марта 2012

В этом вопросе Говард Хиннант сказал

Некоторые реализации std :: tuple используют рекурсивное наследование.Но хорошие не делают.; -)

Может кто-нибудь пролить свет на это?

Ответы [ 3 ]

30 голосов
/ 10 марта 2012

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

Это влияет не только на создание экземпляра самого кортежа.Например, std::get<I>(tuple) будет занимать линейное количество времени компиляции для одной реализации и постоянное количество времени компиляции для другой реализации.Это воздействие может быстро ухудшаться (или нет) при работе с кортежами кортежей.Т.е. рекурсивная реализация может привести к O (N ^ 2) времени компиляции, тогда как нерекурсивная реализация все еще O (1).

Fwiw, реализация libc ++ размещает объекты в порядке, указанном клиентом, но оптимизирует свободное место для пустых компонентов, используя средство оптимизации пустого базового класса компилятора.

3 голосов
/ 10 марта 2012

Я не вспоминаю доклад Андрея Александреску GoingNative 2012 точно , но он говорил об этом, и одним из упомянутых им пунктов было расположение памяти. Если у меня есть std::tuple<int, short, char, char>, он будет в памяти как char, short, int, и этот макет займет (в моей системе) на 4 байта больше, чем если бы он был выложен как int, short, char. R. Мартиньо Фернандес напомнил мне, что лучше всего 1009 * упорядочить их в памяти в порядке, который минимизирует заполнение, что не является ни порядком, заданным , ни обратным порядком. (Наивное наследование делает обратный порядок).

Если я напишу 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.

2 голосов
/ 10 марта 2012

Одна из причин не использовать цепочку базовых классов состоит в том, что цепочка конструкторов не задействована: аргументы напрямую передаются соответствующему подобъекту. Кроме того, кажется, что нерекурсивная реализация создает намного меньшую нагрузку на компилятор и создает намного меньше [внутренних] символов. Не говоря уже о том, что на самом деле не цепочка базовых классов.

...