Создание быстродействующего распределителя памяти, для std::vector или замена глобальных операций выделения памяти Опции

[AD]

Раньше был обычный массив (динамический), который содержал значения определенных параметров, прочитанных из лог-файла (широта, долгота, скорость и пр.). Сейчас сделал в виде вектора. Вместо оператора new теперь использую resize. Но так как эти операции чересчур затратные (а цикл может содержать и 100000 итераций (где каждый раз происходит выделение)), то стало необходимо сделать алгоритм немного по-другому.
Выделять память блоками. Т.е. вместо след. операций:
code1

t.params = new PARAMVALUE[rec_descr.size()];
t.words = new uint[rec_descr.size()];
memset(t.params, 0, sizeof(PARAMVALUE) * rec_descr.size());
memset(t.words, 0, sizeof(uint) * rec_descr.size());

Делать следующее:
code2

/// 0 <= num_block <= 1000
char *buff, *buff1;
if(num_block > 1000)
{
buff = new char[rec_descr.size() * BLOCKSIZE];
buff1 = new char[rec_descr.size() * BLOCKSIZE];
flag = false;
num_block = 0;
}
++num_block;
t.params = buff + rec_descr.size() * num_block;
t.words = buff1 + rec_descr.size() * num_block;

При замене на QVector code1 перешел в следующий:
code3

t.params.resize(rec_descr.size());
t.words.resize(rec_descr.size());

Как переписать code2 для использования в векторе QVector? Заранее благодарен за помощь....

Сообщение отредактировал AD - 30.6.2009, 15:08

[Влад]

Видел: http://rsdn.ru/forum/cpp.applied/930448.aspx ?

[AD]

Так, получилось ускорение с помощью массивов (пока что достаточное, но не необходимое)!
На следующей неделе все-таки доразбираюсь с распределителем памяти и постараюсь перевести решение для векторов.
Код следующий:

// h-file
/// Класс для хранения лог-файла
    class LogReader: public QObject
    {
        Q_OBJECT

    protected:
        QVector<uint> m_vBlock;                    ///< вектор прочитанных слов
        QFile* _file;                            ///< указатель на файл загрузки (лог-файл)
        char* _pm_buff;        ///< буфер памяти, который выделяется для распределения между массивами параметров
        int _pm_buff_count;                        ///< счетчик для корректного выделения памяти

private:
        bool parseBlock(LOGRECORD& t);

public:
            bool tRead();
};

cpp-code

// cpp-file

/// Чтение файла загрузки
    bool LogReader::tRead()
    {
        uint var = (uint)1E+6, index = 0;
        bool bBlock = false, file_read = false;
        QVector<LOGRECORD> log;
        time_t before_read, contin_read;        time(&before_read);

        while(_file -> read((char*)&var, sizeof(var)) > 0)
        {
            Suint adr = var % 256;
            /// Определение начала/конца одной записи и записывание ее в вектор
            switch(adr)
            {
            case 0000:
                m_vBlock.clear();
                bBlock = true;
            break;
            case 0001:
                if(bBlock)
                {
                    log.append(LOGRECORD());
                    parseBlock(log.last());
                    ChangeDateTime(log.last());
                    if(mainWindow -> iniReader() -> indexComputeParam() > 0)
                        FillCompParams(log.last());

                                        /// Сравнение временных меток
                    time(&contin_read);
                    time_t delta = contin_read - before_read;
                    if(delta > 3)
                    {
                        before_read = contin_read;
                        fillVec(log);
                        log.clear();
                    }
                    ++index;
                                  }
                              bBlock = false;
            break;
            default:
                if(bBlock) m_vBlock.append((uint)var);

if(log.size()) { fillVec(log); log.clear(); }

        /// Закрываем файл с логом
        shutdown();
        return true;
}

/// Разбор одной записи
    bool LogReader::parseBlock(LOGRECORD& t)
    {
        if(_pm_buff_count >= BUFF_SIZE) _pm_buff_count = 0;
        if(!_pm_buff_count) 
            _pm_buff = new char[rec_descr.size() * BUFF_SIZE * sizeof(PARAMVALUE)],
            memset(_pm_buff, 0, rec_descr.size() * BUFF_SIZE * sizeof(PARAMVALUE));
        t.params = reinterpret_cast<PARAMVALUE*> (_pm_buff + _pm_buff_count * rec_descr.size()
                                    * sizeof(PARAMVALUE));
        ++_pm_buff_count;
        t.name_file = strippedName(_file -> fileName());
        for(QVector<uint>::iterator iter=m_vBlock.begin(); iter!=m_vBlock.end(); ++iter)
        {
            uint var = *iter;
            Suint adr = var % 256;
            register int i = 0;
            for(paramI jter=rec_descr.begin(); jter!=rec_descr.end(); ++jter, ++i)
            {
                if(adr == (*jter) -> Address())
                {
                    t.params[i] = (*jter) -> GetValue(var);
                    t.params[i].evn = 0;
                }
                           //// anything
                        }
                }
                     /// anything

                   return true;
           }

Именно строки для ускорения кода - вот:

if(_pm_buff_count >= BUFF_SIZE) _pm_buff_count = 0;
        if(!_pm_buff_count) 
            _pm_buff = new char[rec_descr.size() * BUFF_SIZE * sizeof(PARAMVALUE)],
            memset(_pm_buff, 0, rec_descr.size() * BUFF_SIZE * sizeof(PARAMVALUE));
        t.params = reinterpret_cast<PARAMVALUE*> (_pm_buff + _pm_buff_count * rec_descr.size()
                                    * sizeof(PARAMVALUE));
        ++_pm_buff_count;

Еще раз повторюсь, что с помощью векторов я все-таки постараюсь сделать корректный код, но чуть позже!

СПАСИБО ВСЕМ ЗА ПОМОЩЬ! Еще, возможно, обращусь!

Сообщение отредактировал AD - 3.7.2009, 12:04

[AD]

Сделал распределитель памяти следующий:

allocator

#ifndef SPECIFIC_ALLOCATOR_INL
#define SPECIFIC_ALLOCATOR_INL

#include <memory>
#include <cassert>

#include <QObject>
#ifdef Q_WS_WIN
    #pragma once
    #include <windows.h>
#endif

#define ALLOC_PAGE ((64 * 1024) - sizeof(Chunk))

template <class T> class virtalloc;

template <>
class virtalloc<void>
{
public:
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;
    typedef void*       pointer;
    typedef const void* const_pointer;
    typedef void        value_type;
    template <class U>  struct rebind { typedef virtalloc<U> other; };
};

/*                   STRUCTURE OF THE MEMORY POOL
                                    
 <-----------  Chunk0 ----------- ->  <-----------  Chunk1 ----------- -> 
|                                  |                                  |
+----------------------------------+----------------------------------+
| obj0 | obj1 | obj2 | .... | objN |objN+1|objN+2| none | none | none |
+----------------------------------+----------------------------------+
^                                  ^             ^   |  ^   |  ^   |  
|       stored objects             |             |   |__|   |__|   + -> 0
|                                  |             |   
                           m_pChunks       m_pHead   Link*  Link*  Link*
*/
template <class T> class virtalloc
{
private:
    struct Link
    {
    public:
        Link* next;

    public:
        Link(): next(0) {}
        ~Link() { if(next) { delete next; next = 0; } }
    };
    struct Chunk
    {
    public:
        Chunk*    next;
        char    block[0];

    public:
        static void* operator new(size_t size, size_t block)
        { return ::VirtualAlloc(0, size + block, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE); }
        static void operator delete(void* p)
        { ::VirtualFree(p, 0, MEM_RELEASE); }
    };
    class ElementSize
    {
    public:
        ElementSize() { size = 0; }
        void set_once(size_t s) 
        { 
            assert(sizeof(T) <= s);
            if(!size) size = s;
            assert(size == s);
        }
        operator size_t()
        {            
            if(!size)  size = sizeof(T) < sizeof(Link*) ? sizeof(Link*) : sizeof(T);
            return size;
        }
    private:
        size_t  size;
    };
    
    ElementSize        m_elemSize; 
    Chunk*             m_pChunks;
    Link*              m_pHead;
    
public:
    typedef size_t     size_type;
    typedef ptrdiff_t  difference_type;
    typedef T*         pointer;
    typedef const T*   const_pointer;
    typedef T&         reference;
    typedef const T&   const_reference;
    typedef T          value_type;
    template <class U> struct rebind { typedef virtalloc<U> other; };

    virtalloc() throw(): m_pChunks(0), m_pHead(0) {}
    template <class U> virtalloc(const virtalloc<U>&) throw(): m_pChunks(0), m_pHead(0) {}
    ~virtalloc() throw()
    {
        while(m_pChunks)
        {
            Chunk* p  = m_pChunks;
            m_pChunks = m_pChunks -> next;
            delete p;
        }
    }
    pointer address(reference x) const { return &x; }    
    const_pointer address(const_reference x) const { return &x; }
    pointer allocate(size_type elements, virtalloc<void>::const_pointer hint=0)
    {
        assert(elements);

        Link* prev  = m_pHead;
        Link* first = m_pHead;
        Link* last  = m_pHead;

        size_t size = elements * m_elemSize;
        int count   = elements - 1;

        // check if we have enough free space to
        // store a continuous sequence of objects
        while(last && last -> next && count)
        {
            if(size_t((char*)last -> next -(char*)last) != m_elemSize)
            {                        
                prev  = last;
                first = last -> next;
                count = elements - 1;
            }
            else --count;
            last = last -> next;
        }
        if(!count && last)
        {
             // space found in current chunk
            if(first != m_pHead)
            {
                Link* p = last;
                while(p -> next) p = p -> next;
                p -> next = m_pHead;
                prev -> next = 0;
            }
            m_pHead = last -> next;
        }
        else // no free space => allocate one more chunk
        {
            grow(size, m_pHead);
            first = m_pHead;
            m_pHead = ((Link*)((char*)first +size-m_elemSize)) -> next;
        }
        return (pointer) first;
    }
    char* _Charalloc(size_type bytes)
    {
        m_elemSize.set_once(bytes);
        return (char*) allocate(1);
    }
    void deallocate(pointer pBlk, size_type elements)
    {
        if(!pBlk || !elements)
            return;
        
        Link* p = (Link*) pBlk;
        for(size_type n=1; n<elements; ++n)
        {
            p -> next = (Link*)((char*)p + m_elemSize);
            p = p -> next;
        }
        p -> next = m_pHead;
        m_pHead = p;        
    }
    void deallocate(void* pBlk, size_type elements)
    { deallocate(static_cast<pointer>(pBlk), elements); }
    size_type max_size() const throw()
    { return size_t(-1) / sizeof(T); }
    void construct(pointer p, const T& val)
    { ::new((void*)p) T(val); }   
    void destroy(pointer p) { p -> ~T(); }

private:    
    void grow(size_t size, Link* tail=0)
    {        
        size = (size / ALLOC_PAGE + (size % ALLOC_PAGE ? 1:0)) * ALLOC_PAGE;

        Chunk* chunk = new(size) Chunk;
        chunk -> next  = m_pChunks;
        m_pChunks    = chunk;
        
        char* first  = chunk -> block;
        char* last   = &first[(size / m_elemSize - 1) * m_elemSize];

        for(char* p=first; p<last; p+=m_elemSize)
            ((Link*)p) -> next = (Link*)(p+m_elemSize);

        ((Link*)last) -> next = tail;
        m_pHead = (Link*)first;
    }
};

template <class T> 
bool operator ==(const virtalloc<T>&, const virtalloc<T>&) throw()
{ return true; }

template <class T> 
bool operator !=(const virtalloc<T>&, const virtalloc<T>&) throw()
{ return false; }

#endif // SPECIFIC_ALLOCATOR_INL

Распределитель работает. Но работает ну очень медленно! Собственно код чтения остался тот, что я приводил до того, как снова перешел к массивам!
Скачал тестовую версию VTune посмотрел на что уходит время. Основная нагрузка на функцию grow(). Что сделать, чтобы не было такой убийственно-долгой загрузки (даже пары-тройки файлов)?
Где еще исправить и что?

Вот результаты работы профилировщика:
[attachment=697:intelVTune_results.JPG]

А вот работа профилировщика при коде, который был приведен в прошлом посте, т.е. при работе с массивами:
[attachment=698:intelVTu...ts_array.JPG]

P.S. В обоих случаях я загружал один и тот же файл (один!)!

Сообщение отредактировал AD - 6.7.2009, 17:41

[AD]

Буду очень благодарен за любую помощь. Очень требуется - так как самому тяжело найти решение проблемы.

Выяснил, что выделение памяти происходит для каждого элемента, причем функция grow вызывается при добавлении одного элемента даже по несколько раз. Видимо, надо изменить саму технологию добавления? нет? Сейчас это происходит так:

/// Структура для хранения всех значений параметров в логе
struct LOGRECORD
{
public:
    std::vector<PARAMVALUE, virtalloc<PARAMVALUE> > params;    ///< массив параметров
/////////////////////////////////////////
/////////////////////////////////////////
};


/// Чтение файла загрузки
    bool LogReader::tRead()
    {
        uint var = (uint)1E+6, index = 0;
        bool bBlock = false, file_read = false;
        QVector<LOGRECORD> log;
        time_t before_read, contin_read;        time(&before_read);

        while(_file -> read((char*)&var, sizeof(var)) > 0)
        {
            Suint adr = var % 256;
            /// Определение начала/конца одной записи и записывание ее в вектор
            switch(adr)
            {
            case 0000:
                m_vBlock.clear();
                bBlock = true;
            break;
            case 0001:
                if(bBlock)
                {
                    log.append(LOGRECORD(rec_descr.size()));
                                        ///////////////////////////
                                 }
                        default:
                if(bBlock) m_vBlock.append((uint)var);
            }
        }
        if(log.size()) { fillVec(log); log.clear(); }

        /// Закрываем файл с логом
        shutdown();
        return file_read;
    }

Сообщение отредактировал AD - 7.7.2009, 11:09