?

Log in

No account? Create an account

Храните объекты в сберегательной кассе - Общество дровосеков Бердичева по изучению Мишны

May. 24th, 2013

05:58 pm - Храните объекты в сберегательной кассе

Previous Entry Share Next Entry



Пусть у нас есть некий тип, объекты которого создавать дороже, чем копировать. Пусть у нас есть функция, возвращающая объекты этого типа, причем часто эти объекты сконструированы из константных данных (очевидный пример: запись числа прописью). В этом случае более эффективно пользоваться статическими объектами для этих константных данных:
#include <string>
#include <iostream>

#define RET(x) // см. ниже

using namespace std;
string spellout_int(unsigned val) {
// детали додумайте сами
...
switch (val) {
...
case 5: return RET("five");
case 4: return RET("four");
case 3: return RET("three");
case 2: return RET("two");
case 1: return RET("one");
case 0: return string();
}
}

string spellout(unsigned val) {
return val ? spellout_int(val) : RET("zero");
}

int main() {
for (unsigned i = 0; i < 10000000; ++i)
cout << spellout(i) << '\n';
}


Когда RET(x) определено как x, программа, скомпилированная g++ 4.7.2 -O3, работает N секунд. Когда RET(x) определено как ({static string ret(x); ret;}) - а эта конструкция, если кто не в курсе, GNU extension, она работает примерно 0.83*N секунд.

А теперь вопрос: как на этом вашем стандартном С++ написать то же самое, не засоряя код явными объявлениями статических переменных?

Tags:

Comments:

[User Picture]
From:lionet
Date:May 25th, 2013 01:50 am (UTC)
(Link)
Я что-то не разберу, ты скорость libc++ и ядра операционки меряешь что-ли? Какой нафиг cout?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 01:57 am (UTC)
(Link)
Я меряю разницу в user time, т.к. текст печатается в обоих случаях идентичный. Если тело цикла заменить на что-нибудь типа
total += spellout(i).size();
разница получается незначительная, соотношение времен выходит около 0.8.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 01:52 am (UTC)

Если кто интересуется деталями

(Link)
string spellout_int(unsigned val) {
if (val >= 1000000)
return spellout_int(val / 1000000) + RET(" million ") + spellout_int(val % 1000000);
if (val >= 1000) return spellout_int(val / 1000) + RET(" thousand ") + spellout_int(val % 1000);
if (val >= 100) return spellout_int (val / 100) + RET(" hundred ") + spellout_int(val % 100);
switch (val) {
default: return spellout_int(val / 10 * 10) + ' ' + spellout_int(val % 10);
case 90: return RET("ninety");
case 80: return RET("eighty");
case 70: return RET("seventy");
case 60: return RET("sixty");
case 50: return RET("fifty");
case 40: return RET("forty");
case 30: return RET("thirty");
case 20: return RET("twenty");
case 19: return RET("nineteen");
case 18: return RET("eighteen");
case 17: return RET("seventeen");
case 16: return RET("sixteen");
case 15: return RET("fifteen");
case 14: return RET("fourteen");
case 13: return RET("thirteen");
case 12: return RET("twelve");
case 11: return RET("eleven");
case 10: return RET("ten");
case 9: return RET("nine");
case 8: return RET("eight");
case 7: return RET("seven");
case 6: return RET("six");
case 5: return RET("five");
case 4: return RET("four");
case 3: return RET("three");
case 2: return RET("two");
case 1: return RET("one");
case 0: return string();
}
}


А собственно spellout(), если по-хорошему, то string spellout(unsigned val) {
if (val == 0)
return RET("zero");
string ret = spellout_int(val);
size_t s = ret.find_last_not_of(' ');
if (s >= ret.size())
return ret;
else {
ret.resize(s);
return ret;
}
}
(Reply) (Thread)
[User Picture]
From:vaddimka
Date:May 25th, 2013 07:20 am (UTC)
(Link)
а не лучше возвращать const std::string& ?
уберется одно копирование, если gcc его сам не соптимизировал

еще такая штука, по новому стандарту инициализация статических переменных - threadsafe (в gcc так было последние лет 10 по-моему)
однако, ms visual studio (точнее, ms compiler) это дело игнорирует и есть достаточно много вроде как портируемых проектов, которые тем не менее весело падают если используются (скорее, инициализируются) в тяжелых мультитредовых условиях

можно еще обойтись одним статиком
static string s_spellbound[] = {
"", // placeholder for 0
"one",
"two",
....
"twenty",
"", // placeholder for 21
"", // placeholder for 22
...
"thirty",
"", // placeholder for 31
...
"ninety"
};
и заодно уберется кейс
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2013 08:52 pm (UTC)
(Link)
Если возвращать const std::string &, то получается лишняя косвенность, а копирование std::string - это всего лишь атомарный инкремент счетчика.

Действительно, статическим массивом обойтись почти всегда можно, но мемоизацию в произвольных выражениях тоже хочется иметь. Не выдумывать же магические позиции в массиве для " hundred " и т.п.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:yigal_s
Date:May 25th, 2013 02:25 am (UTC)
(Link)
вроде в с++11 лямбды ввели, так что написать УЖЕ можно, по идее. С теми же static

как в с++03 это сделать... в голову не приходит.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 02:36 am (UTC)
(Link)
Синтаксис лямбд я, похоже, так никогда и не запомню, пока не начну активно использовать в коде, а это нам разрешат, когда рак на горе свистнет.

Так-то работает:
#define RET(x) [](const char *arg)->string{static string ret(arg); return ret;}(x)

Но уж больно из пушки по воробьям. Я бы предпочел, чтобы можно было писать static перед любым выражением, например, return static "zero";
(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:May 25th, 2013 02:44 am (UTC)
(Link)
можно по идее и с нулём аргументов, нет?

лямбда - совершенно нормальная вещь, ненормально когда её нет.

т.е. я б не сказал, что это "из пушки"

(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:fatoff
Date:May 25th, 2013 05:27 am (UTC)
(Link)
> А теперь вопрос: как на этом вашем стандартном С++ написать то же самое, не засоряя код явными объявлениями статических переменных?

Некий class factory нужен, который вытаскивает определения для объектов из общей "базы данных", в идеале база данных содержит готовые к применению объекты, скорость доступа к одному элементу есть K, константна. Как-то так, если небрежно и без "физических деталей":

class ClassFactory
{
public:
static const Definition& getDefinition( size_t idx )
{
return instance.retrieveDef( idx );
}
private:
ClassFactory()
{
InitDefinitions(); // allocates definitions wherever you want
}
const Definition& retrieveDefinition(size_t idx)
{
return objDefs[ idx ];
}

Definition* objDefs;
static ClassFactory instance;
}

Edited at 2013-05-25 05:29 am (UTC)
(Reply) (Thread)
[User Picture]
From:fatoff
Date:May 25th, 2013 05:31 am (UTC)
(Link)
Ну и объект типа Definition создаётся только ClassFactory, что не сложно.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 05:52 am (UTC)
(Link)
Есть же конкретный пример кода. Попробуй на нем поупражняться. Уточню: идея в том, чтобы не создавать объекты, которые пока не понадобились.

Edited at 2013-05-25 05:54 am (UTC)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:lider
Date:May 25th, 2013 08:07 am (UTC)
(Link)
"В этом случае более эффективно пользоваться статическими объектами для этих константных данных"
"Непонятно, но здОрово".

0.83 = в примере больше времени жрет і.о. Как измерялось?

Интересно какой фактор покажет вот такой вариант:

#include
#include

using namespace std;
static const char * ty[] = {
"©lider", "All rights reserved.", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };

static const char * one[] = {
"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
"eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };

#define spellout_small_int(i) one[i]

string spellout(unsigned int val)
{
if (val >= 1000000)
return string(spellout_small_int(val / 1000000)) + " million " + spellout(val % 1000000);
if (val >= 1000)
return spellout(val / 1000) + " thousand " + spellout(val % 1000);
if (val >= 100)
{
int h = val % 100;
if( h == 0 )
return string(spellout_small_int (val / 100) )+ " hundred ";
return string(spellout_small_int (val / 100) )+ " hundred " + spellout(h);
}
int t = val%10;
if(val>19)
{
if( t==0 )
return ty[val/10];
return string(ty[val/10])+" "+spellout_small_int(t);
}
return spellout_small_int(val);
}

int main()
{
for (unsigned i = 0; i < 10000000; ++i)
cout << spellout(i) << '\n';
}

(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 03:49 pm (UTC)
(Link)
Измерялось по user time, поэтому полное исключение IO к большой разнице не привело. На той же машине проверить до вторника не смогу (у нас длинный выходной), но предполагаю, что будет ближе к RET(x) == x. При конкатенации важно знать длины строк, а они каждый раз пересчитываются заново.
(Reply) (Parent) (Thread)
[User Picture]
From:lider
Date:May 28th, 2013 09:30 am (UTC)
(Link)
мой прогноз 0.67
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2013 08:04 pm (UTC)
(Link)
Чуть лучше (на 3%), чем при RET(x) == x, и заметно хуже (на ~18%), чем при статической реализации.

А вот если заменить объявления ty[] и one[] на string и больше ничего не трогать, то получается гораздо быстрее (еще на 15%). Почему-то интуитивно не совсем очевидно, что инициализация массивов с помощью неявно вызываемых нетривиальных конструкторов работает, вот никто и не предлагал.
(Reply) (Parent) (Thread) (Expand)