Зачем delphi свой менеджер памяти?

← →
Сергей М. © (2013-01-23 09:29) [80]

> Столько сколько за трабовал программист

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

> память под динамический массив постоянно выделяется освобождается
> статический массив у меня был

Я что-то не понял - ты подменил дельфийский менеджер opencv"шным что ли ?

Полагаю что говоря об OpenCV-менеджере куч мы имеем ввиду MemStorage-механизм с соответствующим набором касаемых его OpenCVAPI-вызовов..

http://locv.ru/wiki/8.1_%D0%A5%D1%80%D0%B0%D0%BD%D0%B8%D0%BB%D0%B8%D1%89%D0%B0_%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8

← →
Ega23 © (2013-01-23 09:49) [81]

> А можно подробнее?

Есть токены. Есть документы, в которых они встречаются. Токенов, ЕМНИП, примерно 3,5 миллиона (попозже уточню). Документов - примерно 15.000
Вероятность встречаемости токена в документе, если я не ошибаюсь, что-то около 40% (считал давно).
Вот и прикидывай, сколько кросс-таблица отношения токенов к документам займёт. 21 миллиард записей.

← →
Ega23 © (2013-01-23 10:35) [82]

Уточнил. Полтора миллиона. Но в индексном файле ещё и в lower case это дело сидит, это, считай, плюс примерно 85% от полутора лямов.
прилично, в общем, набИгает.

← →
Пит (2013-01-23 10:44) [83]

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

Вон Word делает проверку и орфографии и пунктуации, и разбирает синтаксис. Те же самые онлайн переводчики, какой там анализ встроен - я даже не представляю. И они не грузят в памят 4 гб словари...

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

← →
Ega23 © (2013-01-23 10:49) [84]

> Вон Word делает проверку и орфографии и пунктуации, и разбирает
> синтаксис. Те же самые онлайн переводчики, какой там анализ
> встроен - я даже не представляю. И они не грузят в памят
> 4 гб словари...

Ты не понял. подсветка она моментально делается, без всякой загрузки огромных кусков. Речь о поиске в 15.000 документах.
Дано: 15.000 документов. Отбери из них те, в которых есть слова с подстроками "масс", "отбив", "штукат", регистронезависимо, чтобы расстояние между словами было не более 15 слов.

← →
Ega23 © (2013-01-23 10:50) [85]

> Но просто наверняка бизнес-задача как-то и иначе решается.

Решается, 300 метров в памяти, пиковые - может до 600 метров доходить.

← →
Rouse_ © (2013-01-23 11:30) [86]

> Отбери из них те, в которых есть слова

Немного не так - отобрать нужно максимально быстро, бо клиентов на сервере много, чтоб ни у кого ничего не тормозило.

> Пит (23.01.13 10:44) [83]

Есть такая утилитка AvSearch. Удобная и шустрая - делает поиск по папке по введенному выражению (я ей обычно поиск в исходниках делаю). Тестировал на ней, выгрузив все наши документы в текстовом виде. Результат поиска в среднем около двух минут, что с нашим практически моментальны поиском не идет ни в какое сравнение.

← →
Ega23 © (2013-01-23 11:33) [87]

> Немного не так - отобрать нужно максимально быстро, бо клиентов
> на сервере много, чтоб ни у кого ничего не тормозило.

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

← →
Rouse_ © (2013-01-23 11:34) [88]

Да впрочем можно даже посмотреть на поиск самой дельфи.
Берем папку: C:\Program Files\Embarcadero\RAD Studio\7.0\source
В ней 1 718 файлов. Делаем поиск в дельфе по это папке слова GetTickCount.
Результат 11 секунд - что не допустимо в нашей ИСС.

← →
Игорь Шевченко © (2013-01-23 11:40) [89]

Rouse_ © (23.01.13 11:34) [88]

Виндовый поиск с включенной индексацией ?

← →
Rouse_ © (2013-01-23 11:43) [90]

> Игорь Шевченко © (23.01.13 11:40) [89]

Не тестировал.

← →
Rouse_ © (2013-01-23 11:47) [91]

А он внутри текста документов разве ищет?

← →
Sha © (2013-01-23 12:05) [92]

> Ega23 © (23.01.13 10:49) [84]
> Речь о поиске в 15.000 документах.Дано: 15.000 документов. Отбери
> из них те, в которых есть слова с подстроками "масс", "отбив",
> "штукат", регистронезависимо, чтобы расстояние между словами
> было не более 15 слов.

поиск нужен по тексту документов в ОП или по индексам?

← →
Павиа (2013-01-23 12:07) [93]

Проблемы понятны. Сам ковырялся с моментальным поиском. Вот только пути решений у нас разные.

← →
Rouse_ © (2013-01-23 12:10) [94]

> Sha © (23.01.13 12:05) [92]
> поиск нужен по тексту документов

По тексту

← →
Ega23 © (2013-01-23 12:16) [95]

> поиск нужен по тексту документов в ОП или по индексам?

И тот и другой. Просто в документе слова встретились в произвольном порядке - там по общему индексу поиск идёт, это вообще меньше секунды, дольше отображать список документов. А вот если "строгое совпадение фразы", или "расстояние между словами" или "все слова встречаются в пределах параграфа" - тогда двухступенчатый поиск: сначала по первому отбираем все документы, в которых данные слова встречаются, потом к каждому документу подгружаем уже его индексный файл, где порядок слов и параграфов учтён. Тут уже дольше перебор идёт. ЕМНИП, основная просадка на файловых операциях (но тут могу ошибаться).

← →
Sha © (2013-01-23 12:18) [96]

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

Весь алгоритм меньше сотни строчек.

← →
Пит (2013-01-23 12:19) [97]

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

Вы пробовали например хотя бы что-то типа: http://ru.wikipedia.org/wiki/Sphinx_%28%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0%29

?

← →
Sha © (2013-01-23 12:27) [98]

[96] это в ответ на [94]

> Ega23 © (23.01.13 12:16) [95]

Нормальное решение. Очень интересно, есть ли статистика запросов пользователей? Почему недостаточно просто в пределах абзаца?

← →
Rouse_ © (2013-01-23 12:28) [99]

> Sha © (23.01.13 12:18) [96]

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

> Пит (23.01.13 12:19) [97]

Много чего перепробовали - скорость не устроила и возня с настройкой у конечного пользователя.

← →
Sha © (2013-01-23 12:31) [100]

> Rouse_ © (23.01.13 12:28) [99]

Это только упрощает алгоритм в части вычисления хеша.

← →
Ega23 © (2013-01-23 12:33) [101]

> Очень интересно, есть ли статистика запросов пользователей?

К сожалению нет, только по ошибкам.

> Почему недостаточно просто в пределах абзаца?

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

← →
Ega23 © (2013-01-23 12:43) [102]

> Вы пробовали например хотя бы что-то типа

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

← →
Sha © (2013-01-23 12:44) [103]

> Ega23 © (23.01.13 12:33) [101]

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

← →
Rouse_ © (2013-01-23 13:01) [104]

Режимов поиска несколько и все это настраивается. На семинарах как раз показываем различные ситуации и как более оптимально производить поиск для быстрого нахождения правильного результата. Народ вроде не путается...

← →
Ega23 © (2013-01-23 13:09) [105]

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

Именно так. Витала одно время идея абзацем <TR> считать, но, поскольку таблицы в 30% случаев составные, то на <TD> остановились.

← →
DVM © (2013-01-23 13:21) [106]

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

← →
Игорь Шевченко © (2013-01-23 13:57) [107]

DVM © (23.01.13 13:21) [106]

В Windows так сделано давным-давно, см. LookasideLists

← →
DVM © (2013-01-23 15:33) [108]

> Игорь Шевченко © (23.01.13 13:57) [107]

> LookasideLists

Это не совсем то. Насколько я понял, это очередь буферов с которым оперирует драйвер. У того же LibPcap такая очередь тоже есть и на какое то время она предоставляет доступ клиентскому приложению к элементу этого буфера (при приходе очередного пакета). Но валидность переданного указателя фактически доли секунды, потом содержимое будет перезаписано новыми данными и если приложение не успеет скопировать данные в свои буфера, то смысла в этом нет. И клиентское приложение вынуждено организовывать собственные очереди значительно большего размера, в которые оно уже будет помещать данные полученные из драйвера.

> LookasideLists

Или это не только для драйверов? Если не только, то это хорошая штука, но к сожалению только под Windows.

DVM © (23.01.13 15:33) [108]

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

> У того же LibPcap такая очередь тоже есть и на какое то
> время она предоставляет доступ клиентскому приложению к
> элементу этого буфера (при приходе очередного пакета). Но
> валидность переданного указателя фактически доли секунды,
> потом содержимое будет перезаписано новыми данными и если
> приложение не успеет скопировать данные в свои буфера

Эмм, если мне не отбило память, то данные о пакетах накапливаются в драйверном буфере и передаются приложению по таймауту либо по переполнению буфера. Само приложение в память драйвера не лезет (адресация не позволит)

Если абстрагироваться от конкретных реализаций: в чем может быть фишка своего менеджера памяти? Очевидно в захвате некоторого блока у системы и последующее распределение меж нуждающимися без лишних аллокаций-реаллокаций. Все остальное - только вариации на тему. ИМХО.

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

> Rouse_ © (23.01.13 16:37) [111]

> Эмм, если мне не отбило память, то данные о пакетах накапливаются
> в драйверном буфере и передаются приложению по таймауту
> либо по переполнению буфера.

libpcap это не совсем то же, что winpcap. Есть множество вариаций libpcap с разными механизмами передачи пакетов с уровня ядра в юзерспейс. Самый продвинутый вариант для PF_RING, само название которого намекает на кольцевой буфер ассоциированный с каждым сокетом.

← →
Павиа (2013-01-23 17:51) [116]

invert, На осдеве обсуждали создать можно, но это java, net (т.е. компилятор должен быть квазинативный)

> [115] Игорь Шевченко © (23.01.13 17:40)
> Есть и такие

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

> [116] Павиа (23.01.13 17:51)
> На осдеве обсуждали создать можно, но это java, net (т.е.
> компилятор должен быть квазинативный)

Ну, про такие в общем-то понятно. Может, если в процессоре их реализуют, так то и будет.

Inovet © (23.01.13 17:54) [117]

Ты вообще о чем ? О каких процессорах и каких указателях ? Такие указатели были еще в Windows 3.1

← →
Павиа (2013-01-23 18:08) [120]

Ну, про такие в общем-то понятно. Может, если в процессоре их реализуют, так то и будет.
>

Зачем в процессоре! dz делает ОС с такими указателями. Называется ФантомОС (не путать с человеком)

Зачем delphi свой менеджер памяти? Найти похожие ветки