STL Allocator的简单实现及效率对比

本例一共实现了两个简单的allocator,一个使用全局的::new和::delete操作符实现的Allocator。
一个使用固定大小的内存块实现的block_allocator。
在实现一个allocator的时候，一般先要定义一堆的typedef,如下，

image.png

接着需要实现几个固定的接口方法，例如address，construct, destroy，max_size, operator==，operator!=，allocate和deallocate等。

配合allocate和deallocate方法需要实现一个特定的内存控制器，本例的内存控制器[归属于block_allocator类]，叫做block_o_memory。

本例分别使用三种不同分配器的std::string，来测试最原始的remove_ctrl算法的效率，主要想看下不同的分配器[allocator]，对std::string算法效率的影响。

代码如下，
conanfile.txt

[requires]
boost/1.72.0

[generators]
cmake

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)

project(optimize)
set(ENV{PKG_CONFIG_PATH} "$ENV{PKG_CONFIG_PATH}:/usr/local/lib/pkgconfig/")

set ( CMAKE_CXX_FLAGS "-pthread")
set(CMAKE_CXX_STANDARD 17)
add_definitions(-g)

include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake)
conan_basic_setup()

include_directories(${CMAKE_CURRENT_SOURCE_DIR}/include)
LINK_DIRECTORIES(${LINK_DIRS})

file( GLOB main_file_list ${CMAKE_CURRENT_SOURCE_DIR}/*.cpp) 
file( GLOB source_file_list ${CMAKE_CURRENT_SOURCE_DIR}/impl/*.cpp)

foreach( main_file ${main_file_list} )
    file(RELATIVE_PATH filename ${CMAKE_CURRENT_SOURCE_DIR} ${main_file})
    string(REPLACE ".cpp" "" file ${filename})
    add_executable(${file}  ${main_file} ${source_file_list})
    target_link_libraries(${file}  ${CONAN_LIBS} pthread atomic)
endforeach( main_file ${main_file_list})

old_stl_allocator_test.cpp

#include "test_driver.h"
#include "simple_allocator.h"
#include "old_block_allocator.h"
#include "stopwatch11.h"

#include <iostream>
#include <string>


using SimpleStringT = std::basic_string<
    char,
    std::char_traits<char>,
    Allocator<char>>;

using fixed_block_string = std::basic_string<
    char,
    std::char_traits<char>,
    block_allocator<char, 10>>;


// 原始的remove ctrl的三种写法 std::string, SimpleStringT, fixed_block_string
std::string remove_ctrl(std::string s) {
    std::string result;
    for(std::size_t i=0; i<s.length(); ++i) {
        if(s[i] >= 0x20) {
            result = result + s[i];
        }
    }
    return result;
}

SimpleStringT remove_ctrl_simple(std::string s) {
    SimpleStringT result;
    for(std::size_t i=0; i<s.length(); ++i) {
        if(s[i] >= 0x20) {
            result = result + s[i];
        }
    }
    return result;
}

fixed_block_string remove_ctrl_fixed_block(std::string s) {
    fixed_block_string result;
    for(std::size_t i=0; i<s.length(); ++i) {
        if(s[i] >= 0x20) {
            result = result + s[i];
        }
    }
    return result;
}

int test_fixed_block_allocator(int test_no, unsigned long multiplier) {
    typedef unsigned counter_t;
    counter_t const iterations = 100 * multiplier;

    std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07");
    std::string test("Now is the time for all good men to come to the aid of their country. ");
    s = s + s + s;
    test = test + test + test;

    std::string stdresult;
    fixed_block_string fbresult;
    SimpleStringT spresult;

    bool rc = true;

    switch(test_no) {
        default: return -1;
        case 0: return 2;

        case 1: {
            {
                void* p = block_o_memory::allocate(100);
                void* q = block_o_memory::allocate(200);
                void* r = block_o_memory::allocate(333);
                block_o_memory::deallocate(p);
                block_o_memory::deallocate(q);
                block_o_memory::deallocate(r);
                rc &= (block_o_memory::count() <= 1); 
            }

            std::cout << s.length() << " character argument to remove_ctrl()" << std::endl;
            std::cout << iterations << " iterations" << std::endl;

            {
                std::string verifier;
                verifier = remove_ctrl(s);
                rc &= (verifier.compare(test) == 0);

                SimpleStringT result1 = remove_ctrl_simple(s);
                verifier = result1.data();
                rc &= (verifier.compare(test) == 0);

                fixed_block_string result2 = remove_ctrl_fixed_block(s);
                verifier = result2.data();
                rc &= (verifier.compare(test) == 0);
            }
        }
            break;
        
        case 2: {
            {
                StopWatch sw("remove_ctrl()");
                for(counter_t i=0; i<iterations; ++i) {
                    stdresult = remove_ctrl(s);
                }
            }

            {
                StopWatch sw("remove_ctrl_simple()");
                for(counter_t i=0; i<iterations; ++i) {
                    spresult = remove_ctrl_simple(s);
                }
            }

              {
                StopWatch sw("remove_ctrl_fixed_block()");
                for(counter_t i=0; i<iterations; ++i) {
                    fbresult = remove_ctrl_fixed_block(s);
                }
            }
        }
            break;
    } 

    return (rc)? 1: 0;
}

int (*func[])(int, unsigned long) = {
    test_fixed_block_allocator,
    0
};

int main(int argc, char* argv[]) {
    test_driver(func, argc, argv);
    return EXIT_SUCCESS;
}

simple_allocator.h

#ifndef _FREDRIC_SIMPLE_ALLOCATOR_H_
#define _FREDRIC_SIMPLE_ALLOCATOR_H_

#include <limits>
#include <memory>

template <typename T>
class Allocator {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef T const* const_pointer;
    typedef T& reference;
    typedef T const& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
public:
    template <typename U>
    struct rebind {
        typedef Allocator<U> other;
    };
public:
    Allocator() {}
    ~Allocator() {}
    Allocator(Allocator const&) {}
    template <typename U>
    explicit Allocator(Allocator<U> const&) {}

    const_pointer address(const_reference r) {
        return &r;
    }

    void construct(pointer p, T const& t) {
        new (p) T(t);
    }

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

    size_type max_size() const {
        return std::numeric_limits<size_type>::max()/sizeof(T);
    }

    bool operator==(Allocator const&)  {
        return true;
    }

    bool operator!=(Allocator const& a) {
        return !operator==(a);
    } 

    pointer allocate(
        size_type count, 
        typename std::allocator<void>::const_pointer = 0
    ) {
        return reinterpret_cast<pointer>(::operator new(count* sizeof(T)));
    }

    void deallocate(pointer p, size_type) {
        ::operator delete(p);
    }

};
#endif

old_block_allocator.h

#ifndef _FREDRIC_OLD_BLOCK_ALLOCATOR_H_
#define _FREDRIC_OLD_BLOCK_ALLOCATOR_H_
#include <limits>
#include <memory>

// 快速的不好的fixed block分配器
// 实现上在查找free block时，有一个O(n)的复杂度，不好

class block_o_memory {
public:
    static unsigned const size = 8;
    static size_t const blocksize = 512;
    static void* allocate(std::size_t size);
    static void deallocate(void* p);
    static unsigned count();

private:
    static char mem_[size][blocksize];
    static bool free_[size]; // free_指示每个块是否空闲
};

template <typename T, size_t n>
class block_allocator {

public:

    typedef T value_type;
    typedef T* pointer;
    typedef T const* const_pointer;
    typedef T& reference;
    typedef T const& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    pointer address(reference r) {
        return &r;
    }

    const_pointer address(const_reference r) {
        return &r;
    }
    
    template <typename U>
    struct rebind {
        typedef block_allocator<U, n> other;
    };

public:
    block_allocator() {}
    ~block_allocator() {}
    block_allocator(block_allocator const&) {}

    template <typename U>
    explicit block_allocator(block_allocator<U, n> const&) {}

    void construct(pointer p, T const& t) {
        return new (p) T(t);
    }

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

    size_type max_size() const {
        return block_o_memory::blocksize;
    }

    bool operator==(block_allocator const& other) const {
        return true;
    }

    bool operator!=(block_allocator const& a) const {
        return !operator==(a);
    }

    pointer allocate(size_type count,
        typename std::allocator<void>::const_pointer = 0
    ) {
        return reinterpret_cast<pointer>(block_o_memory::allocate(count * sizeof(T)));
    }

    void deallocate(pointer p, size_type) {
        block_o_memory::deallocate(p);
    }
};
#endif

old_block_allocator.cpp

#include "old_block_allocator.h"
#include <exception>

char block_o_memory::mem_[block_o_memory::size][block_o_memory::blocksize];
bool block_o_memory::free_[block_o_memory::size] = {true, true, true, true, true, true, true, true};

void* block_o_memory::allocate(std::size_t size) {
    if(size <= blocksize) {
        for(unsigned i=0; i<sizeof(free_)/sizeof(free_[0]); ++i) {
            if(free_[i]) {
                free_[i] = false;
                return mem_[i];
            }
        }
    }

    throw std::bad_alloc();
}

void block_o_memory::deallocate(void* p) {
    typedef char blocktype[512];
    if(p==0) {
        return;
    }

    if(p<(void*)mem_ || p>(void*)(mem_+size)) {
        throw std::bad_alloc();
    }

    unsigned i = static_cast<blocktype*>(p) - mem_;
    free_[i] = true;
    mem_[i][0] = 0;
}

// 计算分配了多少个block, debugging用
unsigned block_o_memory::count() {
    unsigned ct = 0;
    for(unsigned i=0; i<size; ++i) {
        if(!free_[i]) {
            ct += 1;
        }
    }
    return ct;
}

程序输出如下，
可以看出，在实验次数较少时，使用自定义分配器，可能有一定的效果。但是在实验次数较多时，特别是频繁的分配释放内存的场景时，改变allocator起不到多大效果。

image.png