Created
March 26, 2018 19:12
-
-
Save kvk1920/02986d4bcef67c2199091cc2ac36522e to your computer and use it in GitHub Desktop.
Ломанный англо-саксонский + работает без дебаг-вывода в 1.5 раз дольше стандартного аллокатора. Ну и ещё могу сказать точно: аллокаторы копируются, в них можно хранить инфу. А ещё практика показала, что в качестве WORD лучше всего брать int или long.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <memory> | |
#include <iostream> | |
#include <fstream> | |
#include <list> | |
/* | |
* If function isn't safe, its name looks like a "__FunctionName" | |
*/ | |
namespace VDebugTools { | |
template <typename Function> | |
inline void VRep(size_t n, Function f) { | |
/* | |
* It repeats function f() n times. | |
*/ | |
for (size_t i(0); i < n; ++i) | |
f(); | |
} | |
std::ofstream ferr("log.txt");//log file | |
class { | |
/* | |
* It's global class for debug output. | |
* VDbg(a, b, c) ~ ferr << a << b << c << std::endl | |
*/ | |
private: | |
std::ostream& ostream_ = ferr; //You can fast change error stream to std::cerr by "= std::cerr" | |
size_t indent_size_ = 0; | |
bool on_ = false; //Set this car false if you want turn off debug output. | |
template <typename T> | |
void Print(const T& object) { | |
ostream_ << object; | |
} | |
template <typename T, typename ...Args> | |
void Print(const T& object, const Args& ...args) { | |
Print(object); | |
Print(args...); | |
} | |
public: | |
void IIndent(size_t n = 1) { indent_size_ += n; } //Increase size of indent | |
void DIndent(size_t n = 1) { indent_size_ -= n; } //... | |
template <typename ...Args> | |
void operator()(const Args& ...args) { | |
if (on_) { | |
VRep(indent_size_, [this](){ ostream_ << " "; }); | |
Print(args...); | |
ostream_ << std::endl; | |
} | |
} | |
template <typename ...Args> | |
void In(const Args& ...args) { | |
operator ()(args...); | |
IIndent(); | |
} | |
template <typename ...Args> | |
void Out(const Args& ...args) { | |
DIndent(); | |
operator ()(args...); | |
} | |
} VDbg; | |
} | |
namespace VDebugToolsOff { | |
struct { | |
template <typename ...Args> | |
void operator ()(const Args ...) {} | |
template <typename ...Args> | |
void In(const Args ...) {} | |
template <typename ...Args> | |
void Out(const Args ...) {} | |
} VDbg; | |
} | |
/* <----------------------------------------------------------------------------> */ | |
//using VDebugToolsOff::VDbg; | |
namespace MemoryTools { | |
typedef long WORD; | |
const size_t WORD_LENGTH = sizeof (WORD); | |
class MemoryBlock { | |
private: | |
size_t used_, size_; | |
WORD* buffer_; | |
public: | |
MemoryBlock(const MemoryBlock&) = delete; //Do you realy want copy this l a r g e block? | |
MemoryBlock(MemoryBlock&&) = delete; | |
MemoryBlock& operator =(const MemoryBlock&) = delete; | |
MemoryBlock& operator =(MemoryBlock&&) = delete; | |
explicit MemoryBlock(size_t n) : | |
used_(0), size_(n), | |
buffer_(reinterpret_cast<WORD*>(::operator new[](n * sizeof(WORD)))){ | |
//VDbg("Created new MBlock ", this, " with ", n, " words"); | |
} //O(malloc) | |
~MemoryBlock() { | |
//VDbg.In("Try to destruct MBlock ", this, " ..."); | |
::operator delete[](buffer_); | |
//VDbg("Buffer cleared"); | |
//VDbg.Out("MBlock deleted"); | |
} //O(free) | |
size_t size() const { return size_; } //O(1) | |
bool CanAllocate(size_t bytes) { return (size_ - used_) * WORD_LENGTH >= bytes; } //O(1) | |
void* New(size_t bytes) { //O(1) | |
//VDbg.In("In MBlock ", this, " allocating ", bytes, " bytes..."); | |
size_t number_of_words = (bytes % WORD_LENGTH == 0) | |
? bytes / WORD_LENGTH | |
: bytes / WORD_LENGTH + 1; | |
//VDbg("It's ", number_of_words, " words"); | |
used_ += number_of_words; | |
void* result = reinterpret_cast<void*>(buffer_ + used_ - number_of_words); | |
//VDbg.Out("Memory Allocated"); | |
return result; | |
} | |
}; | |
template <typename T> | |
class DynamicArrayOfPointers { | |
/* | |
* It's a dynamic (only expansive) storage of pointers. | |
* You can put here ONLY a pointers to a SINGLE(no C-style array) object. | |
*/ | |
private: | |
T** buffer_; | |
size_t used_, size_; | |
void Reallocate() { //O(malloc + used_) | |
//VDbg.In("Array ", this, " reallocating..."); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
T** new_buffer = reinterpret_cast<T**>(::operator new[](size_ * 2 * sizeof (T*))); | |
//VDbg("New buffer created"); | |
std::copy(buffer_, buffer_ + used_, new_buffer); //We copy (not move) it because it just pointers | |
//VDbg("Data copied"); | |
::operator delete[](buffer_); | |
//VDbg("Old buffer deleted"); | |
buffer_ = new_buffer; | |
size_ *= 2; | |
//VDbg("Current size: ", size_); | |
//VDbg.Out("Array reallocated"); | |
} | |
bool CanAllocate() { //O(1) | |
return used_ != size_; | |
} | |
void __DeleteData() { | |
//VDbg.In("Array's data of array ", this, " deleting..."); | |
::operator delete[](buffer_); | |
buffer_ = nullptr; | |
//VDbg.Out("Array's data deleted"); | |
} | |
void __ResetData() { //Clear data without deleting | |
//VDbg.In("Array's data of array ", this, " resetting..."); | |
used_ = 0; | |
size_ = 1; | |
buffer_ = reinterpret_cast<T**>(::operator new[](sizeof(T*))); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
//VDbg.Out("Data resetted"); | |
} | |
public: | |
DynamicArrayOfPointers(const DynamicArrayOfPointers& other) : //O(other.used_ + malloc) | |
used_(other.used_), size_(other.size_) { | |
//VDbg.In("Creating array ", this, " by copy of ", &other, " ..."); | |
buffer_ = reinterpret_cast<T**>(::operator new[](size_ * sizeof(T*))); | |
std::copy(other.buffer_, other.buffer_ + other.used_, buffer_); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
//VDbg.Out("Array Created"); | |
} | |
DynamicArrayOfPointers(DynamicArrayOfPointers&& other) : //O(1) | |
buffer_(other.buffer_), used_(other.used_), size_(other.size_) { | |
//VDbg.In("Creating array ", this, " by move of ", &other, " ..."); | |
other.__ResetData(); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
//VDbg.Out("Array Created"); | |
} | |
DynamicArrayOfPointers& operator =(DynamicArrayOfPointers&& other) {//O(1) | |
//VDbg.In("Moving pointers from ", &other, " to ", this, " ..."); | |
__DeleteData(); | |
used_ = other.used_; | |
size_ = other.size_; | |
buffer_ = other.buffer_; | |
other.__ResetData(); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
//VDbg.Out("Move done"); | |
return *this; | |
} | |
DynamicArrayOfPointers& operator =(const DynamicArrayOfPointers& other) { //O(size...) | |
//VDbg.In("Copiing pointers from ", &other, " to ", this, " ..."); | |
__DeleteData(); | |
used_ = other.used_; | |
size_ = other.size_; | |
buffer_ = reinterpret_cast<T**>(::operator new[](size_ * sizeof(T*))); | |
std::copy(other.buffer_, other.buffer_ + other.used_, buffer_); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
//VDbg.Out("Copy done"); | |
return *this; | |
} | |
DynamicArrayOfPointers() { | |
//VDbg.In("Creating array ", this, " ..."); | |
__ResetData(); | |
//VDbg.Out("Array created"); | |
} | |
~DynamicArrayOfPointers() { | |
//VDbg.In("Destroing array ", this, " ..."); | |
__DeleteData(); | |
//VDbg.Out("Array deleted"); | |
} | |
size_t size() const { return used_; } //O(1) | |
T& operator[](size_t i) { return *buffer_[i]; } //O(1) | |
const T& operator[](size_t i) const { return *buffer_[i]; } //O(1) | |
T& back() { return *buffer_[used_ - 1]; } //O(1) | |
const T& back() const { return *buffer_[used_ - 1]; } //O(1) | |
template <typename ...Args> //~O(1) | |
void emplace_back(Args&& ...args) { | |
//VDbg.In("Creating element at array ", this, " ..."); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
if (!CanAllocate()) | |
Reallocate(); | |
//VDbg("Current used: ", used_); | |
//VDbg("Current size: ", size_); | |
buffer_[used_++] = new T(std::forward<Args>(args)...); | |
//VDbg.Out("Element created"); | |
} | |
}; | |
class MemoryStack { | |
private: | |
DynamicArrayOfPointers<MemoryBlock> buffer_; | |
public: | |
MemoryStack(const MemoryStack&) = delete; | |
MemoryStack& operator =(const MemoryStack&) = delete; | |
MemoryStack(MemoryStack&& other) : buffer_(std::move(other.buffer_)) {} | |
MemoryStack& operator =(MemoryStack&& other) { | |
//VDbg.In("Moving Stack from ", &other, " to ", this, " ..."); | |
buffer_ = std::move(other.buffer_); | |
//VDbg.Out("Stack moved"); | |
return *this; | |
} | |
MemoryStack() { | |
//VDbg.In("Creating new Stack ", this, " ..."); | |
buffer_.emplace_back(256); | |
//VDbg.Out("Stack created"); | |
} | |
~MemoryStack() { | |
//VDbg("Stack ", this, " deleted"); | |
} | |
void* New(size_t bytes) { | |
//VDbg.In("Allocating ", bytes, " bytes at stack ", this, " ..."); | |
for (size_t i(0); i < buffer_.size(); ++i) | |
if (buffer_[i].CanAllocate(bytes)) | |
{ | |
//VDbg.Out("Memory allocated"); | |
return buffer_[i].New(bytes); | |
} | |
//VDbg("Free block hasn't found, creating new blocks..."); | |
while (!buffer_.back().CanAllocate(bytes)) | |
buffer_.emplace_back(buffer_.back().size() * 2); | |
void* result = buffer_.back().New(bytes); | |
//VDbg.Out("Memory alocated"); | |
return result; | |
} | |
}; | |
} | |
namespace SmartPointerTools { | |
template <typename T> | |
struct LinkCounter { | |
size_t counter; | |
T object; | |
template <typename ...Args> | |
LinkCounter(Args&& ...args) : counter(0), object(std::forward<Args>(args)...) {} | |
}; | |
template <typename T> | |
void AddLink(LinkCounter<T>* data) { if (data) ++data->counter; } | |
template <typename T> | |
void RemoveLink(LinkCounter<T>* data) { | |
if (data == nullptr) | |
return; | |
if (--data->counter == 0) | |
delete data; | |
} | |
} | |
template <typename T> | |
class SmartPointer { | |
private: | |
SmartPointerTools::LinkCounter<T>* data_; | |
public: | |
explicit SmartPointer(SmartPointerTools::LinkCounter<T>* data) : | |
data_(data) { | |
SmartPointerTools::AddLink(data_); | |
} | |
SmartPointer() : data_(nullptr) {} | |
SmartPointer(const SmartPointer& other) : | |
data_(other.data_) { | |
SmartPointerTools::AddLink(data_); | |
} | |
SmartPointer(SmartPointer&& other) : | |
data_(other.data_) { | |
other.data_ = nullptr; | |
} | |
SmartPointer& operator =(const SmartPointer& other) { | |
SmartPointerTools::RemoveLink(data_); | |
data_ = other.data_; | |
SmartPointerTools::AddLink(data_); | |
} | |
SmartPointer& operator =(SmartPointer&& other) { | |
SmartPointerTools::RemoveLink(data_); | |
data_ = other.data_; | |
other.data_ = nullptr; | |
return *this; | |
} | |
~SmartPointer() { SmartPointerTools::RemoveLink(data_); } | |
T& operator *() { return data_->object; } | |
const T& operator *() const { return data_->object; } | |
T* operator ->() { return &data_->object; } | |
explicit operator bool() | |
{ | |
return data_ != nullptr; | |
} | |
SmartPointer(std::nullptr_t) : data_(nullptr) {} | |
}; | |
template <typename U, typename ...Args> | |
inline SmartPointer<U> Make(Args&& ...args) { | |
return SmartPointer<U>(new SmartPointerTools::LinkCounter<U>(std::forward<Args>(args)...)); | |
} | |
template <typename T> | |
class StackSmartAllocator { | |
public: | |
SmartPointer<MemoryTools::MemoryStack> pool_; | |
typedef T value_type; | |
typedef T* pointer; | |
typedef const T* const_pointer; | |
typedef T& reference; | |
typedef const T& const_reference; | |
template <typename U> | |
struct rebind { typedef StackSmartAllocator<U> other; }; | |
explicit StackSmartAllocator(decltype(pool_) pool = nullptr) : pool_(pool) { | |
if (!pool_) | |
pool_ = Make<MemoryTools::MemoryStack>(); | |
} | |
T* allocate(size_t n) { | |
return reinterpret_cast<T*>(pool_->New(n * sizeof(T))); | |
} | |
void deallocate(T*, size_t) {} | |
template <typename U> | |
StackSmartAllocator(const StackSmartAllocator<U>& other) : pool_(other.pool_) { | |
if (!pool_) | |
pool_ = Make<MemoryTools::MemoryStack>(); | |
} | |
template <typename U, typename ...Args> | |
void construct(U *p, Args&& ...args) { | |
new(p) U(std::forward<Args>(args)...); | |
} | |
template <typename U> | |
void destroy(U *p) { | |
p->~U(); | |
} | |
}; | |
template <typename T> | |
class StackAllocator { | |
public: | |
MemoryTools::MemoryStack* pool_; | |
typedef T value_type; | |
typedef T* pointer; | |
typedef const T* const_pointer; | |
typedef T& reference; | |
typedef const T& const_reference; | |
template <typename U> | |
struct rebind { typedef StackAllocator<U> other; }; | |
explicit StackAllocator(decltype(pool_) pool = nullptr) : pool_(pool) { | |
if (!pool_) | |
pool_ = new MemoryTools::MemoryStack(); | |
} | |
T* allocate(size_t n) { | |
return reinterpret_cast<T*>(pool_->New(n * sizeof(T))); | |
} | |
void deallocate(T*, size_t) {} | |
template <typename U> | |
StackAllocator(const StackAllocator<U>& other) : pool_(other.pool_) { | |
if (!pool_) | |
pool_ = Make<MemoryTools::MemoryStack>(); | |
} | |
template <typename U, typename ...Args> | |
void construct(U *p, Args&& ...args) { | |
new(p) U(std::forward<Args>(args)...); | |
} | |
template <typename U> | |
void destroy(U *p) { | |
p->~U(); | |
} | |
}; | |
void f1() | |
{ | |
double start = clock(); | |
std::list<int, StackSmartAllocator<int>> list; | |
for (int i(0); i < 100000; ++i) | |
list.push_back(i); | |
list.clear(); | |
std::cout << clock() - start << std::endl; | |
} | |
void f2() | |
{ | |
double start = clock(); | |
std::list<int> list; | |
for (int i(0); i < 100000; ++i) | |
list.push_back(i); | |
list.clear(); | |
std::cout << clock() - start << std::endl; | |
} | |
void f3() | |
{ | |
double start = clock(); | |
std::list<int, StackAllocator<int>> list; | |
for (int i(0); i < 100000; ++i) | |
list.push_back(i); | |
list.clear(); | |
std::cout << clock() - start << std::endl; | |
} | |
int main() | |
{ | |
f1(); | |
f2(); | |
f3(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment