Проект "CachedBuffers"

← →
DevilDevil © (2013-03-12 15:51) [120]

> Rouse_ © (12.03.13 15:46) [117]
офтоп:
а зачем тебе кстати столько ?
вроде как объединение баз у вас не часто должно происходить
такой скорости наверное можно достичь если сжать все файлы в zip
и кстати если не сортировать в алфавитном порядке - тоже можно сэкономить время (ибо для хеш-поисков вообще не важен алфавитной порядок)

← →
Павиа (2013-03-12 15:52) [121]

Розыч. Опиши задачу словесно. Хочу попробовать одну штуку из области оптимизации.

← →
DevilDevil © (2013-03-12 15:54) [122]

> brother © (12.03.13 15:44) [116]
> функция копирования большого файла при помощи этой байды
> будет быстрее стандартных примеров?

по тестам, которые я видел - ничего быстрее CopyFile и CopyFileEx не существует. Ибо там какие-то внутренние оптимизации используются

а если говорить о собственных поделиях... то хз. Медленнее работать не должно. Может быть для случаев копирования в рамках одного жёсткого диска нужно будет указать аргумент DoubleThreading false

← →
Игорь Шевченко © (2013-03-12 15:54) [123]

Sapersky (12.03.13 15:50) [119]

Нет, обертка вокруг стандартных вызовов API. Ее текст в какой-то ветке выложен. Если принципиально, могу на API написать то же самое, +10 строк кода :)

← →
Rouse_ © (2013-03-12 15:55) [124]

> Павиа (12.03.13 15:50) [118]
> Розыч. Опиши задачу совестно. Хочу попробовать в оптимизации
> одну штуку.

Сейчас не могу, я дома болею. В принципе все данные по задаче я Диме по асе пересылал, если он сможет их найти в хистори то думаю выложит.
Суть такая есть куски дампа наших баз в определенном формате, нужно их слить в один единственный файл убрав дубляж. Формат файлов есть у DevilDevil.
Мой вариант (который в примере) делает это все за 30 сек примерно, Дима реализовал слияние в районе 7 сек. Jack128 в качестве спортивного интереса сейчас пилит код в свободное время пытаясь выйти на необходимые для нас 4 секунды.
Данная задача решалась примерно два года назад и мы ее решили в Ega23, а этот вот пример остался просто как для разминки пальцев и мозга :)

← →
DevilDevil © (2013-03-12 16:03) [125]

> Формат файлов есть у DevilDevil.
офтоп:
я так и не понял то описание, и хистори не осталось - комп сменили
я смотрел твои сорсы чтобы понять суть

← →
Ega23 © (2013-03-12 16:06) [126]

> Если в твоей работе нет необходимости в высокопроизводительных
> приложениях, то что ты хочешь доказать мне ?

В высокопроизводительных - как раз есть. Мне не совсем понятна фишка зачитки таких гигантских кусков данных.
Да, у нас самый большой файл обновления весит 3,5 гига. Но это файл с определённой структурой, из которой "выдираются" нужные куски по-факту. А сами куски - не такие уж и огромные.
Как раз задница в обратном была: есть куча мелких файлов, но объединить это надо без дублирования (а дублирование там приличное, процентов 70). И когда 2 года назад экспериментировали, то на десятке больших файлов были вполне приемлемые результаты. Но когда выяснилось, что вместо десятка больших будет три сотни мелких - от тогда-то и приплыли.

← →
DevilDevil © (2013-03-12 16:15) [127]

> Ega23 © (12.03.13 16:06) [126]
офтоп:
задачи у вас простые. всё сводится:
1) чтение/запись файлов
2) хеш-поиск
3) грамотный менеджмент памяти

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

← →
Ega23 © (2013-03-12 16:23) [128]

> Розыч. Опиши задачу словесно. Хочу попробовать одну штуку
> из области оптимизации.

Задача такова:
Есть информационная система, нечто похожее на Консультант. Т.е. множество различных документов (законы, стандарты, и т.д.).
Есть ежемесячные "обновления" данной системы (новые документы, поправки к старым). В данный момент полный комплект - около 300 обновлений с парой десятков тысяч документов.
В системе должен быть реализован быстрый поиск.
Соответственно, в каждом обновлении есть стрим со "словарём" для быстрого поиска. Формат словаря: сортированный список токенов, к каждому токену присобачен сортированный список ID документов, в которых данный токен встречается. Также дополнительным стримом лежит словарь токенов в LowerCase, к каждому токену присобачен список офсетов на case-sensetive токены.
Задача: из этих трёхсот стримов сформировать один, исключив дублирование токенов (дублирование, это когда токен "1" с вероятностью 99.99% встречается в каждом документе. А "ГОСТ13-43-4444" - скорее всего в нескольких).
Вроде так, если что - Розыч поправит. цифры тоже он помнит, сколько примерно эти стримы занимают, мне навскидку только процент повторяемости токенов в обновлениях (~70) помню.

← →
Ega23 © (2013-03-12 16:25) [129]

> 2) хеш-поиск

Зачем? Там дихотомия, все словари отсортированы на этапе формирования обновления.

← →
DevilDevil © (2013-03-12 16:26) [130]

> мне навскидку только процент повторяемости токенов в обновлениях (~70) помню.
офтоп:
кстати вы там ошибку допустили при подсчёте повторений. на тех данных которые у меня были - дублирование составило около 50%

← →
DevilDevil © (2013-03-12 16:30) [131]

> Ega23 © (12.03.13 16:25) [129]
> Зачем? Там дихотомия, все словари отсортированы на этапе
> формирования обновления.

мне конечно хочется вставить скриншот "facepalm"
но из уважения к розычу - отвечу
затем, что так быстрее минимум на порядок

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

← →
Rouse_ © (2013-03-12 16:37) [132]

> DevilDevil © (12.03.13 16:26) [130]
> > мне навскидку только процент повторяемости токенов в
> обновлениях (~70) помню.
> офтоп:
> кстати вы там ошибку допустили при подсчёте повторений.
> на тех данных которые у меня были - дублирование составило
> около 50%

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

← →
Rouse_ © (2013-03-12 16:40) [133]

> Ega23 © (12.03.13 16:25) [129]
>
> > 2) хеш-поиск
>
> Зачем? Там дихотомия, все словари отсортированы на этапе
> формирования обновления.

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

← →
Ega23 © (2013-03-12 16:45) [134]

> затем, что так быстрее минимум на порядок

Гм... С этого места по-подробнее, пожалуйста.

← →
Ega23 © (2013-03-12 16:47) [135]

> Хэши самые быстрые, но мы по какой-то причине от них отказались

ЕМНИП, вопрос в хэш-функции был. Ну и на 2 мульёна токенов это при самом хреновом раскладе - 21 операция сравнения.

← →
Rouse_ © (2013-03-12 16:58) [136]

> Ega23 © (12.03.13 16:47) [135]

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

← →
DevilDevil © (2013-03-12 16:58) [137]

> Ega23 © (12.03.13 16:45) [134]
>
> > затем, что так быстрее минимум на порядок
> Гм... С этого места по-подробнее, пожалуйста.

на 2 миллиона элементов дихотомия даёт 11 сравнений
в хеше всего парочка

но в вашем случае:
1) вы сравниваете между собой строки, а не числа, да ещё и вызывая дополнительную функцию - просадка по производительности
2) дихотомия постоянно обращается к разной памяти, что крайне плохо отражается на производительности за счёт кеш-мисс
3) вы используете String, а не PAnsiChar - просадка по выделению/удалению/копированию памяти, преобразования к Wide для Unicode-версий Delphi + оверхед по расходу памяти (пустоты в куче, длинна, счётчик ссылок, ...)

← →
Rouse_ © (2013-03-12 17:09) [138]

> DevilDevil © (12.03.13 16:58) [137]
> 1) вы сравниваете между собой строки, а не числа, да ещё
> и вызывая дополнительную функцию - просадка по производительности
> 2) дихотомия постоянно обращается к разной памяти, что крайне
> плохо отражается на производительности за счёт кеш-мисс
> 3) вы используете String, а не PAnsiChar - просадка по выделению/удалению/копированию
> памяти, преобразования к Wide для Unicode-версий Delphi
> + оверхед по расходу памяти (пустоты в куче, длинна, счётчик
> ссылок, ...)

Во - первый грамотный анализ.
Ты собственно выделил три из пяти основных позиций с которыми мы и боролись.

← →
DevilDevil © (2013-03-12 17:11) [139]

> Rouse_ © (12.03.13 17:09) [138]
офтоп:
четвёртый - это наверное "сложение" id-шников документов
а пятый - работа с файлами

← →
Rouse_ © (2013-03-12 17:18) [140]

четвертый - оверхед токенов (перестраивали набор данных)
пятый - кэширование + быстрая работа с файловым кэшем

← →
Ega23 © (2013-03-12 17:25) [141]

> на 2 миллиона элементов дихотомия даёт 11 сравнений

2^11=2048
Низачот

> вы сравниваете между собой строки, а не числа,

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

> вы используете String, а не PAnsiChar

Не используем мы стринг, всё на ansistring сделано.

> четвёртый - это наверное "сложение" id-шников документов

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

> а пятый - работа с файлами

Собственно, профайлер именно это и показал. Более 90% затрат - файловые операции.

← →
DevilDevil © (2013-03-12 17:29) [142]

> Ega23 © (12.03.13 17:25) [141]
> 2^11=2048> Низачот

да, да, сори :)
тем более !

← →
Rouse_ © (2013-03-12 17:32) [143]

> Собственно, профайлер именно это и показал. Более 90% затрат
> - файловые операции.

Окстись - 97 процентов на файловых операциях, не хочешь? :)
Все остальное летает. Серверную часть будем делать (которая для онлайна) - 64 бита only, 16 гигов склероза, все в память и даже парится не придется.

← →
Rouse_ © (2013-03-12 17:36) [144]

ЗЫ: ЛЕгыч ты уже вообще всю концепцию чтоль забыл?

> > вы сравниваете между собой строки, а не числа,
>
> Ну это да, тут ничего не поделаешь. Но на самом деле это
> не настолько критично, проблемы только в нестрогом соответствии
> на коротких токенах.
>
>
> > вы используете String, а не PAnsiChar
>
> Не используем мы стринг, всё на ansistring сделано.

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

← →
Ega23 © (2013-03-12 17:37) [145]

> Окстись - 97 процентов на файловых операциях, не хочешь? :)

А 97% это меньше 90, да?
Я не помню точное число. Вроде бы из 14.5 секунд 13.7 - на FastGetItemData было. Оно, правда, не точное, под профайлером время довольно субъективно. Но вот процентное отношение - довольно точное.

← →
DevilDevil © (2013-03-12 17:40) [146]

> Ega23 © (12.03.13 17:25) [141]
> Rouse_ © (12.03.13 17:36) [144]

я предлагаю заканчивать флуд
лучше подумайте, кто мне будет помогать создавать быстрейший в мире парсер по XSD :)

← →
Ega23 © (2013-03-12 17:41) [147]

> Строки уже не сравниваются - написан свой аналог на базе
> RAW данных.

Сравниваются. Я спецом глянул. Но это на самом поиске, GetToken

← →
Rouse_ © (2013-03-12 17:48) [148]

> DevilDevil © (12.03.13 17:40) [146]
> > Ega23 © (12.03.13 17:25) [141]
> > Rouse_ © (12.03.13 17:36) [144]
>
> я предлагаю заканчивать флуд
> лучше подумайте, кто мне будет помогать создавать быстрейший
> в мире парсер по XSD :)

Это с XML-ем? Если прислушаешься к озвученной мной и Олегом концепции вчерашней, по поводу совместимости с IXMLNode etc, то некоторое время (но оч маленькое два-три выходных максимум в месяц по шесть часов) мог бы выделить.

Удалено модератором

← →
Джимми Камерманн (2013-03-12 18:54) [154]

Удалено модератором
Примечание: Внимание! В Форуме не принято обсуждение настоящих правил и политики модеpиpования.

Удалено модератором

← →
Джимми Камерманн (2013-03-12 18:59) [156]

Удалено модератором

апдейты на сегодняшний день:

- немного изменил библиотеку и подходы
- отладил работу под x64 (в Delphi). Правда нужно немеряно памяти для стандартного чтения через TStringList в reading_benchmark

Благодаря пользователю Строчкин было найдено одно место, которое существенно тормозило запись файлов
Сейчас:
- баг исправлен
- в writing_benchmark добавлен вариант записи стандартным TextFile с буфером
- методы TCachedBufferWriter.Write() и TCachedBufferReader.Read() частично оптимизированы ассемблером под x86 и x64
- проведено тестирование на запись и чтение данных, разный размер и условия работы. Версия стабильна

скриншоты (Windows7, Delphi6):
http://a.fsdn.com/con/app/proj/cachedbuffers/screenshots/screen_reading.png
http://a.fsdn.com/con/app/proj/cachedbuffers/screenshots/screen_writing.png

таки запись в 464 раза быстрее, чем стандартным TFileStream :)

Ну прям уж в 464. Это ни в коей мере не показывает и не доказывает какой либо ущербности tfilestream. Никому в здравом уме не придет в голову использовать tfilestream в чистом виде так как используется он в тесте. На пару с буферизованным декоратором он отстает совсем не намного уже.

Проект "CachedBuffers" Найти похожие ветки