Если это верно для какого-то одного способа организации таблицы, это не значит, что это верно для всех. В закрытом и открытом хешировании ДОПУСКАЕТСЯ существование коллизий, и 'коллизий хэша не допускается от слова СОВСЕМ' в этом случае неверно
njeen, я рассматриваю хэш акь средство генерации уид. А если нам требуются просто ид-ы (без необходимости уникальности), то хэширование по большей части излишне == можно просто счётчики делать и уж тем более не нужны никакие квадраты.
Аналогично, но индексы ('просто ид-ы') тоже получаются уникальными, и хеширование не излишне. Тот же самый уид, только короткий.
ид и уид могут быть одинаковой длины == способ формирования тут не основополагающий. хэши в основном требуются для сортировок строк большой и/ль переменной длины + с большим разбросом значений (хэшируемых данных). так же они хороши для систем безопасности и проверки целостности данных, где опять же речь идёт именно об уид-ах.
У меня есчо есть вопрос, по той же теме, но не про трансляцию, более общий. Сборка в памяти(бинарная трансляция). В моём случае буфер нельзя удерживать долго, если обернуть RWL то всё станет. Поток инструкция должен сохраняться в буфер и каждая инструкция дополняться ветвлением на общий стаб. Можно использовать общий буфер, взяв размер MAX_IP_LENGTH + BRANCH_LENGTH, выравненный на 4. Но тогда может образоваться затыка по профайлу при синхронном выделении памяти из глобал буфера. Так же в буфере будет рандом последовательность инструкций разных тредов. Хотелось бы собрать там их последовательность в порядке исполнения(хотя бы части cfg), это позволило бы избежать адресной трансляции(так как следующий блок следует за текущим). Вот только как это сделать синхронно и без поточных блокировок
Indy_, обычно делается разделением режимов прогонки.. 1. ридмоуд == собирается статистика о запущенном бине и формируются гаджеты (блоки трансляции). 2. активмоуд == ранее сформированные гаджеты начинают использоваться для изменения поведения бина.
UbIvItS, Приложение может себя по разному вести при разных запусках, да и зачем накапливать статистику.. если можно налету всё сделать. Получается если несколько потоков выполняют общий код, тогда пока происходит сборка для первого треда, остальные будут простаивать. Иначе будут повторения в буфере(утечка памяти). Наверно синхрон должен происходить не с одной инструкцией, а со всей ветвью. Так пока описывается одна инструкция, потоки ждут, но затем может быть ветвление не на первую инструкцию, таким образом это не линейная сборка. Если транслировать всю ветвь, то тоже не не ясно - пока выполняется сборка, другой поток может перейти к исполнению есчо не описанной части ветви(которая собирается в данный момент) и что тогда делать.. как то связывать или разбивать ветвь на части?
современные железки построены на асинхронных операциях. Ты же пытаешься соорудить синхронку, но такое катит лишь на одно-потоке и то далеко не всегда. Всем бы хотелось бы бт налету, однако ЖЪЪЪ физ возможности жестянок слишком скромны для таких амбиций. приложуха может себя вести по разному, но никто не мешает делать контроль входных данных, что урезает осетра на палитру её поведений.
UbIvItS, А какие принципиальные трудности могут быть ? Если есть синхронный быстрый буфер, формирование описателя атомарно. На ветвлении в первом потоке пойдут синхронные формирования серии описателей в процессе диза блока(ветви). Если при этом второй поток пойдёт по описанной ветви(те загруженным описателям), он обнаружит что описатель сформирован и сборка прекратится синхронно. Если же второй поток перейдёт к части блока строящегося первым потоком, но которые он не успел собрать, то первый поток завершит сборку, так как доступ синхронный. Спин блокировка в описателе, её захват прежде анализа кода(диза) отменит повторную сборку. Не вижу возможных проблем. Задача весьма сложная, прежде чем браться за коденг нужно все алго и нюансы продумать, иначе придётся как всегда переписывать десятки раз. Придётся для оптимизации ветвлений использовать стек ветвлений(кэш), аналогично как в rfg. Это позволит за несколько инструкций выбирать из него описатель, быстрее чем трансляция в десятки инструкций. Но это тоже нужно продумать. Объединение в линейные блоки теоретически позволит экономить на памяти, так как она сократится как минимум в 32 раза, если хранить для блока не описатели, а битовую карту(где маркированы начала инструкций).
начнём с того, что у каждого много-потока есть своя логика блокировок и, накладывая свои, можно легко получить краши, дэдлоки и даже порчу файлов.
Код (Text): ICD struct Flags BYTE ? ; ICD_/Class S1ze BYTE ? ; Size/Pfx Delta BYTE ? ; Mrm/Disp union Cc BYTE ? ; 4i Ea BYTE ? ; SIB ends Pfx BYTE ? ; wDisp(2^n)/Mpfx Srg BYTE ? ; XED.Rseg ?, XED.Dis -> Jcc.Disp ? Vid BYTE ? ; VcTable{} Rsrv BYTE ? ICD ends ; 32i ICE struct ; i31: spinlock Ip PVOID ? ; Current Ip union Ic PVOID ? ; Next Ic(line/jcc/jmp) ; if [LA] = Ic.Ip then Ic else Ic = IcTouch([LA]) ends union Gp PVOID ? ; Current entry in graph. Fc PVOID ? ; Flow Ic for jcc. ends Rsrv4 DWORD ? Dis ICD <> ICE ends PICE typedef ptr ICE - трансляционный кэш, это то что я искал. 4x4d не улаживается диз, для выравнивания нужно 8x4d. Проход по кэшу это быстрый проход по ссылке ICE.Ic. Gp: указатель на сборку. Для не статик указателей типо ret нужно использовать стек ветвлений. Блокировка для построения ветви не имеет смысла, так как второй поток будет тупо простаивать, при этом нагрузка на потоки будет очень не равномерна. Статистика для примитивов 350(dye)/15(bt).
Покодил немного на выходных, в целом основной шаблон транслятора готов, вроде даже как то работает. Пока рано снимать профайл, так как не полноценно(нельзя крутнуть апп). Необходимая для трансляции инфа не влазит в структуру выше, изменил: Код (Text): ICD struct Flags BYTE ? ; ICD_/Class S1ze BYTE ? ; Pfx/Size Delta BYTE ? ; Mrm/Disp union Cc BYTE ? ; 4i Ea BYTE ? ; SIB ends Pfx BYTE ? ; Mpfx:5i/XED.Rseg:3i BYTE ? ; wDisp(2^n):2i, XED.Dis -> Jcc.Disp ? Vid BYTE ? ; VcTable{} Rsrv BYTE ? ICD ends ICD_SIZE equ 00001111B ICD_CLASS equ 00001111B ICD_DISP equ 00001111B ICD_MRM equ 11110000B ICD_FETCH equ 4 ICD_BASE equ 5 ICD_SIB equ 6 ICD_DISP8 equ 7 ICE struct ; i31: spinlock Ip PVOID ? ; Current Ip union Ic PVOID ? ; Next Ic(line/jcc/call) ends union Gp PVOID ? ; Current entry in graph. Fc PVOID ? ; Flow Ic for jcc. ; if [LA] = Fc.Ip then Ic = Fc else Ic = IcTouch([LA]; use statistics) ends Rsrv4 DWORD ? Dis ICD <> ICE ends PICE typedef ptr ICE Сборка идёт в виде приоритета: кэш - трансляция - сборка. Для стековых ветвлений нужен стек с PICE, подобно защите(RFG). Единственное что так и не понял, нужна ли обратная трансляция(GP -> IC, те буфер со сборкой на инструкцию). Такое может понадобится для обработки исключений, но перед ним ведь кэшируется адрес, так что пока такое не нужно, это потребовало бы есчо много памяти надеюсь что не нужно будет. Есть вопрос, не хочу тему поднимать. Для оптимизации нужна частичная эмуляция самых простых инструкций(которые не проводят выборку в память). Я посмотрел сурки qemu - это ведь полное говно без оптимизации, какой то треш там. Видимо рипнуть не выйдет, не охота эмулировать примитивы.
