Оптимизация Декодирования Хаффмана


Я работаю на реализации быстрая Хаффман декодер для декодирования видео. С некоторой помощью от вас, я был в состоянии производить достойную реализацию. Однако я все еще не удовлетворены результатами. Я сделал некоторые исследования, как на переполнение стека и некоторых научных работ, однако я не нашел ничего, чтобы улучшить мой текущей реализации.

Я с помощью подстановки-таблица для декодирования. Я удалил большинство филиалов и Байт ходов (MOVZX). А также соответствие моих данных для оптимального использования кэша.

Я думаю, что я должен сам расшифровывать так быстро, как он может сделать, однако построение таблицы подстановок (build_tables2) занимает столько же времени, как и сама расшифровка.

Мой профайлер дает мне:

  • декодирование: 52%
  • построить таблицы подстановок (build_tables2): 45%

В среднем мой декодер дом ~100 таблиц за кадр (Макс 256, по одному для каждого узла в самое большое дерево), который является много, но я не понимаю, как я могу уменьшить его. 16 бит столы, кажется, речи не идет.

У кого-нибудь есть идеи о том, как я могу ускорить построение таблицы подстановок? Может я как-то кодируют какие-то дополнительные данные в рамке/"вход", которая поможет для создания таблиц?

typedef uint8_t block_type;
static const int bits_per_block = 8;
static const int values_per_block = 256;

struct node_t
{
    node_t* children; // 0 right, 1 left
    int32_t value;    // if leaf then its the value of the current node, if not leaf then its the index of the next lookup-table
    int32_t is_leaf;
};

// NOTE:
// entry is 16 bytes and will be aligned during allocation, thus "values" will always be on 16 byte alignment
struct entry 
{
    uint8_t values[bits_per_block];
    std::array<entry, values_per_block>* next_table;
    int32_t num_values;
};

typedef std::array<entry, values_per_block>     table_t;
typedef std::array<table_t, values_per_block-1> tables_t;

void build_tables2(node_t* nodes, tables_t& tables, int& table_count);

void unpack_tree(void* data, node_t* nodes);

void decode_huff(void* input, uint8_t* dest)
{
    // Initial setup
    std::shared_ptr<node_t> nodes(reinterpret_cast<node_t*>(scalable_aligned_malloc(sizeof(node_t)*(513), 64)), scalable_aligned_free); // cacheline alignment  
    memset_sse(nodes.get(), 0, sizeof(node_t)*512);

    auto data = reinterpret_cast<uint32_t*>(input); 
    size_t table_size   = *(data++); // Size is first 32 bits.
    size_t result_size  = *(data++); // Data size is second 32 bits.

    // Unpack huffman-tree.
    unpack_tree(data, nodes.get());

    if(nodes->children != nullptr)
    {           
        // BUILD LOOKUP-TABLE   

        std::shared_ptr<tables_t> tables(reinterpret_cast<tables_t*>(scalable_aligned_malloc(sizeof(tables_t), 64)), scalable_aligned_free); // cacheline alignment 

        int table_count = 0;

        // Build lookup-table from huffman-tree.
        build_tables2(nodes.get(), *tables, table_count);

        // INIT DECODING

        auto huffman_data = data + table_size/32; 
        auto ptr          = dest;
        auto end          = ptr + result_size;

        entry entry2;
        entry2.next_table = tables->data();

        // NOTE:
        // Use 2x MOVQ instead of memcpy, could use MOVDQA and MOVDQU but we only care about 64 bits, thus we use MOVQ which might be faster?
        // _mm_storel_epi64(reinterpret_cast<__m128i*>(ptr), _mm_loadl_epi64(reinterpret_cast<__m128i*>(entry))); load is aligned, store is unaligned
        // <=>
        // memcpy(ptr, entry, entry->num_values);
        //
        // The decoding loop will always be overwriting some values ahead (which haven't been decoded), this means
        // that the target memory buffer will need to have extra padding in the end to avoid access violations.

        // DECODING

        auto entry = &entry2;
        while(ptr < end)
        {
            auto elem = *(huffman_data++); // Use single mov and shift and masking, instead of 4x movzx/byte-moves

            entry = entry->next_table->data() + (elem & 0xff); // entry = &entry->next_table->at(elem & 0xff);
            _mm_storel_epi64(reinterpret_cast<__m128i*>(ptr), _mm_loadl_epi64(reinterpret_cast<__m128i*>(entry)));          
            ptr += entry->num_values;

            entry = entry->next_table->data() + ((elem >> 8) & 0xff);
            _mm_storel_epi64(reinterpret_cast<__m128i*>(ptr), _mm_loadl_epi64(reinterpret_cast<__m128i*>(entry)));          
            ptr += entry->num_values;

            entry = entry->next_table->data() + ((elem >> 16) & 0xff);
            _mm_storel_epi64(reinterpret_cast<__m128i*>(ptr), _mm_loadl_epi64(reinterpret_cast<__m128i*>(entry)));          
            ptr += entry->num_values;

            entry = entry->next_table->data() + (elem >> 24);
            _mm_storel_epi64(reinterpret_cast<__m128i*>(ptr), _mm_loadl_epi64(reinterpret_cast<__m128i*>(entry)));          
            ptr += entry->num_values;
        }
    }
    else
        memset_sse(dest, static_cast<char>(nodes->value), result_size);
}

void build_tables2(node_t* nodes, tables_t& tables, int& table_count)
{
    // Using a stack instead of function recursion helps the profiler.
    std::stack<node_t*> stack;
    stack.push(nodes);

    while(!stack.empty())
    {
        auto root = stack.top();
        stack.pop();

        auto& table = tables[root->value];

        for(int n = 0; n < values_per_block; ++n)
        {
            auto current = root;

            auto& entry = table[n];

            entry.num_values = 0;

            // Looped and branched version
            //for(int i = 0; i < 8; ++i)
            //{
            //  current = current->children + ((n >> i) & 1);       
            //  if(current->is_leaf)
            //      entry.values[entry.num_values++] = current->value;      
            //}

            // NOTE:
            //*reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            // <=>
            // entry.values[entry.num_values] = current->value;
            //
            // Avoids byte moves, the last write can overwrite the next element in the entry structure, "next_table",
            // this is not a problem since we set "next_table" below and don't care about its current value

            current = current->children + (n & 1); // +0 is left and +1 is right child      
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value; // dummy write if not leaf
            entry.num_values += current->is_leaf; // only increment if it was a leaf

            current = current->children + ((n >> 1) & 1);       
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            entry.num_values += current->is_leaf;

            current = current->children + ((n >> 2) & 1);       
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            entry.num_values += current->is_leaf;

            current = current->children + ((n >> 3) & 1);       
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            entry.num_values += current->is_leaf;


            current = current->children + ((n >> 4) & 1);       
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            entry.num_values += current->is_leaf;

            current = current->children + ((n >> 5) & 1);       
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            entry.num_values += current->is_leaf;

            current = current->children + ((n >> 6) & 1);       
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            entry.num_values += current->is_leaf;

            current = current->children + (n >> 7);     
            *reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;
            entry.num_values += current->is_leaf;

            if(!current->is_leaf)
            {
                // a non-leaf, then current->value is the next lookup-table
                if(current->value == 0)
                {
                    current->value = ++table_count;
                    stack.push(current);
                }

                table[n].next_table = &tables[current->value];
            }
            else
                table[n].next_table = &tables[0]; // All bits were used, back to root
        }   
    }
}


1739
6
задан 31 августа 2011 в 08:08 Источник Поделиться
Комментарии
1 ответ

У вас есть некоторый контроль над вход энкодера?
Если так и должно быть, если вы с дельты дерево Хаффмана, а не целое дерево для каждого кадра. Таким же образом, что алгоритм НТ применяет правила подобия закодированных данных, от кадра к кадру ХТ будет также имеют очень высокую степень сходства.

Также некоторым соображениям эффективности и платформы:
Пожалуйста, перепишите выражения формы

((n >> #) & 1)

где # - это цифра, как,

(((n & (1 << #)) != 0) ? 1 : 0)

Время компиляции против выполнить расчет времени всегда будет быстрее.

*reinterpret_cast<int32_t*>(entry.values + entry.num_values) = current->value;

Зависит от Little архитектуры прямым. Предпочитаю исправлять по-быстрому.

auto* next_value = entry.values; // get the starting value element address
...
*next_value = static_cast<uint_8>(current->value); // set its value
next_value += current->is_leaf;
...
// at the end of the loop unrolling do this calculate num_value
// from the offset, thus avoiding multiple dereferences of the struct member
entry.num_values = next_value - entry.values;

4
ответ дан 10 сентября 2011 в 07:09 Источник Поделиться