Вопрос к программистам на C , Исходники ядра Linux

linuxfan, вообще, все очень сильно зависит от оптимизатора. И его возможностей. Кстати, мне (как и LuckLess'у) интересно посмотреть - сколько будет оверхеда в аналогичном коде на С. Т. е. сформулируем задачку так. Нам нужно написать операцию конкатенации (даже не сложения) двух векторов. На С++ я набросал такой код:

class TestClass1
{
    std::vector<int> m_Vec;
public:
    TestClass1() {;}
    TestClass1(int v)
    {
        m_Vec.push_back(v);
    }
 
    TestClass1& operator += (const TestClass1& c)
    {
        m_Vec.insert(m_Vec.end(), c.m_Vec.begin(), c.m_Vec.end());
        return *this;
    }
 
    friend TestClass1 operator + (TestClass1 c1, const TestClass1& c2)
    {
        //std::cout << "c1 = " << &c1 << ", c2 = " << &c2 << std::endl;
        return c1 += c2;
    }
 
    void Print()
    {
        std::copy(m_Vec.begin(), m_Vec.end(), std::ostream_iterator<int>(std::cout, " "));
    }
};
int main(int argc, char**)
{
 
    TestClass1 c[5] = {
        TestClass1(1),
        TestClass1(2),
        TestClass1(3),
        TestClass1(4),
        TestClass1(5)
    };
    TestClass1 c4;
 
    c4 = c[0] + c[1] + c[2] + c[3] + c[4];
 
    c4.Print();
    return 0;
}

Как выглядел бы аналогичный код на С?

Поскольку вектора в стандартной библиотеке C нет, то выглядело бы это примерно так (valid C99):

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
 
#define ELEMENT_FMT "%i"
typedef int velement_t;
 
struct vector_t {
    size_t count;
    velement_t *data;
};
 
void vector_init(struct vector_t *self)
{
    self->count = 0; self->data = NULL;
}
 
velement_t* vector_push(struct vector_t *self,velement_t value)
{
    velement_t *old_data = self->data;
    self->data = (velement_t*)realloc(self->data,(self->count+1)*sizeof(velement_t));
    if (self->data) {
        self->data[self->count] = value;
        self->count++;
        return self->data+(self->count-1);
    } else {
        self->data = old_data;
        return NULL;
    }
}
 
struct vector_t* vector_concat(struct vector_t *self,...)
{
    va_list arg;
    int grow = 0;
    /* Precalculate number of elements being appended */
    va_start(arg,self);
    for (struct vector_t* v = va_arg(arg,struct vector_t*); v; v = va_arg(arg,struct vector_t*)) {
        grow += v->count;
    }
    va_end(arg);
    /* Append elements */
    if (grow > 0) {
        velement_t *ptr = self->data;
        self->data = (velement_t*)realloc(self->data,(self->count+grow)*sizeof(velement_t));
        if (!self->data) {
            self->data = ptr;
            return NULL;
        }
        ptr = self->data + self->count;
        va_start(arg,self);
        for (struct vector_t* v = va_arg(arg,struct vector_t*); v; v = va_arg(arg,struct vector_t*)) {
            memcpy(ptr,v->data,v->count*sizeof(velement_t));
            ptr += v->count;
        }
        va_end(arg);
        self->count += grow;
    }
    return self;
}
 
void vector_print(struct vector_t *self)
{
    putchar('{');
    for (int i=0; i<self->count; i++) {
        if (i < self->count-1) {
            printf (ELEMENT_FMT ", ",self->data[i]);
        } else {
            printf (ELEMENT_FMT, self->data[i]);
        }
    }
    puts("}");
}
 
int main()
{
    struct vector_t res,v[5];
    vector_init(&res);
    for (int i=0; i<5; i++) {
        vector_init(&v[i]);
        vector_push(&v[i],i+1);
    }
    vector_concat(&res,v,v+1,v+2,v+3,v+4,NULL);
    vector_print(&res);
    return 0;
}

Раз нам всегда точно известно, что складывать, то почему бы не сделать функцию с переменным числом аргументов? Оверхеда практически 0%. Подходит исключительно для того, что в C++ называют POD-типами. Но вроде как ставилась задача исследования рантаймового оверхеда?

Цитата linuxfan @ 28.07.06, 09:48

Раз нам всегда точно известно, что складывать, то почему бы не сделать функцию с переменным числом аргументов? Оверхеда практически 0%. Подходит исключительно для того, что в C++ называют POD-типами. Но вроде как ставилась задача исследования рантаймового оверхеда?

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

template<typename T> struct va_list_t
{
    typedef va_list_t<T> this_type;
    va_list_t(const T& v) : m_Val(&v), m_Next(NULL), m_Prev(NULL) {;}
    va_list_t(const T& v, this_type& prev) : m_Val(&v)
    {
        prev.m_Next = this;
        m_Prev = &prev;
        m_Next = NULL;
    }
 
    const T* m_Val;
    this_type* m_Next;
    this_type* m_Prev;
 
    friend this_type operator, (this_type& prev, const T& v)
    {
        return this_type(v, prev);
    }
};
 
template<typename T> va_list_t<T> my_va_list(const T& v)
{
    return va_list_t<T>(v);
}
 
TestClass1 accumulate(const va_list_t<TestClass1>& args)
{
    size_t count = 0;
    const va_list_t<TestClass1>* real_head = NULL;
    for (const va_list_t<TestClass1>* head = &args; head != NULL; real_head = head, head = head->m_Prev)
    {
        count += head->m_Val->GetContainer().size();
    }
 
    TestClass1 ret_val;
    ret_val.GetContainer().reserve(count);
    for (const va_list_t<TestClass1>* head = real_head; head != NULL; head = head->m_Next)
    {
        ret_val += *head->m_Val;
    }
    return ret_val;
}
 
int main(int argc, char**)
{
 
    TestClass1 c[5] = {
        TestClass1(1),
        TestClass1(2),
        TestClass1(3),
        TestClass1(4),
        TestClass1(5)
    };
    TestClass1 c4;
 
    c4 = accumulate((my_va_list(c[0]), c[1], c[2], c[3], c[4]));
 
    c4.Print();
 
        return 0;
}

Тут оверхед - это связывание списка, эмулирующего переменное количество аргументов. Но, ИМХО, оверхед оправдан тем, что в итоге мы точно знаем - где, что и сколько лежит. И не накосячим с точки зрения типов. Вот что будет, если я (в твоем варианте) забуду в качестве последнего параметра передать NULL?

Цитата Flex Ferrum @ 28.07.06, 10:29

Вот что будет, если я (в твоем варианте) забуду в качестве последнего параметра передать NULL?

Скорее всего, signal 11

Цитата Flex Ferrum @ 28.07.06, 10:29

Тут оверхед - это связывание списка, эмулирующего переменное количество аргументов.

А как же копирование результата (конечно, легко исправляется добавлением еще одного аргумента в accumulate).

В итоге мы пришли к тому, что я писал свой мини-вектор, а ты писал передачу переменного числа аргументов. Но, честно сказать, у меня велосипед побольше (в смысле объема кода) и пошустрее (потому что memcpy), а у тебя универсальней (потому что и не для POD покатит). В конечном итоге все равно ведь пришлось отказаться от перегрузки оператора '+', т. к. лишний оверхед, а?

Цитата linuxfan @ 28.07.06, 10:42

В конечном итоге все равно ведь пришлось отказаться от перегрузки оператора '+', т. к. лишний оверхед, а?

Не совсем так (ИМХО). Ты решил заменить "серийный" плюс (т. е. когда в одном выражении несколько операторов) на одну функцию, оптимизированную конкретно для этой задачи. Но (при этом) ты не можешь в одном выражении сделать, например, и конкатенацию и (ну предположим) векторное умножение или сложение векторов. Тебе все равно надо будет вводить временные "вектора", в которых ты будешь хранить промедуточные результаты.

Цитата linuxfan @ 28.07.06, 10:42

А как же копирование результата (конечно, легко исправляется добавлением еще одного аргумента в accumulate).

Дело в том, что ты реализовал аналог оператора +=, который модифицирует левый аргумент. А я - именно операции +, которая возвращает новый результат. В итоге я могу, например, сделать так:

c4 = accumulate((my_va_list<TestClass1>(0), 1, 2, 3, 4, 6, 7, 8, 9));

Т. е. сконкатенировать чисто константные значения (экземпляры) класса. А тебе нужен хотя бы один неконстантный.

Добавлено 28.07.06, 10:51
ЗЫ: А идею с таким переменным списком аргументов нужно будет довести до ума...

Цитата Flex Ferrum @ 28.07.06, 10:50

А я - именно операции +, которая возвращает новый результат.

Посколькольку в C за меня никто не будет заниматься уничтожением временных объектов, такая реализация конкатенации "вполне в духе времени"
Ничто не не помешает мне, например, сделать так:

vector_conctat(&res1,a,vector_concat(&res2,b,c))

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

Цитата linuxfan @ 28.07.06, 11:06

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

Ну в С++ с этим тоже не все так плохо. В С++ у тебя есть выбор - использовать временные объекты, или обходится без них. Т. е. никто мне не мешает написать так:

с4 += с[0];
c4 += c[1];
c4 += c[2];
c4 += c[3];

Таким образом я буду гарантирован от создания временных переменных (все передается по ссылке). А могу переложить работу по созданию хранению промежуточных результатов на компилятор и написать так, как было написано (c[0] + c[1] + c[2] + c[3]).