Monthly Archives: Июль 2015

Perfect Hashing of Very Short Strings

This post is a (bit modified) translation of my older post in Russian.

Let a small set of very short strings (1—4 bytes here) is given and we want to construct a dictionary with strings from this set being used as keys. A simple solution is to use a universal hash table with a generic hash function (usually the one provided by the library implementing the hash table, e.g. C++ Standard library provides some std::hash implementation for strings) such as Murmur or FNV hashes.

However such a solution is a heavyweight one in some cases, for example when keys are known in advance and are short enough. This is the case when a generic array may handle the job. For this to be true we have to find a hash function that suffers no collisions for inputs from the set of our keys, so called perfect hash function.

Another feature I want is high hash computation speed, so I am not going to use complex and costly hash functions. For example Pearson hashing is too complex for me (plus I am considering CPUs capable of fast integer hardware multiplication). Finally, I am not going to use division or remainder operations. Instead I will use an array having size equal to some power of 2 (I am OK with some cells left unused).

For strings no longer than four bytes I can use 32-bit words as keys, «NUL» character is not used in texts so one-character strings have only the least significant byte being non-zero and the other three bytes being zero, two-character strings have the least significant half non-zero and the other half zero and so on. The function casting strings to integers that way may be written in C++ as follows.

inline uint32_t to_number(const std::string &word)
{
  register uint32_t result = 0;
  switch (word.size())
  {
  case 4: result  = (uint32_t)word[3] << 24;
  case 3: result |= (uint32_t)word[2] << 16;
  case 2: result |= (uint32_t)word[1] << 8;
  case 1: result |= word[0];
  default: return result;
  }
}

The hash function I am going to construct belongs to the family defined by the following template (one has to find N and b for the given set of keys).

template <uint32_t N, unsigned b>
uint32_t ssphash(uint32_t word)
{
  return (word * N) >> b;
}

Of course, there is no guarantee that for the given set of keys this family of functions contains a perfect hash function. But due to its simplicity and small combinatorial size of the problem (for modern computers) we can try to brute-force N and b (the software was written for MSVC and uses _alloca from malloc.h and intrinsic __lzcnt from intrin.h, some CPUs do not support the latter). The size of the array (our hash table) is taken as the smallest power of 2 not less than quantity of keys.

For examples for the following set of keys (operator and punctuation lexemes of C++)

+ - ! ~ # % ^ & * ( ) / // /* */ [ ] { } | ? : ; , . && || ++ -- < > " ' <= >= = == -> .* ->* << >>

I have got N == 242653, b == 17.

Реклама

Xor delta coding

This post is a (bit modified) translation of my older post in Russian.

Delta coding is widely used as a component of different algorithms e. g. data compression or digital signal processing. Delta encoding is done through computation of differences between adjacent elements of a sequence and hence is the result of applying the first-order finite difference operator, which is a discrete analogue of a continuous differential operator. Delta decoding is done through computation of partial sums and is a discrete analogue of a continuous integration operator.

Delta encoding has the following important feature: a sequence of repeating values produces a sequence of zeroes. That made me ponder what if difference be replaced with something else conserving the mentioned property of converting sequences of repeating values into zeroes. The obvious candidate (for the case when values have fixed-size binary representation) is the bitwise exclusive or operation (xor; do other viable candidates exist?). This operation is commutative and associative. It also has the following properties (for any a):

  • a xor 0 ≡ a;
  • a xor a ≡ 0.

A corollary of this is (a xor b) xor ba for any a and any b. (This is the base of the well-known trick of swapping values of two variables without explicitly using temporary storage.)

Thus for a set of functions defined as { xora | aZ, xora(x) ≡ a xor x } we have an identity element xor0. Any element of this abelian group (with function composition operation) is an inverse to itself.

These properties made xor popular in cryptographic algorithms (is there any well-known cipher or hash that doesn’t use it?).

The following code replaces addition and subtraction in «classic» delta coding algorithm with bitwise xor.

void xor_delta_encode(char *begin, size_t n)
{
  char prev = begin[0], t;
  for (size_t i = 1; i < n; ++i)
  {
    t = begin[i];
    begin[i] ^= prev;
    prev = t;
  }
}
 
void xor_delta_decode(char *begin, size_t n)
{
  char prev = begin[0];
  for (size_t i = 1; i < n; ++i)
    prev = begin[i] ^= prev;
}

Simple testing code is available here.

This code has an amusing property: repeated xor-delta encoding leads to coincidence of prefixes of the resulting sequence and the original sequence. It can be shown on paper (due to properties of xor) that after 2n repeats we have coincidence of prefix of length 2n (or coincidence of the entire sequences if the original sequence is no longer than 2n). Therefore after 2N repeats of encoding, where N = ceil(log2(sequence length)), we have the original sequence recovered. Repeating of the inverse operation (decoding) has the same property and enumerates the same intermediate sequences but in inverse order.

Выделение выровненных блоков динамической памяти

Проблема: стандартные средства выделения блоков динамической памяти в C99 и C++14, будь то malloc и free или new и delete гарантируют выравнивание выделенных блоков, достаточное только для базовых примитивных типов (alignof(max_align_t)). Для типов данных, имеющих более жёсткие ограничения по выравниванию, например, данные SSE (16 байт) и AVX (32 байта), либо в случае когда требуется выравнивать блоки по строкам кэша или страницам памяти, нет готового стандартного способа получить корректно выровненную память. Только в стандарте C11 появилась функция aligned_alloc, которая позволяет явно указать желаемое выравнивание (число, которому должен быть кратен адрес блока). Возвращённый этой функцией указатель можно передать затем free (для освобождения) или realloc (для изменения размера блока, realloc не гарантирует сохранения выравнивания!), так же, как если бы блок был выделен вызовом malloc. К сожалению, данная функция пока не вошла в стандарт C++, из-за чего могут возникнуть проблемы с компиляцией C++ кода, использующего эту функцию.

Описанная проблема стоит давно, часто поднималась, например, на StackOverflow: раз, два. Тем более, что в C++11 были добавлены средства управления выравниванием при статическом выделении памяти (см. alignas, align, aligned_storage). Однако, почему-то динамическое выделение памяти обошли вниманием, что, конечно, является существенным недостатком для языков системного программирования. Просто удивительно, что в C это было закрыто только в 2011 году. Для решения данной проблемы с недавних пор также создана библиотека Boost.Align.

Ниже я приведу типичное решение (но не универсальное) указанной проблемы для случая, когда мы не ориентируемся на C11 и не используем Boost.

Итак, обычный выбор заключается в использовании вариантов, предлагаемых конкретными платформами (обычно Windows и POSIX), плюс, возможно, универсальный неоптимальный вариант на основе стандартных функций управления динамической памятью. Рассмотрим эти три варианта (следуя также информации из ответов на StackOverflow).

В случае платформы POSIX (_POSIX_VERSION >= 200112L) имеем функцию posix_memalign, результат которой можно освобождать с помощью стандартной функции free.

// POSIX version
#include <stdlib.h>
// возвращает код ошибки, 0 -- успех
// адрес выделенного блока записывается по указателю memptr
int posix_memalign(void **memptr, size_t alignment, size_t size);

В случае использования Windows (точнее, Microsoft Visual C++ runtime) имеем пару функций _aligned_alloc и _aligned_free (есть также _aligned_realloc и т.д.).

// MSVC version
#include <malloc.h>
void* _aligned_malloc(size_t size, size_t alignment);
void _aligned_free(void*)

Документация к компилятору Intel предлагает аналогичные функции с другими названиями.

// ICC version
#include <malloc.h>
void* _mm_malloc(size_t size, size_t alignment);
void _mm_free(void*)

Более того, в MSVC (malloc.h) _mm_malloc и _mm_free определены как макросы, раскрывающиеся в _aligned_alloc и _aligned_free, что позволяет использовать первые вместо последних и на MSVC и на ICC. То же самое касается MinGW и сборки TDM-GCC для Windows.

Если варианты, приведённые выше, не подходят, то можно выделить блок размера (запрошенный размер + размер указателя + выравнивание — min(гарантированное выравнивание, размер указателя)), выбрать в нём наименьший выровненный адрес (адрес результата) и записать адрес блока в указатель прямо перед адресом результата, чтобы затем извлечь его при удалении блока. Недостаток данного метода заключается в перерасходе памяти, который может превышать 100% в неудачных случаях (т.е. более чем двойной расход). Кроме того, может замусориваться кэш (обращение к предыдущей строке или странице для сохранения указателя на реальный блок).

// Generic version
#include <cstdlib>
#include <cstdint>
#include <cassert>

void* aligned_alloc(size_t size, size_t alignment)
{
  using namespace std;
  if (alignment < alignof(max_align_t))
  {
    // Проверим, что alignment -- степень двойки.
    const bool good_al = (alignment & (alignment - 1)) == 0;
    assert(good_al);
    if (!good_al)
      return nullptr;
    // Заменим alignment минимальным доступным значением.
    alignment = alignof(max_align_t);
  }
  else
  {
    // Проверим, что alignment / alignof(max_align_t) -- степень двойки.
    const auto ptr_al = alignment / alignof(max_align_t);
    const bool good_al = (ptr_al & (ptr_al - 1)) == 0;
    assert(good_al);
    if (!good_al) // Bad alignment value.
      return nullptr;
  }

  static const auto excess_bytes = 
    sizeof(void*) < alignof(max_align_t)? sizeof(void*): alignof(max_align_t);
  auto block = (char*)malloc((size + sizeof(void*)) + (alignment - excess_bytes));
  if (!block) // No memory allocated.
    return nullptr;

  // Вычислим смещение адреса относительно выделенного блока.
  const auto block_repr = reinterpret_cast<uintptr_t>(block);
  const auto block_offs = (alignment - (sizeof(void*) + block_repr)) & (alignment - 1);
  // Вычислим результирующий указатель.
  const auto result = block + sizeof(void*) + block_offs;
  // Сохраним адрес исходного блока.
  *(void**)(result - sizeof(void*)) = block;
  return result;
}

void aligned_free(void *ptr)
{
  using namespace std;
  if (ptr)
    free(*((void**)ptr - 1));
}

Откровенно говоря, у меня есть подозрение, что _aligned_malloc и _mm_malloc реализованы примерно так же, и их использование влечёт те же недостатки.

Проведены тесты (generic version и платформенной): MSVC2013.4 x64 (Windows), tdm-gcc 5.1 x64 (Windows), g++ 4.8.3 x64 (Linux) — многократное повторное выделение-удаление, заполнение. Код: Bitbucket.

Обобщённая функция удаления элементов из контейнера

Введение

Стандартная библиотека C++ не предлагает общего интерфейса для удаления элементов из произвольного контейнера. Тем не менее, средства метапрограммирования и принцип SFINAE позволяют реализовать такой интерфейс (например, в виде функции-шаблона) поверх стандартных компонент и выполнять выбор подходящего для переданного контейнера метода на этапе компиляции. Наша функция будет удалять элементы контейнера, удовлетворяющие произвольному предикату, переданному в виде функтора. Обычно это линейная по числу элементов контейнера операция, в случае же ассоциативных контейнеров, реализованных в виде деревьев, она может быть линеарифмической.

Далее предполагаем следующую «шапку».

#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>
using namespace std;

Реализации свободной функции для разных видов контейнеров

Контейнеры-списки реализуют желаемую функцию в виде функции-члена, которой и следует переадресовать вызов.

/// Удаляет элементы, для которых pred возвращает истину,
/// из связных списков (std::list, std::forward_list).
template <class List, class Pred> inline
void list_remove_if(List &l, Pred pred)
{
  l.remove_if(pred);
}

Прочие линейные контейнеры с изменяемым размером (вектор, дек) предполагают перемещение элементов в начало (затирая удаляемые) с сохранением относительного порядка и «отрезание хвоста» контейнера.

/// Удаляет элементы, для которых pred возвращает истину,
/// из линейных контейнеров (std::vector, std::deque).
template <class Vector, class Pred> inline
void vector_remove_if(Vector &v, Pred pred)
{
  v.erase(remove_if(begin(v), end(v), pred), end(v));
}

Ассоциативные контейнеры требуют прямого обхода с удалением конкретных элементов.

/// Удаляет элементы, для которых pred возвращает истину,
/// из ассоциативных контейнеров (разные варианты set и map).
/// В случае map предикат вычисляется для пары ключ-значение.
template <class Assoc, class Pred>
void assoc_remove_if(Assoc &a, Pred pred)
{
  for (auto it = begin(a), it_end = end(a); it != it_end; )
    if (pred(*it))
      it = a.erase(it);
    else
      ++it;
}

 
Автоматический выбор правильного варианта по виду контейнера

Автоматический выбор между представленными тремя вариантами можно организовать через банальную лобовую перегрузку функции remove_if для std::list, std::vector, std::set и т.д. Но мне не нравится этот вариант, так как он не способен автоматически «принять» нестандартные контейнеры, удовлетворяющие интерфейсу того или иного STL-контейнера — для каждого вида контейнера надо будет написать явную перегрузку.

Вместо этого мы можем заставить компилятор автоматически выбирать тот или иной вариант в зависимости от того, какие операции доступны для контейнера (сделать это позволяет SFINAE).

Вариант list_remove_if годится тогда, когда контейнер предоставляет метод remove_if (сам контейнер лучше знает как эффективно удалять из него элементы). Вариант vector_remove_if годится для контейнеров с методом удаления диапазона erase(iterator, iterator) и итератором произвольного доступа (формально достаточно итератора однонаправленного последовательного доступа («forward»), но тогда будут подходить и ассоциативные контейнеры). Наконец, вариант assoc_remove_if годится для всех контейнеров с методом iterator erase(iterator).

Далее приводится код метафункций, проверяющих наличие тех или иных операций и таким образом определяющих вид контейнера.

namespace impl
{
  /// Категория итератора для условного типа "не-итератора".
  struct Not_an_iterator_tag {};
  /// Специальный тип, означающий отсутствие типа,
  /// но позволяющий создавать объекты (в отличие от void).
  struct No_type_tag {};
  /// Условный тип "не-итератор", имитирует итератор с
  /// определёнными вложенными типами std::iterator_traits.
  struct False_iterator
    : iterator<Not_an_iterator_tag, No_type_tag> {};
 
  /// Метафункция. Извлекает тип итератора коллекции X 
  /// (использует для этого [std::]begin).
  /// Если begin(X) не определена, возвращает False_iterator.
  template <class X>
  class Collection_iterator
  {
    template <class Y>
    static False_iterator check(unsigned long, Y&&);
 
    template <class Y>
    static auto check(int, Y &&y) -> decltype(begin(y));
 
  public:
    using type = decltype(check(1, declval<X>()));
  };
 
  /// Проверяет, является ли X "коллекцией".
  /// Коллекция -- объект, для которого свободные функции
  /// begin и end возвращают итераторы с категорией,
  /// приводимой к forward_iterator_tag.
  /// Проверяется только [std::]begin.
  /// В качестве коллекции может выступать любой STL контейнер,
  /// объект std::basic_string или статический массив.
  template <class X>
  struct Is_collection
    : is_convertible<typename
        iterator_traits<typename Collection_iterator<X>::type>::iterator_category,
        forward_iterator_tag> {};
 
  ///////////////////////////////////////////////////////////////////////////// 
  /// Проверка, возможен ли вызов assoc_remove_if для объекта Cont.
  template <class Cont>
  class Assoc_remove_if_possible
  {
    template <class C>
    static false_type check(unsigned long, C&&);
 
    template <class C>
    static auto check(int, C &&c) ->
      is_convertible<
        decltype(c.erase(begin(c))),
        decltype(begin(c))>;
 
    static const bool
      erase_defined = decltype(check(1, declval<Cont>()))::value,
      is_collection = Is_collection<Cont>::value;
 
  public:
    using type = integral_constant<bool, erase_defined && is_collection>;
    static const bool value = type::value;
  };
 
  /// Проверка, возможен ли вызов vector_remove_if для объекта Cont.
  template <class Cont>
  class Vector_remove_if_possible
  {
    template <class C>
    static false_type check(unsigned long, C&&);
 
    template <class C>
    static auto check(int, C &&c) -> integral_constant<bool,
         is_convertible<typename
            iterator_traits<typename Collection_iterator<C>::type>::iterator_category,
            random_access_iterator_tag>::value
      && is_convertible<
            decltype(c.erase(begin(c), end(c))),
            decltype(begin(c))>::value>;
 
  public:
    using type = decltype(check(1, declval<Cont>()));
    static const bool value = type::value;
  };
 
  /// Проверка, возможен ли вызов list_remove_if.
  template <class Cont>
  class List_remove_if_possible
  {
    template <class C>
    static false_type check(unsigned long, C&&);
 
    // Универсальный предикат.
    struct Unipred
    {
      template <class T> 
      bool operator()(const T&) { return false; }
    };
 
    template <class C>
    static auto check(int, C &&c) ->
      decltype((void)c.remove_if(Unipred{}), true_type{});
 
  public:
    using type = decltype(check(1, declval<Cont>()));
    static const bool value = type::value;
  };
 
  ///////////////////////////////////////////////////////////////////////////// 
  // Статическая диспетчеризация вызова
  // Теги для статического выбора соответствующего варианта remove_if.
  struct Assoc_remove_if_tag {};
  struct Vector_remove_if_tag {};
  struct List_remove_if_tag {};
 
  /// Выбор подходящего тега remove_if для контейнера.
  template <class Cont>
  class Remove_if_tag
  {
    static const bool
      assoc_possible  = Assoc_remove_if_possible<Cont>::value,
      vector_possible = Vector_remove_if_possible<Cont>::value,
      list_possible   = List_remove_if_possible<Cont>::value;
 
    static_assert(assoc_possible || vector_possible || list_possible,
        "remove_if can not be called for this type");
 
  public:
    using type = conditional_t<list_possible, List_remove_if_tag,
                 conditional_t<vector_possible, Vector_remove_if_tag,
                 conditional_t<assoc_possible, Assoc_remove_if_tag,
                               void>>>;
  };

  // Перенаправление вызова remove_if на варианты для различных типов контейнеров.
  template <class Cont, class Pred> inline
  void remove_if(Cont &c, Pred pred, Assoc_remove_if_tag)
  { assoc_remove_if(c, pred); }
 
  template <class Cont, class Pred> inline
  void remove_if(Cont &c, Pred pred, Vector_remove_if_tag)
  { vector_remove_if(c, pred); }
 
  template <class Cont, class Pred> inline
  void remove_if(Cont &c, Pred pred, List_remove_if_tag)
  { list_remove_if(c, pred); }
}

/// Вызов разрешается статически в подходящий вариант в зависимости от типа контейнера.
template <class Cont, class Pred> inline
void remove_if(Cont &container, Pred pred)
{
  impl::remove_if(container, pred, typename impl::Remove_if_tag<Cont>::type{});
}

Итак, remove_if(контейнер, предикат) выбирает один из трёх способов удаления элементов, удовлетворяющих предикату, в зависимости от операций, предоставляемых контейнером. Приведённый код целиком и небольшой проверочный код: ideone, Bitbucket.

UPD. Увидел, что нечто подобное предлагалось для добавления в стандартную библиотеку. Пока оно представлено в виде расширения в пространстве имён experimental.