Нужен алгоритм для максимально быстрого синхронного приведения указателя к описателю(связать произвольное значение с адресом). AVL медленный, чем больше элементов, тем больше нужно итераций. Пока лучше чем индексировать таблицы я не придумал. При тестах скорость ~150M(n)/s. Для AVL 4M/s.
UbIvItS, В моём случае для каждой инструкции нужно хранить структуру и быстро получить эту структуру по адресу инструкции.
самый быстрый вариант действительно индексация.. i=hash(adr); другой вопрос, это получить наиболее быстрый хэш.
UbIvItS, Для этого нужно знать конкретный диапазон адресов, что бы заранее сформировать таблицу. Но адрес может быть любой < 2GB. Тогда и массив получится линейный, сам адрес это и есть индекс, причём размером больше адресного пространства приложения.
тут дело даже не в диапазоне адресов, а в кол-ве адресов == у любого диапазона есть базовый адрес и от него можно все смещения получить. А вот для хэша можно замутить такой вариант.. i=from_odd_bits(adr)+from_even_bits(adr) То бишь одна функа формирует число из всех нечётных бит искомого адреса, а другая из чётных. к примеру, adr=111b, тогда.. from_odd_bits == 1b from_even_bits == 11b иль adr=101b, тогда.. from_odd_bits == 0 from_even_bits == 11b можно использовать два хэша, чтобы уменьшить колво совпадений == второй хэш, к примеру, такой.. i1=from_odd_bits(adr) xor from_even_bits(adr) Зы.. ну, и понятно, что, чтобы упаковать хэш в нужную битность, можно использовать рекурсию|цикл i=hash(hash(..hash(adr)..)). Ззы.. таблицу можно делать статичную с запасом места иль расширяемую == выбор в зависимости от твоих нужд и/ль лени
UbIvItS, Можно более понятно обьяснить, с реальным примером который хотя бы можно предположить для использования.. во первых какой хэш, как и от чего его вычислять, если заранее не известно ничего про адреса. Даже если и как то можно на основе хэш таблиц такое реализовать, то врядле это будет быстрее, чем обычный авл. Есчо нужно как то синхронно сделать в потоках, если из моего примера убрать lock(btr/s), то все потоки уйдут в деадлок. > у любого диапазона есть базовый адрес и от него можно все смещения получить. Заранее не вычислимо, просто потому, что ASLR не даёт предсказать, там рандом. 64k % 2GB, можно есчо несколько участков исключить, например старшие адреса, тк по ним по дефолту ничего не грузится и не выделяется(нужен спец флаг для сервисов выделения памяти). Если задать число 0x20000000 то у меня на системе ~1.8GB запрашивает семпл, так что NtAlloc -> STATUS_NO_MEMORY. Хотя это 512M адресов, что крайне много и реально такого значения никогда нет. Если взять среднюю длину инструкции 1/3макс, то получится размер кода 2.5GB.. Если для статикстики посмотреть число инструкций например у IE на младшей версии, то это ~850K, размер буферов крайне мал.
Ну хеш таблица - это массив записей с индексами от 0 до B . Задача хеш функции y = f(x) - получить для любого допустимого входного значения индекс в этой таблице. Хеш можно посчитать от чего угодно - хоть от строки, хоть от числа. Например, примитивная функция для числа (коим является адрес) - возвести число в квадрат и взять у получившегося значения числа на определенных позициях где-нибудь в середине, чтобы размерность укладывалась в диапазон B. Например, хотим хешировать 5 значное число, и у нас есть хеш таблица размерностью B = 100, то для формирования индекса достаточно взять числа у значения, полученного в результате возведения в квадрат, например, на позициях 5 и 6. Скорость доступа в хеш таблице к ячейке занимает фиксированное время, стремится к O(1) сложности, что грубо сравнимо с индексированием массива. А вообще скорость зависит от того, как равномерно хеш функция распределяет входные значения по индексам и от того, насколько заполнена таблица. Ну и при обращении к записи по вычисленному индексу (например, поиск) - смотрится, совпадает ли искомое с хранящимся там. Если содержимого нет - не найдено. Если совпадает - найдено. Если не совпадает - коллизия, смотрится дальше есть ли записи в ячейке, сравнивается последовательно. Хеш таблица всем хороша (если подобрать хорошую хеш функцию), кроме того, что памяти для эффективной и быстрой работы нужно грубо x2 от количества содержащихся элементов. В случае с адресами - если неизвестно заранее, хотя бы примерно количество записей, - то, наверное, придется брать число записей в таблице B наугад, а если будет заполняться до значений, при которых скорость упадет - пересоздавать новую с увеличенным B и перезаполнять имеющимися значениями из старой. Про блокировку - можно не блокировать, если записи/удаления из таблицы гарантированно не будет в дальнейшем, - на чтение можно и без синхронизации. Про хеш таблицы хорошо написано в "Структуры данных и алгоритмы" Ахо, Хопкрофт, Ульман. А если не устраивает хеш таблица - можно взять бинарное дерево - сразу можно указатели использовать для построения. Памяти не требует столько лишней , как хеш таблица, но и скорость медленей - сложность поиска N*logN , что все равно всяко быстрее последовательного перебора всех элементов линейного массива.
хеш будет сильно быстрей, пч расчёт его можно уложить в цпу, то бишь без паразитных прокидок до озу. Что касается прожорливости, дикий расход озу лишь в случае статических таблиц. А можно использовать множество таблиц с заданным размером. То бишь первый хэш указывает на номер таблицы, а второй уже указывает номер записи в таблице. Можно использовать и более глубокую иерархию == номер группы таблиц --> номер таблицы в группе --> номер в таблице. итд-итп. Indy_, ты концепцию файловых систем и бд, так понимаю, знаешь. Вот в их основе динамические варианты индексной сортировки
Indy_, А память ведь страницами выделяется? Может это как-то поможет сэкономить память. То есть создаём двумерный массив указателей где первый индекс - порядковый номер страницы, а второй - смещение относительно начала страницы. Таким образом память расходуется в основном только на интересующие тебя страницы. Код (Text): type index=array[0..<размер страницы>] of pointer; //массив указателей на структуры данных var pages: array[0..N] of ^index; //массив указателей на массивы указателей на структуры данных Или бред?
njeen, Как эти таблицы работают ежу ясно. Можно вот здесь поподробней: Как это наугад ? UbIvItS, Никак не пойму от чего хэш ? Ничего про адреса не известно. Есть диапазон памяти, верхний предел на 86 2GB. При этом хранить таблицы нужно в том же адресном пространстве, те локально в тех же 2GB. > без паразитных прокидок до озу. При выборке из памяти просадка менее 1%. Так что никак асинхронное обращение к памяти профайл не меняет. murder, В общем я и сделал похожим образом, так как не понятно как сделать иначе. Вся таблица вне памяти, при индексации в ней выделяется страница(4k/4) обнулённых указателей, в неё вставляется ссылка на начало блока из N-структур. Вирт адрес определяет номер страницы и смещение в блоке.
Например, 1000 записей для начала ) . Потом увеличивать с каким-нибудь инкрементом, например, на размер страницы. Хотя, может, есть более правильный способ.
njeen, Допустим известно максимальное количество адресов. Вы можете обьяснить как их случайных уложить в линейный массив по этим хэшам
Это зависит от способа организации таблицы. Например, в случае открытого хеширования в ячейках хеш таблицы хранятся связные списки значений, у которых вычисленный хеш соответствует данной ячейке. Как их случайных уложить в линейный массив - ну как, - вычисляется хеш у N-го входного значения, получается индекс в таблице. Если в ячейке по индексу список пуст - входное значение кладется его первым значением. Если не пуст - то в конец списка, в дополнение к уже имеющимся. Впоследствии различение одного от другого значения производится по сравнению сопоставляемого значения и тех, что хранятся в списке. 'Допустим известно максимальное количество адресов.' - это особо и не нужно, разве что для того, чтобы правильно выбрать количество ячеек в таблице, чтобы стремиться к тому, чтобы в каждой ячеке список был максимально коротким. https://studfile.net/preview/3651697/page:18/ Есть ещё закрытое хешировние - без списков, только в таблице, значения хранятся прямо в ячейках, но там отличие - для поиска применяется метод повторного хеширования, если по вычисленному адресу уже что-то лежит, коллизия, ищется следующая свободная. И нужны специальные пометки ячеек как пустая , удаленная. Как это - напр. на с. 120 описано. https://c-sharp4you.ru/wp-content/u...-Уллман-Структуры.данных.и.алгоритмы-2003.pdf
njeen, > вычисляется хеш у N-го входного значения, получается индекс в таблице. Вы не ответили на вопрос. Как вычисляется хэш, что получается индекс в таблице, при условии что входное значение не известно ? Значение может быть любое и их последовательность так же. Заранее это не известно. Если все значения индексируются через хэш, то зачем тогда вообще хэш нужен, если это линейно индексируемый массив по входному значению. Допустим есть три адреса: rand1, rand2, rand3 из диапазона 2GB. Как мне применить ваше хэширование" ? Как будет выглядеть структура таблиц/списков ?
"Как вычисляется хэш" - у вас есть некий указатель. Это просто число входное, оно может быть абсолютно любым и заранее неизвестным. К нему пременяется хеш функция, например, та примитивная про возведение в квадрат и вычленение из середины чисел на опред. позициях. В результате получается индекс. "Если все значения индексируются через хэш, то зачем тогда вообще хэш нужен, если это линейно индексируемый массив по входному значению." - нет. Отличие в том, что размер хеш таблицы сильно меньше массива, соответствующего, например, всем указателям из диапазона адресов, т.к не все будут использоваться адреса, например, 300 адресов из 2 Гб. Не, ну если в пределе будут задействованы все адреса из диапазона, тогда да, эквивалент массива, но такое вряд ли будет. Допустим есть три адреса: rand1, rand2, rand3 из диапазона 2GB. Как мне применить ваше хэширование" - Применить к каждому функцию хеширования. index1 = f(rand1), index2 = f(rand2) и т.д и получить индексы для каждого, выбрать ячейку, и т.д.
njeen, > index1 = f(rand1), index2 = f(rand2) Если возвести в квадрат рандом, то и получится рандом, а не индекс в таблице
допустим, возьмём иерархию с глубиной 1, тогда имеется главная таблица и в ней указываются ссылки на другие (нижние) таблицы заданного размера. пусть размер нижней таблицы будет 4кб, для главной получаем 524288 записей для полной адресации 2гб. Получаешь адрес, создаёшь запись в главной таблице (если его там ещё нет), создаёшь нижнюю таблицу (если её ещё нет), заносишь ссылку на твой объект в эту таблицу. короче, стандартная схема манагера озу. Ежли адреса сильно разбросаны (так, что плотность чуть ли не один адрес на нижнюю таблицу), то имеет смысл взять более глубокую иерархию.
