VPF::C++ - производительность - Форум программистов

Mayk

Дата 5.2.2008, 18:54 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134

Ещё одна си-шная реализация против реализации maxim1000 ( по сравнению с Архимедом в ней букв мало, в варианте MAKcimа sigsegv ).

Код


#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>

enum{ DEPTH = 3 };

static char* DELIMITERS = ";:";

typedef struct buffer_s
{
    void** data;
    int count;
    int capacity;
}buffer_t;

typedef struct entry_s
{
    int entries[DEPTH];
}entry_t;

static buffer_t strings[DEPTH];

void** buffer_alloc( buffer_t* buffer )
{
    ++buffer->count;
    if( buffer->count >= buffer->capacity ){
        if( buffer->capacity )
            buffer->capacity *= 2;
        else 
            buffer->capacity = 8;
        buffer->data = realloc(buffer->data, sizeof(void*) * buffer->capacity );
    }
    return &buffer->data[buffer->count - 1];
}

static char* hash_to_string( int hash, unsigned depth )
{
    assert( depth < DEPTH );
    return strings[depth].data[hash];
}

static int string_to_hash( const char* ptr, unsigned depth )
{
    assert( depth < DEPTH );
    buffer_t* buf = &strings[depth];
    for( int i = 0; i < buf->count; ++i ){
        if( strcmp(buf->data[i], ptr) == 0 ){
            return i;
        }
    }
    char** new_string = (char**)buffer_alloc( buf );
    *new_string = strdup( ptr );
    return buf->count-1;
}

static int compar( entry_t* a, entry_t * b )
{
    for( int i = 0; i < DEPTH; ++i ){
        if( a->entries[i] < b->entries[i] ){
            return -1;
        }
        if( a->entries[i] > b->entries[i] ){
            return  1;
        }
    }
    return 0;
}


static buffer_t entries;

void sort_entries()
{
    for( int i = 0; i < entries.count; ++i ){
        for( int j = i+1; j < entries.count; ++j ){
            if( compar( entries.data[i], entries.data[j] ) < 0 ){
                entry_t* tmp = entries.data[j];
                entries.data[j] = entries.data[i];
                entries.data[i] = tmp;
            }
        }
    }
}

void add_entry(entry_t* entry)
{
    entry_t* dup = malloc(sizeof(entry_t));
    memcpy( dup, entry, sizeof(entry_t) );
    *buffer_alloc(&entries) = dup;
};


void parse_entry( char* ptr )
{
    entry_t entry;
    for( int i = 0; i < DEPTH-1; ++i ){
        int len = strcspn(ptr, DELIMITERS );
        assert( len > 0 );
        ptr[len]=0;

        entry.entries[i] = string_to_hash( ptr, i );
        ptr += 1+len;
    }

    ptr[strlen(ptr)-1] = 0;
    entry.entries[DEPTH - 1] = string_to_hash( ptr, DEPTH - 1 );
    add_entry( &entry );
}

int main( int argc, char** argv)
{
    int sort = argc==4;
    char buffer[1024];
    if( argc < 3 ){
        fprintf( stderr, "usage: %s in out [sort]\n", argv[0] );
        return 1;
    }

    FILE* f = fopen(argv[1],"r");
    int c =0;
    while( fgets(buffer, sizeof(buffer), f) ){
        parse_entry( buffer );
    }
    fclose(f);

    if( sort ){
        sort_entries();
    }

    entry_t nonEntry;
    entry_t lastEntry;
    for( int i = 0; i < DEPTH; ++i ){
        nonEntry.entries[i]=-1;
    }
    lastEntry = nonEntry;

    char* indents[DEPTH]={"","  ","    "};
    assert( indents[DEPTH-1] != NULL );

    FILE* out = fopen( argv[2], "w" );
    for( int i = 0; i < entries.count; ++i ){
        int printTail = 0;
        entry_t* entry = entries.data[i];
        for( int j = 0; j < DEPTH; ++j ){
            if( printTail || lastEntry.entries[j] != entry->entries[j] ){
                fprintf( out, "%s%s\n",indents[j], hash_to_string(entry->entries[j], j));
                printTail = 1;
                lastEntry.entries[j] = entry->entries[j];
            }
        }
    }
    fclose(out);
}

а теперь цифры(порежу всё что не real)

Код


21:49:dvl:~/src/catsort$ time ./main data /dev/null
real    0m0.021s
21:49:dvl:~/src/catsort$ time ./main data /dev/null
real    0m0.024s
21:49:dvl:~/src/catsort$ time ./main data /dev/null
real    0m0.022s
21:49:dvl:~/src/catsort$ time ./maxim1000 data /dev/null
real    0m0.009s
21:49:dvl:~/src/catsort$ time ./maxim1000 data /dev/null
real    0m0.011s
21:49:dvl:~/src/catsort$ time ./maxim1000 data /dev/null
real    0m0.009s

Итого. Вариант maxim1000 рулит. Во всех остальных букв много. В топку.

с сортировкой сишный вариант ухудшается до 0.0056-0.0080[квотить не буду, лень] секунд.

PS. заменил в maxim1000'вском варианте map'ы на unordered_map'ы. результаты ухудшились до ~0.0014.

Это сообщение отредактировал(а) Mayk - 5.2.2008, 18:58

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Void

Дата 5.2.2008, 19:12 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 11
Всего: 173

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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Mayk

Дата 5.2.2008, 19:18 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134

Цитата(Void @ 5.2.2008, 23:12

)

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

Когда речь идёт о 0.0021 против 0.0009 в течение нескольких запусков --- не думаю что погрешности здесь исказят лидера.
А ждать пока они отработают на миллион записей мне лень. 1000 записей весьма большая n.
К тому же при увеличении n мой сишный код начнёт ещё больше тормозить из-за квардатичнго построение строк через string_to_hash'а (кстати, привет profiler).
Переписывать во что-то более быстрое не получится не раздувая код(раздувать код -- лень).

Сишный по компактности с STL'ным точно не сравнится. вообщем моё имхо --- фффтопку Варианты с >100 строками.

Это сообщение отредактировал(а) Mayk - 5.2.2008, 19:24

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Любитель

Дата 5.2.2008, 19:34 (ссылка)

(нет голосов)

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

Репутация: 5
Всего: 92

Цитата(Mayk @ 5.2.2008, 19:18

)

фффтопку Варианты с >100 строками

--------------------

http://oryolalex.mybrute.com

Void

Дата 5.2.2008, 21:21 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 11
Всего: 173

В Boost 1.33, который в пакетах, нет foreach, поэтому вариант с бустом по совету Mayk пошёл в топку. Поскольку решили, что выруливает вариант maxim1000, буду сравнивать с ним.
GCC 4.1.2, Python 2.5.1, Athlon 64 3200+
Из флагов gcc только -O2.
Входной файл на 100 тыс. элементов, ~2,5 Мб.
Вывод в /dev/null.
Серии по 12 запусков, первый не учитывается.

C++ (STL): mean = 0.93, stddev = 0.04
Python: mean = 0.92, stddev = 0.09
Python (sort): mean = 1.11, stddev = 0.02

Итак, мой прогноз оправдался в точности:

Цитата(Void @ 25.1.2008, 23:47

)

у меня есть подозрение, что как минимум не сортирующий вариант будет не медленнее

Если в варианте C++ использовать unordered_map/hash_map, вероятно, будет прибавка в скорости, но вряд ли более чем двукратная.

Та-ак, на чём бы ещё написать этот тестик smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

MAKCim

Дата 5.2.2008, 22:39 (ссылка)

(голосов:1)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 8
Всего: 207

Mayk,
сортировочку у тебя можно в qsort() запихнуть
будет быстрее
в add_entry() вызывать постоянно malloc()...не слишком быстро

Добавлено через 12 минут и 38 секунд
вот мой исправленный вариант

Код


#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <string.h>
#include <time.h>

#define AREA_SIZE    (4096 << 3)
static char area[AREA_SIZE];
static char buffer[4096];
static char * pointer = buffer;
struct list_head {
    struct list_head * prev;
    struct list_head * next;
};
struct element {
    char * string;
    int offsets;
    struct list_head list;
};
struct list_head elements = {
    &elements, &elements
};
static int compare(struct element * a, struct element * b) {
    int result = strcmp(a -> string, b -> string);
    if (result > 0)
        return 1;
    else if (result < 0)
        return -1;
    else if ((result = strcmp(a -> string + (a -> offsets & 0xFFFF), b -> string + (b -> offsets & 0xFFFF))) > 0)
        return 1;
    else if (result < 0)
        return -1;
    else if ((result = strcmp(a -> string + ((a -> offsets) >> 16), b -> string + ((b -> offsets) >> 16))) > 0)
        return 1;
    else if (result < 0)
        return -1;
    return 0;
}
static void sort(void) {
    struct list_head * entrya;
    struct list_head * entryb;
    struct element * elementa;
    struct element * elementb;
    char * sw_string;
    int sw_offsets;
    for (entrya = elements.next; entrya != &elements; entrya = entrya -> next) {
        for (entryb = entrya -> next; entryb != &elements; entryb = entryb -> next) {
            elementa = (struct element*)((char*)entrya - offsetof(struct element, list));
            elementb = (struct element*)((char*)entryb - offsetof(struct element, list));
            if (compare(elementa, elementb) <= 0)
                continue;
            sw_string = elementa -> string;
            elementa -> string = elementb -> string;
            elementb -> string = sw_string;
            sw_offsets = elementa -> offsets;
            elementa -> offsets = elementb -> offsets;
            elementb -> offsets = sw_offsets;
        }
    }
}
static int find(struct element * elem) {
    struct list_head * entry = elements.next;
    struct element * a;
    for (; entry != &elements; entry = entry -> next) {
        a = (struct element*)((char*)entry - offsetof(struct element, list));
        if (!compare(elem, a))
            return 0;
    }
}
static void print(int level, struct element * elem, FILE * fs) {
    static char array[sizeof(int) * 2];
    unsigned int * ptr = (unsigned int*)array;
    ptr[0] = ptr[1] = 0x20202020;
    switch (level) {
        case 0:
            array[0] = '\0';
            fprintf(fs, "%s%s\n", array, elem -> string);
            array[0] = ' ';
        case 1:
            array[2] = '\0';
            fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) & 0xFFFF));
            array[2] = ' ';
        case 2:
            array[4] = '\0';
            fprintf(fs, "%s%s\n", array, elem -> string + ((elem -> offsets) >> 16));
    }
}
#define DELIMITER    ';'
int main(int argc, char * argv[]) {
    clock_t startTime = clock(), endTime;
    FILE * fs;
    long position, start, end;
    unsigned long last;
    char * current;
    struct element * element;
    unsigned long count;
    unsigned long shift = 1;
    printf("%d\n", startTime);
    fs = fopen(argv[1], "r");
    fseek(fs, 0, SEEK_END);
    position = ftell(fs);
    rewind(fs);
    start = 0;
    last = AREA_SIZE;
    current = area;
    count = 0;
    while (fgets(pointer, 4096, fs) != NULL) {
        if ((end = (ftell(fs) - start + sizeof(struct element))) > last) {
            last = AREA_SIZE << shift;
            current = malloc(last);
           ++shift;
        }
        start = end + start - sizeof(struct element);
        element = (struct element*)current;
        current = (char*)(element + 1);
        element -> string = current;
        element -> offsets = 0;
        for (; (*current = *pointer) != DELIMITER; ++pointer, ++current);
        *current++ = '\0';
        element -> offsets |= (current - element -> string);
        for (++pointer; (*current = *pointer) != DELIMITER; ++pointer, ++current);
        *current++ = '\0';
        element -> offsets |= ((int)(current - element -> string) << 16);
        for (++pointer; (*current = *pointer) != '\n'; ++pointer, ++current);
        *current++ = '\0';
        pointer = buffer;
        if (!find(element)) {
            current = (char*)element;
            continue;
        }
        last -= (current - element -> string + sizeof(struct element));
        elements.next -> prev = &element -> list;
        element -> list.next = elements.next;
        element -> list.prev = &elements;
        elements.next = &element -> list;
    }
    if (argc == 4 && !strcmp(argv[3], "sort"))
        sort();
    FILE * w = fopen(argv[2], "w");
    struct list_head * entry = elements.next;
    struct list_head * previos;
    struct element * entrye;
    struct element * previose;
    print(0, (struct element*)((char*)entry - offsetof(struct element, list)), w);
    for (previos = entry, entry = entry -> next; entry != &elements; previos = entry, entry = entry -> next) {    
        entrye = (struct element*)((char*)entry - offsetof(struct element, list));
        previose = (struct element*)((char*)previos - offsetof(struct element, list));
        if (!strcmp(entrye -> string, previose -> string)) {
            if (!strcmp(entrye -> string + ((entrye -> offsets) & 0xFFFF), 
                    previose -> string + ((previose -> offsets) & 0xFFFF))) {
                print(2, entrye, w);
            } else print(1, entrye, w);
        } else print(0, entrye, w);
    }
    endTime = clock();
    printf("%d\n", endTime);
    printf("%d\n", endTime - startTime);
    return 0;
}

--------------------

Mayk

Дата 6.2.2008, 07:23 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 2
Всего: 134

Цитата(MAKCim @ 6.2.2008, 02:39

)

сортировочку у тебя можно в qsort() запихнуть
будет быстрее
в add_entry() вызывать постоянно malloc()...не слишком быстро

Про сортировку соглашусь. Самое смешное что в начале так и было, но я зачем-то убрал smile

А на add_entry профайлер не советует обращать вниманин. По идее нужно string_to_hash чем-то нормальным заменить. Ибо n раз линейный поиск отстой ещё тот.

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Правила ведения Религиозных войн
	1. Уважайте собеседника 2. Собеседник != враг 3. Старайтесь воздерживаться от тем вида "Windows Rulez" или "Linux Rulez" С уважением, Smartov.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Религиозные войны \| Следующая тема »