Навело вопросом про способы организации деревьев на С...
Ведь есть возможность для шаблонных деревьев типа stl перенести в объектник методы вставки — удаления нод. Достаточно передавать указатель на функцию сравнения нод (которая в свою очередь будет уметь приводить их к типу элемента дерева). Минусом является невозможность инлайнинга функторов сравнения элементов. Зато можно довольно ощутимо снизить размер сегмента кода. Вопрос в том, что же перевесит — ускорение за счет inline или cache latency. Тестирование "в лоб" показало снижение производительности в среднем процентов на 30. Но если в приложении куча деревьев разного типа, может компактность будет более предпочтительной?
Есть мнения?

Здравствуйте, sokel, Вы писали:

S>Есть мнения?
Есть мнение, что выбор "размер vs скорость" должен решаться каждый раз в зависимости от ситуации. Где-то важнее скорость, а где-то размер. Так что оба подхода (и с инлайном (C++ style) и с указателем на ф-ию (C-style)) имеют право на жизнь. Выбирать должен программист.

Здравствуйте, sokel, Вы писали:

S>Навело вопросом про способы организации деревьев на С...
S>Ведь есть возможность для шаблонных деревьев типа stl перенести в объектник методы вставки — удаления нод. Достаточно передавать указатель на функцию сравнения нод (которая в свою очередь будет уметь приводить их к типу элемента дерева).

ИМХО чем меньше вызовов функций, тем лучше. Это совсем не такое дешевое удовольствие, а если еще и на каждую вставку будет энное количество сравнений через функцию, то скорость действительно упадет.

>Минусом является невозможность инлайнинга функторов сравнения элементов. Зато можно довольно ощутимо снизить размер сегмента кода.

А зачем ? Код и так чаще всего имеет очень малый размер по сравнению с объемом данных.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>ИМХО чем меньше вызовов функций, тем лучше. Это совсем не такое дешевое удовольствие, а если еще и на каждую вставку будет энное количество сравнений через функцию, то скорость действительно упадет.

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

>>Минусом является невозможность инлайнинга функторов сравнения элементов. Зато можно довольно ощутимо снизить размер сегмента кода.

PD>А зачем ? Код и так чаще всего имеет очень малый размер по сравнению с объемом данных.

Если в приложении много вставок — удалений в деревья различных типов, для каждого из них будут сгенерированы свои шаблонные методы. В результате при очередной вставке будет меньше вероятность получить искомый кусок кода в кэшах различного уровня.

Вариант реализации — легковесная шаблонная обвязка с инлайновым поиском и вынесенными в cpp методами перебалансировки дерева. Проект большой, создать эталонную нагрузку для оценки производительности тяжело. Интересует — не задавался ли кто ранее тем же вопросом, и если да, то к каким выводам пришел.

Здравствуйте, sokel, Вы писали:

S>Навело вопросом про способы организации деревьев на С...
S>Ведь есть возможность для шаблонных деревьев типа stl перенести в объектник методы вставки — удаления нод. Достаточно передавать указатель на функцию сравнения нод (которая в свою очередь будет уметь приводить их к типу элемента дерева). Минусом является невозможность инлайнинга функторов сравнения элементов. Зато можно довольно ощутимо снизить размер сегмента кода. Вопрос в том, что же перевесит — ускорение за счет inline или cache latency. Тестирование "в лоб" показало снижение производительности в среднем процентов на 30. Но если в приложении куча деревьев разного типа, может компактность будет более предпочтительной?
S>Есть мнения?

если интересно, вот код теста:

test.cpp:

#include <stdio.h>
#include <time.h>
#include "index.h"

#define test_count 100
#define elem_count 100000

struct tree_element
{
    tree_node node;
    int key;
};
struct tree_element_order
{ inline bool operator () (const tree_element* e1, const tree_element* e2) const { return e1->key < e2->key; } };

typedef index<tree_element, offsetof(tree_element, node), tree_element_order >    idx_type;

tree_element e[elem_count];
idx_type idx;

int main()
{
    int i, j;
    for(j=0;j<elem_count;++j) e[j].key = j;
    clock_t t1, t2;
    t1 = clock();
    for(i=0;i<test_count; ++i) 
    {
        idx.clear();
        for(j=0;j<elem_count;++j) idx.insert(&e[j]);
    }
    t2 = clock();
    printf("insert: %lu ticks\n", t2 - t1);
    t1 = clock();
    for(i=0;i<test_count; ++i) 
    {
        idx.clear();
        for(j=0;j<elem_count;++j) idx.insert_inline(&e[j]);
    }
    t2 = clock();
    printf("inline insert: %lu ticks\n", t2 - t1);
    return 0;
}

index.h:

#ifndef index_h__
#define index_h__
#include <stddef.h>
#include <set>

#define rb_red 0
#define rb_black 1

struct tree_node
{
    tree_node() : parent(0), left(0), right(0), color(rb_red) {}
    tree_node*        parent;
    tree_node*        left;
    tree_node*        right;
    unsigned char    color;
    void clear() { parent = left = right = 0; color = rb_red; }
};
inline tree_node* iterate_forward(tree_node* node) 
{
    if(node->right) 
    {
        node = node->right;
        while(node->left) node = node->left;
    }
    else 
    {
        tree_node* y = node->parent;
        while(y && node == y->right){ node = y; y = y->parent; }
        if(!y || node->right != y) node = y;
    }
    return node;
}   
inline tree_node* iterate_backward(tree_node* node)  
{
    if(node->left) 
    {
        node = node->left;
        while(node->right) node = node->right;
    }
    else 
    {
        tree_node* y = node->parent;
        while (y && node == y->left){ node = y; y = y->parent; }
        node = y;
    }
    return node;
}
inline void rotate_left(tree_node*& root, tree_node* x)
{
    tree_node* y = x->right;
    x->right = y->left;
    if(y->left) y->left->parent = x;
    y->parent = x->parent;
    if(x == root) root = y;
    else if(x == x->parent->left)x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}
inline void rotate_right(tree_node*& root, tree_node* x)
{
    tree_node* y = x->left;
    x->left = y->right;
    if(y->right) y->right->parent = x;
    y->parent = x->parent;
    if(x == root) root = y;
    else if(x == x->parent->right) x->parent->right = y;
    else x->parent->left = y;
    y->right = x;
    x->parent = y;
}

typedef bool (*compare_func)(const tree_node*, const tree_node*);
tree_node* insert_node(tree_node*& root, tree_node* node, compare_func cmp);

template<typename T, size_t offset, typename order>
struct index
{
    inline static T* get_element(tree_node* node) { return (T*)((char*) node - offset); }
    inline static tree_node* get_node(T* elem) { return (tree_node*)((char*)elem + offset); }
    inline static const T* get_element(const tree_node*    node) { return (const T*)((const char*) node - offset); }
    inline static const tree_node* get_node(const T* elem) { return (const tree_node*)((const char*)elem + offset); }
    tree_node* root;
    index() : root(0) {}
    static bool static_cmp(const tree_node* n1, const tree_node* n2) { return order()(get_element(n1), get_element(n2)); }
    inline bool cmp(const tree_node* n1, const tree_node* n2) { return order()(get_element(n1), get_element(n2)); }
    void clear() { root = 0; }
    tree_node* insert_node_inline(tree_node* v);
    inline T* insert(T* v) { return get_element(insert_node(root, get_node(v), static_cmp)); }
    inline T* insert_inline(T* v) { return get_element(insert_node_inline(get_node(v))); }
};

template<typename T, size_t offset, typename order>
tree_node* index<T, offset, order>::insert_node_inline(tree_node* v)
{
    v->clear();
    tree_node* y = 0;
    tree_node* x = root;
    bool comp = true;
    while(x) { y = x; comp = cmp(v, x); x = comp?x->left:x->right; }
    if(!y){ root = v; v->color = rb_black; return v; }
    if(comp) { tree_node* z = iterate_backward(y); if(z && !cmp(z, v)) return z; y->left = v; }
    else { if(!cmp(y,v)) return y; y->right = v; }
    v->parent = y;
    x = v;
    while(x != root && x->parent->color == rb_red) 
    {
        if(x->parent == x->parent->parent->left) 
        {
            y = x->parent->parent->right;
            if(y && y->color == rb_red) 
            {
                x->parent->color = rb_black;
                y->color = rb_black;
                x->parent->parent->color = rb_red;
                x = x->parent->parent;
            }
            else 
            {
                if(x == x->parent->right) { x = x->parent; rotate_left(root, x); }
                x->parent->color = rb_black;
                x->parent->parent->color = rb_red;
                rotate_right(root, x->parent->parent);
            }
        }
        else 
        {
            y = x->parent->parent->left;
            if(y && y->color == rb_red)
            {
                x->parent->color = rb_black;
                y->color = rb_black;
                x->parent->parent->color = rb_red;
                x = x->parent->parent;
            }
            else 
            {
                if(x == x->parent->left) { x = x->parent; rotate_right(root, x); }
                x->parent->color = rb_black;
                x->parent->parent->color = rb_red;
                rotate_left(root, x->parent->parent);
            }
        }
    }
    root->color = rb_black;
    return v;
}

#endif // index_h__

index.cpp:

#include "index.h"
tree_node* insert_node(tree_node*& root, tree_node* v, compare_func cmp)
{
    // код в точности до знака повторяет insert_node_inline
}

Здравствуйте, sokel, Вы писали:

S>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>ИМХО чем меньше вызовов функций, тем лучше. Это совсем не такое дешевое удовольствие, а если еще и на каждую вставку будет энное количество сравнений через функцию, то скорость действительно упадет.

S>Код, разбухающий от обилия шаблонных методов тоже не есть хорошо.

У тебя там что, десятки типов для элемента дерева ? И вперемежку выполняются вставки в деревья разных типов ? Вряд ли. А остальное оставь диспетчеру памяти, он ненужные страницы уберет.

S>Если в приложении много вставок — удалений в деревья различных типов, для каждого из них будут сгенерированы свои шаблонные методы. В результате при очередной вставке будет меньше вероятность получить искомый кусок кода в кэшах различного уровня.

Проверять надо.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>У тебя там что, десятки типов для элемента дерева ? И вперемежку выполняются вставки в деревья разных типов ? Вряд ли. А остальное оставь диспетчеру памяти, он ненужные страницы уберет.

Именно десятки и именно вперемежку. А что в этом такого? Таймеры, индексы всех сортов по таблицам из БД и т.п. Вопрос не в том, чтобы убрать лишние страницы, вопрос в том чтобы нужная страница всегда доступна была.

Здравствуйте, sokel, Вы писали:

S>Именно десятки и именно вперемежку. А что в этом такого? Таймеры, индексы всех сортов по таблицам из БД и т.п. Вопрос не в том, чтобы убрать лишние страницы, вопрос в том чтобы нужная страница всегда доступна была.

Ну если так...

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