本例一共实现了两个简单的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
网友评论