1. Как у этого решения с переносимостью с точки зрения выравнивания данных.
2. Как у этого решения с переносимостью с точки зрения использования этого решения на экзотических платформах типа Гарвардской архитектуры, когда указатели разные для разных типов памяти?
3. Хотелось бы хэш-функцию без цикла, чтобы побыстрее было. Что можно предложить?
Здравствуйте, pepsicoca, Вы писали:
P>Пока что сделал что-то вроде этого:
Есть проблемы с pointer aliasing.
Плюс хэш-функции вида "суммируем байт" дают обычно очень плохие распределения.
P>Посоветуйте, какую хэш-функцию лучше взять, чтобы было быстро и переносимо.
Кастуй указатель к uintptr_t, и возвращай это значение.
Если тебе известно, что от хэш-функции чаще используются младшие биты, то можно сдвинуть (циклически или даже просто так) результат вправо на число бит, равное логарифму типичного выравнивания при выделении памяти (скорее всего будет равно чему-то вроде 2-х или 3-х бит).
Ну или можно дальше вокруг значения типа uintptr_t сделать этап обычного целочисленного хэширования. Хотя для указателей это скорее лишнее.
Здравствуйте, pepsicoca, Вы писали:
P>1. Как у этого решения с переносимостью с точки зрения выравнивания данных.
На 32-битной платформе все указатели делятся на 4, а на 64-битной — на 8. Если вы получаете свои структуры от malloc'а или new, то в зависимости от реализации может оказаться, что все ваши указатели делятся на 16 или еще хуже. А поскольку вы их просто складываете, то и значения вашей хеш-функции будут делиться на 4, 8 или 16. А это означает, что вы просто теряете несколько младших бит.
P>2. Как у этого решения с переносимостью с точки зрения использования этого решения на экзотических платформах типа Гарвардской архитектуры, когда указатели разные для разных типов памяти?
Не заморачивайте этим свою голову.
P>3. Хотелось бы хэш-функцию без цикла, чтобы побыстрее было. Что можно предложить?
Разверните цикл, у него в вашем случае фиксированное количество проходов.
Здравствуйте, watch-maker, Вы писали:
WM>Здравствуйте, pepsicoca, Вы писали:
P>>Пока что сделал что-то вроде этого:
WM>Есть проблемы с pointer aliasing.
What is "pointer aliasing"?
WM>Плюс хэш-функции вида "суммируем байт" дают обычно очень плохие распределения.
P>>Посоветуйте, какую хэш-функцию лучше взять, чтобы было быстро и переносимо. WM>Кастуй указатель к uintptr_t, и возвращай это значение.
Кстати это мысль. В типичном случае платформы х86 при выделении памяти в куче указатели отличаются в младших разрядах.
WM>Если тебе известно, что от хэш-функции чаще используются младшие биты, то можно сдвинуть (циклически или даже просто так) результат вправо на число бит, равное логарифму типичного выравнивания при выделении памяти (скорее всего будет равно чему-то вроде 2-х или 3-х бит).
Зачем вправо?
Вправо сдвинуть значит потерять различия в близкорасположеных указателях. Как раз тогда и будет плохое распределение, все хеш-значения будут одинаковыми.
Может влево?
WM>Ну или можно дальше вокруг значения типа uintptr_t сделать этап обычного целочисленного хэширования. Хотя для указателей это скорее лишнее.
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, pepsicoca, Вы писали:
P>>1. Как у этого решения с переносимостью с точки зрения выравнивания данных.
Pzz>На 32-битной платформе все указатели делятся на 4, а на 64-битной — на 8. Если вы получаете свои структуры от malloc'а или new, то в зависимости от реализации может оказаться, что все ваши указатели делятся на 16 или еще хуже. А поскольку вы их просто складываете, то и значения вашей хеш-функции будут делиться на 4, 8 или 16. А это означает, что вы просто теряете несколько младших бит.
Значение выравнивания я никак не узнаю, чтобы это было переносимо. Так что придется терпеть.
P>>2. Как у этого решения с переносимостью с точки зрения использования этого решения на экзотических платформах типа Гарвардской архитектуры, когда указатели разные для разных типов памяти?
Pzz>Не заморачивайте этим свою голову.
P>>3. Хотелось бы хэш-функцию без цикла, чтобы побыстрее было. Что можно предложить?
Pzz>Разверните цикл, у него в вашем случае фиксированное количество проходов.
Может потребоваться портирование на х64 или вообще на другую архитектуру.
Не хотелось бы каждый раз переделывать хэш-функцию для каждой платформы.
Здравствуйте, pepsicoca, Вы писали:
P>Здравствуйте, watch-maker, Вы писали:
WM>>Здравствуйте, pepsicoca, Вы писали:
P>>>Пока что сделал что-то вроде этого:
WM>>Есть проблемы с pointer aliasing.
P>What is "pointer aliasing"?
WM>>Плюс хэш-функции вида "суммируем байт" дают обычно очень плохие распределения.
P>>>Посоветуйте, какую хэш-функцию лучше взять, чтобы было быстро и переносимо. WM>>Кастуй указатель к uintptr_t, и возвращай это значение.
P>Кстати это мысль. В типичном случае платформы х86 при выделении памяти в куче указатели отличаются в младших разрядах.
WM>>Если тебе известно, что от хэш-функции чаще используются младшие биты, то можно сдвинуть (циклически или даже просто так) результат вправо на число бит, равное логарифму типичного выравнивания при выделении памяти (скорее всего будет равно чему-то вроде 2-х или 3-х бит).
P>Зачем вправо? P>Вправо сдвинуть значит потерять различия в близкорасположеных указателях. Как раз тогда и будет плохое распределение, все хеш-значения будут одинаковыми. P>Может влево?
А, понял почему. При суммировании может и неважно, а при приведении к типу uintptr_t может помочь.
Но переносимо никак не узнать, какой шаг выравнивания на данной платформе.
WM>>Ну или можно дальше вокруг значения типа uintptr_t сделать этап обычного целочисленного хэширования. Хотя для указателей это скорее лишнее.
Здравствуйте, pepsicoca, Вы писали:
P>Значение выравнивания я никак не узнаю, чтобы это было переносимо. Так что придется терпеть.
Тогда надо подобрать такую хеш-функцию, которая не деградирует в случае, если входные данные всегда имеют несколько младших битов равными нулю.
P>Может потребоваться портирование на х64 или вообще на другую архитектуру. P>Не хотелось бы каждый раз переделывать хэш-функцию для каждой платформы.
Здравствуйте, pepsicoca, Вы писали:
P>>>>Посоветуйте, какую хэш-функцию лучше взять, чтобы было быстро и переносимо. WM>>>Кастуй указатель к uintptr_t, и возвращай это значение.
P>>Кстати это мысль. В типичном случае платформы х86 при выделении памяти в куче указатели отличаются в младших разрядах.
В типичной x86 у почти всех адресов структур в младшем бите стоит 0. И в следующем бите тоже. Не ноль там только в разных указателях на упакованные структур, да в указателях на подстроки.
WM>>>Если тебе известно, что от хэш-функции чаще используются младшие биты, то можно сдвинуть (циклически или даже просто так) результат вправо на число бит, равное логарифму типичного выравнивания при выделении памяти (скорее всего будет равно чему-то вроде 2-х или 3-х бит).
P>>Зачем вправо? P>>Вправо сдвинуть значит потерять различия в близкорасположеных указателях. Как раз тогда и будет плохое распределение, все хеш-значения будут одинаковыми. P>>Может влево?
P>А, понял почему. При суммировании может и неважно, а при приведении к типу uintptr_t может помочь. P>Но переносимо никак не узнать, какой шаг выравнивания на данной платформе.
И не нужно. Во-первых, log₂ sizeof int даст хорошее приближение. Во-вторых, циклический сдвиг гарантирует, что мы не потерям информацию, даже если слегка ошибёмся. В-третьих, можно получить нужные параметры и извне. Ну и в-четвёртых, читай следующую строчку: WM>>>Ну или можно дальше вокруг значения типа uintptr_t сделать этап обычного целочисленного хэширования.
Целочисленное хэширование как раз размазывает все биты, и работает вполне универсально. Просто обычно без него можно обойтись. Но если хочется гарантий, то задействуй его — это не дорого.
P>Добрый день.
P>Есть структуры, которые нужно хранить в хэш-таблице. P>При этом ключ хэш-таблицы это указатель (пусть для простоты будет указатель void*).
P>Посоветуйте, какую хеш-функцию лучше взять, чтобы было быстро и переносимо.
P>Пока что сделал что-то вроде этого:
P>
P>Вопросы:
P>1. Как у этого решения с переносимостью с точки зрения выравнивания данных. P>2. Как у этого решения с переносимостью с точки зрения использования этого решения на экзотических платформах типа Гарвардской архитектуры, когда указатели разные для разных типов памяти? P>3. Хотелось бы хэш-функцию без цикла, чтобы побыстрее было. Что можно предложить?
P>Спасибо.
А может быть просто взять логарифм или синус от указателя?
Что-то вроде этого:
typedef int hashtablelength;
ob_type_hashtablelength ob_hash(void* ptr){
hashtablelength hashvalue;
unsigned long int mask=0;
char* mptr=(char*)&mask;
size_t i;
size_t l;
if(sizeof(void*)>sizeof(unsigned long int)) l=sizeof(unsigned long int); else l=sizeof(void*);
for(i=0;i!=l;++i) mptr[i]=(char)0xff;
unsigned long int val=0;
val|=*((unsigned long int*)(&ptr));
val&=mask;
double dlog=log((double)val);
hashvalue=(hashtablelength)dlog;
return hashvalue;
}
Разумеется, цикл подготовки маски вынести из функции, так как маску нужно сделать один раз.
Здравствуйте, pepsicoca, Вы писали:
P>А может быть просто взять логарифм или синус от указателя?
P>Что-то вроде этого:
P>
P>typedef int hashtablelength;
P>ob_type_hashtablelength ob_hash(void* ptr){
P>hashtablelength hashvalue;
P>unsigned long int mask=0;
P>char* mptr=(char*)&mask;
P>size_t i;
P>size_t l;
P>if(sizeof(void*)>sizeof(unsigned long int)) l=sizeof(unsigned long int); else l=sizeof(void*);
P>for(i=0;i!=l;++i) mptr[i]=(char)0xff;
P>unsigned long int val=0;
P>val|=*((unsigned long int*)(&ptr));
P>val&=mask;
P>double dlog=log((double)val);
P>hashvalue=(hashtablelength)dlog;
P>return hashvalue;
P>}
P>
P>Разумеется, цикл подготовки маски вынести из функции, так как маску нужно сделать один раз.
Это настолько ужасно, что хуже сделать уже не легко. Абсолютно непереносимо, много где не будет работать вообще, а если где работать и будет, то с отвратительным распределением.
Что ты хочешь сделать? Нужно нечто практичное или просто интересна экзотическая кроссплатформенности?
Если тебе нужна хэш-функция для какого-то списка архитектур, то напиши их для каждой отдельно. Например, для x86-64 или x86 c плоской моделью памяти неплохо подойдёт код
uintptr_t hash(void *p) {
return (uintptr_t)p;
}
Это замечательная функция. Если вдруг тебе она кажется слишком простой, то вызови её как std::hash(hash(p)), но не городи логарифмов и прочей ерунды.
Целочисленный логарифм от численного значения адреса — это вообще ужас, это же всего лишь позиция старшего ненулевого бита в представлении. Посмотри, например, на ту же популярную архитектуру x86-64 и какие там где используются адреса. У половины же старший бит всегда единица, и вся твоя функция будет возвращать константу. Да, у второй половины адресов там ноль, но они же не все используются, особенность устройства ОС такова, что остальные адреса обычно сгруппированы и находятся где-то рядом, на них твоя функция тоже окажется константой. Считать вместо логарифма синус или экспоненту менее бессмысленно, но не намного.
О кроссплатформенности. Так залезать в указатель просто нельзя. Если хочешь получить численное значение, то сделай каст к uintptr_t (как сделано выше или через union, если хочется). Но учти, что численное значение указателя не может служить хэшом в общем случае. Например, по причине того, что у одного указателя может быть несколько численных значений. Когда такие указатели сравниваются, то компилятор генерирует код нормализации, который это учитывает. Когда ты залезаешь вручную внутрь, то очевидно этого не происходит. И это не экзотика, да всё тот же x86 в реальном режиме работает именно таким образом.
P>Не хотелось бы каждый раз переделывать хэш-функцию для каждой платформы.
Так может идентифицировать структуры по их содержимому? Или надо именно указатели?
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, pepsicoca, Вы писали:
P>>Посоветуйте, какую хеш-функцию лучше взять, чтобы было быстро и переносимо.
BZ>крутое обсуждение. бери (int64(ptr)*123456791)>>32
Это не самый хороший вариант. Нетрудно заметить, что функция работает почти как деление значения адреса на примерно 34,789 с последующим округлением результата. Например, если в машине размер слова и адреса равен 32-м битам, то такая функция будет принимать менее менее 3% различных значений от максимальных 2³². А следовательно будет множество коллизий.
Если у процессора есть дешевое умножение, то мультипликативные хэш-функции, конечно, хороши, но в них старшие биты результата нужно отбрасывать, а в качестве ответа брать следующие за ними. В данном случае это означает, что если убрать из выражения сдвиг, то новая функция станет работать только лучше.
P>>Разумеется, цикл подготовки маски вынести из функции, так как маску нужно сделать один раз. WM> WM>Это настолько ужасно, что хуже сделать уже не легко. Абсолютно непереносимо, много где не будет работать вообще, а если где работать и будет, то с отвратительным распределением.
Надо будет продать этот код в Голливуд как сценарий фильма ужасов.
WM>Что ты хочешь сделать? Нужно нечто практичное или просто интересна экзотическая кроссплатформенности? WM>Если тебе нужна хэш-функция для какого-то списка архитектур, то напиши их для каждой отдельно. Например, для x86-64 или x86 c плоской моделью памяти неплохо подойдёт код WM>
К сожалению, реальность гораздо страшнее.
Даже если не рассматривать гипотетическое будущее, в суровом настоящем нужно, чтобы этот код транслировался на Borland C++ Builder 6.0.
А в Borland C++ Builder 6.0 нет никаких новомодных uintptr_t.
Может попробовать size_t вместо uintptr_t?
WM>Это замечательная функция. Если вдруг тебе она кажется слишком простой, то вызови её как std::hash(hash(p)), но не городи логарифмов и прочей ерунды. WM>Целочисленный логарифм от численного значения адреса — это вообще ужас, это же всего лишь позиция старшего ненулевого бита в представлении. Посмотри, например, на ту же популярную архитектуру x86-64 и какие там где используются адреса. У половины же старший бит всегда единица, и вся твоя функция будет возвращать константу. Да, у второй половины адресов там ноль, но они же не все используются, особенность устройства ОС такова, что остальные адреса обычно сгруппированы и находятся где-то рядом, на них твоя функция тоже окажется константой. Считать вместо логарифма синус или экспоненту менее бессмысленно, но не намного.
WM>О кроссплатформенности. Так залезать в указатель просто нельзя. Если хочешь получить численное значение, то сделай каст к uintptr_t (как сделано выше или через union, если хочется). Но учти, что численное значение указателя не может служить хэшом в общем случае. Например, по причине того, что у одного указателя может быть несколько численных значений. Когда такие указатели сравниваются, то компилятор генерирует код нормализации, который это учитывает. Когда ты залезаешь вручную внутрь, то очевидно этого не происходит. И это не экзотика, да всё тот же x86 в реальном режиме работает именно таким образом.
P>К сожалению, реальность гораздо страшнее. P>Даже если не рассматривать гипотетическое будущее, в суровом настоящем нужно, чтобы этот код транслировался на Borland C++ Builder 6.0. P>А в Borland C++ Builder 6.0 нет никаких новомодных uintptr_t. P>Может попробовать size_t вместо uintptr_t?
