Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 9 лет назад, По-русски

Добрый день.

В конце декабря-начале января я писал прототип отдельного сервиса на C++, чтобы вынести из Java-кода Codeforces тяжелые данные в С++. Давненько я не писал на C++, испытал забавные ощущения погружения в другой мир.

С удивлением обнаружил отсутствие в C++ хэш-мэпа с открытой адресацией в стандартной библиотеке, как впрочем и в boost-e, как впрочем и других нормальных библиотеках. Даже странно как-то, ведь правда же довольно часто открытая адресация будет делать разрешение коллизий цепочками как по времени, так и по памяти. А так как я предполагаю хранить мелкие объекты, то и наверняка.

Я быстренько набросал прототип, который в самом деле показывает, что открытая адресация в раза 2-3 работает быстрее стандартного unordered_map, так что такой контейнер, наверняка, имеет смысл. Вот вывод бенчмарка на моём ноуте:

std::map takes 15779 ms
std::unordered_map takes 4698 ms
oaht::hash_map takes 1473 ms

Мне кажется, что нормальной реализации в stl-стиле с поддержкой С++11 (move semantics) нет. Может кто-то покажет, но я не нашел.

Вот мой прототип на github: https://github.com/MikeMirzayanov/open_addressing_hash_table К сожалению, я не крутой эксперт C++, и со временем у меня совсем не круто, так что довести до ума такой контейнер в обозримом будущем не получится.

С другой стороны, на Codeforces регулярно поднимается обсуждение C++ и, кажется, есть много участников, понимающих современный С++. Алгоритмы же — это вообще вода и воздух Codeforces. У меня есть надежда, что вселенский разум Codeforces и прямые руки кого-то из сообщества поможет довести до ума такой контейнер. Конечно, хочется максимальной совместимости с unordered_map, чтобы API и семантика были максимально эквивалентны (где можно, конечно). Вот примерный список фич, что хочется видеть:

  1. One more template type parameter class Pred = std::equal_to<Key>
  2. Member function at
  3. Member function clear
  4. Member function empty
  5. Member function insert
  6. Member function equal_range
  7. Member function swap
  8. Member function operator=
  9. Member functions load_factor, max_load_factor, rehash, reserve
  10. Constant members
  11. Member types: difference_type, hasher, key_type, mapped_type, reference, size_type, value_type, pointer, const_reference, key_equal
  12. Iterators: member types iterator, const_iterator, member functions begin, end, cbegin, cend
  13. Member function emplace
  14. Member function emplace_hint
  15. Relational operators
  16. Non-member function overload: swap
  17. Move semantics

Кроме того, хочется сохранить работоспособность на основных реализациях C++11: g++, Visual Studio 13+, clang. Пожалуйста, постарайтесь следовать принципам форматирования oaht.h, чтобы не нарушить единообразие.

Я с удовольствием передам управление этим проектом кому-то, у кого есть энтузиазм, знания C++ и зарекомендованный опыт в задачах. Доброволец, найдись! С меня футболка и +5 к уважению.

P.S. На выходе хочется иметь приличную реализацию, а не абы что, так что есть желание вливать в проект только правильный и красивый код.

  • Проголосовать: нравится
  • +140
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

Will we be able to use oaht::hash_map h; after #include "codeforces.h" on codeforces in the future? It sounds very interesting :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

(http://code.google.com/p/morzhovets/source/browse)

Может быть вот это подойдет? (momo::cstyle::unordered_map)

Есть отклонения от стандарта и не все функции пока сделаны, но можно доделать.

Там три типа bucket'ов: для открытой адресации (если так уж хочется), цепочки (но в виде массивов) и гибридный способ (по умолчанию он).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    momo/cstyle/../HashSet.h:585:4: error: 'begin' was not declared in this scope
        for (const Item& item : bucket.GetBounds())
    

    Вроде же в самом деле для итерации в таком стиле у итерируемого должны быть begin()/end(). В SVN разломан trunk?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А если сделать

      #include <iterator>
      

      ?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Для такой итерации достаточно определить std::begin(container) и std::end(container). Каким компилятором вы билдаете?

      Технические подробности наверное лучше будет по почте обсудить: morzhovets gmail com

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      возможно последний блок с функциями std:: нужно повыше поднять и/или поставить пробел между ">>".

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

Have you tried SGI hash_map?

Unfortunately I couldn't find the collision resolution method used in it, but I've tried your benchmark.cpp on my laptop and it shows a better performance (than the std::unordered_map). So you might want to check it out.

Header file: <ext/hash_map>

Namespace: __gnu_cxx

Edit1: It's not SGI's hash_map, I misinterpreted this comment in <ext/hash_map>

/** @file backward/hash_map
 *  This file is a GNU extension to the Standard C++ Library (possibly
 *  containing extensions from the HP/SGI STL subset).
 */

Edit2: After some digging into the header files, I found that it uses closed addressing method for collision resolution.

You can find that in the header file <backward/hashtable.h> function name ... insert_equal_noresize(...).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It seems it has worst performance than open addressing hash map proof-of-concept:

    n oaht::hash_map __gnu_cxx::hash_map
    500000 204 ms 374 ms
    1000000 408 ms 841 ms
    2000000 860 ms 1760 ms
    4000000 1731 ms 3787 ms
    8000000 3956 ms 8250 ms
»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Have you tried Google Dense Hashmap? Though it might not 100% matching your specs, its a lot faster then stl containers and really nicely written.

https://code.google.com/p/sparsehash/

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Looks promising, thanks. But I've tried test<GOOGLE_NAMESPACE::sparse_hash_map<int64_t,int64_t>>("GOOGLE_NAMESPACE::sparse_hash_map"); and it works ~2000 ms while open addressing hash map proof-of-concept ~400 ms. Right now I can't use it MinGW (can't compile), using in MS VS 2013.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think dense_hash_map is more time efficient while sparse_hash_map is more space efficient. Can you try dense_hash_map?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I checked and default dense_hash_map is about 2x slower on my machine.

      I wonder how much of this difference is due to the fact that your proof of concept supports few operations, namely only inserts but not deletes.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Did you use benchmark code from my github repository? So dense_hash_map wasn't tested on erases as well. I do not see that support of more functionallity in oaht will reduce performance.

        Also in my case I will not use erases often.

        How to use dense_hash_map? I've got Assertion failed: settings.use_empty(), file google\sparsehash/internal/densehashtable.h, line 476.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yes, I cloned your github code.

          Also had that error with dense_hash_map, but it is explained in the readme:

             dense_hash_map requires you to set aside one key value as the
             'empty bucket' value, set via the set_empty_key() method.  This
             *MUST* be called before you can use the dense_hash_map.  It is
             illegal to insert any elements into a dense_hash_map whose key is
             equal to the empty-key.
          

          So, I created a new test with

          // Init
          google::dense_hash_map<int64_t, int64_t> m;
          m.set_empty_key(1LL << 62);
          // do operations
          
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Sorry for the multiple replies. Just noticed that dense_hash_map also uses open addressing with quadratic probing for collisions resolution.

          So, I think these efficiency differences are more about the particular data set or hash function used, rather than the hash map implementation.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I believe that +1 strategy could be better than quadratic probing or double hashing because of better cpu cache usage.

            • »
              »
              »
              »
              »
              »
              »
              9 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится

              I think it depends on the data set. Linear probing has the risk of clumping, having too many adjacent buckets occupied.

              If you feel this is unlikely to occur in the data you'll use, then it's probably better.

              My feeling is that libraries like dense_hash_map are designed to minimize the probability of an adversarial input, which may not be the best solution for your case.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I remember a long time ago I tried to implement my own oaht and it was also considerably faster than dense_hash_map for all benchmarks. I was using double hashing to resolve collisions.

            For some reason, in the case of hash maps, it seems the more generic the code is, the less-performant it becomes. Maybe it has something to do with working well against most datasets, or is really just a load factor issue, I don't know.

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Постойте, но если встретилось ERASED, то надо пройти дальше до первого FREE, чтоб убедиться, что таких ключей все же не было. И если не было — то записать туда, где было первое ERASED. Разве не так это работает?

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Еще rehash надо делать не только в сторону увеличения, но и в сторону уменьшения. Если добавить 100500 элементов, а потом удалить 100000 из них, то foreach будет бегать очень долго. Это то, что мне уже два месяца очень лень фиксить в моей библиотеке.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

0. Открытая адресация со смещением при коллизии на 1, кажется, плоха.
1. Код nodes[i] = node<_Key,_Value>(); выглядит странно. Должно вызываться само собой.
2. Думаю, технически лучше делать rehash с параметром n_capacity...
2.1. ... и вызвать таки его в конструкторе.
2.2. ... хотя в своем рабочем коде я бы предпочел видеть реализацию rehash через swap с новой таблицей.

На самом деле, когда dalex писал код для библиотеки, мы обсуждали с ним некоторые тонкости в открытой адресации, можете просто позаимствовать (не думаю, что он будет против). В частности, мы capacity решили делать степенью двойки, после этого можно использовать любое нечетное число для смещения по коллизии (вычисляем из хеша) и, кроме того, мы вносили рандомизацию в процесс хеширования.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    0) Не очевидно. Есть известные оценки, что длина кластера быстрее растет, но при load factor достаточно далеком от 1 кластеры всё еще небольшие, а вот в кэш процессора лучше попадают. На самом деле я тестил варианты и с квадратичными пробами и двойное хеширование, работало похуже видимо из-за cache-miss-ов.

    1) Да.

    2) Да.

    Есть надежда, что подойдет Walrus-реализация или какая-то другая, хотя предварительные тестам и https://www.sgi.com/tech/stl/hash_map.html и https://code.google.com/p/sparsehash/ не блещут производительностью.

»
9 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

How to use it on Codeforces? What compiler should be chosen and #include what file(s) I got lots of CE……