0001248: Ускорение отрисовки карты заполнения

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

>Насколько значительное?
Точную величину ускорения в процентах посчитать конечно не могу, сильно зависит от наполненности файлами и каталогами отображаемой области. И от распределения файлов по вертикалям и горизонталям.
А вот что ускорение будет - это слишком очевидно (для меня), когда отрисовка полупустой карты заполнения +6 от текущего зума на экран 1680*1050 занимает порядка МИНУТЫ - это ВАХ!!

>Если же вопрос про правильный итератор тайлов для карты заполнения
Итератор тут вообще нипричём, я же в начале (пункт 2) написал, порядок обхода файлов любой, ускорение всё равно будет, может немного разное, совсем немного.

>там и так есть эта проверка
Так я предлагаю не просто проверку наличия каталогов, которая может и есть, но которая всё равно идёт через ОС и долгая, а кэшировать проверки каталогов во внутренних массивах и заполнять горизонтали и вертикали если в них точно нет ни одного тайла БЕЗ анализа всех тайлов на этой горизонтали/вертикали, только по фпризнаку отсутствия каталога.

>На участках где все тайлы есть очевидно будет медленнее простого перебора.
Вовсе не очевидно. Лишняя работа при этом - только опрос наличия каталогов. А это тоже можно закэшировать, их мало, или похожим образом, или или хеш-табличкой на сотню вхождений. Но учитывая область применения карты заполнения - просмотр большого куска на маленьком зуме на предмет наличия высокодетальных снимков/тайлов, при большой разнице между текущим зумом и карты заполнения - чаще будет встречаться ситуация отсутствия файла, чем наличия. Для тайлов x16 и более - намного чаще. Что как раз и есть основное применение (на мой взгляд) карты заполнения.
Так что частое значительное ускорение при редком небольшом замедлении думаю стоят усилий.

>Любой вызов API на порядки медленнее работы с линейным массивом в памяти из тысячи байтов.
Это бывает не совсем верно. А бывает и совсем неверно. Чтобы это стало понятно - достаточно натянуть примитив синхронизации на этот массив - и вот уже вызовы API и переходы в режим ядра и обратно в полный рост.

>точно медленнее трёх обращений во внутренний массив
Массив ещё формировать надо и поддерживать. Для 1920x1200 отображается порядка 60 тайлов на экране. Есть оценка среднего количества "лишних" запросов проверки наличия папок, если все без исключения тайлы есть, или тайлов нет, или 50\50, для построения карты заполнения например для зума +4? Без таких оценок очевидно идея останется идеей, ну или придётся делать самому через fork.

>Достоинство предлагаемого метода как раз в том что не надо заморачиваться с кэшированием файлов
На самом деле с точностью до наоборот. Фактически предлагается кэшировать отсутствие папок (как признака отсутствия тайлов). Идея здравая. Но хотелось бы понять "алгоритмический" выигрыш а некоторых характерных случаях. Просто потому что не факт, что кэшировать надо всё (например можно ли опустить кэширования отсутствия папок с тысячами x или у, и к чему это приведёт).

Тьфу, да проще написать готовый код и проверить живьём, чем расчитывать статистику что да когда ...
Вот, всё практически готовенькое, даже с оптимизацией опроса существования каталогов, каждый из них будет опрошен максимум один раз. Приложил как файл Caching.pas к исходному посту.
Разработчики, гляньте глазками нет ли ошибок и вставьте, проверьте скорость и сколько лишней работы делается (уж завести для отладки десяток счетчиков - тривиально). Да хоть по хоткею сделайте вкл/выкл вызова TileExist лишь для родного кэша и визуально сравните в разных режимах! А пока чисто теоретическая прикидка.

При расчёте карты заполнения +3 на экране 1920*1200 влезет максимум (1920/32+1)*(1200/32+1)+1=2380 тайлов, ((1920/32+1+1023)>>10)+1=2 каталогов тысяч по x, 1920/32+1=61 каталогов по x, ((1200/32+1+1023)>>10)+1=2 каталогов тысяч по y, всего 65 каталогов. Т.е. лишних обращений к ОС за каталогами будет лишь максимум 65, меньше 3% от количества файлов. Т.е. замедление не превысит 3%. Столько глазами не видно.

При расчёте карты заполнения +8 (пиксель на тайл) на экране 1920*1200 влезет максимум (1920*1+1)*(1200*1+1)+1=2307122 тайлов, ((1920*1+1+1023)>>10)+1=3 каталогов тысяч по x, 1920*1+1=1921 каталогов по x, ((1200*1+1+1023)>>10)+1=3 каталогов тысяч по y, всего 1927 каталогов. Т.е. лишних обращений к ОС за каталогами будет лишь максимум 1927, меньше 0.1% от количества файлов. Т.е. замедление не превысит 0.1%. Для +8 карты заполнения это считаю великолепный результат!

При расчёте карты заполнения +13 на экране 1920*1200 влезет максимум (1920*32+1)*(1200*32+1)+1=2359395842 тайлов, ((1920*32+1+1023)>>10)+1=62 каталогов тысяч по x, 1920*32+1=61441 каталогов по x, ((1200*32+1+1023)>>10)+1=39 каталогов тысяч по y, всего 61542 каталогов. Т.е. лишних обращений к ОС за каталогами будет лишь максимум 61542, меньше 0.003% от количества файлов. Т.е. замедление не превысит 0.003%. Для +13 карты заполнения - вообще грандиозно! Более 2 млрд файлов, а лишней работы лишь 60к.

Считать лишнюю работу по работе с массивами в памяти и сколько времени займёт первый if - imho глупость, это на несколько порядков быстрее обращений к ОС за файлом или каталогом.
В самом худшем случае процедура будет делать указанное количество обращений к ОС за каталогом, и кучу внутренних операций в if и массивах. На фоне опроса наличия тысяч файлов - это бесплатно! Т.е. реального замедления работы не будет никогда!! Разве что в случае +0..+2 карт заполнения, а там общее количество работы мало и визуально замедления тоже не будет.

Вы меня конечно извините, но ради ускорения на порядок (а то и два) даже не в 100% случаев и отсутствии замедления в любых режимах - можно и сделать разные процедуры для каждого кэша. И даже завести десяток глобальных переменных для переключения работы этих процедур. Сейчас пользоваться картой при +5 и выше - мучение. Да, можно, но сидеть и ждать минуты пока всё отрисуется ... :'(
И я не такой уж юный друг, да ещё и ваш, более 15 лет работы программистом.

PS. Эх, чувствую быстрее будет обернуть процедурку в консольную обёртку и натравить на реальный кэш в разных вариантах, чем уговаривать проверить. Уже давно хочу написать утилитку для формирования слоя с битовой маской заполнения +8 карты, да всё никак. Останавливает сложность прикручивания к SAS, а вот для теста и экспериментов - легко.

Выкачал в родной кэш в отдельный контейнер TrueCrypt размером 1гиг город Калугу из Спутник.Яндекс, z19 (в SAS), 415 каталогов и в них 17104 файла, общий объём 196624050, тайловый диапазон по x=157364..157570, по y=83635..83822.
Для расчёта взят экран разрешением 1600*900, с центром в центре тайла x=157467, y=83728, реальные координаты N54°32'11.33", E36°14'55.33", ссылка в яндекс http://maps.yandex.ru/?ll=36.256253%2C54.536979&spn=0.460052%2C0.160710&z=12&l=sat , всё что коричневым - всё есть в разрешении z19.
Отображение конечно не в SAS, всё считалось отдельной утилиткой, в нескольких вариантах (с разным обходом, с/без кэширования), сама карта заполнения физически не формировалась, опрашивался лишь флаг наличия файла (и находился ограничивающий прямоугольник). Процедура опроса при этом полностью функциональна. В рамках теста скорости опроса файлов этого достаточно.
-------------------------------------------------------------------------------------
Зум___Размеры_______Тайлов______Проверено__Box_____Найдено__Каталогов__Время_SAS/кэш
z6____51201*28801___1474640001__5961807____38916___17104____1075_______-/387
z7____25601*14401___368680001___2981007____38916___17104____1050_______-/178
z8____12801*7201____92180001____1490607____38916___17104____1038_______-/90
z9____6401*3601_____23050001____745407_____38916___17104____1031_______-/49
z10___3201*1801_____5765001_____372807_____38916___17104____1028_______330/30
z11___1601*901______1442501_____186507_____38916___17104____1027_______85/17
z12___801*451_______361251______93357______38916___17104____631________22/9.6
z13___401*225_______90225_______46575______38916___17104____402________6.7/4.8
z14___201*113_______22713_______22713______22713___15149____202________2.2/2.3
z15___101*57________5757________5757_______5757____5647_____102________0.6/0.6
z16___51*29_________1479________1479_______1479____1479_____52_________0.2/0.2
z17___25*15_________375_________375________375_____375______26_________0.1/0.0
z18___13*7__________91__________91_________91______91_______14_________0.0/0.0
z19___7*3___________21__________21_________21______21_______8__________0.0/0.0
-------------------------------------------------------------------------------------
Пояснения к табличке.
Зум - на каком зуме показывать карту заполнения z19-го.
Размеры - это количество тайлов по горизонтали и вертикали, покрывающее экран.
Тайлов - общее количество тайлов, покрывающих экран. Они все проверяются на наличие на диске.
Проверено - сколько реально тайлов проверила моя процедура (сколько вызовов FileExists в дельфи). В отличии от проверки SAS-ом предыдущего количества. Разница "Проверено-Тайлов" и есть величина оптимизации от кэширования.
Box - это количество тайлов, внутри ограничивающего город по z19 прямоугольника, влезающие на экран. На z13 прямоугольник влезает на экран целиком. По идее за его пределами файлов точно нет и проверять смысла мало. Если б ещё знать все ограничивающие прямоугольники для всех масштабов и всех городов ...
Найдено - сколько файлов найдено. Если их меньше 17104, значит некоторые тайлы оказались за пределами экрана.
Каталогов - сколько разных каталогов проверила процедура. Это сколько раз была вызвана DirectoryExists в дельфи. Фактически это величина вреда от кэширования.
Время - первое сколько времени выполнялась полная проверка всех тайлов покрывающих экран (аналогично SAS), второе сколько времени заняла проверка с использованием кэширования. В секундах.

Замечания по табличке.
Зум z9 и меньшие терпения не хватило запускать полный перебор, уже z10 больше 5-ти минут шуршит, а z9 будет минут 20.
До z13 включительно город весь влезает в экран, потому найдены все файлы.
Начиная с z14 город целиком на экран не влезает, потому уменьшается количество найденных файлов. И город перекрывает все вертикали экрана, потому "Проверено=Тайлов" - кэширование перестаёт помогать и начинает лишь вредить. На z14 вред равен 202 лишних обращений к ОС с вопросом есть ли на диске каталог. При этом запрашивалось и 22713 файлов. Вред составил 0.9%.
При z14 и z15 на экране ещё есть пустые тайлы, потому найдено файлов меньше чем Box и чем их вообще есть.
Начиная с z16 город заполняет весь экран и пустых кусочков уже нет. И начиная с этого зума точность измерения времени никакая, я не стал заморачиваться с микросекундами, всё равно оно сильно плавает на этих масштабах.

Выводы.
1. Метод вполне рабочий. Ошибок не продуцирует. Разницы в результатах работы с кэшированием и без не выявлено (кроме времени работы).
2. Хм, при карте заполнения аж +6 всего 7с обработка сотни тысяч файлов? Похоже я погорячился когда говорил про минуты ожидания в SAS-е ... Или не погорячился, а основные тормоза вовсе не в опросе наличия файлов (см. следующий вывод).
3. На z14 (т.е. карта заполнения +5) проверка всех 22к тайлов занимает чуть больше двух секунд, почему SAS отрисовывает её же почти 20 секунд я не знаю. Специально скопировал чистый SAS в папку с сохранённым кэшем и замерил секундомером.
4. При разнице в зуме меньше 7 эффективность кэширования невелика.
5. Но весьма мал и вред от кэширования, до z13 он какие-то доли процента, а потом общее время становится почти нулевым, а значит и вред не вредит. :-)
6. Наличие больших пустых областей (и главное отсутствие для них каталогов!) слабо увеличивает вред от кэширования и время работы - зависимость явно не квадратичная, как для полного перебора, а близка скорее к линейной.
7. На лету можно строить лишь +5 (ну +6) карту, остальное слишком медленно даже с кэшированием. Жаль, я так хотел +8, пиксель на тайл ...
8. Для работы кэширования на любых зумах вплоть до z24 достаточно массивов на 64кб и на 8М, суммарно 8.1 мегабайтов. Не мало, но и не много. Если ограничиться разумной разницей масштабов +12, то хватит и 32кб памяти. Но немного усложнится исходник функции (добавятся десяток вычитаний в формулы).
9. Сюда не приводил, но сам проверил, зависимость от порядка перебора между худшим и лучшим случаем (x потом y или наоборот) менее 3%. Делать другие итераторы пока лень, не думаю что будет заметная разница.
10. А в прикреплёной процедуре есть логическая ошибка, проверку по y надо вообще выкинуть, каталоги по y не уникальны однако. Результаты выше уже по правильной процедуре.

Итог.
Практическая польза от внедрения данного варианта кэширования спорна. Надежды не оправдались. На малых разницах зума и так всё быстро, а на больших и кэширование работает не мгновенно, десятки секунд уже не комфортно. Хотя по сравнению с реализованным сейчас выигрыш и ускорение несомненны, уже при +9 карте заполнения выигрыш больше порядка. Вред же от кэширования никогда не становится визуально заметным.
Вот только оказывается основные тормоза в SAS вовсе не в опросе файлов, а где-то ещё. Разница на порядок в скорости работы SAS и тупого перебора всех файлов в одинаковых условиях (см. выше вывод 3) - весьма показательна.
Значит заморачиваться именно этим вариантом ускорения отрисовки карты - никто не будет. А себе я сам сделаю офлайн пересчёт всех нужных зумов в слои внешней утилиткой.
Хотелку закрываем. Ускорить отрисовку очень желательно, но данный метод малоприменим.

Не давала мне покоя скорость работы "dir" на слабо заполненных зумах, таки переделал обход тайлов не по порядку, а обход только реально существующих каталогов, не тайлов, да ещё и с кэшированием проверок по типу вышеописанного. Сначала по наличию каталогов формируется битовая карта (1к*8к бит), потом её не пустые участки рассовываются по выходным тайлам. И вот что вышло:
-------------------------------------------------------------------------------------
Zoom______x,y__________full____dirs____find__________size______filled____tiles____work
YaK\z19___0..262143___2^36____207____17104____196624050_____0.000025%______4____0.75s

G\z8______0..127______2^14____128____16384_____55067382___100.000000%______1____4.03s
G\z15_____0..16383____2^28___5459___117146___1151197172_____0.043640%_____57___40.33s
G\z16_____0..32767____2^30____646_____6285_____78189536_____0.000585%_____16____6.86s
G\z17_____0..65535____2^32___1566____65476___1213387994_____0.001524%_____20___25.52s
G\z18_____0..131071___2^34___3079___266240___3628973926_____0.001550%_____31___72.30s

Ya\z15____0..16383____2^28____478_____9703____124332249_____0.003615%_____17____5.47s
Ya\z17____0..65535____2^32____522____20657____323287159_____0.000481%_____12____8.59s
Ya\z18____0..131071___2^34____576____47053____682029595_____0.000274%_____17___15.89s
-------------------------------------------------------------------------------------
Пояснения.
x,y - это диапазон координат, обрабатывается весь мир, так что по x и y он одинаковый и максимальный.
full - сколько максимум тайлов надо обработать (на весь мир).
dirs - в отличии от ранее, это сколько найдено непустых каталогов. Как раньше, сколько проверялось - не выводил, предыдущая практика и специальная проверка показала что тормоза не в этом.
find - сколько в них найдено файлов (тайлов). Сами файлы при этом не читаются, опрашивается лишь их наличие, как и ранее.
size - общий размер найденных файлов.
filled - сколько площади мира покрыто тайлами. Просто процент отношения find к full. Чисто для справки.
tiles - сколько тайлов сгенерировано для карты заполнения. Пустые тайлы разумеется не генерятся. Для z9 и менее их всегда один (или 0). Тайл с z8 показать конечно нельзя, он должен быть 128*128, но считать битовую карту это не мешает. :)
work - время обработки зума в секундах.

Первый результат для примера из №6323, вторая группа для части зумов кэша гугла, третья группа для части кэша яндекса. Везде *.jpg снимки, *.tne файлов нет в принципе. Вот каталоги пустые в дереве есть, немного, единицы процентов от общего числа. Для примера отобрал зумы с наибольшим временем обработки.
Обращаю внимание, что в данном случае обрабатывается не часть кэша, как в прошлой табличке, а ВЕСЬ кэш соответствующего зума! Влазит он на экран, не влазит - не колышит. Карта заполнения формируется всегда для всего мира целиком. Для сравнения первого результата с прошлыми надо использовать по идее что-то среднее между z12 и z13 из прошлой таблицы - по обшему количеству обрабатываемых тайлов.
При желании можно и прикрутить ограничивающий прямоугольник по тайловым координатам, будет ещё быстрее, но для внешней утилиты оно мне не нужно, пусть всю карту генерит.
Прикидочно получается 3000-4000 файлов в секунду обрабатывается.
Ещё, замечено, что времена в десятки секунд легко превращаются в единицы секунд (7с-10с-12с) при повторном запуске утилиты. Похоже винда кэширует дерево каталогов, как и должно быть.
Извините, но 2ТБ (и даже 200ГБ) кэша у меня для проверки нет, взял что есть. :)

PS. Теперь думаю это тема скорее для форума, чем хотелка... Отрисовку и опросы всего и вся ускорить надо, но другим методом.