0002076: Добавить в наборы векторных объектов хэш входящих в них объектов и операцию проверки равенства

Notes
(0012476) vasketsov (manager) 18-08-2013 19:48 edited on: 18-08-2013 20:05	По моим данным, отображение меток заметно просело после натягивания хэша на имя и описание. На референсном полигоне примерно 4200 полигонов и путей DrawSubset, GetMarks и прочие (отфильтруйся примерно по Total >= 0.020 - они и останутся) при включении меток выросли примерно на 5-10% (относительно времени, когда хэш натягивался только на геометрию). upd. при сборке в debug разница ещё больше. Я к тому, что тебе реально надо на имена и описания хэш натягивать?

(0012477) vdemidov (manager) 18-08-2013 20:24	Вряд ли тут дело именно в вычислении хэшей для строк. У меня на нетбуке вычисление хэша строк длиннее 32 символов занимает (8 мкс) практически столько же, сколько добавление хэша к уже существующему (7 мкс)

(0012478) vasketsov (manager) 18-08-2013 20:57	Внезапно подумалось. А может для строк (точнее, для текста) хэш (ну то есть функция, конечно) может быть более оптимален, если будет отличен от хэша для бинарных данных?

(0012479) vdemidov (manager) 18-08-2013 21:11	В смысле? Другую хэш функцию использовать? Раскрой мысль. Меня сейчас больше всего смущает время на добавление хэша к хэшу. Сильно хочется заменить на простой ксор.

(0012480) vasketsov (manager) 18-08-2013 21:32	>Раскрой мысль Я к тому, что по человеческому тексту может быть есть более оптимальная функция. Скажем, верхний int вообще может быть оптимальнее брать просто как длину строки. >Вряд ли тут дело именно в вычислении хэшей для строк Очень даже запросто. Подробностей не знаю, но например, если размер буфера кратен 32 байта - всё отстреливает быстро, как только нет - хвост считается отдельно и медленнее. Ну а для строк соответственно длина произвольная и чаще всего некратная. По крайней мере я просто сравниваю две ревизии 705 и 708 у себя. Разница ощутима. >время на добавление хэша к хэшу А меня смущает немного другая мулька. То что ты прикрутил хэш к геометрии - резко ускорило отображение (всё на том же моём референсном скрине и кучей меток проверял). А вот дальше IsSame или что там для меток - хэш не вкорячил. Соответственно самостоятельной проверки IsSame нет и для картинок, а хэш тоже есть. Так может оставить 2 хэша (в смысле 2 поля), один на геометрию, другой на остальное? Как минимум один твой "xor" пропадает, сравнивать два не сильно сложнее чем один. Даже если и не пропадает - линковка геометрии и остального выполнится последним шагом, и фактически будет отдельный хэш на геометрию и на остальное. Сменили геометрию - не пересчитываем остальное, и наоборот. А вообще там же если 0 - геометрия сравнивается по-старому. Вот наоборот бы: если 0 - строки по-старому, и тогда можно было бы фейковую функцию для строк сделать, пусть SameText работает. Хотя если строить хэш по списку объектов, то никаких фейковых функций нельзя использовать. Но я пока не очень понял смысл хэша на весь список.

(0012481) vasketsov (manager) 18-08-2013 22:05 edited on: 18-08-2013 22:16	Вон их пачка, не считая СRC: http://en.wikipedia.org/wiki/List_of_hash_functions#Non-cryptographic_hash_functions А вообще как вариант - для координат CH64, для остального CH32. Чтобы было понятнее: в конструктор метки падает геометрия. Уже с хэшем. Его оставляем как есть, а хэш метки считаем без его учёта (минус один "xor"). Сравнение меток - сравнение двух хэшей, первого с первым, второго - со вторым. Даже если надо собирать хэш по списку - собираем отдельно геометрию, отдельно остальное. Соответственно функции могут быть разные.

(0012486) vdemidov (manager) 19-08-2013 05:13	> То что ты прикрутил хэш к геометрии - резко ускорило отображение (всё на том же моём референсном скрине и кучей меток проверял) Ты уверен? Странно, я такого эффекта сразу не ожидал. Основная идея, кроме сравнения была в возможности потом добавить кэширование промежуточных результатов с использованием хэш-таблиц (чего пока нет). А сравнение геометрий там вроде не так уж и часто применяется. >А вот дальше IsSame или что там для меток - хэш не вкорячил. Ну не все сразу. Просто не успел еще. И еще один хэш для векторного объекта нужен, что бы потом хэш для набора объектов считать и пореже на коллизии натыкаться. Но нужно подумать на эту тему.

(0012487) vasketsov (manager) 19-08-2013 07:41	>Ты уверен? Да. Между моей последней ревизией с моими appearance и ревизией 705 (хэш по геометрии) резко упали значения total. ProjPoly с 13000 до 3700 примерно. BGDraw c 1.4 до 0.8. GetMarks с 0.2 до 0.1. Воспроизводится с небольшими отлонениями в значениях. Естественно, это может быть специфика данных (куча полигонов, немного длиннющих треков), особеность проца и т.п., и у тебя может быть и по другому. А может просто Луна другой стороной повернулась или напруга в сети подскочила ))) >IsSame или что там для меток >Просто не успел еще Ну вот я к тому, что заодно и подумай, по мне так проще в разные фабрики даже возможно отдать разные функции, и в той же метке сравнивать в IsSame без ненужного вычисления хэша от хэшей, а просто две пары value по очереди. >хэш для набора объектов считать и пореже на коллизии натыкаться А где ты предполагаешь считать хэш для списка векторов? Вернее, зачем? Типа, для тех же меток, собрали новый subset, а он как старый, не обновляем метки на экране? )))) Так тупо же собирать новый subset только для этого, имея статичный старый ))) Да ещё может и от порядка элементов хэш зависит - тогда вообще пересортировка будет ломать хэш.

(0012488) vdemidov (manager) 19-08-2013 08:01	> Естественно, это может быть специфика данных (куча полигонов, немного длиннющих треков), особеность проца и т.п., и у тебя может быть и по другому. А может просто Луна другой стороной повернулась или напруга в сети подскочила ))) Так может там дело в переделке векторного слоя? Вроде оно могло уменьшить число перерисовок? >Ну вот я к тому, что заодно и подумай, по мне так проще в разные фабрики даже возможно отдать разные функции, и в той же метке сравнивать в IsSame без ненужного вычисления хэша от хэшей, а просто две пары value по очереди. Посмотрим. Но вряд ли. Хочется иметь один хэш для всего объекта. >Вернее, зачем? Типа, для тех же меток, собрали новый subset, а он как старый, не обновляем метки на экране? Именно. Получили из базы меток новый сабсет после изменения в базе или сдвига экрана и если они одинаковые, то просто не пересчитываем спроецированное и не рисуем заново тайлы. На самом создании сабсета может и не сэкономим, зато на всех последующих операциях очень даже.

(0012489) vasketsov (manager) 19-08-2013 08:59	>может там дело в переделке векторного слоя? А как оно может сыграть при включении меток (после отключения с сброса счётчиков)? Кроме того, я специально проверял - после переделки было небольшое (несколько процентов, меньше 5) замедление (именно на включении меток проверяю, не на перемещении и не на зуме). >Хочется иметь один хэш для всего объекта Это в разы увеличивает вероятность коллизий. Причём, если отдельный хэшик для appearance в случае случайной коллизии просто приведёт к тому, что цвет у объекта будет другой, то коллизия по геометрии будет совсем неприятной. А если один хэш - вообще может объект не отобразится. Да и кроме того идея технически небезупречна: проще сравнить отдельно (a1,b1) и (a2,b2), и возможно вывалиться уже на сравнении a1 и a2, чем сравнивать f(a1,b1) и f(a2,b2). Не говоря уже о том, что размер a и b может быть разным. Не говоря уже о том, что расчёт a и b может требоваться в разное время, и глупо считать b и f(a,b) только потому что потребовался хэш а. Вот будет у тебя хэш от appearance - опять же свою другую функцию лучше (возможно какой-то xor со сдвигом достаточно будет), там buffer маленький совсем, куда там его крыть CH64? Для Line само тело 8 байт - этак можно вообще хэш не считать, и даже быстрее будет. Для картинок есть сквозной фиксированный список в памяти. Им в качестве кэша достаточно просто id: Integer. Операция изменения картинки (не у метки, а собственно картинки) мало того что нереальная, так ещё и легко устранимая просто добавлением изменённой картинки в конец. Зачем картинкам Int64, просто чтобы одна функция была на все случаи жизни, и плевать, что размер хэша больше чем обхэшированное тело? )))) Вот и соответственно получается, что оптимальнее на объектах типа метки иметь свои хэши для составных частей, а сверху если и собирать одно значение - то на их основе ), и возможно другой функцией. -------------- ) сейчас: hash = Geo.hash hash = F1(hash,Name.hash) hash = F1(hash,Desc.hash) hash = F1(hash,Appearance.hash) а надо: hash = F2(hash,Name.hash) hash = F2(hash,Desc.hash) hash = F3(hash, Geo.hash, Appearance.hash) чтобы разые по природе куски собирались в хэш в самом конце, и при изменении одного пересчитывать только последний хэш. >и если они одинаковые А разве порядок элементов в списке гарантируется? А не лучше ли сразу идти по старому списку (ведь он же есть, значит его можно отдать и попросить собрать новый, только если есть изменения), запоминая последний индекс от Find, и собирать новый список, только если есть первое отличие в элементах? >на всех последующих операциях очень даже Это понятно, но у меня такое ощущение, что при большом числе меток любой микросдвиг карты на z8 зацепит новую метку или хотя бы одна выйдет из области экрана. И реальная польза этого будет только при небольшом числе меток. Зато хэши будем считать исправно и зазря. Даже если для списка сделать "ленивый" расчёт хэша, и в сравнении сначала Count сравнить, а потом уже хэши (возможно рассчитав нерассчитанные значения, и тут как раз будет полезно разделение хэшей отдельно для геометрии) - и то выигрыщ будет, чем тупо на всякий случай всегда считать хэши для всего подряд.

(0012490) vasketsov (manager) 19-08-2013 09:18 edited on: 19-08-2013 09:19	>Для картинок есть сквозной фиксированный список в памяти Для apearance кстати можно сделать такой же. И тогда при создании метки просто будешь просить типа "дайте IAppearance по 4-ём INT-ам", и фактически получать от AppearanceFactory глобально уникальный Pointer. И безо всяких торчащих наружу ненужных хэшей appearance. А общий конечный хэш метки просто строится с учётом этого Pointer-а.

(0012491) vdemidov (manager) 19-08-2013 09:23	>Вот будет у тебя хэш от appearance - опять же свою другую функцию лучше (возможно какой-то xor со сдвигом достаточно будет), там buffer маленький совсем, куда там его крыть CH64? Для Line само тело 8 байт - этак можно вообще хэш не считать, и даже быстрее будет. Вполне возможно, что следующей оптимизацией будет выбрасывание поля FHash и замена его генерируемым из ширины и цвета простой конкатенацией. Но есть одно но. Для хэш таблицы мне нужно что бы каждый бит хэша зависил от исходных данных, что бы можно было просто откусить нужное количество бит и не замедлять работу кучей коллизий. >чтобы разые по природе куски собирались в хэш в самом конце, и при изменении одного пересчитывать только последний хэш. Оно бы было так, если бы векторные объекты были изменяемыми, а так оно создается и больше не модифицируется. >А разве порядок элементов в списке гарантируется? Нет, но с большой вероятностью сохранится. >А не лучше ли сразу идти по старому списку (ведь он же есть, значит его можно отдать и попросить собрать новый, только если есть изменения), запоминая последний индекс от Find, и собирать новый список, только если есть первое отличие в элементах? Слишком сложный интерфейс получается. Причем ИМХО неоправданно сложный. >Это понятно, но у меня такое ощущение, что при большом числе меток любой микросдвиг карты на z8 зацепит новую метку или хотя бы одна выйдет из области экрана. Зато на больших зумах будет очень сильно помогать. >Даже если для списка сделать "ленивый" расчёт хэша, и в сравнении сначала Count сравнить, а потом уже хэши (возможно рассчитав нерассчитанные значения, и тут как раз будет полезно разделение хэшей отдельно для геометрии) - и то выигрыщ будет, чем тупо на всякий случай всегда считать хэши для всего подряд. Никто не запретит это добавить в любой момент.

(0012492) vdemidov (manager) 19-08-2013 09:27	>Для apearance кстати можно сделать такой же. И тогда при создании метки просто будешь просить типа "дайте IAppearance по 4-ём INT-ам", и фактически получать от AppearanceFactory глобально уникальный Pointer. И безо всяких торчащих наружу ненужных хэшей appearance. Так ты можешь нарваться на OutOfMemory если меток много и все разные. плюс ты не будешь знать когда можно удалять лишнее, а в моем случае оно в случае такой ситуации, просто станет работать медленнее и в худшем случае просто некоторые одинаковые appearance станут разными объектами вместо того что бы схлопнуться в один.

(0012493) vasketsov (manager) 19-08-2013 10:41	>бы было так, если бы векторные объекты были изменяемыми Так ModifyMark закидывает же новую геометрию в метку? Вот и сравнивать старый хэш геометрии и новый. Если разные - считать только общий конечный. А не заново натягивать Name и Desc. И наоборот, добавляем кусок геометрии в метку (объединение добавление трека к треку) - пересчёт только общего хэша геометрии + общего хэша, не трогая Name, Desc и Appearance. >на больших зумах будет очень сильно помогать Это не от зума зависит, а от плотности меток на экране. Если меток мало - в любом случае быстро будет. Секунда - это когда порядка 4-5 тыщ меток, причём есть сложные и большие, на кучу тайлов. >можешь нарваться на OutOfMemory если меток много и все разные Если просто много разных меток - всё равно надо хранить в памяти все разные appearance - а это никак не меньше, чем их суммарный sizeof + count*sizeof(pointer). Так что просто оттого что много разных - ничего не изменится. >ты не будешь знать когда можно удалять лишнее С чего бы это? Наружу отдаётся IAppearance - когда его больше никто не юзает, его можно просто похерить, на остальные Pointer(IAppearance) это никоим образом не повлияет, если в общем списке оставить NIL - даже индексы не изменятся.

(0012494) vasketsov (manager) 19-08-2013 10:51	>Слишком сложный интерфейс получается Разве? а) у фабрики просим не просто новый список, а отавая ещё и возможно существующий старый список; б) не нужны общие хэши на список (IVector*Subset), так как общие хэши списков не сравниваются, такой же список просто не построится, будет отдан признак, что юзаем старый; в) если ничего не поменялось - итератор по старому списку даже передёргивать не придётся, ибо на каждом следующем объекте он как раз даст (через Next) такой же точно объект (IsSame). Может я конечно чего и не догоняю, но это и быстрее, и не добавляет новых коллизий, и память экономит.

(0012495) vdemidov (manager) 19-08-2013 11:00	> Так ModifyMark закидывает же новую геометрию в метку? Вот и сравнивать старый хэш геометрии и новый. Если разные - считать только общий конечный. А не заново натягивать Name и Desc. И наоборот, добавляем кусок геометрии в метку (объединение добавление трека к треку) - пересчёт только общего хэша геометрии + общего хэша, не трогая Name, Desc и Appearance. Скорее всего так и сделаю. Просто ModifyMark это не та операция, которая как-то повлияет на производительность всей программы :) И это всегда можно сделать потом внутри конкретных фабрик с минимальным изменением интерфейсов. >Это не от зума зависит, а от плотности меток на экране. Если меток мало - в любом случае быстро будет. Секунда - это когда порядка 4-5 тыщ меток, причём есть сложные и большие, на кучу тайлов. Так то оно так, но генерация тайла даже с одной меткой это весьма затратная операция и смысла пересоздавать 40 штук таких тайлов просто так не самая лучшая идея. А при наличии хэша у набора объектов, можно будет еще и кэшировать уже сгенеренные тайлы и держать какое-то их количество в памяти. Насчет остального спорить не буду. Можно и так сделать. Сделай сравним результаты :) PS: По поводу коллизий. Вероятность коллизии для 64битного хєша на наших количествах объектов практически нулевая. Я не начинал всю эту бодягу, имея только CRC32 и CRC64, именно потому что у них слишком много шансов было на коллизию, а у CityHash с этим все обстоит гораздо лучше. Может и не идеально, но гораздо лучше. И кстати коллизия совсем не обязательно значит не правильную работу программы, в случае коллизии во многих случаях просто что-то не будет кэшироваться.

(0012496) vdemidov (manager) 19-08-2013 11:36	>Может я конечно чего и не догоняю, но это и быстрее, и не добавляет новых коллизий, и память экономит. Может, может я не могу внятно объяснить чего хочу, а вполне может быть, что я где-то ошибаюсь. Разберемся. Отключить подсчет хэшей для сабсетов это заремить пару строк.

Users who viewed this issue
User List	Anonymous (2820x)
Total Views	2820
Last View	21-11-2024 12:47

Issue History
Date Modified	Username	Field	Change
09-08-2013 08:30	vdemidov	New Issue
09-08-2013 08:30	vdemidov	Issue generated from: 0002075
09-08-2013 08:30	vdemidov	Relationship added	parent of 0002075
09-08-2013 08:30	vdemidov	Status	new => confirmed
09-08-2013 08:31	vdemidov	Relationship added	parent of 0001927
18-08-2013 19:48	vasketsov	Note Added: 0012476
18-08-2013 19:58	vasketsov	Note Edited: 0012476	View Revisions
18-08-2013 19:59	vasketsov	Note Edited: 0012476	View Revisions
18-08-2013 20:05	vasketsov	Note Edited: 0012476	View Revisions
18-08-2013 20:24	vdemidov	Note Added: 0012477
18-08-2013 20:57	vasketsov	Note Added: 0012478
18-08-2013 21:11	vdemidov	Note Added: 0012479
18-08-2013 21:32	vasketsov	Note Added: 0012480
18-08-2013 22:05	vasketsov	Note Added: 0012481
18-08-2013 22:16	vasketsov	Note Edited: 0012481	View Revisions
19-08-2013 05:13	vdemidov	Note Added: 0012486
19-08-2013 07:41	vasketsov	Note Added: 0012487
19-08-2013 08:01	vdemidov	Note Added: 0012488
19-08-2013 08:59	vasketsov	Note Added: 0012489
19-08-2013 09:18	vasketsov	Note Added: 0012490
19-08-2013 09:19	vasketsov	Note Edited: 0012490	View Revisions
19-08-2013 09:23	vdemidov	Note Added: 0012491
19-08-2013 09:27	vdemidov	Note Added: 0012492
19-08-2013 10:41	vasketsov	Note Added: 0012493
19-08-2013 10:51	vasketsov	Note Added: 0012494
19-08-2013 11:00	vdemidov	Note Added: 0012495
19-08-2013 11:36	vdemidov	Note Added: 0012496
25-10-2013 10:36	vdemidov	Status	confirmed => resolved
25-10-2013 10:36	vdemidov	Fixed in Version	=> 131111
25-10-2013 10:36	vdemidov	Resolution	open => fixed
25-10-2013 10:36	vdemidov	Assigned To	=> vdemidov
27-10-2013 22:01	vdemidov	Target Version	24xxxx => 131111

SASGIS