Смерть Кащея

lexa - 23/Янв/2009 18:43
Смерть Кащея в игле, игла в яйце, яйцо в утке, утка в зайце, заяц в шоке!

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

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

Я бы такую сложную структуру руками запрограммировать бы быстро не сумел (да и не стал бы), а несколько дней выпиливал бы какое-нибудь zero-copy решение, которое копий строк не содержит (или по-возможности не содержит).

Но вторая сторона проблемы остается забытой: на 32-битной архитектуре каждый vector - это 12 байт, список - 8 (плюс 8 на каждый элемент), строка - 4 (ну хоть тут нет оверхеда). Когда мы это намешаем в кучу - получим десятки байт оверхеда на каждый элемент. А элементов может быть много. И когда их становятся первые миллионы - оверхед вдруг становится первыми сотнями мегабайт и это уже после утаптывания кода.

Потом, все это нужно аллоцировать/деаллоцировать. И Malloc Trace мне гордо сообщает, что при обработке 60 тысяч входных элементов в трейс записались 2 миллиона событий. Понятно, отчего все так хотят быстрый malloc.

Ну и не забываем, что просто побегать по плотному массиву (пусть и аллоцированному с небольшим запасом), особенно выровненому на 32 байта - это одно. А 3-4 dereference на каждый элемент - совсем другое, кэш не резиновый.

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

Comments

kagand (not verified) - 23/Янв/2009 12:54

Никак морфология? ;-)

lexa - 23/Янв/2009 12:58

Не, морфология у нас уже вылизана до блеска.

Это совсем новый проект, не скажу какой.

vitus_wagner (not verified) - 23/Янв/2009 13:28

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

Почему я и люблю многоязычные технологии. К примеру С+Tcl.

lexa - 23/Янв/2009 13:52

В близкой по духу (но не по содержанию) задаче у меня опыт такой
- перловый вариант медленнее С/C++ ного раз в 10, когда оба написаны в лоб
- после этого перловый ускоряется в ~100 раз за полдня и на этом резервы
кончаются.
- С-шный можно сделать еще в 100 раз быстрее, потратив неделю и еще
в 10 раз быстрее (итого уже 5 порядков от исходного) переформулировав
задачу на разреженные матрицы и взяв BLAS для них.

10/100 - раз - это порядки величины, естественно.

vitus_wagner (not verified) - 23/Янв/2009 14:18

Возможность выноса критической функциональности в XS-модуль в качестве резерва рассматривалась? А перловый вариант усовершенствованного алгоритма с использованием Math::GSL::BLAS?
А сколько времени занимает разгон C-шного варианта до скорости, равной максимальному полученному перловому?

Двуязычные решения хороши тогда, когда нужен баланс скорости разработки и скорости выполнения. Очевидно, что если необходим однократный рассчет, который на исходном C-шном варианте занимает 10 дней, с перлом результат можно получить за полтора дня, а с сями - за неделю+2 с половиной часа.

lexa - 23/Янв/2009 14:36

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

Поэтому, кстати, не BLAS, а sparse BLAS, это немножко другая история.

beldmit (not verified) - 23/Янв/2009 17:59

А, вот небось для чего GPU и CUDA!
Читаю как раз сейчас их документацию.

lexa - 24/Янв/2009 04:47

До этого не дошло (все-таки до недавних буквально пор оно было совсем нетехнологично), но там можно еще изрядный выигрыш получить (раз 10-20 еще). Но N^2-ные задачи это мало спасает.

polyestr (not verified) - 23/Янв/2009 22:05

Полностью согласен с комментарием про STL.

Однажды, одной моей программе, которая читала строки из файла в vector, подсунули миллион строк. И массивчик из файла 14 мегабайт в памяти занял 60. В общем, пришлось бороться.

v_shabanoff (not verified) - 23/Янв/2009 17:57

Чемберлену можно ответить
boost::object_pool и boost::pool
немного оверхед (в malloc-чной части) снимает, хотя, конечно, не рукоблудное решение с зеро-копи и указателями, в которых младшие пару бит используется для хранения погоды на завтра.

lexa - 24/Янв/2009 04:46

Re: Чемберлену можно ответить
Я про оверхед маллока (который ТОЖЕ есть) вообще ничего не говорил, я только про чистый оверхед на структурах данных.

Вообще, один из поинтов в том, что какая-то сильно избыточная структура данных с редко используемыми полями, но аллокация ее массивом - несмотря на кажущуюся избыточность может оказаться сильно экономнее.

А выпиливание - интересная штука. Скажем, на 64-битной архитектуре в поле для указателя на строку влезет подавляющее количество самих слов (и тем более основ), вместо указателя на динамическую строку. А если считать malloc overhead, то и тем более.

lexa - 24/Янв/2009 05:37

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

А дальше - реальные данные и выясняется, что написан прототип, а вовсе не настоящая программа.

gabaidulin (not verified) - 23/Янв/2009 18:29

А почему std::string - 4 байта?
По-моему в любой популярной реализации stl выделяется буфер в куче, равный, 16 байт?

lexa - 24/Янв/2009 04:39

Я смотрел sizeof-ы типов, что для строки методологически неверно, вы правы.

Оно все особенно смешно, если вспомнить, что все это хозяйство навешивается на слово, а средняя длина слова в русском - символов 7 или около того.

alsep (not verified) - 26/Янв/2009 05:55

А кто сказал, что STL таблетка от всех бед? Это не так. Для меня STL в двух трёх смыслах есть:

1. С применением мозга, когда больше думаешь чем пишешь. Считаешь, и ещё раз думаешь. Потом ещё раз оцениваешь и один из контейнеров пишешь сам.

2. Стандартизирует. Это реально удобно и нужно хотя бы по минимуму: если и делать свой контейнер, то АПИ чтобы не совсем от балды было.

3. Черновик. На STL пишутся многие вещи почти так же просто как и скриптовых языках.

Ну и потом, есть предлагаю вам посмотреть на Java и C#. Тогда узнаете, что есть настоящее зло.

lexa - 26/Янв/2009 17:08

Проблема в том, что прототип (черновик) на STL зачастую имеет все признаки реальной программы - работает более-менее, памяти жрет более-менее.

И грабли вылезают при попытке скормить ему терабайт-другой, отчего хочется его в 10-100 раз ускорить, отчего ему лезется в пузо, а там - такое....

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

Знающие люди, впрочем, уверяют, что это лечится административными мерами, например поркой по пятницам.

alsep (not verified) - 27/Янв/2009 07:35

Я в своём старом отделе Буст запретил. А когда готов черновик, запускается gprof, и говорится автору что-то типа такого: Дорогой аффтар, ускорь в 10 раз свой код, ну и по памяти заодно посмотри...

Аффтар включает мозг и думает, где STL плохой, а где он использует неправильно.

lexa - 27/Янв/2009 07:44

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

lexa - 27/Янв/2009 07:45

Но вообще, с тезисом "афтар включает моск" я даже спорить не буду, идея правильная.

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

alsep (not verified) - 27/Янв/2009 08:00

Я могу привести вложенность 3 только на STL. :)

В моем индексаторе, цитирую код:

struct document_token
{
std::string original;
std::string normal_form;
u_int64_t grammems;
double weight;
};

Это элемент текста.

typedef std::vector<document_token> token_list;

Это результат всех омонимических вариантов разбора. Кстати, то что там original может быть 10 раз не страшно, потому что там строки копируются как указатели.

typedef std::tr1::unordered_map<int, token_list> position2tokens;

Это по позиции списки.

typedef std::tr1::array<position2tokens, XXX> PoS2positions;

Это статический массив по части речи.

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

К чему это всё? Вложенность не вредит, если используется правильно.

alsep (not verified) - 27/Янв/2009 08:01

ух как парсер ЖЖ-шный торкнуло...

lexa - 27/Янв/2009 08:20

Да-да, очень похоже на то, что мы программируем.

А когда в эту штуку засовывают Библиотеку Мошкова одним файлом - что происходит?

alsep (not verified) - 27/Янв/2009 09:20

Кстати, именно этот контейнер (большой) скорее для предложения, ну или для абзаца в "плохом" тексте типа каментов, когда на предложение не бьётся. Эта стуктура для расставления весов по idf, снятия омонимии первого и второго плана. Первого очевидные случаи, второго согласованно с тематикой.

Все системы анализа текстов похожи, как похожи все веб-сервера или почтовые сервера.