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

Notes
(0006304) vasketsov (manager) 28-03-2012 17:33	>будет значительное ускорение Насколько значительное? >НЕ МЕДЛЕННЕЕ существующего На участках где все тайлы есть очевидно будет медленнее простого перебора. >чтобы при отсутствии каталога вообще не проверять список файлов в них Если мне не изменяет склероз, там и так есть эта проверка. Если же вопрос про правильный итератор тайлов для карты заполнения - так и надо писать прямым текстом. >Кэширование происходит лишь на время формирования карты заполнения Ну и глупо. Покуда есть кэширование тайлов - ничего не мешает кэшировать и карту заполнения, и сбрасывать участки кэша. В частности если построить карту заполнения и потом сдвинуть карту на один тайл - незачем строить карту заполнения снова с нуля.

(0006306) Dima2000 (developer) 28-03-2012 17:59 edited on: 28-03-2012 18:02	>ничего не мешает кэшировать и карту заполнения Кэширование карты заполнения обсуждать не буду, это вопрос слишком отдельный и мне помнится я где-то видел кучу возражений против этого (типа что файлы в кэш могут подсовываться и другими программами, а тогда кэширование будет вредить). Да и не нужно оно при предлагаемом методе. >Насколько значительное? Точную величину ускорения в процентах посчитать конечно не могу, сильно зависит от наполненности файлами и каталогами отображаемой области. И от распределения файлов по вертикалям и горизонталям. А вот что ускорение будет - это слишком очевидно (для меня), когда отрисовка полупустой карты заполнения +6 от текущего зума на экран 1680*1050 занимает порядка МИНУТЫ - это ВАХ!! >Если же вопрос про правильный итератор тайлов для карты заполнения Итератор тут вообще нипричём, я же в начале (пункт 2) написал, порядок обхода файлов любой, ускорение всё равно будет, может немного разное, совсем немного. >там и так есть эта проверка Так я предлагаю не просто проверку наличия каталогов, которая может и есть, но которая всё равно идёт через ОС и долгая, а кэшировать проверки каталогов во внутренних массивах и заполнять горизонтали и вертикали если в них точно нет ни одного тайла БЕЗ анализа всех тайлов на этой горизонтали/вертикали, только по фпризнаку отсутствия каталога. >На участках где все тайлы есть очевидно будет медленнее простого перебора. Вовсе не очевидно. Лишняя работа при этом - только опрос наличия каталогов. А это тоже можно закэшировать, их мало, или похожим образом, или или хеш-табличкой на сотню вхождений. Но учитывая область применения карты заполнения - просмотр большого куска на маленьком зуме на предмет наличия высокодетальных снимков/тайлов, при большой разнице между текущим зумом и карты заполнения - чаще будет встречаться ситуация отсутствия файла, чем наличия. Для тайлов x16 и более - намного чаще. Что как раз и есть основное применение (на мой взгляд) карты заполнения. Так что частое значительное ускорение при редком небольшом замедлении думаю стоят усилий.

(0006309) vasketsov (manager) 28-03-2012 18:17	>файлы в кэш могут подсовываться и другими программами Да. Но на это у нас есть свои методы мониторинга папок. >проверку наличия каталогов, которая может и есть, но которая всё равно идёт через ОС и долгая Она самая быстрая из теоретически возможных. Быстрее будет только если я на Native NT API перепишу кэширование преобразования DOS-имён в NT-имена файлов. Могу если интересно рассказать, как работает GetFileAttributes. >думаю стоят усилий Безусловно. Но я бы начал с кэширования, что именно кэшировать, как именно сливать кэш, что нюхать через ReadDirectoryChangesW.

(0006310) Dima2000 (developer) 28-03-2012 18:28 edited on: 28-03-2012 18:30	>Она самая быстрая из теоретически возможных. Не спорю, возможно так и есть. Но она точно медленнее трёх обращений во внутренний массив! Причём медленнее в десятки тысяч раз! Любой вызов API на порядки медленнее работы с линейным массивом в памяти из тысячи байтов. Достоинство предлагаемого метода как раз в том что не надо заморачиваться с кэшированием файлов, всё делается чисто на внутренних массивах и лишь на время формирования карты заполнения. Т.е. полностью прозрачно для всей остальной программы кроме самого процесса формирования карты заполнения. И по идее не будет ни на что больше влиять. И модифицировать надо лишь две процедурки, обнуления карты и проверку наличия одного файла, причём, повторю, по идее без побочных эффектов. А ловить обновления каталогов через ОС никто не мешает, это отдельная задача, независимая от данного метода, может работать в пару с ним, да и вообще это совсем другой вопрос. Я говорю лишь об ускорении отрисовки карты заполнения, а не о кэшировании файлов с диска.

(0006311) vasketsov (manager) 28-03-2012 19:00	>Любой вызов API на порядки медленнее работы с линейным массивом в памяти из тысячи байтов. Это бывает не совсем верно. А бывает и совсем неверно. Чтобы это стало понятно - достаточно натянуть примитив синхронизации на этот массив - и вот уже вызовы API и переходы в режим ядра и обратно в полный рост. >точно медленнее трёх обращений во внутренний массив Массив ещё формировать надо и поддерживать. Для 1920x1200 отображается порядка 60 тайлов на экране. Есть оценка среднего количества "лишних" запросов проверки наличия папок, если все без исключения тайлы есть, или тайлов нет, или 50\50, для построения карты заполнения например для зума +4? Без таких оценок очевидно идея останется идеей, ну или придётся делать самому через fork. >Достоинство предлагаемого метода как раз в том что не надо заморачиваться с кэшированием файлов На самом деле с точностью до наоборот. Фактически предлагается кэшировать отсутствие папок (как признака отсутствия тайлов). Идея здравая. Но хотелось бы понять "алгоритмический" выигрыш а некоторых характерных случаях. Просто потому что не факт, что кэшировать надо всё (например можно ли опустить кэширования отсутствия папок с тысячами x или у, и к чему это приведёт).

(0006312) vdemidov (manager) 28-03-2012 19:25	На самом деле, вся ваша бурная дискуссия разбивается тем мелким фактом, что для такой оптимизации нужно полностью переделывать класс тайлохранилища в файловой системе, потому что он сейчас один на все типы именования файлов, их там 5 штук разных, а вы обсуждаете только один из них.

(0006313) vasketsov (manager) 28-03-2012 19:32	Да ладно, чего пугаешь, с остальными ничуть не сложнее будет. Хотя конечно для GoogleMV это особенно актуально )))

(0006314) vdemidov (manager) 28-03-2012 19:57	Проблема не только в том что нужно 5 разных алгоритмов, а в том, что процедура, которая строит карту заполнения не подозревает о этих разных алгоритмах.

(0006315) vasketsov (manager) 28-03-2012 20:09	Пока что для меня проблема в том, что непонятно, кэширование отсутствия чего именно будет оптимальным. Лично я без априорных оценок ничего делать не собираюсь. Другой вопрос, я их сам выполню, ну или кто другой, или наш юный друг всё таки попробует добить тему до логического завершения. Пусть даже и только для "старого" режима построения карты заполнения. Ну а то что алгоритмы разные - так то не сильно страшно. Там уже давно надо что-то делать с получением имени тайла, ибо имя tne формируется просто до неприличия неприлично. Незачем добавлять дефолтное расширение, если его потом заменять на tne. Да и ещё не факт, что нельзя алгоритмы кэширования отсутствия папок к одному свести.

(0006316) vdemidov (manager) 28-03-2012 21:11	Ну, я только за, но, настоятельно прошу, серьезные изменения в архитектуре предварительно обсудить со мной.

(0006318) Dima2000 (developer) 28-03-2012 21:55	Тьфу, да проще написать готовый код и проверить живьём, чем расчитывать статистику что да когда ... Вот, всё практически готовенькое, даже с оптимизацией опроса существования каталогов, каждый из них будет опрошен максимум один раз. Приложил как файл Caching.pas к исходному посту. Разработчики, гляньте глазками нет ли ошибок и вставьте, проверьте скорость и сколько лишней работы делается (уж завести для отладки десяток счетчиков - тривиально). Да хоть по хоткею сделайте вкл/выкл вызова TileExist лишь для родного кэша и визуально сравните в разных режимах! А пока чисто теоретическая прикидка. При расчёте карты заполнения +3 на экране 19201200 влезет максимум (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 (пиксель на тайл) на экране 19201200 влезет максимум (19201+1)(12001+1)+1=2307122 тайлов, ((19201+1+1023)>>10)+1=3 каталогов тысяч по x, 19201+1=1921 каталогов по x, ((12001+1+1023)>>10)+1=3 каталогов тысяч по y, всего 1927 каталогов. Т.е. лишних обращений к ОС за каталогами будет лишь максимум 1927, меньше 0.1% от количества файлов. Т.е. замедление не превысит 0.1%. Для +8 карты заполнения это считаю великолепный результат! При расчёте карты заполнения +13 на экране 19201200 влезет максимум (192032+1)(120032+1)+1=2359395842 тайлов, ((192032+1+1023)>>10)+1=62 каталогов тысяч по x, 192032+1=61441 каталогов по x, ((120032+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, а вот для теста и экспериментов - легко.

(0006320) vasketsov (manager) 29-03-2012 06:15	>И я не такой уж юный друг, да ещё и ваш Вот только пожалуйста не надо обижаться. >написать утилитку для формирования слоя с битовой маской заполнения +8 карты На самом деле всё куда проще и интереснее. Все поддерживаемые сейчас нефайловые кэши могут дать не менее грандиозное ускорение, если сразу строить карту заполнения по всей прямоугольной области. Например для кэша GE вообще говоря не будет большой разницы, сколько +N указано для карты заполнения, там один проход по индексу (больше времени потратится на выделение памяти куском и на запись в "клеточки"). Для кэша над СУБД (пока не опубликован) не всё так идеально и независимо, но тоже куда проще выполнить один select. Пожалуй надо сделать отдельную хотелку для нефайловых кэшей, обкатать её, чтобы карта строилась за один проход, а уже потом эту хотелку натягивать на ту.

(0006323) Dima2000 (developer) 29-03-2012 15:18 edited on: 29-03-2012 15:20	Выкачал в родной кэш в отдельный контейнер TrueCrypt размером 1гиг город Калугу из Спутник.Яндекс, z19 (в SAS), 415 каталогов и в них 17104 файла, общий объём 196624050, тайловый диапазон по x=157364..157570, по y=83635..83822. Для расчёта взят экран разрешением 1600900, с центром в центре тайла 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____5120128801___1474640001__5961807____38916___17104____1075_______-/387 z7____2560114401___368680001___2981007____38916___17104____1050_______-/178 z8____128017201____92180001____1490607____38916___17104____1038_______-/90 z9____64013601_____23050001____745407_____38916___17104____1031_______-/49 z10___32011801_____5765001_____372807_____38916___17104____1028_______330/30 z11___1601901______1442501_____186507_____38916___17104____1027_______85/17 z12___801451_______361251______93357______38916___17104____631________22/9.6 z13___401225_______90225_______46575______38916___17104____402________6.7/4.8 z14___201113_______22713_______22713______22713___15149____202________2.2/2.3 z15___10157________5757________5757_______5757____5647_____102________0.6/0.6 z16___5129_________1479________1479_______1479____1479_____52_________0.2/0.2 z17___2515_________375_________375________375_____375______26_________0.1/0.0 z18___137__________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) - весьма показательна. Значит заморачиваться именно этим вариантом ускорения отрисовки карты - никто не будет. А себе я сам сделаю офлайн пересчёт всех нужных зумов в слои внешней утилиткой. Хотелку закрываем. Ускорить отрисовку очень желательно, но данный метод малоприменим.

(0006329) vasketsov (manager) 29-03-2012 18:39	>Хотелку закрываем Ни в коем случае! Как минимум нельзя забывать, что "локальная" проверка - совсем не то же самое что по сетке с шары. >основные тормоза в SAS вовсе не в опросе файлов, а где-то ещё Разумеется. Потому что "микротайл" надо как минимум перепроецировать и нарисовать. >почему SAS отрисовывает её же почти 20 секунд я не знаю Пока что в хранилищах тайлов нет счётчиков производительности. Так что может быть всё что угодно. >Если ограничиться разумной разницей масштабов +12 При +8 уже "микротайл" в пиксель превращается. Для +12 вообще бессмысленно это всё.

(0006331) Dima2000 (developer) 29-03-2012 19:11	>При +8 уже "микротайл" в пиксель превращается. Для +12 вообще бессмысленно это всё. Да, в пиксель и это прекрасно! И нет, не бессмысленно! Лишь продумать как именно несколько субпикселей объединять в один экранный пиксель чтобы нужная информация не терялась. Наверное делать пиксель прозрачным лишь если все его субпиксели тоже прозрачные. А так, отрыть z4 и отрисовать на нём карту заполнения z16,z17,z18,z19 (на выбор) всего мира - сразу будет видно где есть снимки высокого разрешения! Их ведь мало в сумме по миру. Мегакруть и удобство. Останавливают лишь страшные тормоза - если на +5 уже 20с, то каждый следующий уровень грубо в 4 раза дольше, значит +12 (с z4 рисовать карту заполнения z16) будет часов 5. А с кэшированием - минут 5-10! Почувствуйте разницу. :-) И данный пример не совсем из пальца. Я часто пытаюсь так делать, выкачать большую область к примеру z16 (первого, которого нет сплошняком), посмотреть где есть детальные снимки, выделить область где есть и натравить закачку больших зумов. Это в много раз быстрее тотальной закачки всего мира в z19.

(0006332) vdemidov (manager) 29-03-2012 19:15	Дайте мне пару дней и я закончу принципиально другой способ отрисовки слоев на экран. LockFree, по сути. Скорость отрисовки должна будет увеличиться.

(0006333) vasketsov (manager) 29-03-2012 19:18	>Это в много раз быстрее тотальной закачки всего мира в z19 Даже не смешно. >Лишь продумать как именно несколько субпикселей объединять в один экранный пиксель То есть тормозов реально мало, надо ещё накатить? >сразу будет видно где есть снимки высокого разрешения Всё это делается намного проще. Генерацией вышележащих зумов. Фактически получается хранимая карта заполнения, только визуальная и без карты заполнения.

(0006334) Dima2000 (developer) 29-03-2012 19:29	>Дайте мне пару дней О! Конечно дадим! Сколько нужно! Хорошо что не просите точки опоры, как некоторые несознательные античные личности. :-) Вот у меня экран 1680*1050, московская область есть вся в z16-z18 на яндекс-карте и влезает на экран лишь при z9, это +7..+9 карта заполнения. z15 же есть гораздо дальше. +7 конечно ещё не смертельно, но и z9 слишком подробный для обзора, надо бы хоть z7. Но столько ждать у меня терпения категорически не хватает. В общем, звиняйте если что не так, я пытался помочь ликвидировать неудобное узкое место, насколько я его вижу. :)

(0006335) vasketsov (manager) 29-03-2012 19:46	>Скорость отрисовки должна будет увеличиться Как бы вопрос скорости отрисовки несколько отделён от вопроса кэширования для условно медленных тайловых хранилищ. >я пытался помочь ликвидировать неудобное узкое место, насколько я его вижу Место видишь правильно. Просто сработает это в другом. В хранении тайлов (и не только тайлов, кстати) в сетке. А вообще переход z13___401225_______90225_______46575______38916___17104____402________6.7/4.8 z14___201113_______22713_______22713______22713___15149____202________2.2/2.3 конечно интересный.

(0006336) Dima2000 (developer) 29-03-2012 19:55	Приложил ещё один файл, совершенно рабочая консольная программа на дельфи обхода кэша, именно ей и получены все цифры (с кэшированием). Возможно вам пригодится для тестов. Если кэширование надо отключить, то в функции оставить лишь первую и две последних строки. Просьба первый файл (Caching.pas) убить как глюкавый.

(0006337) Garl (manager) 30-03-2012 04:17	ага на дальней сетевой шаре - вообще устаёшь ждать пока построится карта заполнения даже на +3 :(

(0006349) Dima2000 (developer) 30-03-2012 16:00	Ой, на том же кэше команда "dir /s/b/a-d/o z19\. >\1.1" отрабатывает за 0.4с! И создаёт 550кб файл с 17104 строками об имени (и тайловых координатах!) всех файлов. Распарсить меговый текстовый файл займёт ещё секунду. Т.е. на данном конкретном кэше формирование любой карты заполнения может занимать пару секунд. Хоть для z1. Для более заполненных зумов будет дольше и больше, понятное дело. Но значит ещё есть куда стремиться, опрос наличия каждого тайла возможно вообще не лучшее решение и никакое кэширование его не спасёт. PS. Не понял чем интересен указанный переход? На z14 ускорения ещё нет (все экранные вертикали покрыты тайлами), на z13 уже есть, на экране есть пустые вертикали, для них очень много файлов (фактически половина) не запрашиваются у ОС.

(0006352) vasketsov (manager) 30-03-2012 19:31	>файл с 17104 строками об имени Это потому что пример игрушечный. Был бы кэш гигов на 500 хотя бы... >на z13 уже есть А ну то есть, особенность примера.

(0006355) Dima2000 (developer) 30-03-2012 19:51	>пример игрушечный Ну да. Для сильно разреженного кэша. При большом проценте заполнении/покрытии файл станет огроменным, это очевидно. Суть в другом, что опрос всех тайлов для разреженных кэшей сильно неэффективен, даже с предлагаемым кэшированием отсутствующих каталогов. >А ну то есть, особенность примера. Нет, не особенность, пример хоть и искусственный, специально для повторяемости результатов, но разве кэш всегда забит на 100% на всех зумах? Могу и на весь свой кэш натравить, а толку? Характер поведения не изменится. Пока тайлы карты заполнения не заполняют экран целиком кэширование будет давать ускорение (будет меньше файлов опрашиваться с диска).

(0006359) Dima2000 (developer) 01-04-2012 20:22 edited on: 01-04-2012 20:30	Не давала мне покоя скорость работы "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 показать конечно нельзя, он должен быть 128128, но считать битовую карту это не мешает. :) work - время обработки зума в секундах. Первый результат для примера из №6323, вторая группа для части зумов кэша гугла, третья группа для части кэша яндекса. Везде .jpg снимки, .tne файлов нет в принципе. Вот каталоги пустые в дереве есть, немного, единицы процентов от общего числа. Для примера отобрал зумы с наибольшим временем обработки. Обращаю внимание, что в данном случае обрабатывается не часть кэша, как в прошлой табличке, а ВЕСЬ кэш соответствующего зума! Влазит он на экран, не влазит - не колышит. Карта заполнения формируется всегда для всего мира целиком. Для сравнения первого результата с прошлыми надо использовать по идее что-то среднее между z12 и z13 из прошлой таблицы - по обшему количеству обрабатываемых тайлов. При желании можно и прикрутить ограничивающий прямоугольник по тайловым координатам, будет ещё быстрее, но для внешней утилиты оно мне не нужно, пусть всю карту генерит. Прикидочно получается 3000-4000 файлов в секунду обрабатывается. Ещё, замечено, что времена в десятки секунд легко превращаются в единицы секунд (7с-10с-12с) при повторном запуске утилиты. Похоже винда кэширует дерево каталогов, как и должно быть. Извините, но 2ТБ (и даже 200ГБ) кэша у меня для проверки нет, взял что есть. :) PS. Теперь думаю это тема скорее для форума, чем хотелка... Отрисовку и опросы всего и вся ускорить надо, но другим методом.

(0006360) vdemidov (manager) 01-04-2012 20:45	В общем понятно. Нужно менять принцип построения. Мне давно ненравилось, что тайлохранилище само занимается еще и рисованием. Так что будет что-то в таком духе: 1. У тайлохранилища будет метод "Получить_Инфу_о_прямоугольнике_тайлов" 2. Полученную от тайлохранилища инфу обрабатываем и рисуем картинку

(0006365) vasketsov (manager) 02-04-2012 14:13 edited on: 02-04-2012 14:15	>Нужно менять принцип построения Ты этим типа займёшься? Я сегодя залью уже правки по смежной теме для нефайловых хранилищ. Там в общем-то так и сделано. Ну разве что кроме того прискорбного факта, что по-прежнему всё зовётся изнутри TTileStorageAbstract.LoadFillingMap и "тайлохранилище само занимается еще и рисованием". Разумеется если вынести это "наружу", сразу будет сильно красивше. Можно будет звать сразу по всему прямоугольнику (сейчас только по одному тайлу текущего зума, эту особенность TTileStorageAbstract.LoadFillingMap я не трогаю, разумеется скорости это тоже не прибавляет). Буфер для карты можно будет один раз выделить, и потом только чистить, а не потайлово выделять. По сему охота понять, ждать тебя, или ты потом будешь выковыривать LoadFillingMap из TTileStorage*?

(0006367) vdemidov (manager) 02-04-2012 16:48	Думаю займусь в ближайшее время.

(0006370) vasketsov (manager) 02-04-2012 18:09	Кстати, дабы не ждать построения всей карты заполнения целиком по одной битовой маске, можно поделить экран на вертикальные полоски по одному тайлу шириной, соответственно диапазон будет по x всегда 1. Автоматически получаем возможность быстрой проверки наличия x. Ведь тайлы для разных x лежат всегда в разных папках.

(0006371) vdemidov (manager) 02-04-2012 18:29	Ага. Особенно для qrts тайлов. Нет. Запросы будут целиком на весь экран для малой разницы зумов или так как и сейчас по тайлам для большей разницы зумов.

(0006372) vasketsov (manager) 02-04-2012 18:47 edited on: 02-04-2012 18:47	>Особенно для qrts тайлов Да, нафига? >или так как и сейчас по тайлам для большей разницы зумов А чем так мешает промежуточный варант?

(0006373) vdemidov (manager) 02-04-2012 19:37	Промежуточный вариант плох тем, что имеет смысл только для одного конкретного типа кэша.

(0006374) vasketsov (manager) 02-04-2012 20:35 edited on: 03-04-2012 06:46	А мне казалось, что как раз для всех кроме qrts. А для qrst надо максимальными целыми квадратиками области на экране делать, чтобы по ним запускать enum файлов по маске. Для GE (и для хранилища над СУБД) вообще без разницы, сколько +N ставить для карты заполнения, скорость построения вообще от этого не зависит (ну разве что памяти больше выделить и переслать), так как там ровно один проход по индексу. Как ни крути - хранилище лучше всего знает, какими кусками строить карту заполнения.

(0006375) vasketsov (manager) 03-04-2012 11:36	В DLL кэша для GC заменил function XYZtoXYZPath(const APoint: TPoint; const AZoom: Byte): String; begin Result := 'z' + IntToStr((AZoom+1)) + PathDelim + IntTostr(APoint.x shr 10) + PathDelim + 'x' + IntToStr(APoint.x) + PathDelim + IntTostr(APoint.y shr 10) + PathDelim; end; на procedure XYZtoXYZPath2(const APoint: TPoint; const AZoom: Byte; out ARelParts: TRelativeTilePath); begin ARelParts.FirstPart := 'z' + IntToStr((AZoom+1)) + PathDelim + IntTostr(APoint.x shr 10) + PathDelim + 'x' + IntToStr(APoint.x) + PathDelim; ARelParts.SecondPart := IntTostr(APoint.y shr 10) + PathDelim; end; С двумя проверками DirectoryExists (первая - для Base + FirstPart, если прошла и есть SecondPart - добавляем его и снова проверяем) - работает по кэшу _ощутимо_ быстрее. Это при наличии версий и дат. Надо что-то похожее и для обычных файловых кэшей сделать. Как я уже писал, быстрее DirectoryExists ничего нет из доступного, её отлично кэширует сама винда.

(0006376) Dima2000 (developer) 03-04-2012 14:59	Ещё один шаг и придёте к изначально предложенному методу, запоминать каких каталогов нет и больше про их внутренности не спрашивать ОС, а сразу возвращать false. :)

(0006377) vasketsov (manager) 03-04-2012 15:39	Я уже вроде попытался популярно объяснить, что пользы от этого будет мало. Покуда над кэшем будет висеть примитив синхронизации (доступ из кучи потоков, некоторые вносят данные в кэш, отдельный сборщик мусора для сливания "старого" кэша), переключения в ядро не избежать. Минимум дважды даже при реализации примитива через KeyedEvent. И тут на арену выходит простой сермяжный кэш ФС, который всё это и так имеет, всё это и так кэширует, да ещё и за один вызов ядра ОС (функция DirectoryExists не открывает никаких HANDLE внутри).

(0006378) Dima2000 (developer) 03-04-2012 18:52	Не буду спорить, Вам разумеется виднее. Хотя и не согласен. На интервале времени построения карты заполнения можно априори считать состояние кэша стабильным и не изменяемым, оборачивать в синхронизацию лишь реально уходящие в ОС вызовы, которые и экономить. Я про это говорил с самого начала, что кэширование в ФС не спасает при миллионе запросов к ОС. Впрочем наверняка я чего-то не понимаю.

(0010248) vdemidov (manager) 29-12-2012 10:31	Нужно оптимизировать GetTileRectInfo причем для каждого типа файлового кэша по своему.

Users who viewed this issue
User List	Anonymous (3659x), hrucker (1x)
Total Views	3660
Last View	21-11-2024 13:11

Issue History
Date Modified	Username	Field	Change
28-03-2012 16:32	Dima2000	New Issue
28-03-2012 16:36	Dima2000	Tag Attached: карта заполнения
28-03-2012 16:36	Dima2000	Tag Attached: отображение
28-03-2012 16:36	Dima2000	Tag Attached: перерисовка экрана
28-03-2012 16:36	Dima2000	Tag Attached: скорость
28-03-2012 16:36	Dima2000	Tag Attached: экран
28-03-2012 17:33	vasketsov	Note Added: 0006304
28-03-2012 17:59	Dima2000	Note Added: 0006306
28-03-2012 18:02	Dima2000	Note Edited: 0006306	View Revisions
28-03-2012 18:17	vasketsov	Note Added: 0006309
28-03-2012 18:28	Dima2000	Note Added: 0006310
28-03-2012 18:30	Dima2000	Note Edited: 0006310	View Revisions
28-03-2012 19:00	vasketsov	Note Added: 0006311
28-03-2012 19:25	vdemidov	Note Added: 0006312
28-03-2012 19:32	vasketsov	Note Added: 0006313
28-03-2012 19:57	vdemidov	Note Added: 0006314
28-03-2012 20:09	vasketsov	Note Added: 0006315
28-03-2012 21:11	vdemidov	Note Added: 0006316
28-03-2012 21:54	Dima2000	File Added: Caching.pas
28-03-2012 21:55	Dima2000	Note Added: 0006318
29-03-2012 06:15	vasketsov	Note Added: 0006320
29-03-2012 06:36	vasketsov	Relationship added	related to 0001253
29-03-2012 15:18	Dima2000	Note Added: 0006323
29-03-2012 15:20	Dima2000	Note Edited: 0006323	View Revisions
29-03-2012 18:39	vasketsov	Note Added: 0006329
29-03-2012 19:11	Dima2000	Note Added: 0006331
29-03-2012 19:15	vdemidov	Note Added: 0006332
29-03-2012 19:18	vasketsov	Note Added: 0006333
29-03-2012 19:29	Dima2000	Note Added: 0006334
29-03-2012 19:46	vasketsov	Note Added: 0006335
29-03-2012 19:54	Dima2000	File Added: CachingTest.public.dpr
29-03-2012 19:55	Dima2000	Note Added: 0006336
29-03-2012 20:02	vasketsov	File Deleted: Caching.pas
30-03-2012 04:17	Garl	Note Added: 0006337
30-03-2012 16:00	Dima2000	Note Added: 0006349
30-03-2012 19:31	vasketsov	Note Added: 0006352
30-03-2012 19:51	Dima2000	Note Added: 0006355
01-04-2012 20:22	Dima2000	Note Added: 0006359
01-04-2012 20:24	Dima2000	Note Edited: 0006359	View Revisions
01-04-2012 20:30	Dima2000	Note Edited: 0006359	View Revisions
01-04-2012 20:45	vdemidov	Note Added: 0006360
02-04-2012 14:13	vasketsov	Note Added: 0006365
02-04-2012 14:15	vasketsov	Note Edited: 0006365	View Revisions
02-04-2012 16:48	vdemidov	Note Added: 0006367
02-04-2012 18:09	vasketsov	Note Added: 0006370
02-04-2012 18:29	vdemidov	Note Added: 0006371
02-04-2012 18:47	vasketsov	Note Added: 0006372
02-04-2012 18:47	vasketsov	Note Edited: 0006372	View Revisions
02-04-2012 19:37	vdemidov	Note Added: 0006373
02-04-2012 20:35	vasketsov	Note Added: 0006374
03-04-2012 06:46	vasketsov	Note Edited: 0006374	View Revisions
03-04-2012 11:36	vasketsov	Note Added: 0006375
03-04-2012 14:59	Dima2000	Note Added: 0006376
03-04-2012 15:39	vasketsov	Note Added: 0006377
03-04-2012 18:52	Dima2000	Note Added: 0006378
09-08-2012 06:55	vdemidov	Product Version	.Nightly => 110418
29-12-2012 10:31	vdemidov	Note Added: 0010248
29-12-2012 10:31	vdemidov	Status	new => resolved
29-12-2012 10:31	vdemidov	Resolution	open => won't fix
29-12-2012 10:31	vdemidov	Assigned To	=> vdemidov
29-12-2012 10:31	vdemidov	Status	resolved => closed

SASGIS