?

Log in

No account? Create an account

Программистское абстрактное - Общество дровосеков Бердичева по изучению Мишны

Aug. 24th, 2012

11:40 am - Программистское абстрактное

Previous Entry Share Next Entry


Дано:

using std::string;
string dotted_pair1(const string & a, const string & b) {
    return a + '.' + b;
}
string dotted_pair2(const string & a, const string & b) {
    return (a + '.') += b;
}

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

Ну и совсем абстрактно: интересно, программисты на ФЯП в принципе задумываются о зависимости эффективности выполняемого кода от идиоматики исходного, или они выше этих глупостей?

Comments:

From:rezkiy
Date:August 24th, 2012 06:52 pm (UTC)
(Link)
мне всегда казалось, что как только больше двух слагаемых, надо использовать что-то типа stringstream.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 24th, 2012 06:55 pm (UTC)
(Link)
Если нет форматных преобразований, то из пушки по воробьям будет, да и совершенно неидиоматично.
(Reply) (Parent) (Thread)
From:rezkiy
Date:August 24th, 2012 07:03 pm (UTC)
(Link)
Надо профайлить.
(Reply) (Parent) (Thread) (Expand)
(Deleted comment)
[User Picture]
From:fatoff
Date:August 25th, 2012 05:23 pm (UTC)
(Link)
AFAIK, всего лишь избежать перераспределения памяти оптимизирует код достаточно сильно, чтобы к этой теме вообще возвращаться.

Вместо:

string dotted_pair1(const string & a, const string & b) {
return a + '.' + b;
}

Вот это:

string dotted_pair1(const string & a, const string & b) {
string s(a);
s.reserve(EXPECTED_LENGTH * 2);
s += ".";
s += b;
return s;
}

Ну и/или вместо возврата строки через return использовать неконстатную передачу объекта возвращаемой строки по ссылке. Но это банальщина...
(Reply) (Parent) (Thread)
From:lazyreader
Date:August 28th, 2012 12:01 pm (UTC)
(Link)
string dotted_pair1(const string & a, const string & b) {
string s(a);
s.reserve(EXPECTED_LENGTH * 2);
s += ".";
s += b;
return s;
}


или, иначе говоря,
string dotted_pair1(string a, const string & b) {
a.reserve(EXPECTED_LENGTH * 2);
a += ".";
a += b;
return a;
}


Один из классиков недаром написал статью со спорным названием типа "хочешь скорости - передавай по значению!".

Edited at 2012-08-28 12:02 pm (UTC)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:dvv
Date:August 24th, 2012 07:11 pm (UTC)
(Link)
gcc 4.1.2: апсолютно адинхуй.
gcc 4.7.1: апсолютно адинхуй.

Почему второй вариант вообще проходит — на первый взгляд непонятно.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 24th, 2012 07:17 pm (UTC)
(Link)
И даже глядя на ассемблер - апсолютно?
Я тоже пробовал с опаской, но видимо, потому что r-values нельзя лишь передавать по неконстантным ссылкам, а применять к ним неконстантные методы - можно.
(Reply) (Parent) (Thread)
[User Picture]
From:dvv
Date:August 24th, 2012 07:21 pm (UTC)
(Link)
Именно глядя на ассемблер.

Различия только вот в чём:

В первом случае пускается конструктор на временную строку с аргументом a, к ней цепляется одна точка, и ей же инициируется возврат, к возврату цепляется b. Деструктор на временную строку, выход из функции.

Во втором случае пускается конструктор на временную строку с аргументом a, к ней цепляется одна точка, к ей же цепляется b, ей же инициируется возврат. Деструктор на временную строку, выход из функции.

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

Edited at 2012-08-24 08:02 pm (UTC)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:mynine
Date:August 24th, 2012 07:22 pm (UTC)
(Link)
А на чем вы тестировали?
Я проверил VC2010 - практически идентичные варианты. По числу объектов совершенно одинаковые - один временный, где конкатенируются строки. Разница только в том что во втором случае временный объект создается явно внутри функции, а в первом через move внутри второго оператора конкатенации.
(Reply) (Thread)
[User Picture]
From:mynine
Date:August 24th, 2012 07:44 pm (UTC)
(Link)
Чуть поторопился - в обоих случаях все-таки два объекта генерятся.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 24th, 2012 08:00 pm (UTC)
(Link)
Я тестировал на GCC 4.4. По идее на C++11 можно выразить эту идею, объявив оператор конкатенации 4 раза: со всеми комбинациями обычных ссылок и rvalue ссылок (которого у нас еще не установлено), но я задумался, нельзя ли выразить это более изящно.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:mynine
Date:August 24th, 2012 08:17 pm (UTC)
(Link)
Ну все равно, вряд ли тут можно обойтись всего одним объектом - первый дейстивтельно временный нужен для слияния строк, и второй это само возвращаемое значение.

(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:cema
Date:August 24th, 2012 07:46 pm (UTC)
(Link)
В каком смысле исходного?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 24th, 2012 08:01 pm (UTC)
(Link)
В смысле - текста на ФЯП, написанного программистом.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 24th, 2012 09:01 pm (UTC)
(Link)
А небось printf в строку будет еще эффективнее.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 24th, 2012 09:04 pm (UTC)
(Link)
Для коротких строк накладные расходы на парсинг формата могут превзойти выигрыш.
(Reply) (Parent) (Thread)
[User Picture]
From:mynine
Date:August 24th, 2012 09:27 pm (UTC)
(Link)
я быстро проверил: проигрыш сишного варианта в два раза при оптимизации кода; без оптимизации быстрее раза в полтора.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:fregimus
Date:August 25th, 2012 10:41 am (UTC)
(Link)
«программисты на ФЯП в принципе задумываются о зависимости эффективности выполняемого кода от идиоматики исходного» — если задумываются, значит, язык дурной. Как C++, например. Читали The Rise Of Worse Is Better? Гениальный человек rpg написал — в таком быстро меняющемся мире программирования все предсказал абсолютно точно на 20 лет вперед.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 26th, 2012 04:31 pm (UTC)
(Link)
Нет, не читал. Спасибо, посмотрю. А задумываться приходится на любом языке при решении индустриальных задач.
(Reply) (Parent) (Thread)
[User Picture]
From:fregimus
Date:August 25th, 2012 10:45 am (UTC)
(Link)
Хотя… задумываются, конечно. В хаскеле, ML и лиспе присобачить голову к списку — O(1), a хвост — O(N) и памяти, и времени. Когда строят список, начиная с головы, то строят его в обратном порядке, а потом переворачивают. А в Математике, хоть она и ML-подобная, все иначе — но там свои трюки с оптимизацией.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 26th, 2012 04:30 pm (UTC)
(Link)
Об оптимальной алгоритмической сложности задумываться надо всем и всегда. Вопрос был, скорее, заботятся ли они о константах у достигнутых сложностей.
(Reply) (Parent) (Thread)
[User Picture]
From:thesz
Date:August 25th, 2012 07:16 pm (UTC)
(Link)
http://stgcompiler.googlecode.com/svn/trunk/Docs/Artigos/fusion(strings).pdf

Чуть ли не самый известный пример, когда программисты на FP задумались о производительности. И каким образом она была достигнута.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 26th, 2012 04:27 pm (UTC)
(Link)
Спасибо. ForeignPtr rules!
(Reply) (Parent) (Thread)
[User Picture]
From:besisland
Date:August 25th, 2012 09:40 pm (UTC)
(Link)
По второму вопросу хочу предположить, что такое в корне неправильно и может быть только лишь вынужденной мерой.
(Reply) (Thread)
From:lazyreader
Date:August 28th, 2012 12:04 pm (UTC)
(Link)
С новым стандартом могу вообразить

string operator+(string&& a, string&& b);


и умный компилятор, который сможет использовать этот факт в вычислениях типа

return a + '.' + b;
(Reply) (Thread)