STL, Boost

[homo ludens]

Хеш таблица 2

На таких вещах работаю лексеры многих компиляторов.
Как точка отсчета - http://www.gnu.org/software/gperf/
На вход подается текстовый файл со списком ключевых слов, на выходе имеем исходный текст на С функции реализующей minimal perfect hash.
Есть и лучшие версии, например учитывающие частотное распределение.
Писать ничего не надо, кроме #include <output.text>
STL не при делах и такое сделать не сможет даже вместе с Boost.
Интересно, что человеку воспитанному на STL и в голову не придет искать такое решение.
Аналогов на C++ не встречал.

Хеш таблица 3
Это первая сторонняя либа в списке задач.
http://cmph.sourceforge.net/
minimal perfect hash on billions of keys

Таблица готовится отдельной утилитой, в отличие от предыдущего случая это отдельный файл.
STL применить негде, даже если сильно захотеть.
Аналогов на C++ не встречал.

последнюю таблицу обсудим чуть позже.
Она интересна тем, что там и только там, можно использовать Boost.
Делать этого правда не нужно.

[18-я весна]

[Скипнуто то, где я согласен или пошли по кругу.]

Не в первый раз привожу пример - бывают ситуации, когда память автоматической переменной очищается, а деструктор не вызывается.
Соответственно утечка гарантирована. Экзотика, да. Но бывает.

А можно конкретный пример, а то я не присутствовал при предыдущих демонстрациях.


По поводу RAII.

Вообще говоря я пишу на С++, а не на С, не из-за RAII.
Cуществует такая тема как исключения vs коды возврата.
Я в своих проектах максимально использую исключения для отделения обработки ошибок от прикладного кода.
Прикладной код в своей массе - линейный.
Обработка ошибок вносит в него ветвление и вообще загромождает его ненужными подробностями (особенно если ошибка произошла в глубине вызовов, а обрабатывать ее надо наверху).
Исключения идеально подходят для этой задачи.
Но при работе с исключениями без RAII не обойтись, иначе просто проверки кодов возврата заменятся проверками try/catch и задача отделения кода обработки ошибок от прикладного не будет выполнена.
А это отделение - основа написания легко поддерживаемого кода, что для меня является наиглавнейшим приоритетом.

Таким образом если в неком С++ проекте не используются исключения в сочетании с RAII (для всех без исключения ресурсов), то на С++ такой проект нет смысла реализовывать. Получится мешанина из С-стайл и С++-стайл, что практически гарантированно ведет к деградации кода при внесении изменений.
Возможно что те проекты С++, что вы приводили как пример плохих, как раз имели именно такую проблему.

[18-я весна]

STL в принципе не при делах.
И ничего здесь улучшить не могут.

В этом топике нигде ни разу не говорилось что STL может улучшить код.
Говорилось что можно сделать не хуже.
Так что не понятно чего вы к этому прицепились.

[18-я весна]

Хеш таблица 2

На таких вещах работаю лексеры многих компиляторов.
Как точка отсчета - http://www.gnu.org/software/gperf/
На вход подается текстовый файл со списком ключевых слов, на выходе имеем исходный текст на С функции реализующей minimal perfect hash.
Есть и лучшие версии, например учитывающие частотное распределение.
Писать ничего не надо, кроме #include <output.text>
STL не при делах и такое сделать не сможет даже вместе с Boost.
Интересно, что человеку воспитанному на STL и в голову не придет искать такое решение.
Аналогов на C++ не встречал.

А причем здесь С или С++?
Некоторые классы задач можно решить используя генераторы кода. Какая разница на каком языке код который они генерируют или на каком языке они сами написаны? Вы ж не пишете при этом ни строчки.
А конкретно для словаря с фиксированным набором слов в С/С++, я бы использовал генератор лексических анализаторов flex (или его аналоги в других языках).
Впрочем я подозреваю, что ваш gperf как раз и является таким аналогом и содержит в себе генератор конечных автоматов .

[18-я весна]

Хэш-таблица 1

Если уж смотреть формально, то ваша реализация не обеспечивает условие LRU (поскольку вполне возможно что два подряд вызова попадут в один бакет и при вызове в цикле они будут затирать друг друга и в итоге ни один из них не будет закеширован), поэтому не является корректным решением

//! cache
struct cacheItem
{
  char arg[MAXSIZE];
  double val;
} cache[CACHESIZE];

Про улучшения.
Я вижу ряд проблем в это коде.
1) размер кеша нельзя поменять без пересборки программы.
2) память под кеш выделяется даже если к кешу ни разу не обратились.
3) ...
std::vector решает эти вопросы элементарно, при этом сохраняя фиксированное выделение памяти.
Так что конкретно код приведенный вами можно оптимизировать с помощью STL
Счас вы мне скажете что и в С можно применить malloc и получить то же самое. Однако же в С++ я бы сразу сделал это на "векторе", поскольку это просто и интуитивно, а вам на С показалось интуитивнее или проще использовать статический массив со всеми вытекающими недостатками.
Используемые инструменты вырабатывают стереотип, который потом подсознательно применяется в реальной работе, особенно когда горят сроки.
В больших проектах все эти мелочи накапливается и до них никогда не доходят руки.

[homo ludens]

А можно конкретный пример, а то я не присутствовал при предыдущих демонстрациях.

Любая функция, убивающая поток выполнения и ничего не знающая про С++.
pthread_cancel например, или longjump, которым пугают первокурсников.

По поводу RAII.

ППКС
Я вполне понимаю RAII как средство обойти exception.
Вопрос то был, что в С оно не нужно в том виде, в каком используется в С++ - там можно сделать проще.
Опять таки, да, коды возврата вещь менее удобная и более мусорящая код, чем исключения.
Но все имеет свою цену.
Бывает эта цена высокой, бывает низкой, от задачи зависит.
Для меня например отказ от возможности работать с исходниками является достаточно большой платой.

В этом топике нигде ни разу не говорилось что STL может улучшить код.
Говорилось что можно сделать не хуже.
Так что не понятно чего вы к этому прицепились.

Имелось в виду, что любое решение на STL будет хуже.

А причем здесь С или С++?
Некоторые классы задач можно решить используя генераторы кода. Какая разница на каком языке код который они генерируют или на каком языке они сами написаны? Вы ж не пишете при этом ни строчки.

Разница в том, что многие кодогенераторы обычно ООП и шаблоны и многие фишки С++ не поддерживают.
И держаться в рамках чистого С++ с "правильным" кодом не удается все равно - ну не поддерживает эта штука например исключений, значит надо код возврата использовать. И получается, что в программе сосуществуют два разных стиля.
Причем выбор здесь понятный - либо ты не используешь сторонних программ, либо не используешь С++-стиль.
При этом согласись, написать свой map несколько проще, чем написать свой gperf.

А конкретно для словаря с фиксированным набором слов в С/С++, я бы использовал генератор лексических анализаторов flex (или его аналоги в других языках).
Впрочем я подозреваю, что ваш gperf как раз и является таким аналогом и содержит в себе генератор конечных автоматов .

ни в коем случае нельзя здесь использовать flex!
Решение будет хуже.
Flex не дает О(1), он заточен больше на использование регексов.
Другой вопрос если надо сделать лексер, который в потоке кейвордов распознает еще и числа и квотированные строки.
Тогда да, flex вполне юзабелен.

Если уж смотреть формально, то ваша реализация не обеспечивает условие LRU (поскольку вполне возможно что два подряд вызова попадут в один бакет и при вызове в цикле они будут затирать друг друга и в итоге ни один из них не будет закеширован), поэтому не является корректным решением

Блин, таки да, имелось в виду LRU корзины, но я специфицировал как LRU всей системы. Извините.

Я вижу ряд проблем в это коде.
1) размер кеша нельзя поменять без пересборки программы.

Я для упрощения текста, понятно, что IRL будет конструктор/инициализатор и размер переменный, а не макросом.

2) память под кеш выделяется даже если к кешу ни разу не обратились.
3) ...
std::vector решает эти вопросы элементарно, при этом сохраняя фиксированное выделение памяти.
Так что конкретно код приведенный вами можно оптимизировать с помощью STL

Не, нельзя.
Условие - очень быстрый, это раз.
Поэтому все выделения памяти должны быть сделаны один раз.
Второе, почему копирование строки, а не увеличение счетчика ссылок.
Такой кэш имеет фиксированную верхнюю границу используемой памяти и фиксированную верхнюю границу скорости работы.
Поэтому кстати анализируется, кэшируется и хранится только часть строки.

Я этот код часто использовал в GP системах, где функция вычисляется при случайных значениях много раз во внутреннем цикле.
Так что никаких malloc и vector, будет хуже.

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

ППКС, во многих реальных проектах такие оптимизации нафиг не нужны.
Но с другой стороны привычка к этим инструментам через годы работы приучает забивать разводным ключом гвозди...

Или заставляет говорить вот что:

Конечно такую задачу в жизни я бы делал не на С и не на С++, а на БД ориентированных языках. Например PowerBuilder+Firebird. И уж конечно без лимита диска.

На вполне решаемую задачу.

[homo ludens]

4 таблица

Может быть решена с помощью http://en.wikipedia.org/wiki/Bloom_filter

Странная задача. Видно что надуманная. Я с такими сразу отшиваю.

Эта структура используется Гуглем в BigTable для префильтрации данных.
Эта структура используется в некоторых контроллерах и DSP на аппаратном уровне.
Про базы данных я вообще молчу - там это первое дело.
Привязка динамических библиотек к линуксовому экзешнику происходит быстрее чем к виндовому - потому что в формате ELF используется такая таблица для внешних имен, в отличие от PE executables.

Да, и еще. Этой структуре данных в этом году исполняется 40 лет и в середине прошлого года она таки появилась в Boost sandbox
Соответственно если я буду использовать например cache-friendly BF образца 2002 года, мне придется некоторое время подождать, пока Boost не созреет.

Использовать STL и Boost здесь можно и вполне православно.
Если в таком виде структура достаточна.
Но если не дай бог надо перейти на тот-же cache-friendly версию или на compressed-версию или на out-of-core версию - про Boost можно будет забыть сразу.
И писать с нуля самому.
Благо битовая строка - вещь простенькая...

Я собственно и не стал ждать милостей от Boost и написал свое, когда понадобилось.
И не жалею.

[18-я весна]

Любая функция, убивающая поток выполнения и ничего не знающая про С++.
pthread_cancel например, или longjump, которым пугают первокурсников.

Я не использую либы которые без моего указания манипулируют потоками.
С longjump аналогично.

Разница в том, что многие кодогенераторы обычно ООП и шаблоны и многие фишки С++ не поддерживают.
И держаться в рамках чистого С++ с "правильным" кодом не удается все равно - ну не поддерживает эта штука например исключений, значит надо код возврата использовать. И получается, что в программе сосуществуют два разных стиля.

Использование генераторов это один из методов инкапсуляции. АПИ - это синтаксис на входе, а генерируемый код - это реализация.
Так что с ООП тут все в порядке.
К тому же ООП никакого отношения к стилю или языку не имеет. Это надъязыковая техника.

ни в коем случае нельзя здесь использовать flex!
Решение будет хуже.
Flex не дает О(1), он заточен больше на использование регексов.

Регексы это синтаксис. А реализуются они обычно конечными автоматами, которые широко оптимизируются (теми же генераторами) для разных частных случаев.
Если в регексе только инварианты фиксированной длины (а словарь ключевых слов именно такой: /(a|b|c|...)/) то получается DFA, чья производительность не зависит от кол-ва инвариантов в регексе, а зависит только от длины слов подаваемых на вход для парсинга (так же как и идеальная хеш-ф-я). Таким образом сложность алгоритма O(1).

Не, нельзя.
Условие - очень быстрый, это раз.
Поэтому все выделения памяти должны быть сделаны один раз.
Второе, почему копирование строки, а не увеличение счетчика ссылок.
Такой кэш имеет фиксированную верхнюю границу используемой памяти и фиксированную верхнюю границу скорости работы.

Я этот код часто использовал в GP системах, где функция вычисляется при случайных значениях много раз во внутреннем цикле.
Так что никаких malloc и vector, будет хуже.

//! yes, this is cache size, really :-)
#define CACHESIZE	0x100000UL

//! very long function..... maxlen has same semantics as 'n' in str'n'cpy/str'n'cmp
double tormozzzz(const char*,int maxlen);

//! some fast hash function (i.e. Bernstein hash). maxlen as above
uint32_t hash(const char*,int maxlen);

//! cache
struct cacheItem
{
  char arg[MAXSIZE];
  double val;
};
vector<cacheItem> cache(0);

double getFunctionVal(const char* s)
{
  if (cache.size() == 0)
    cache.resize(CACHESIZE);
  cacheItem& p = cache[hash(s, MAXSIZE) % CACHESIZE];
  // first predicate work in case of test uninitialized cache cell
  if(p.arg[0] != '\0' && strncmp(p.arg, s, MAXSIZE) == 0)
    return p.val;
  strncpy(p.arg, s, MAXLEN);
  return  (p.val = tormozzzz(s, MAXSIZE));
}

Покажите, в каком месте этот код медленее исходного варианта.
Надеюсь вы не имеете ввиду два дополнительных if c проверкой размера массива (второй внутри operator[])?
Покажите, где в этом коде перераспределяется память в процессе работы.

Поэтому кстати анализируется, кэшируется и хранится только часть строки.

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

[18-я весна]

Странная задача. Видно что надуманная. Я с такими сразу отшиваю.

Эта структура используется Гуглем в BigTable для префильтрации данных.
Эта структура используется в некоторых контроллерах и DSP на аппаратном уровне.
Про базы данных я вообще молчу - там это первое дело.
Привязка динамических библиотек к линуксовому экзешнику происходит быстрее чем к виндовому - потому что в формате ELF используется такая таблица для внешних имен, в отличие от PE executables.

Я правильно понял, вы предлагаете задачу про базу рефератов решать на собеседовании с помощью BF? А если человек не знал про BF и не смог ничего придумать то это идет ему в минус? А если знал, то просите доказать применимость алгоритма для задачи (рассчитать вероятность коллизий для заданного размера и кол-ва)? Не слишком ли мозгоклюйская задача для собеседования? В спокойной обстановке за день два я бы изобрел этот алгоритм и формулы вероятностей бы вывел, но не в стрессовой ситуации собеседования.

А что касается классов задач описанных вами как Тип 1-4, то подходящие под них алгоритмы легко ищутся (даже если не знаешь конкретные названия этих алгоритмов) и так же легко кодируются на любом языке. Или вы опять про то как STL тормозит? Так вы пока этого не показали

[homo ludens]

Я правильно понял, вы предлагаете задачу про базу рефератов решать на собеседовании с помощью BF? А если человек не знал про BF и не смог ничего придумать то это идет ему в минус? А если знал, то просите доказать применимость алгоритма для задачи (рассчитать вероятность коллизий для заданного размера и кол-ва)? Не слишком ли мозгоклюйская задача для собеседования? В спокойной обстановке за день два я бы изобрел этот алгоритм и формулы вероятностей бы вывел, но не в стрессовой ситуации собеседования.

Меня в данном случае интересует не столько знание, сколько реакция.
Незнание BF в минус не идет (кстати у меня не идет в минус и незнание STL).
В минус идут попытки доказать что решение невозможно.
Которые я наблюдал на этом форуме - вполне за день-два и не в стрессовой ситуации.
И алгоритм никто не изобрел и формулы вероятностей не вывел.

А что касается классов задач описанных вами как Тип 1-4, то подходящие под них алгоритмы легко ищутся (даже если не знаешь конкретные названия этих алгоритмов) и так же легко кодируются на любом языке. Или вы опять про то как STL тормозит? Так вы пока этого не показали

Я показал, что люди замкнутые в STL, не ищут эти алгоритмы и иногда вообще отрицают их существование.
На наглядном примере.
Вообще надо было задачи на неделю оставить без ответа...
Было бы показательней.
Кроме того я показал, что люди, замкнутые в STL склонны решать задачи втыкая STL там, где он отолько ухудшает решение и в принципе не нужен.

[homo ludens]

Я не использую либы которые без моего указания манипулируют потоками.
С longjump аналогично.

А плюсовики много чего не используют, им все жить мешает.
Странное дело - есть фича, которая не моделируется другими фичами в принципе.
Т.е. расширяет возможности.
Не, вот ограничить и специально сделать неудобной конверсию типов - это мы можем.

К тому же ООП никакого отношения к стилю или языку не имеет. Это надъязыковая техника.

Т.е. ООП к С++ не имеет отношения?
Сильный ход.
Интересно что по этому поводу сказал бы Страуструп, вот он явно был другого мнения.

Покажите, в каком месте этот код медленее исходного варианта.

Показываю

Просто компилируем и запускаем
[someone@somewhere flame]$ g++ -Wall x.cc -o xrun
[someone@somewhere flame]$ ./xrun 100000
STL: 140 ms
non-STL: 84 ms

Теперь с отладкой
[someone@somewhere flame]$ g++ -Wall -g x.cc -o xrun
[someone@somewhere flame]$ ./xrun 100000
STL: 139 ms
non-STL: 84 ms

Теперь на виртуальной машине
[someone@somewhere flame]$ vg ./xrun 10000
STL: 531 ms
non-STL: 262 ms

Ок, может все проблемы уйдут с оптимизацией?
[someone@somewhere flame]$ g++ -Wall -O3 x.cc -o xrun
[someone@somewhere flame]$ ./xrun 100000
STL: 112 ms
non-STL: 62 ms

Ладно, но у тебя в коде грубая ошибка.
Ты лишний if вставил во внутренний цикл.
А надо сказать, что if во внутреннем цикле очень затратен - он вызывает срыв кеша инструкций.
Особо продвинутые дзен-мастера на этот случай могут реализовывать min и max только на логических операциях.
Твой if - это часть семантики конструктора, но не самой функции.
Исправим твою ошибку и начнем по новой.

Это уже ближе к реальности.
[someone@somewhere flame]$ ./xrun2 100000
STL: 84 ms
non-STL: 84 ms
[someone@somewhere flame]$ g++ -Wall -g x2.cc -o xrun2
[someone@somewhere flame]$ ./xrun2 100000
STL: 83 ms
non-STL: 84 ms
Странный результат, который вызван похоже ошибкой округления.
Для проверки повторим:
[someone@somewhere flame]$ ./xrun2 100000
STL: 84 ms
non-STL: 84 ms

Под эмулятором
[someone@somewhere flame]$ vg ./xrun2 10000
STL: 275 ms
non-STL: 254 ms

С полной оптимизацией
[someone@somewhere flame]$ g++ -Wall -O3 x2.cc -o xrun2
[someone@somewhere flame]$ ./xrun2 100000
STL: 60 ms
non-STL: 56 ms
[someone@somewhere flame]$ ./xrun2 100000
STL: 59 ms
non-STL: 56 ms
[someone@somewhere flame]$ ./xrun2 1000000
STL: 598 ms
non-STL: 571 ms
[someone@somewhere flame]$ ./xrun2 1000000
STL: 598 ms
non-STL: 569 ms

Т.е. использование STL привело к ухудшению качества программы.
А такие мелочи как увеличение времени компиляции мы вообще во внимание не принимаем.

Регексы это синтаксис. А реализуются они обычно конечными автоматами, которые широко оптимизируются (теми же генераторами) для разных частных случаев.
Если в регексе только инварианты фиксированной длины (а словарь ключевых слов именно такой: /(a|b|c|...)/) то получается DFA, чья производительность не зависит от кол-ва инвариантов в регексе, а зависит только от длины слов подаваемых на вход для парсинга (так же как и идеальная хеш-ф-я). Таким образом сложность алгоритма O(1).

Давай проверим?

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

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

[18-я весна]

Меня в данном случае интересует не столько знание, сколько реакция.
Незнание BF в минус не идет (кстати у меня не идет в минус и незнание STL).
В минус идут попытки доказать что решение невозможно.
Которые я наблюдал на этом форуме - вполне за день-два и не в стрессовой ситуации.
И алгоритм никто не изобрел и формулы вероятностей не вывел.

Глупо рассчитывать, что кто-то увидев ваши сообщение сразу бросится искать решения. Здесь не собеседования и никто никому не должен.
Кроме того я сразу написал, что допускаю что решение возможно, но тратить время на бредовые по своей сути задачи я не собираюсь. Задача была надумана. Была бы практическая польза у тех лимитов что установлены, я бы может и потратил свое время, для меня нет проблемы изобрести алгоритм, тем более такой примитивный.
А так простите.

Я показал, что люди замкнутые в STL, не ищут эти алгоритмы и иногда вообще отрицают их существование.
На наглядном примере.

Нет, вы всего лишь показали что существуют задачи чье решение никому кроме вас не интересно.

Кроме того я показал, что люди, замкнутые в STL склонны решать задачи втыкая STL там, где он отолько ухудшает решение и в принципе не нужен.

Ой, прямо, STL ухудшил алгоритм, который сам по себе ошибочен
Ну, про тесты скорости следующим постом.

[18-я весна]

А плюсовики много чего не используют, им все жить мешает.

Извините, но вам тоже мешает STL и буст. Так что вы счас прямо описали самого себя.

Т.е. ООП к С++ не имеет отношения?
Сильный ход.
Интересно что по этому поводу сказал бы Страуструп, вот он явно был другого мнения.

Мне все равно что думает Страуструп. Для меня мнение авторитета не является аргументом.

Ладно, но у тебя в коде грубая ошибка.
Ты лишний if вставил во внутренний цикл.
А надо сказать, что if во внутреннем цикле очень затратен - он вызывает срыв кеша инструкций.

Разрешите вам не поверить про кеш инструкций (применительно к данному случаю). См. ниже.

С полной оптимизацией
[someone@somewhere flame]$ g++ -Wall -O3 x2.cc -o xrun2
[someone@somewhere flame]$ ./xrun2 1000000
STL: 598 ms
non-STL: 571 ms
[someone@somewhere flame]$ ./xrun2 1000000
STL: 598 ms
non-STL: 569 ms

Т.е. использование STL привело к ухудшению качества программы.

Вы зря остановились на 1000000 итераций.

Вот мои измерения на компиляторе MSVC 2008 с оптимизацией по умолчанию (max speed: /O2) (см. вложение)
STL if(100000000 iters): 40219 ms (это с if но без resize())
STL cache resize(100000000 iters): 40531 ms
STL preallocated cache(100000000 iters): 39453 ms
non-STL(100000000 iters): 39688 ms

Что мы видим? Что на достаточно большом промежутке времени (где самопальные таймеры перестают вносить погрешность в измерения), разница в скорости между STL/nonSTL перестает быть существенной (доли процента). Причем видно, что в среднем возможно и возрастание скорости, но это конечно не заслуга STL а так данные просто сгенерировались.
Из-за этих, не выходящих за погрешность измерений, различий принимать решение не использовать удобный и главное стандартный инструмент - увольте.

Что касается кеша инструкций и if, то именно переходы по if находящимуся внутри цикла и срабатывающему преимущественно по одному и тому же ветвлению (как в данном случае) очень хорошо предсказываются на любых современных процессорах.
А задержка связанная с if (cache.size() == 0) действительно имеется, во первых из-за собственно выделения памяти, во вторых из-за непонятно почему громоздкой реализации самого cache.size() (теперь буду знать). Кеш инструкций здесь не при делах.

Давай проверим?

ОК. Вы реализуйте идеальной хеш-ф-ей, а я реализую flex-ом.

Проверять будем парсингом большого буфера памяти содержащего ключевые слова, другие слова и пробелы, cгенерированого заранее.
Я утверждаю что при разборе каждого очередного слова в потоке сложность определения является ли оно ключевым будет не выше O(1). Это значит, что скорость поиска одного слова не зависит от кол-ва слов в словаре. Т.е. если сократить набор ключевых слов в два раза, скорость парсинга того же буфера не должна измениться.

[Antisies]

Для библиотеки Boost есть .net обертка?