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

Лучший ответ:
да, массив постоянно будет делать reAllocMem , если текущий размер окажется мельче, чем номер ячейки. Поэтому, если массив будет часто писаться с инкрементом, то выгоднее сперва прописать в последнее допустимое значение (8191 для 26 патча) типа MyArray[8191]=0
чисто чтобы его по памяти не возили туда-сюда каждые X значений (не смотрел, сколько изначально выделяется)
я вот у себя пофиксил такую же байду с таблицей строк. игра выделяет по 16 ячеек под строки, а у меня в доте они генерируются десятками в секунду. Каждую секунду игра делала ре-аллок памяти, а к середине игры там уже несколько мб таблица туда-сюда ездила. Сделал аллок в разы больше - и таблица всего 2 раза переедет за 40 минут игры максимум. Экономия тактов налицо.
Хеш-таблицы вообще не являются массивами, гугл в помощь, поэтому там об этом думать не стоит. Стоит думать лучше о том, чтобы первичных (родительских) ключей было меньше, чем вторичных, чисто исходя из того, что в этом случае перебор по таблице окажется быстрее


Views: 1 069

» Лучшие комментарии


Это сообщение удалено
PT153 #2 - 10 months ago 1
Голосов: +1 / -0
Почему информация о массивах является верной? Не стал бы верить этому, хотя бы потому что можно сразу в последнюю ячейку писать.

Поговаривают, что хеш в варе - обычная сишная или си-плюс-плюсная хеш-таюлица.
Ev3nt #3 - 10 months ago 0
Голосов: +0 / -0
PT153, так и есть.
PT153 #4 - 10 months ago 0
Голосов: +0 / -0
Ev3nt, а по поводу массивов - они действительно динамические?
Ev3nt #5 - 10 months ago 0
Голосов: +0 / -0
PT153, а это я уже не помню, но отследить удавалось :D
Vlod #6 - 10 months ago 0
Голосов: +0 / -0
PT153:
Почему информация о массивах является верной?
Не знаю является ли она верной, но её написал Hanabishi, а не ноунейм, она выбрана лучшим ответом на этом сайте, никто из пользователей в комментариях (DracoL1ch, Doc, Clamp, nvc123, quq_CCCP) никак не опровергнул это
Hate #7 - 10 months ago 0
Голосов: +0 / -0
вполне возможно так и есть, но какая практическая польза от этих знаний?
DracoL1ch #8 - 10 months ago (изм. ) 2
Голосов: +2 / -0

да, массив постоянно будет делать reAllocMem , если текущий размер окажется мельче, чем номер ячейки. Поэтому, если массив будет часто писаться с инкрементом, то выгоднее сперва прописать в последнее допустимое значение (8191 для 26 патча) типа MyArray[8191]=0
чисто чтобы его по памяти не возили туда-сюда каждые X значений (не смотрел, сколько изначально выделяется)
я вот у себя пофиксил такую же байду с таблицей строк. игра выделяет по 16 ячеек под строки, а у меня в доте они генерируются десятками в секунду. Каждую секунду игра делала ре-аллок памяти, а к середине игры там уже несколько мб таблица туда-сюда ездила. Сделал аллок в разы больше - и таблица всего 2 раза переедет за 40 минут игры максимум. Экономия тактов налицо.
Хеш-таблицы вообще не являются массивами, гугл в помощь, поэтому там об этом думать не стоит. Стоит думать лучше о том, чтобы первичных (родительских) ключей было меньше, чем вторичных, чисто исходя из того, что в этом случае перебор по таблице окажется быстрее
Ev3nt #9 - 10 months ago 0
Голосов: +0 / -0
DracoL1ch, есть костыльный метод, добавить новую JASS функцию, работающую непосредственно с массивом, который вам нужен.
DracoL1ch #10 - 10 months ago 0
Голосов: +0 / -0
для чего? зачем?
Ev3nt #11 - 10 months ago 0
Голосов: +0 / -0
DracoL1ch, ну мне так раньше было удобнее, я вообще только память использовал, когда оригинальный game.dll редактировал.
Vlod #12 - 10 months ago 0
Голосов: +0 / -0
Не понял. Если в jass hashtable это хеш-таблица хеш-таблиц, то зачем экономить parentkey?
PT153 #13 - 10 months ago (изм. ) 0
Голосов: +0 / -0
Хеш-таблицы вообще не являются массивами
Но ведь хештаблица в стандартной реализации - это массив, к каждой ячейке которого прикреплён список (который тоже может быть ArrayList). При увеличении объектов в таблице основной массив может быть заменён более большим массивом.
Как сделано в С\С++ не знаю точно.
ScorpioT1000 #14 - 10 months ago (изм. ) 0
Голосов: +0 / -0
Есть вероятность, что это один хешмап с конкатенацией двух ключей при работе из jass
DracoL1ch #15 - 10 months ago 0
Голосов: +0 / -0
Точно помню, что хештаблица варкрафта не эквивалентна настоящей, там даже по ключам ограничения есть, но деталей не помню, для кодера жасс это неважно.
Мы не экономим парентов, мы стараемся, чтобы корзин для поиска было меньше, чем яиц в них. На вскидку это связный список, а не массив, но я не эксперт в реализациях, да и исходников не имею
Vlod #16 - 10 months ago (изм. ) 0
Голосов: +0 / -0
  1. parentKey и childKey могут принимать значения от 2147483647 до -2147483648.
  1. Количество parentKey или childKey ограничено 18747, то есть не более 351450009 элементов.
  1. Не зависимо от загруженности таблицы и порядка опроса ключей, обращения выдают одинаковую нагрузку на поток.
  1. Так как существует функция FlushChildHashtable(), то конкатенация ключей возможна, но маловероятна.
DracoL1ch #17 - 10 months ago 0
Голосов: +0 / -0
в моих тестах было - чем больше данных в таблице, тем дольше они ищутся, т.к. списковый перебор, не? иначе объясни устройтво, плез Vlod:
Vlod #18 - 10 months ago 0
Голосов: +0 / -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.

Таким образом, мы видим внешнее поведение, как оно внутри, узреть не удастся
DracoL1ch #19 - 10 months ago (изм. ) 0
Голосов: +0 / -0
стоп, а каким образом кол-во операций, ограниченных виртуалкой жасса, говорит о трудозатратах перебора внутренних списков? JASS OPlimit считает только кол-во операций байт-кода, скомпилиированного из JASS-кода, внутренняя кухня никак не влияет - будь то тяжеленная функция создания юнита или крохотная функция установки владельца предмету, они займут 10 и 5 байт-слов соответственно, однако производительность второй не в пример выше, потому что операций там - просто сдвиг битов.
я глянул методы Load*() и вижу, что там идет перебор списка по листьям (чайлд) ветки (родителю) дерева, пока не встретится элемент с нужным ID ячейки. так что чем больше данных в таблице, тем дольше перебор
Vlod #20 - 10 months ago (изм. ) 0
Голосов: +0 / -0
Эта hashtable - лист листов?
pro100master #21 - 10 months ago 0
Голосов: +0 / -0
{}
DracoL1ch #22 - 10 months ago 3
Голосов: +3 / -0
я хз, в реале с таким не работал, пою что вижу в коде
Ev3nt #24 - 10 months ago 0
Голосов: +0 / -0
pro100master #25 - 10 months ago 0
Голосов: +0 / -0
типично
{id {parent:{id: {parent}}}}
ScorpioT1000 #26 - 10 months ago (изм. ) 0
Голосов: +0 / -0
Перебор списка там как решение проблемы коллизий.
А каквы так тестировали, что порвали поток - это надо постараться запустить это в жасс без таймеров и экзекуэьютов. Попробуйте на луа
PT153 #27 - 10 months ago 0
Голосов: +0 / -0
ScorpioT1000, у него 1.26.
Vlod #28 - 10 months ago 0
Голосов: +0 / -0
Проверил по другому. Да, обращение к заполненной hashtable чуть тяжелее, как и должно быть. В ходе экспериментов было выяснено:
  1. Обращение к последним добавленным parentKey быстрее, чем к первым.
  1. Обращение к последним childKey внутри одного parentKey быстрее, чем к первым добавленным.
  1. При постоянном обращении к одному и тому же элементу со временем нагрузка выравнивается.
  1. Падение производительности незначительное, обычно это 6-0 фпс.
Слишком много сходства между parent и child, надеюсь это хеш-таблица хеш-таблиц, а списки там лишь для решения коллизий, как и сказал ScorpioT1000 (что объясняет пункт 1 и 2)
DracoL1ch #29 - 10 months ago 0
Голосов: +0 / -0
чел, который ковырял таблицы, остался недоволен их качеством, ну и то, что ключи делаются по битовому (userKey & parentUniqueKey) вместо реальной хеш-функции, что повышает шанс коллизий в теории. Но я сам ни разу не сталкивался с коллизиями, хз
PT153 #30 - 10 months ago (изм. ) 0
Голосов: +0 / -0
В любой хеш-таблице будут коллизии, их можно решать по-разному, одним способом является chaining: в ячейке массива hash(key) хранится не (key, value), а ссылка на список, который хранит все элементы (key, value), у которых hash(key) одинаков.
IceFog #31 - 10 months ago 3
Голосов: +3 / -0
Для доступа к ячейке хэштаблицы jass'а нужно пройти через 3 словаря.
Ключ для первого - номер хэштаблицы, для остальных двух - parentKey и childKey.
Игра использует собственные коллекции.
Вот как выглядит поиск в их словаре:
» code
type
	generic TSHashTable<TKey, TValue, TKeyManager> = object
	public type
		PValue = ^TValue;
		TItems = specialize TSLinkedList<TValue>;
		PItems = ^TItems;
		TPages = specialize TSGrowableArray<TItems>;
	public
		vtable: Pointer;
		Items: TItems;
		Counter: Dword;
		Pages: TPages;
		HashMask: Dword;
	end;

function TSHashTable.Find(const AKey: TKey): PValue;
var
	Hash: Dword;
	Index: Integer;
	Page: PItems;
	Item: PValue;
begin
	Result:= nil;

	if HashMask = Dword(-1) then exit;
	
	Hash:= TKeyManager.GetKeyHash(AKey);
	Index:= Hash and HashMask;
	Page:= Pages.ItemPointers[Index];

	for Item in Page do begin
		if (Item^.HashKeyData.Hash = Hash) and
			TKeyManager.IsKeysEqual(Item^.HashKeyData.Key, AKey)
		then begin
			Result:= Item;
			break;
		end;
	end;
end;
Vlod #33 - 10 months ago 0
Голосов: +0 / -0
Интересно, что в Pascal есть дженерики. Тогда у нас 3 расширяемых массива, но количество номеров хеш-таблиц ограничено же 256ю.
IceFog, спасибо за разъяснение ситуации с массивами и списками)