?

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)
[User Picture]
From:vaddimka
Date:May 28th, 2013 11:52 pm (UTC)
(Link)
std::string это же не смартпоинтер, там память должна копироваться
если понаделать static std::shared_ptr< const std::string > - тогда будет инкремент счетчика
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 29th, 2013 12:23 am (UTC)
(Link)
/usr/include/c++/4.4.0/bits/basic_string.h:

   *  A string looks like this:
   *
   *  @code
   *                                        [_Rep]
   *                                        _M_length
   *   [basic_string<char_type>]            _M_capacity
   *   _M_dataplus                          _M_refcount
   *   _M_p ---------------->               unnamed array of char_type
   *  @endcode


NB: refcount

Edited at 2013-05-29 12:24 am (UTC)
(Reply) (Parent) (Thread)
[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)
[User Picture]
From:spamsink
Date:May 25th, 2013 03:00 am (UTC)
(Link)
Да, я стормозил. Можно и
[]()->string{static string ret(x); return ret;}()
что уже ближе к правде, но так или иначе, я продолжаю пребывать в состоянии "близок локоть, да не укусишь".
(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:May 25th, 2013 01:20 pm (UTC)
(Link)
если вы согласитесь вместо RET("twenty") писать RET(20, "twenty"),
до далее можно забабахать темплейт:

#define RET(i, s) StringHolder<i>::get(s)

внутри функции 'get' опять же статическая переменная один раз инициализируемая значением 's'.

Edited at 2013-05-25 01:20 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 03:51 pm (UTC)
(Link)
Да, видимо, в С++03 лучше не сделать.
(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:May 25th, 2013 04:16 pm (UTC)
(Link)
времена, когда я считал, что прекрасно знаю С++ давно прошли.

так что я не поручусь.
(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:May 25th, 2013 01:53 pm (UTC)
(Link)
Впрочем, можно попробовать


#define RET(s) StringHolder<__LINE__>::get(s)

что не 100% надежно, но кому какое дело...


Edited at 2013-05-25 01:54 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 03:50 pm (UTC)
(Link)
Я вчера перед сном придумал что-то подобное и сам себя испугался. :)
(Reply) (Parent) (Thread)
[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)
[User Picture]
From:fatoff
Date:May 25th, 2013 06:48 am (UTC)
(Link)
Присмотревшись к деталям, не могу не отметить банальной строчной конкатенации с выделениями памяти, что дорого. Вот это очень даже оптимизируемо для подобных задач. Знаю, как. std::string::reserve будет довольно грубовато, там можно и лучше. Ну и плюс облагородить морду, class factory и исключить множественные статические переменные. Одна-то будет...

P.S. У нас сегодня было "мероприятие" после работы и в общем, три пива. Потому, завтра по утру, думаю.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 06:59 am (UTC)
(Link)
Я знаю, как этот конкретный случай эффективно написать на ассемблере, но вопрос был не в этом, а о способах неявной мемоизации.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:May 25th, 2013 07:05 am (UTC)
(Link)
В C++ там можно не очень сложно нарисовать код, с много большей эффективностью. Даже приходилось однажды в софте предназначанном для финансовых аналитиков. Там был Excel COM add-in для объёмных баз данных, и неимоверное количество сток, которое в постановке задачи решили предоставить для "наборного" запроса. Утро вечера мудренее.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:May 25th, 2013 03:00 pm (UTC)
(Link)
// что-то потерял ссылку на конвертер в HTML, один нашёл, но очень длинный код, lj не пропускает

#include
#include
#include

using namespace std;

static std::vector
[Error: Irreparable invalid markup ('<char *>') in entry. Owner must fix manually. Raw contents below.]

// что-то потерял ссылку на конвертер в HTML, один нашёл, но очень длинный код, lj не пропускает

#include <iostream>
#include <string>
#include <vector>

using namespace std;

static std::vector<char *> vectorOfWords;
std::vector<char *>& RET( char* x )
{
vectorOfWords.push_back( x );
return vectorOfWords; // we don't really have to return it
}

std::vector<char *>& spellout_int(unsigned val) {
if (val >= 1000000)
{
spellout_int(val / 1000000); RET(" million "); spellout_int(val % 1000000); return vectorOfWords;
}
if (val >= 1000)
{
spellout_int(val / 1000); RET(" thousand "); spellout_int(val % 1000); return vectorOfWords;
}
if (val >= 100)
{
spellout_int (val / 100) ; RET(" hundred ") ; spellout_int(val % 100); return vectorOfWords;
}
switch (val) {
default: { spellout_int(val / 10 * 10) ; RET(" "); spellout_int(val % 10); return vectorOfWords; }
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 RET("");
}
}

std::vector<char *>& spellout(unsigned val) {
if (val == 0)
return RET("zero");
auto ret = spellout_int(val);
return ret; // yeah, can easily avoid it
}

static string str; // static string for minimizing reallocation
std::string& vectorToString( vector< char* > vct )
{
str.clear();

// minimizes reallocation
for (size_t n=0; n < vct.size(); n++)
{
str += vct[ n ];
}
return str;
}

int main() {
vectorOfWords.reserve( 100 );
str.reserve( 100 );
for (unsigned i = 0; i < 10000000; ++i)
{
vectorOfWords.clear();
spellout(i);
std::cout << vectorToString( vectorOfWords ) << '\n';
}
}
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:May 25th, 2013 03:11 pm (UTC)
(Link)
Могу "подчистить" до полного отсутствия статических переменных, поместив их в класс как переменные класса.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 03:43 pm (UTC)
(Link)
Спасибо, конечно, но я ж говорю: пример исключительно демонстрационный. Вместо строк с тем же успехом могут быть более сложные объекты - например, логические цепи, реализующие данную таблицу истинности, или еще что-нибудь. :)
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:May 25th, 2013 04:46 pm (UTC)
(Link)
Нет проблем с другими объектами, избежать reallocation можно почти всегда, а цепочные присвоения/инкременты, как для std::string, увы, красивы, но зачастую вовлекают ненужное. Ну, можно и свой оператор для своего типа ввести, <<, например.

И какой результат для моего кода?

Edited at 2013-05-25 04:46 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 25th, 2013 08:28 pm (UTC)
(Link)
Чтобы сравнивать яблоки с яблоками, придется подождать до вторника.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2013 09:06 pm (UTC)
(Link)
Он примерно вдвое быстрее лучшего из имеющихся рекурсивных вариантов, но с нарушением интерфейса.
Если каждый раз возвращать новую строку, которой предварительно сделано reserve(100), то в полтора раза быстрее.
А если не делать reserve, то скорость совпадает.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:May 28th, 2013 09:31 pm (UTC)
(Link)
Подрихтовать интерфейс не проблема, но определяя свой тип вместо string. Может, вечером. И там ещё есть где поэкономить CPU cycles.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2013 10:10 pm (UTC)
(Link)
Есть-есть, но это чисто ради hack value.
(Reply) (Parent) (Thread)
[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)
[User Picture]
From:lider
Date:May 29th, 2013 06:41 am (UTC)
(Link)
string ty[] и подобное я держал в рукаве ;)

если убрать рекурсию и добавить предвьїделение памяти для результата, то можно еще разогнать ф-цию примерно до t/3 от RET(x) == x

Edited at 2013-05-29 06:42 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 29th, 2013 06:48 am (UTC)
(Link)
А если заменить malloc на нормальный (например, tcmalloc), то будет еще быстрее. :)
(Reply) (Parent) (Thread)
[User Picture]
From:lider
Date:May 29th, 2013 03:19 pm (UTC)
(Link)
А как именно?

То, что я имел ввиду:

string spellout(unsigned long long val)
{
string result('r',1024);
result.resize(0);

result+=...
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 29th, 2013 03:42 pm (UTC)
(Link)
Ну да, как fatoff и предлагал. Но зачем такой кошмар, когда можно просто

string result;
result.reserve(1024);

(Какого рожна разработчики STL не сделали резервирующий конструктор - загадка.)

Я имел в виду, что стандартный malloc в libc - старое медленное уродство, и замена его на современный ускорит работу в любом случае.
(Reply) (Parent) (Thread)
[User Picture]
From:lider
Date:May 29th, 2013 08:34 pm (UTC)
(Link)
Согласен, так лучше — убирается мемсет.
(Reply) (Parent) (Thread)