Vlod
WarCraft 3

Выделение памяти в хеш-таблице

Добавлен
Добрый вечер. Тут говорится, что при обращении к массиву выделяется память на 1024 элемента.
Вопрос. Выделение памяти в хеш-таблицах работает так же? То есть при обращении к первым выделится 1024, а при вызове FlushChildHashtable() - освободится? 1.26а

Принятый ответ

да, массив постоянно будет делать reAllocMem , если текущий размер окажется мельче, чем номер ячейки. Поэтому, если массив будет часто писаться с инкрементом, то выгоднее сперва прописать в последнее допустимое значение (8191 для 26 патча) типа MyArray[8191]=0
чисто чтобы его по памяти не возили туда-сюда каждые X значений (не смотрел, сколько изначально выделяется)
я вот у себя пофиксил такую же байду с таблицей строк. игра выделяет по 16 ячеек под строки, а у меня в доте они генерируются десятками в секунду. Каждую секунду игра делала ре-аллок памяти, а к середине игры там уже несколько мб таблица туда-сюда ездила. Сделал аллок в разы больше - и таблица всего 2 раза переедет за 40 минут игры максимум. Экономия тактов налицо.
Хеш-таблицы вообще не являются массивами, гугл в помощь, поэтому там об этом думать не стоит. Стоит думать лучше о том, чтобы первичных (родительских) ключей было меньше, чем вторичных, чисто исходя из того, что в этом случае перебор по таблице окажется быстрее
20 янв 2020
  • Размещен: 20.01.2020 16:34:39
  • Создан: 20.01.2020 16:34:39
  • Обновлен: 20.01.2020 16:34:39
2 991
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
16
4 года назад
0
в моих тестах было - чем больше данных в таблице, тем дольше они ищутся, т.к. списковый перебор, не? иначе объясни устройтво, плез Vlod:
0
18
4 года назад
0
Оцениваю не время, а количество операций. То есть: если блок кода больше нагружает, то внутри одного потока он выполнится меньшее количество раз.
Тест проводился следующим образом:
  1. Сначала проверил, что и parentKey и childKey принимают все доступные int-ы.
  1. Дальше нужно было наполнить таблицу и посмотреть на разницу в работе. В процессе выяснилось, что значения перестали сохраняться. Экспериментально были вычислен порог для parentKey. Далее проверил, что childKey ведут себя так же и каждый родительский ключ может иметь не более 18747 дочерних.
  1. Когда мы убедились, что hashtable наполняется корректно, можно начать нагрузочное тестирование. Максимальное кол-во элементов 74985 (все доступные parentKey и три полных childKey) и варьировалось в зависимости от цели конкретного теста.
  1. Нагрузочное тестирование.
4.1 Запоминаем количество успешных обращений к пустой hashtable внутри одного потока.
4.2.1 Заполняем все доступные parentKey.
4.2.2 Считаем количество обращений к первому, к последнему, к выбранным мной случайно. Получаем идентичное число операций с пустой hashtable.
  • 4.3. Проверяем, нет ли встроенного кеширования. Обращаемся к случайному parentKey. Запускаем несколько раз, результат не меняется. (Либо обход списка инкапсулирован в виртуальной машине, либо это не список)
  1. Идентично с childKey.
Таким образом, мы видим внешнее поведение, как оно внутри, узреть не удастся
0
16
4 года назад
Отредактирован DracoL1ch
0
стоп, а каким образом кол-во операций, ограниченных виртуалкой жасса, говорит о трудозатратах перебора внутренних списков? JASS OPlimit считает только кол-во операций байт-кода, скомпилиированного из JASS-кода, внутренняя кухня никак не влияет - будь то тяжеленная функция создания юнита или крохотная функция установки владельца предмету, они займут 10 и 5 байт-слов соответственно, однако производительность второй не в пример выше, потому что операций там - просто сдвиг битов.
я глянул методы Load*() и вижу, что там идет перебор списка по листьям (чайлд) ветки (родителю) дерева, пока не встретится элемент с нужным ID ячейки. так что чем больше данных в таблице, тем дольше перебор
0
18
4 года назад
Отредактирован Vlod
0
Эта hashtable - лист листов?
0
23
4 года назад
0
{}
3
16
4 года назад
3
я хз, в реале с таким не работал, пою что вижу в коде
0
19
4 года назад
0
DracoL1ch, +
0
23
4 года назад
0
типично
{id {parent:{id: {parent}}}}
0
37
  • Комментарий официального представителя Администрации сайта
    • 4 года назад
    Отредактирован ScorpioT1000
    0
    Перебор списка там как решение проблемы коллизий.
    А каквы так тестировали, что порвали поток - это надо постараться запустить это в жасс без таймеров и экзекуэьютов. Попробуйте на луа
    0
    28
    4 года назад
    0
    ScorpioT1000, у него 1.26.
    0
    18
    4 года назад
    0
    Проверил по другому. Да, обращение к заполненной hashtable чуть тяжелее, как и должно быть. В ходе экспериментов было выяснено:
    1. Обращение к последним добавленным parentKey быстрее, чем к первым.
    1. Обращение к последним childKey внутри одного parentKey быстрее, чем к первым добавленным.
    1. При постоянном обращении к одному и тому же элементу со временем нагрузка выравнивается.
    1. Падение производительности незначительное, обычно это 6-0 фпс.
    Слишком много сходства между parent и child, надеюсь это хеш-таблица хеш-таблиц, а списки там лишь для решения коллизий, как и сказал ScorpioT1000 (что объясняет пункт 1 и 2)
    Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
    Чтобы оставить комментарий, пожалуйста, войдите на сайт.