понадобилось тут как-то раздавать файлам уникальные id — с учётом того, что inode у них не всегда имеется. попробовал разные простенькие хэши, что под рукой оказались. из тех, что не очень много кода. понятно, что какой-нибудь длинный криптохэш бы справился, но идея такая, что желательно несколько строчек асма бы. результат оказался довольно забавный.
взял, значит, базу mlocate, оставил там только уникальные имена, и смотрел как её кушают вороны. 3192666 unique file names. (666 само вышло, я не специально!)
по итогу простенький хэш Боба Дженкинса «one-at-a-time» зарулил его же lookup2, lookup3 и fasthash32 (этот взял чисто поржать).
joaat вот такие результаты дал:
4105 (117 for same length) collisions found.
lookup2 — как Боб и предупреждал — просто хуже, по всем параметрам (кроме, может, скорости). общих коллизий чуть больше, чем у joaat. если считать коллизии с учётом длины имени (то есть, включать в id длину) — то, парадоксально, у joaat вообще в два раза меньше.
4228 (336 for same length) collisions found.
lookup3 по количеству общих коллизий чуть-чуть выиграл, но с учётом длины результат всё ещё сильно хуже, чем у joaat.
3791 (290 for same length) collisions found.
fasthash32 по количеству общих ещё сильнее выиграл, но с учётом длины — не смог.
3765 (182 for same length) collisions found.
понятно, что 64-битные варианты lookup3 и fasthash64 дали 0 коллизий. но lookup3 довольно большой, а у fasthash64 — 64-битное умножение. joaat же — пара сдвигов, сложение и xor.
поскольку мне avalanche в unique id не нужен, надо только чтобы уникальные, то аугментировал joaat до 64 битов вот так:
static void joaat2x (const void *buf, size_t len, uint32_t *hash1p, uint32_t *hash2p) {
uint32_t hash1 = *hash1p, hash2 = 0;
const uint8_t *s = (const uint8_t *)buf;
while (len--) {
hash1 += *s;
hash1 += hash1<<10;
hash1 ^= hash1>>6;
hash2 -= hash1;
s += 1u;
}
hash1 += hash1<<3;
hash1 ^= hash1>>11;
hash1 += hash1<<15;
hash2 -= hash1;
*hash1p = hash1;
*hash2p = hash2;
}
то есть, просто добавил дешёвый аккумулятор во внутренний цикл — одно вычитание (можно было и сложение, в данном случае неважно). с таким дополнением коллизий стало ожидаемо 0.
это я всё к тому, что иногда Старые Простые Методы как минимум не хуже, а то и лучше Новых Продвинутых. то, что joaat обрабатывает буфер побайтово — в данном случае опять неважно: имена файлов особо длинными не бывают. зато он охуеть маленький, и на асме пишется буквально в несколько строчек. опять же: всегда можно сделать оптимизированый вариант joaat, который будет читать по 32 бита в регистр за раз, а потом unrolled loop их обработки.
в принципе, последнее вычитание из hash2 не нужно, я его для красоты добавил. если убрать — результаты ожидаемо не изменятся: аваланч в аккумуляторе всё равно никакой, акк работает чисто контрольной суммой.
тащемта, в таком виде joaatx2 отлично подходит для создания каталогов каких-нибудь архивов, чтобы там находить имена буквально несколькими сравнениями, например. или для хранения списка заинклюденых файлов (мне именно для этого и понадобился). в случае списка инклюдов на статистически ничтожную вероятность коллизии можно просто забить болт.
я в списке инклюдов беру базовое имя файла (без пути), и домешиваю к хэшу ещё размер и mtime. это может не очень хорошо сработать, если в разных каталогах инклюды с одинаковым именем и размер совпадает (у меня в системе это частая ситуация: главный файл каталога всегда называется одинаково, и в основном он делает один include файла уже с нормальным именем), но ирл спасает mtime. могут быть проблемы, если систему развернули из какого-нибудь архива, который mtime не сохраняет, правда. но в моём случае это неважно. |