gcc комплексное постоянное складывание

Похоже, что у gcc есть некоторое ограничение на сложное постоянное сворачивание. Вот пример:

static inline unsigned int DJBHash(const char *str)
{
   int i;
   unsigned int hash = 5381;

   for(i = 0; i < strlen(str); i++)
   {
      hash = ((hash << 5) + hash) + str[i];   
   }

   return hash;
}

int f(void)
{   
    return DJBHash("01234567890123456");
}

При работе с уровнем оптимизации -O3 (gcc 4.8) он прекрасно разворачивает цикл в DJBHash и вычисляет значение хеш-функции для этой строки во время компиляции.

Однако при создании строки на один символ длиннее return DJBHash("012345678901234567"); он больше не сворачивает его и генерирует цикл с инструкцией условного перехода.

Я хотел бы сложить буквенную строку любой длины в ее хеш-значение в качестве постоянной времени компиляции.
Можно ли это сделать?

осветление

Мой вопрос был об оптимизации сворачивания констант на gcc (см. Заголовок - пожалуйста , не удаляйте теги gcc и компилятора)
Многие ответы здесь пытаются решить проблему с помощью шаблонов или constexpr. Полезно знать об этих опциях, и спасибо за размещение их на благо всех. Однако они прямо не отвечают на мой вопрос.

Практически я работаю над портом gcc, чтобы при необходимости я мог изменить и собрать исходный код gcc. Но я ограничен C и хотел бы решить эту проблему в этой области.

Источник

4 ответа

Вот версия, использующая constexpr, Это немного отличается от других в одном отношении - будучи рекурсивным, проще всего было, так сказать, хешировать строку обратно вперед. Например, значение, которое он дает для "abc", будет тем, что вы обычно ожидаете от "cba". Я не думаю, что это должно иметь какое-то реальное значение в использовании, если вы используете одно или другое последовательно (но, учитывая капризы хеширования, я могу ошибаться в этом).

Это действительно оценивает во время компиляции, хотя - например, мы можем использовать результаты как метки в switch заявление:

#include <iostream>

unsigned constexpr const_hash(char const *input) {
    return *input ?
           static_cast<unsigned>(*input) + 33 * const_hash(input + 1) :
           5381;
}

int main(int argc, char **argv) {
    switch (const_hash(argv[1])) {
    case const_hash("one"): std::cout << "one"; break;
    case const_hash("two"): std::cout << "two"; break;
    }
}

Очевидно, что могут быть коллизии, поэтому вы, как правило, не захотите использовать его в качестве меток оператора case - я в основном делал это, чтобы вызвать ситуацию, в которой он не сможет скомпилироваться, если результат не будет константой времени компиляции.

Редактировать: если вы заботитесь о том, чтобы алгоритм хеширования был "правильным", я думаю, это более точно (благодаря @Abyx):

unsigned constexpr const_hash(char const *input, unsigned hash = 5381) {
    return *input ?
        const_hash(input + 1, hash * 33 + static_cast<unsigned>(*input)): 
        hash;
}
Источник

OP заинтересован в свёртывании констант в C, но только для своего брата в C++: в C++14 вы можете просто поставить constexpr перед обеими функциями, и изменить цикл, чтобы компенсировать strlen() Не существует constexpr

#include<iostream>

static inline constexpr unsigned int DJBHash(const char *str)
{
   unsigned int hash = 5381;

   for(auto i = 0; i < 512; ++i) {
      if (*str == '\0') return hash;
      hash = ((hash << 5) + hash) + static_cast<unsigned int>(*str);   
   }

   return hash;
}

constexpr unsigned int f(void)
{   
    return DJBHash("01234567890123456");
}

int main()
{
    constexpr auto h = f(); 
    std::cout << std::hex << h << "\n"; // 88a7b505
}

Живой пример с использованием Clang 3.4 SVN с -std=c++1y,

ПРИМЕЧАНИЕ: текущая реализация Clang не работает должным образом с while(*str != '\0'), Вместо этого, конечный цикл 512 с условием возврата внутри делает работу.

Источник

Возможно, C++ TMP сможет это сделать. Я не уверен, хотя.

Это возможно, если вы не возражаете против использования списков литеральных переменных вместо строковых литералов:

#include <type_traits>
#include <iostream>

template<unsigned acc, char... values>
struct DJBhash_helper
     : std::integral_constant<unsigned, acc> {};

template<unsigned acc, char head, char... tail>
struct DJBhash_helper<acc, head, tail...>
     : DJBhash_helper<(acc << 5) + acc + head, tail...> {};

template<char... str>
struct DJBhash
     : DJBhash_helper<5381, str...> {};

int main()
{
    std::cout << DJBhash<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                         '0', '1', '2', '3', '4', '5', '6', '7'>::value << '\n';
}

Ideone Live Demo

Источник

Не ответ, просто еще один пункт данных.

Следующая реализация еще хуже. GCC 4.7.3 правильно применяет TCO, чтобы превратить эту реализацию в цикл, но он вычисляет только до "0" во время компиляции!

static inline unsigned int DJBHash2(const char *str, unsigned int hash) {
   return *str ? DJBHash2(str + 1, 33 * hash + *str) : hash; }

С положительной стороны, рекурсивная версия на 7 байт короче.

Кто-то еще упомянул clang, так что вот результаты для clang 3.1 -O3. Он генерирует разные коды для двух версий DJBHash, но они имеют одинаковое количество байтов. Интересно, что он преобразует сдвиг и добавить из оригинальной версии в умножение. Он оптимизирует обе версии вплоть до констант для строк длиной до 100 символов. И, наконец, код Clang на 5 байтов короче, чем самый короткий код GCC.

Источник
Другие вопросы по тегам