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

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

  1. njeen

    njeen Active Member

    Публикаций:
    0
    Регистрация:
    26 мар 2017
    Сообщения:
    138
    Адрес:
    Ташлинск
    Если это верно для какого-то одного способа организации таблицы, это не значит, что это верно для всех. В закрытом и открытом хешировании ДОПУСКАЕТСЯ существование коллизий, и 'коллизий хэша не допускается от слова СОВСЕМ' в этом случае неверно
     
  2. UbIvItS

    UbIvItS Well-Known Member

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

    njeen Active Member

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

    UbIvItS Well-Known Member

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

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    У меня есчо есть вопрос, по той же теме, но не про трансляцию, более общий. Сборка в памяти(бинарная трансляция).

    В моём случае буфер нельзя удерживать долго, если обернуть RWL то всё станет.

    Поток инструкция должен сохраняться в буфер и каждая инструкция дополняться ветвлением на общий стаб. Можно использовать общий буфер, взяв размер MAX_IP_LENGTH + BRANCH_LENGTH, выравненный на 4. Но тогда может образоваться затыка по профайлу при синхронном выделении памяти из глобал буфера. Так же в буфере будет рандом последовательность инструкций разных тредов. Хотелось бы собрать там их последовательность в порядке исполнения(хотя бы части cfg), это позволило бы избежать адресной трансляции(так как следующий блок следует за текущим). Вот только как это сделать синхронно и без поточных блокировок :dash1:
     
  6. UbIvItS

    UbIvItS Well-Known Member

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

    1. ридмоуд == собирается статистика о запущенном бине и формируются гаджеты (блоки трансляции).
    2. активмоуд == ранее сформированные гаджеты начинают использоваться для изменения поведения бина.
     
  7. Indy_

    Indy_ Well-Known Member

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

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

    Получается если несколько потоков выполняют общий код, тогда пока происходит сборка для первого треда, остальные будут простаивать. Иначе будут повторения в буфере(утечка памяти). Наверно синхрон должен происходить не с одной инструкцией, а со всей ветвью. Так пока описывается одна инструкция, потоки ждут, но затем может быть ветвление не на первую инструкцию, таким образом это не линейная сборка. Если транслировать всю ветвь, то тоже не не ясно - пока выполняется сборка, другой поток может перейти к исполнению есчо не описанной части ветви(которая собирается в данный момент) и что тогда делать.. как то связывать или разбивать ветвь на части?
     
  8. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    современные железки построены на асинхронных операциях. Ты же пытаешься соорудить синхронку, но такое катит лишь на одно-потоке и то далеко не всегда. Всем бы хотелось бы бт налету, однако ЖЪЪЪ физ возможности жестянок слишком скромны для таких амбиций. приложуха может себя вести по разному, но никто не мешает делать контроль входных данных, что урезает осетра на палитру её поведений.
     
  9. Indy_

    Indy_ Well-Known Member

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

    А какие принципиальные трудности могут быть ?

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

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

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

    Объединение в линейные блоки теоретически позволит экономить на памяти, так как она сократится как минимум в 32 раза, если хранить для блока не описатели, а битовую карту(где маркированы начала инструкций).
     
    Последнее редактирование: 19 мар 2020
  10. UbIvItS

    UbIvItS Well-Known Member

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

    Indy_ Well-Known Member

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

    UbIvItS Well-Known Member

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

    Indy_ Well-Known Member

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

    Именно блокировки были причиной не понимания общего алго.
     
  14. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    Код (Text):
    1. ICD struct
    2. Flags    BYTE ?    ; ICD_/Class
    3. S1ze        BYTE ?    ; Size/Pfx
    4. Delta    BYTE ?    ; Mrm/Disp
    5. union
    6.     Cc    BYTE ?    ; 4i
    7.     Ea    BYTE ?    ; SIB
    8. ends
    9. Pfx        BYTE ?    ; wDisp(2^n)/Mpfx
    10. Srg        BYTE ?    ; XED.Rseg ?, XED.Dis -> Jcc.Disp ?
    11. Vid        BYTE ?    ; VcTable{}
    12. Rsrv        BYTE ?
    13. ICD ends
    14.  
    15. ; 32i
    16. ICE struct
    17. ; i31: spinlock
    18. Ip        PVOID ?    ; Current Ip
    19. union
    20.     Ic    PVOID ?    ; Next Ic(line/jcc/jmp)
    21.     ; if [LA] = Ic.Ip then Ic else Ic = IcTouch([LA])
    22. ends
    23. union
    24.     Gp    PVOID ?    ; Current entry in graph.
    25.     Fc    PVOID ?    ; Flow Ic for jcc.
    26. ends
    27. Rsrv4    DWORD ?
    28. Dis        ICD <>
    29. ICE ends
    30. PICE typedef ptr ICE
    - трансляционный кэш, это то что я искал. 4x4d не улаживается диз, для выравнивания нужно 8x4d.

    Проход по кэшу это быстрый проход по ссылке ICE.Ic. Gp: указатель на сборку.

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

    Статистика для примитивов 350(dye)/15(bt).
     
  15. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    Покодил немного на выходных, в целом основной шаблон транслятора готов, вроде даже как то работает. Пока рано снимать профайл, так как не полноценно(нельзя крутнуть апп). Необходимая для трансляции инфа не влазит в структуру выше, изменил:

    Код (Text):
    1. ICD struct
    2. Flags    BYTE ?    ; ICD_/Class
    3. S1ze        BYTE ?    ; Pfx/Size
    4. Delta    BYTE ?    ; Mrm/Disp
    5. union
    6.     Cc    BYTE ?    ; 4i
    7.     Ea    BYTE ?    ; SIB
    8. ends
    9. Pfx        BYTE ?    ; Mpfx:5i/XED.Rseg:3i
    10.         BYTE ?    ; wDisp(2^n):2i, XED.Dis -> Jcc.Disp ?
    11. Vid        BYTE ?    ; VcTable{}
    12. Rsrv        BYTE ?
    13. ICD ends
    14.  
    15. ICD_SIZE    equ 00001111B
    16. ICD_CLASS    equ 00001111B
    17. ICD_DISP    equ 00001111B
    18. ICD_MRM    equ 11110000B
    19.  
    20. ICD_FETCH    equ 4
    21. ICD_BASE    equ 5
    22. ICD_SIB    equ 6
    23. ICD_DISP8    equ 7
    24.  
    25. ICE struct
    26. ; i31: spinlock
    27. Ip        PVOID ?    ; Current Ip
    28. union
    29.     Ic    PVOID ?    ; Next Ic(line/jcc/call)
    30. ends
    31. union
    32.     Gp    PVOID ?    ; Current entry in graph.
    33.     Fc    PVOID ?    ; Flow Ic for jcc.
    34.     ; if [LA] = Fc.Ip then Ic = Fc else Ic = IcTouch([LA]; use statistics)
    35. ends
    36. Rsrv4    DWORD ?
    37. Dis        ICD <>
    38. ICE ends
    39. PICE typedef ptr ICE
    Сборка идёт в виде приоритета: кэш - трансляция - сборка. Для стековых ветвлений нужен стек с PICE, подобно защите(RFG).

    Единственное что так и не понял, нужна ли обратная трансляция(GP -> IC, те буфер со сборкой на инструкцию). Такое может понадобится для обработки исключений, но перед ним ведь кэшируется адрес, так что пока такое не нужно, это потребовало бы есчо много памяти надеюсь что не нужно будет.

    Есть вопрос, не хочу тему поднимать. Для оптимизации нужна частичная эмуляция самых простых инструкций(которые не проводят выборку в память). Я посмотрел сурки qemu - это ведь полное говно без оптимизации, какой то треш там. Видимо рипнуть не выйдет, не охота эмулировать примитивы.
     
    Последнее редактирование: 12 май 2020