Программистское абстрактное

[spamsink]

Дано:

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

[rezkiy.livejournal.com]

мне всегда казалось, что как только больше двух слагаемых, надо использовать что-то типа stringstream.

[spamsink]

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

[rezkiy.livejournal.com]

Надо профайлить.

[fatoff.livejournal.com]

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 использовать неконстатную передачу объекта возвращаемой строки по ссылке. Но это банальщина...

[lazyreader.livejournal.com]

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;
}

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

[dvv.livejournal.com]

gcc 4.1.2: апсолютно адинхуй.
gcc 4.7.1: апсолютно адинхуй.

Почему второй вариант вообще проходит — на первый взгляд непонятно.

[spamsink]

И даже глядя на ассемблер - апсолютно?
Я тоже пробовал с опаской, но видимо, потому что r-values нельзя лишь передавать по неконстантным ссылкам, а применять к ним неконстантные методы - можно.

[dvv.livejournal.com]

Именно глядя на ассемблер.

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

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

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

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

[mynine.livejournal.com]

А на чем вы тестировали?
Я проверил VC2010 - практически идентичные варианты. По числу объектов совершенно одинаковые - один временный, где конкатенируются строки. Разница только в том что во втором случае временный объект создается явно внутри функции, а в первом через move внутри второго оператора конкатенации.

[mynine.livejournal.com]

Чуть поторопился - в обоих случаях все-таки два объекта генерятся.

[spamsink]

Я тестировал на GCC 4.4. По идее на C++11 можно выразить эту идею, объявив оператор конкатенации 4 раза: со всеми комбинациями обычных ссылок и rvalue ссылок (которого у нас еще не установлено), но я задумался, нельзя ли выразить это более изящно.

[cema.livejournal.com]

В каком смысле исходного?

[spamsink]

В смысле - текста на ФЯП, написанного программистом.

[sab123.livejournal.com]

А небось printf в строку будет еще эффективнее.

[spamsink]

Для коротких строк накладные расходы на парсинг формата могут превзойти выигрыш.

[mynine.livejournal.com]

я быстро проверил: проигрыш сишного варианта в два раза при оптимизации кода; без оптимизации быстрее раза в полтора.

[fregimus.livejournal.com]

«программисты на ФЯП в принципе задумываются о зависимости эффективности выполняемого кода от идиоматики исходного» — если задумываются, значит, язык дурной. Как C++, например. Читали The Rise Of Worse Is Better? Гениальный человек rpg написал — в таком быстро меняющемся мире программирования все предсказал абсолютно точно на 20 лет вперед.

[spamsink]

Нет, не читал. Спасибо, посмотрю. А задумываться приходится на любом языке при решении индустриальных задач.

[fregimus.livejournal.com]

Хотя… задумываются, конечно. В хаскеле, ML и лиспе присобачить голову к списку — O(1), a хвост — O(N) и памяти, и времени. Когда строят список, начиная с головы, то строят его в обратном порядке, а потом переворачивают. А в Математике, хоть она и ML-подобная, все иначе — но там свои трюки с оптимизацией.

[spamsink]

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

[thesz.livejournal.com]

http://stgcompiler.googlecode.com/svn/trunk/Docs/Artigos/fusion(strings).pdf

Чуть ли не самый известный пример, когда программисты на FP задумались о производительности. И каким образом она была достигнута.

[spamsink]

Спасибо. ForeignPtr rules!

[thesz.livejournal.com]

Что интересно, ForeignPtr не совсем хорош: http://hackage.haskell.org/package/text-0.11.2.3 ;)

При больших объёмах текста в ByteString эта штука начинает фрагментировать кучу. Поэтому и был придуман text.

[besisland.livejournal.com]

По второму вопросу хочу предположить, что такое в корне неправильно и может быть только лишь вынужденной мерой.

[lazyreader.livejournal.com]

С новым стандартом могу вообразить

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

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

return a + '.' + b;