Эффективный буфер байт

porshe

29 марта 2015

Здравствуйте.
Пишу программу, при этом стараюсь не использовать стандартную библиотеку (ради академического интереса). В одном из модулей мне требуется более-менее эффективный буфер байт.
Для реализации написал класс byte_buff (пока ещё не дописан):
byte_buff.h

#ifndef BYTE_BUFF_H
#define BYTE_BUFF_H

/*Класс byte_buff - класс для простой работы с буфером байт
 * Память буфера выделяется блоками, что должно, в теории, быть более-менее быстро
 * Методы:
 * byte_buff(): конструктор, который создаёт пустой буфер
 * byte_buff(std::size_t): конструктор, который создаёт буфер заданного размера
 * byte_buff(const byte_buff&): конструктор копирования
 * ~byte_buff(): деструктор, освобождающий память
 *
 * std::size_t size(): размер буфера
 * std::size_t rsize(): реальный размер буфера
 *
 * void add(char): добавление байта в конец
 * void add(const char*, std::size_t): добавление данных в конец буфера
 *
 * void insert(char, std::size_t): вставка байта
 * void insert(const char*, std::size_t, std::size_t): вставка данных
 *
 * void erase(std::size_t): удаление байта
 * void erase(std::size_t, std::size_t): удаление данных
 *
 * void clear(): очистка буфера
 *
 * Оператор присваивания и доступа к элементу перегружены
 *
 * Размер блока памяти указан в статической mem_block_size
 * */

#include <cstddef>

namespace sfar
{

    class byte_buff
    {
    public:
        byte_buff();
        byte_buff( std::size_t s );
        byte_buff( const byte_buff &ob );
        ~byte_buff();

        std::size_t size() const;
        std::size_t rsize() const;

        void add( char val );
        void add( const char *data, std::size_t s_data );

        void insert( char val, std::size_t pos );
        void insert( const char *data, std::size_t s_data, std::size_t pos );

        void erase( std::size_t pos );
        void erase( std::size_t beg_pos, std::size_t end_pos );

        void clear();

        char &operator[] ( std::size_t pos );
        byte_buff &operator=( const byte_buff &ob );

        static const std::size_t mem_block_size;

    private:
        //Указатель на буфер, количество используемых байт, реальный размер
        char *buffer;
        std::size_t used_size;
        std::size_t real_size;

        //Пара вспомогательных функций

        //Добавляет в конец nblock блок памяти к буферу
        void add_mem_block( std::size_t nblock );

        //Убирает блоки памяти из конца буфера
        void del_mem_block( std::size_t nblock );

        //Расчёт необходимого количества блоков,
        //для ураковки в них заданного количества байт
        std::size_t cblocks_fb( std::size_t nbyte );
    };

}

#endif // BYTE_BUFF_H

byte_buff.cpp


#include "byte_buff.h"

//Пусть размер блока памяти будет равен 16
const std::size_t sfar::byte_buff::mem_block_size = 16;

//Пустой конструктор
sfar::byte_buff::byte_buff():
    buffer( NULL ),
    used_size( 0 ),
    real_size( 0 )
{
}

//Конструирование исходя из размера буфера
sfar::byte_buff::byte_buff( std::size_t s ):
    buffer( NULL ),
    used_size( s ),
    real_size( 0 )
{
    //Выделяем необходимое количество блоков памяти
    add_mem_block( cblocks_fb( used_size ) );
}

//Конструтор копирования
sfar::byte_buff::byte_buff( const byte_buff &ob ):
    buffer( NULL ),
    used_size( ob.used_size ),
    real_size( ob.real_size )
{
    //Эффективнее будет выделить память без add_mem_block
    buffer = new char[real_size];

    for ( std::size_t i = 0; i < used_size; i++ )
    {
        buffer[i] = ob.buffer[i];
    }
}

//Деструктор освобождает память, занятую буфером
sfar::byte_buff::~byte_buff()
{
    clear();
}

//Возвращение размера буфера
std::size_t sfar::byte_buff::size() const
{
    return used_size;
}

//Возвращение реального размера буфера
std::size_t sfar::byte_buff::rsize() const
{
    return real_size;
}

//Вставка байта в буфер
void sfar::byte_buff::add( char val )
{
    //Если места достаточно
    if ( used_size + 1 < real_size )
    {
        //Просто запихиваем символ
        buffer[used_size++] = val;
    }
    else
    {
        //Иначе добавляем блок памяти
        add_mem_block( 1 );
        buffer[used_size++] = val;
    }
}


//Полная очиста буфера
void sfar::byte_buff::clear()
{
    //Забываем всё, что было...
    used_size = real_size = 0;
    delete []buffer;
    buffer = NULL;
}


//Доступ к байту
char& sfar::byte_buff::operator[] ( std::size_t pos )
{
    return buffer[pos];
}

//Копирование
sfar::byte_buff& sfar::byte_buff::operator= ( const sfar::byte_buff &ob )
{
    clear();

    //Поступаем так же, как и в конструкторе копирования
    buffer = new char[real_size = ob.real_size];

    used_size = ob.used_size;
    for ( std::size_t i = 0; i < used_size; i++ )
    {
        buffer[i] = ob.buffer[i];
    }

    return *this;
}


//Выделение блоков памяти
void sfar::byte_buff::add_mem_block( std::size_t nblock )
{
    //Увеличиваем реальный размер
    real_size += mem_block_size * nblock;

    //Создаём новый буфер
    char *new_buf = new char[real_size];

    //Если буфер до этого был не пуст
    if ( buffer != NULL )
    {
        //Копируем в новый буфер содержимое старого
        for ( std::size_t i = 0; i < used_size; i++ )
        {
            new_buf[i] = buffer[i];
        }

        //И удаляем старый буфер
        delete []buffer;
    }

    //Перенаправляем буфер на актуальный
    buffer = new_buf;
}

//Удаление блоков памяти
void sfar::byte_buff::del_mem_block( std::size_t nblock )
{
    //Если буфер не был пуст, то нам есть что удалять
    if ( buffer != NULL )
    {
        //Если удаляются все блоки, то можно вызвать clear, так будет эфективнее
        if ( real_size <= nblock * mem_block_size )
        {
            clear();
        }
        else
        {
            //Иначе создаём новый буфер, уменьшенного размера
            char *new_buf = new char[(real_size -= nblock * mem_block_size)];

            //Копируем в него то, что осталось после удаления
            for ( std::size_t i = 0; i < real_size; i++ )
            {
                new_buf[i] = buffer[i];
            }

            //Перенаправляем буфер на актуальный
            buffer = new_buf;
        }
    }
}

//Расчёт необходимого количества блоков памяти
//Для упаковки в них заданного количества байт
std::size_t sfar::byte_buff::cblocks_fb( std::size_t nbyte )
{
    return (( nbyte / mem_block_size ) + ( (nbyte % mem_block_size)? 1:0 ));
}

Проверил код:

int main()
{
    sfar::byte_buff v;
    for ( int i = 0; i< 0xFFFFF; i++ )
        v.add(1);
}

Время работы — 20,321 сек.

Собственно, решил сранить производительность с std::vector:

int main()
{
    std::vector<char> v;
    for( int i = 0; i < 0xFFFFF; i++ )
       v.push_back(1);
}

Результаты, мягко говоря, меня удивили: время работы 0,04 сек. Такой производительности буфера я могу добится только увеличивая размер блока памяти до 0xFFFF, но врядли std::vector выделяет память такими блоками. Собственно вопрос: что такого добавляют в вектор, что он так быстро работает?

selevit

29 марта 2015

Первое — используй realloc для увеличения размера блока. Он сам позаботится о копировании данных в другой блок памяти, если фрагментация не позволяет просто выделить новые ячейки в конце блока.

По поводу блочного выделения памяти у std::vector, почитай эту статью http://alenacpp.blogspot.ru/2005/06/vector_30.html. Особенно, начиная с раздела «Коэффициент K».

И посмотри исходный код самого std::vector. Уверен, много полезного встретишь.

Croessmah

30 марта 2015

Первое — используй realloc для увеличения размера блока. Он сам позаботится о копировании данных в другой блок памяти, если фрагментация не позволяет просто выделить новые ячейки в конце блока.

Для не POD типов можем получить кучу сюрпризов и потом долго искать ошибку.

porshe, давайте просто разберем хотя бы одну строчку из функции-члена add.
Возьмем только не тип char, а некоторый «тяжелый» класс someClass

void sfar::byte_buff::add( const someClass & val )
{
        buffer[used_size++] = val; 
//У Вас объект был создан во время выделения памяти, и здесь простое присвавание. 
//Для многих объектов это будет критично.

//В std::vector этого объекта еще нет, но память под него уже выделена.
//Память в векторе выделяется аллокатором, но объекты не конструируются.
//Для std::vector эта строчка будет выглядеть примерно так:
//alloc.construct ( buffer + user_size++ , val ) ;
//функция-член у аллокатора создаст объект с помощью конструктора копий.
    }

Посмотрим также на стратегию расширения памяти. У Вас это

real_size += mem_block_size * nblock;

Судя по вызову

add_mem_block( 1 );

Память увеличивается на sizeof(someClass)*mem_block_size
То есть на постоянное значение.
В std::vector же, как правило, используются другие модели. Например,

real_size += real_size ;

при таком подходе сначала память будет выделяться малыми блоками, а потом запасы станут гигансткими.
Например вот: https://ideone.com/hPvkyq

16000
16000

16001
32000

Как видите, запас увеличился на 16000, а не на 16, т.е. Вашему вектору потребуется в 1000 раз больше перевыделений для заполнения такого участка.

porshe

30 марта 2015

В std::vector этого объекта еще нет, но память под него уже выделена

А как это достигается? Путём вызова std::malloc?

Cranium

30 марта 2015

Для не POD типов можем получить кучу сюрпризов и потом долго искать ошибку.

Croessmah, вроде в теме указано, что это буфер байт.

Croessmah

30 марта 2015

А как это достигается? Путём вызова std::malloc?

Если Вы посмотрите на объявление вектора

template < class T, class Alloc = allocator<T> > class vector;

то увидите второй параметр — это аллокатор. Его задача выделять память по запросу. В векторе задается стандартный std::allocator<T>, но Вы можете его поменять на свой. Задача аллокатора — выделять и освобождать память.

После этого в выделенной памяти можно построить объект. Для этого можно использовать placement new (это отсыл к не долгому гуглению).

Например, в std::allocator есть функция-член

template <class T> class allocator
{
    //...
    void construct ( pointer p, const_reference val );
}

реализована она примерно так:

void construct ( pointer p, const_reference val )
{
    new (p) value_type (val) ;//тот самый placement new
    //такой вид new-выражения не выделяет память(operator new для этого перегружен и просто возвращает переданный указатель), а просто строит объект по указанному адресу, вызывая конструктор объекта.
}

Память же выделяется в функции-члене allocate. Как внутри это делается — дело сугубо аллокатора. Стандартный, скорее всего, просто использует оператор new (не путать с new-выражением, это разные вещи).

Уничтожение объекта в функции-члене аллокатора

void destroy (pointer p)
{
    p->~value_type() ;
}

Естевственно, такое управление памтью очень эффективно и гибко, но в то же время намного сложнее, ведь необходимо «вручную» следить за созданием и уничтожением объектов (вызывать конструкторы и деструкторы) перед выделением и освобождением памяти.

Хм... может написать статью по аллокаторам?

Croessmah, вроде в теме указано, что это буфер байт.

Тогда смысл сравнивать его с std::vector?
Не указано как он будет использоваться.

porshe

30 марта 2015

Спасибо

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

Ответить

Вы можете использовать разметку markdown для оформления комментариев и постов. Используйте функцию предпросмотра для проверки корректности разметки.

Пожалуйста, оформляйте исходный код в соответствии с правилами разметки. Для того, чтобы вставить код в комментарий, скопируйте его в текстовое поле ниже, после чего выделите то, что скопировали и нажмите кнопку «код» в панели инструментов. Иначе ваш код может принять нечитаемый вид.

Либо производите оформление кода вручную, следующим образом:

``` #include <iostream> using namespace std; int main() { // ... } ```

Текст

Имя

Это поле — ловушка для роботов, оставьте его пустым

Предпросмотр сообщения

Ваше сообщение пусто.