The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

Компания Google открыла код hash-функций CityHash

12.04.2011 17:21

Разработчики из компании Google представили реализацию 64- и 128-разрядных hash-функций CityHash, позволяющих получить отпечаток фиксированной длины, идентифицирующий больший по размеру набор входящих данных. Код функций написан на языке C++, распространяется в рамках лицензии MIT и разработан в стиле "всё ради высокой производительности".

Код CityHash был написан для реализации высокопроизводительных хэш-таблиц, используемых для организации хранения баз ключ-значение, для использования в криптографии он не предназначен. Функция CityHash128 оптимизирована для строк размером в несколько сотен байт. Оптимизация кода, использование 64-разрядных регистров, обеспечение параллелизма выполнения на уровне инструкций и быстрый доступ к невыровненным областям памяти позволили добиться значительного превосходства в производительности по сравнению с другими реализациями хэшей. Ценой производительности является достаточно сильная запутанность кода.

Алгоритм работы CityHash подразумевает смешивание битов входящего потока. По сравнению с прошлыми реализациями высокопроизводительных хэшей от компании Google, CityHash демонстрирует в реальных условиях ускорение как минимум на 30%. В некоторых ситуациях наблюдается увеличение производительности до двух раз. Достаточная степень уникальности сгенерированных хэшей, подтверждена статистическими исследованиями.

  1. Главная ссылка к новости (http://google-opensource.blogs...)
Лицензия: CC BY 3.0
Короткая ссылка: https://opennet.ru/30218-google
Ключевые слова: google, hash
При перепечатке указание ссылки на opennet.ru обязательно


Обсуждение (29) Ajax | 1 уровень | Линейный | +/- | Раскрыть всё | RSS
  • 1.1, pavlinux (ok), 17:29, 12/04/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • –1 +/
    http://code.google.com/p/cityhash/source/browse/trunk/src/city.cc

    А где там C++ ? :)

    ---

    А, во, нашел

    #include <algorithm>

    using namespace std;

    pair<uint64, uint64> v, w;
    std::swap(z, x);

    и всё :)

     
     
  • 2.6, Аноним (-), 18:05, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    По вашему любой код на плюсах должен использовать все, включая самые безумные, возможности этого монструозного языка?
     
  • 2.8, parad (??), 18:32, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +2 +/
    блин, ну оберни это в класс, сделай фабрику, опиши это в интерфейсах, как-нибудь припиши к этому буст, и оповести всех нас и компанию гугл о своих достижениях письмом на spam@google.com и очередным бессмысленно-неинформативным комментом здесь. порадуй.
     
     
  • 3.23, pavlinux (ok), 01:00, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    На, жуй

    http://pavlinux.ru/CityHash/city.c
    http://pavlinux.ru/CityHash/city.h

    Кампилитца как С так С++ одновременно.

     
     
  • 4.27, oops_ (?), 05:33, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    И где там C++?

    А, во, нашел #ifdef __cplusplus

     
     
  • 5.30, pavlinux (ok), 17:20, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > И где там C++?
    > А, во, нашел #ifdef __cplusplus

    :)

     
  • 2.9, gildor (?), 18:37, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • –7 +/
    В коде есть объявления локальных переменных в середине тела функции - такое C-компилятор не "переварит".
     
     
  • 3.14, pavlinux (ok), 19:02, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +5 +/
    > В коде есть объявления локальных переменных в середине тела функции - такое
    > C-компилятор не "переварит".

    переварит.

     
     
  • 4.24, gildor (?), 01:17, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • –4 +/
    > переварит.

    Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис отключить.

     
     
  • 5.25, pavlinux (ok), 01:28, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    >> переварит.
    > Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис
    > отключить.

    Я чего-то не пойму... где проблема?



    struct a {int x; int y;};

    void vodi() {

        int x = 0;

        printf("%e\n", x);
        memset(NULL, 0, 1);


       for (int i = 0; i < 1024; i++) { // С99

      int x = 1024;                    // С99
              struct a vec = {i+2*i, (x+i)/i}; // С99
         }
    }


    какое место не нравиться?

     
     
  • 6.31, gildor (?), 16:47, 17/05/2011 [^] [^^] [^^^] [ответить]  
  • +/
    >>> переварит.
    >> Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис
    >> отключить.
    > Я чего-то не пойму... где проблема?
    > ...
    > какое место не нравиться?

    Здесь всё в порядке. Но код вида



    int a = 1;  // объявление переменной
    a = a + 1;  // операция без объявления переменной
    int b = 2;  // снова объявление переменной



    по крайнёй мере Visual C++ 9 (2008) не возьмёт - в 3й строке выдаст ошибку, если компились файл как C, а не как C++. Недавно перекомпилировал SDL 1.3 - там как раз была такая проблема.

     
  • 5.26, bircoph (ok), 04:32, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Уже лет 8 как жуёт без всяких расширений, если не больше.

     
  • 2.10, User294 (ok), 18:53, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • –1 +/
    > http://code.google.com/p/cityhash/source/browse/trunk/src/city.cc
    > А где там C++ ? :)
    > #include <algorithm>
    > using namespace std;
    > pair<uint64, uint64> v, w;
    > std::swap(z, x);
    > и всё :)

    Еще коменты в виде // :).Или в свежих вариантах стандарта си это уже можно? Я понимаю что компилерам пофиг и они и это жрут, но формально // вроде как считается не совместимым с большей частью стандартов на си.


     
     
  • 3.11, Aleksey (??), 18:56, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    Это C++. Там же теплейты, а это щастье доступно только на C++.
     
  • 3.13, pavlinux (ok), 19:01, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    >> http://code.google.com/p/cityhash/source/browse/trunk/src/city.cc
    >> А где там C++ ? :)
    >> #include <algorithm>
    >> using namespace std;
    >> pair<uint64, uint64> v, w;
    >> std::swap(z, x);
    >> и всё :)
    > Еще коменты в виде // :).Или в свежих вариантах стандарта си это
    > уже можно?

    С99 можно.

     
     
  • 4.18, User294 (ok), 19:19, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • –1 +/
    > С99 можно.

    А, тогда ок.

     
  • 3.15, klalafuda (?), 19:02, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > Еще коменты в виде // :).Или в свежих вариантах стандарта си это уже можно? Я понимаю что компилерам пофиг и они и это жрут, но формально // вроде как считается не совместимым с большей частью стандартов на си.

    ISO/IEC 9899:1999 (E)

      6.4.9 Comments
    1 Except within a character constant, a string literal, or a comment, the characters /*
      introduce a comment. The contents of such a comment are examined only to identify
      multibyte characters and to find the characters */ that terminate it.69)
    2 Except within a character constant, a string literal, or a comment, the characters //
      introduce a comment that includes all multibyte characters up to, but not including, the
      next new-line character. The contents of such a comment are examined only to identify
      multibyte characters and to find the terminating new-line character.

     
  • 2.17, Fixxxer (??), 19:19, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • –6 +/
    Согласен - везде где можно использовать возможности плюсов, надо их использовать. Не на убогом Си же в конце то концов писать? Хотя мазохистов в последнее время полно. =)
     
     
  • 3.4, klalafuda (?), 17:49, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    Им было удобнее выразить uint128 через пару uint64 + uint64. Хотя от плюсов там конечно не много. Прямо скажем - ничего. Да и то, что есть... using namespace std - расстрел. stdlib.h vs cstdlib, переопределение uintXX_t в uintXX (нахуа?), сплошной char * vs std::string & и пр.. в общем, тяжелое бремя C просто так не проходит. Уж лучше бы написали на C и не вы&^$%&^сь почем зря.
     
     
  • 4.5, klalafuda (?), 17:53, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    > Им было удобнее выразить uint128 через пару uint64 + uint64. Хотя от плюсов там конечно не много. Прямо скажем - ничего. Да и то, что есть... using namespace std - расстрел. stdlib.h vs cstdlib, переопределение uintXX_t в uintXX (нахуа?), сплошной char * vs std::string & и пр.. в общем, тяжелое бремя C просто так не проходит. Уж лучше бы написали на C и не вы&^$%&^сь почем зря.

    PS: Впрочем, к самому алгоритму и получаемому хешу это отношения не имеет. Переписывается на что угодно как угодно в течении часа. Если очень хочется. Всего лишь мелкие придирки к стилю конкретного девелупера гугла, не более. А вот то, что описание подоплеки и математическое обоснование алгоритма отсутствует и есть лишь тупой код не важно какого размера - use it on your own risk. Удачи.

     
     
  • 5.7, pavlinux (ok), 18:10, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • –1 +/
    static uint128 CityMurmur(const char *s,...

    Как англоязычные программеры читают этот бред?! :)

    cтатичный бцел128 ГородМурмур(пост символ *s,...

     
     
  • 6.12, User294 (ok), 19:00, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • –1 +/
    > static uint128 CityMurmur(const char *s,...
    > Как англоязычные программеры читают этот бред?! :)
    > cтатичный бцел128 ГородМурмур(пост символ *s,...

    А все-равно у нас круче умеют :). На вот тебе, http://habrahabr.ru/blogs/compilers/116301/
    Самопальный гопоязык то черт с ним, а вот "сишный" сорц в коментах выглядит убедительно....

     
  • 6.16, Аноним (-), 19:16, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • +1 +/
    CityMurmur - ШёпотГорода, что такого?
     
  • 4.28, Аноним (-), 09:25, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • +/
    char* вместо std::string это как раз очень правильно, с остальным согласен.
     

  • 1.19, Aquarius (ok), 19:39, 12/04/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    > Утверждается, что представленные функции не подходят для использования в криптографии, так как алгоритм работы CityHash подразумевает смешивание битов входящего потока, что допускает появление коллизий (вероятность коллизий крайне низка, что подтверждено накопленной статистикой).

    существование коллизий - генетическое свойство любых hash-функций

    P.S. математики это доказали задолго до появления компьютеров

     
     
  • 2.22, User294 (ok), 21:18, 12/04/2011 [^] [^^] [^^^] [ответить]  
  • –1 +/
    Все правильно, просто для криптографически стойких хеш-функций подбор коллизии для известного хеша должен быть сравним по затратности с лобовым брутфорсом. У гугли видимо это требование не выполняется - видимо, можно подобрать коллизии существенно проще. Поэтому их функция может и неплоха для некоторых применений (как фукция для hash-table), но не годится для криптографических применений(как функция криптографически удостоверяющая неизменность некоего сообщения, например). А то что существует бесконечно много наборов данных которые мапятся в 128-битный результат не понятно только идиотам да копирасам которые дошли до того что пытаются качать права на вполне конкретные хеши :))))
     
     
  • 3.29, kibab (?), 16:15, 13/04/2011 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Её и не предполагается использовать для криптографии. Об этом в статье написано.
     

  • 1.20, Аноним (-), 19:44, 12/04/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +2 +/
    > Утверждается, что представленные функции не подходят для использования в криптографии, так как алгоритм работы CityHash подразумевает смешивание битов входящего потока, что допускает появление коллизий (вероятность коллизий крайне низка, что подтверждено накопленной статистикой).

    Давно не читал подобного бреда.

    1. Коллизии по определению имеет абсолютно любая хэш-функция, у которой на входе бит больше, чем на выходе.
    2. Для криптографии интерес представляет обратимость хэш-функции (то есть возможность за разумное время угадать такую входную последовательность, чтобы она давала нужную выходную).

     
  • 1.21, FastDuck (?), 21:08, 12/04/2011 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    Мы вам верим, но всё же - где ссылка на бенчмарки?
     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Партнёры:
    PostgresPro
    Inferno Solutions
    Hosting by Hoster.ru
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2024 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру