Указатель в описатель.

Тема в разделе "WASM.A&O", создана пользователем Indy_, 10 мар 2020.

  1. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    Не нужен, если у вас терабайты ОЗУ и 2гб для вас ничто. Если возможны, скажем, адреса в диапазоне 0 - 200 000 , то в случае массива надо выделять памяти N*200'000 . Но большая часть его пустой будет, т.к использоваться адреса будут сильно не все . Если из 200'000 возможных будет использоваться где-то 200 рандомных, то их можно разместить в хеш таблице размером под 300 записей. Между размером выделенной памяти под 200'000 и 300 есть разница?
     
  2. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    > имеет смысл взять более глубокую иерархию.

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

    njeen,

    Как применить хэш к рандому вы не сказали(я ведь спрашивал функцию для примера), твердя одно и тоже :don-t_mention:

    Хэш-функция выбирается для известных значений!?
     
  3. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    ну-прям супер расти-то некуда == 4 байта адрес даёт ссылку а-ля цепочка из 4 таблиц по 256 записей в каждой и экономия места получается существенной.
    самый большой лаг получается на создание таблиц, при большом разлёте адресов может быть печалька сильная. единственно лечить можно более жадным потреблением озу, то бишь увеличиваем размер таблиц.. но тут уЖО смотри по своей ситуации акий конфиг лучше.

    что это?
     
  4. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
  5. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    Нет. Функция независима от значений. Инде может придумать абсолютно любую функцию, которая генерирует индекс в диапазоне, лишь бы равномерно по таблице. Как применить - мною описано ранее. Как применить к рандому - тоже (в #16) . И функция тоже дана была как пример.
     
  6. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    смахивает на некое жёсткое извращение == пользовать пойнтер на 32 бита для сверхбольших датасетов.
     
  7. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    njeen,

    Я не понимаю о чём вы говорите:

    > функцию, которая генерирует индекс в диапазоне

    Вот из вчерашнего лога значения и их квадратичная функция:

    Код (Text):
    1. 007B403B    1110110101011011001000110011111000110110011001
    2. 0051BB15    0110100001011111101100000000011010111110111001
    3. 007B4048    1110110101011011010101010101000001010001000000
    4. 0051BB15    0110100001011111101100000000011010111110111001
    5. 007B4055    1110110101011011100001110110001001110000111001
    6. 0051BB15    0110100001011111101100000000011010111110111001
    - что дальше с этим делать ?
    --- Сообщение объединено, 13 мар 2020 ---
    UbIvItS,

    Для отображения придётся вызывать ядро, что можно делать очень редко, ибо не профайл. Например переключить какие то таблицы. Только что это может дать не знаю.
     
  8. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    сколько получается в среднем адресов?
     
  9. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    ~1M для младшей версии IE. Зависит от приложения, позже сниму статистику на чём либо крупном.
     
  10. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    Indy_, вроде, размер не супер критичный == можь одну здоровую таблицу будешь пользовать? хэш главное, чтоб без коллизий был.
     
  11. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    Допустим, у нас в данный момент хеш таблица на 100 записей. Нам нужны из полученных квадратов индексы получить, чтобы были в диапазоне 0-100. Очевидно, что для этого достаточно взять 2 цифры на определенных позициях (возьмем на 5 и 6) .
    Тогда в десятичном виде будут взяты цифры для индекса:
    value (hex) ^2 (hex) ^2 (dec) полученный индекс
    007B403B3B56C8CF8D996524392227164127
    0051BB151A17EC01AFB92869004610348110
    007B40483B56D55414406524413228345628
    0051BB151A17EC01AFB92869004610348110
    007B40553B56E1D89C396524434229560929
    --- Сообщение объединено, 13 мар 2020 ---
    не главное :) . Немного коллизий - это нормально
     
    Indy_ нравится это.
  12. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    для борьбы с коллизиями можно так таблицу замутить..

    <>------hash----adr------pointer to description-------<>
    то бишь хэш тут есмь индекс таблицы, потом идёт взятый адрес (дабы проверять наличие коллизий).
    не пойму, а зачем квадраты нужны? и второй коварный вопрос == как выделять место под таблицу, то бишь с запасом иль как ???
    в куче случаев "немного" -- это уЖО МНОГО :grin:
     
  13. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    Что-что? Какой ещё борьбы? Коллизии неизбежны, для каждого способа организации хеш таблицы есть метод работы с ними. В в случае открытого хеширования это списки элементов, у которых совпадает вычисленный номер ячейки.

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

    "второй коварный вопрос == как выделять место под таблицу, то бишь с запасом иль как ???" - вы вообще предыдущие посты читаете? Идеальный метод начального размера таблицы взятия мне неизвестен, предполагаю первое значение размера наугад.
     
  14. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    njeen,

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

    UbIvItS,

    > в куче случаев "немного" -- это уЖО МНОГО :grin:

    Гипотетически в данном случае если есть коллизии, то пришлось бы каждый адрес помечать(а это затраты на память), иначе после ошибки всё упало бы.

    Foxit Reader, 6.1
    24 минуты на трассировку до появления гуя.
    Память апп 73MB с маркировкой адресов данным механизмом.
    4 минуты открытие доки..
    1699477
    ~1.6Mips

    fox.png
    --- Сообщение объединено, 13 мар 2020 ---
    Плохой пример выбрал. Слишком долго оно варится". Забыл строку коментнуть и есчо ждать пол часа; два запуска ~ час.. Даже крипторы быстрее заводятся..

    Но это и есть суть задачи. Что бы перейти от копирования в статик буфер на каждой итерации к бинарной трансляции.

    Запуск без сохранения Ip:

    16MB

    Общее количство инструкций при запуске гуя(что бы сравнить выше) 2.729.380.014

    ~ 2.542GBips
    --- Сообщение объединено, 14 мар 2020 ---
    Есчо один запуск, забыл про время :)

    Разница по времени, без использования данного механизма:

    24мин/25.. погрешность, разницы нет.

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

    Вложения:

    • Icl.asm
      Размер файла:
      3,3 КБ
      Просмотров:
      326
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    это с чего они неизбежны? :) вероятность коллизий падает по 2n, где энн есмь длина хэша.
    я уже упоминал быстрые алгосы хэша ==запруженность разрешима чрез них.
    нужно ориентироваться по размеру исследуемого файла == к примеру, 20% от него.
    --- Сообщение объединено, 14 мар 2020 ---
    Indy_, а не легче ли не все потоки осилить за раз, а только один поток за сессию?
    1. выборка маловата.
    2. тут ещё надо смотреть процент загрузки проца. к примеру, в одном случае получается получить 500 000нс доступа к процу каждую секунду, а в другом всего лишь 25 000.
    3. также имеется сильная зависимость от набора используемых апи.
     
  16. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS

    > я уже упоминал быстрые алгосы хэша ==запруженность разрешима чрез них.

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

    > не легче ли не все потоки осилить за раз, а только один поток за сессию?

    Приложение должно транслироваться(бинарная трансляция), а не трассироваться как сейчас. Из за копирований инструкций в буфера такие тормоза. А для этого необходимо реализовать две максимально быстрые функции - получение описателя по указателю(те когда происходит ветвление нужно найти соответствие в собранном коде) и синхронное выделение памяти для сборки.
    --- Сообщение объединено, 14 мар 2020 ---
    Можно ли имея некоторое большое количество адресов составить для них хэш функцию автоматикой ?

    Иначе хэши в данной задаче не применимы.
    --- Сообщение объединено, 14 мар 2020 ---
    > один поток за сессию?

    Как это, будет ведь деадлок.
     
  17. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    Я не знаю, что это за формула, но отображение б0льшего множества в меньшее означает вероятность коллизий > 0 . Если вероятность ненулевая, то получение на вход потенциально бесконечно большого множества входных различных входных данных означает неизбежность коллизии.

    Можно только оценить количество накопленных адресов и основываясь на этом выбрать размер таблицы. При открытом хешировании средняя длина списков элементов в ячейках равняется N/B, где N - количество размещаемых элементов, B - количество ячеек таблицы. И опять же, при этом типе хеширования (открытом) необходимость увеличения таблицы наступает когда возникает ситуация N > 2B ; нужно стремиться к тому, чтобы B = 2N ориентировочно при формировании таблицы.

    Составить функцию - да, основываясь на текущем B . (Здесь опять я с возведением в квадрат и взятием б0льшего количества чисел из середины получившегося числа =) )
     
  18. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    njeen,

    Можно вопрос общего плана. Вы понимаете о чём идёт речь ?

    По мойму нет, раз игнорите всё сказанное выше. Какой прок мне от ваших хэшей, если функцию от последовательности невозможно рассчитать автоматически ?
     
    q2e74 нравится это.
  19. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    Кмк, да. У вас есть некоторый код, который выдает поток адресов из опред. диапазона, и вы каждому хотите соответствие. В массиве перебор слишком долгий, поэтому вы задали вопрос, как это можно улучшить. Но упорно не хотите понять хеш таблицы.
    Чем вам коррекция функции хеширования в зависимости от числа встреченных адресов не автоматика?
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    ну-так, принцип бт в чём? по ходу дела собираешь адреса/куски кода и переделываешь их в нужную форму. из тех адресов, что за кэшировал, лабаешь хэши. даже можешь залабать хэши из уже кэшированных кусков кода, если такое по нраву :) Возьми исходники виртуалбокса и/ль кему, там имеется динамическая рекомпиляция.
    если быть точней, хэш отображает строку из энн бит в строку из эмм бит, где энн больше эмм. среднее кол-во совпадений хэша при отображение ВСЕХ строк длины энн == 2 в степени энн делить на два в степени эмм. ключевым словом тут является "ВСЕХ". обычно кол-во вхождений в таблицу гораздо меньше, чем кол-во возможных значений хэша. Тч в таблице никаких коллизий хэша не допускается от слова СОВСЕМ.
    N в идеале должно быть == кол-ву строк в таблице, а кол-во столбцов вариативно (не на стадии исполнения, конечно). второй момент, если мы говорим о статичных кодах, то кол-во накопленных адресов не может превышать размер бина. но даже в случае всяких тамо хитроЖО.. протекторов и морфах вполне можно задавать размер таблицы на основе размера подопытного бин файла.
    это довольно силовой приём.. так можно ещё и модульную арифу вспомнить :) но зачем так напружать проц(???), если легковесные хэши на +/-/ИЛИ/КСОР/И/СДВИГ позволяют получать тот же результат, но быстрей. например, такая таблица вполне робитЪЪЪ..

    <>-----hash----id of hash func-----adr-----pointer to object-----<>
     
    q2e74 нравится это.