Создание быстродействующего распределителя памяти, для 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