fork download 
  1. #include <iostream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <ctime>
  5. #include <cstdlib>
  6. #include <memory>
  7. #include <functional>
  8. #include <algorithm>
  9.  
  10. namespace Wide {
  11.     namespace Memory {
  12.         template<typename T> std::unique_ptr<T> MakeUnique() {
  13.             return std::unique_ptr<T>(new T);
  14.         }
  15.         // Overloads with more parameters added as necessary
  16.         template<typename T, typename Arg1> std::unique_ptr<T> MakeUnique(Arg1&& arg) {
  17.             return std::unique_ptr<T>(new T(std::forward<Arg1>(arg)));
  18.         }
  19.         class Arena {
  20.         public:
  21.             static const auto BufferSize = 20 * 1024; // Not chosen for any specific reason
  22.         private:
  23.             std::vector<std::function<void()>> destructors;
  24.             class MemoryBuffer {
  25.                 friend class Arena;
  26.                 Arena* mem_arena;
  27.                 std::unique_ptr<MemoryBuffer> next;
  28.                 char buffer[BufferSize];
  29.                 std::size_t usage;
  30.                 template<typename T> void* AllocateForNext() {
  31.                     if (!next)
  32.                         next = MakeUnique<MemoryBuffer>(mem_arena);
  33.                     return next->AllocateFor<T>();
  34.                 }
  35.                 void* AllocateForNext(std::size_t size, std::size_t alignment) {
  36.                     if (!next)
  37.                         next = Memory::MakeUnique<MemoryBuffer>(mem_arena);
  38.                     return next->AllocateFor(size, alignment);
  39.                 }
  40.             public:
  41.                 MemoryBuffer(Arena* pointer)
  42.                     : usage(0)
  43.                     , mem_arena(pointer) {
  44.                         pointer->tail = this;
  45.                 }
  46.                 void* AllocateFor(std::size_t size, std::size_t alignment) {
  47.                     if (usage + size < BufferSize) {
  48.                         if (usage % alignment != 0) {
  49.                             auto alignment_increase = alignment - (usage % alignment);
  50.                             if (usage + size + alignment_increase > BufferSize)
  51.                                 return AllocateForNext(size, alignment);
  52.                             usage += alignment_increase;
  53.                         }
  54.                         auto ptr = &buffer[usage];
  55.                         usage += size;
  56.                         return ptr;
  57.                     }
  58.                     return AllocateForNext(size, alignment);
  59.                 }
  60.                 template<typename T> void* AllocateFor() {
  61.                     static const auto size = sizeof(T);
  62.                     static const auto alignment = 8;//std::alignment_of<T>::value;
  63.  
  64.                     if (usage + size < BufferSize) {
  65.                         if (usage % alignment != 0) {
  66.                             auto alignment_increase = alignment - (usage % alignment);
  67.                             if (usage + size + alignment_increase > BufferSize)
  68.                                 return AllocateForNext<T>();
  69.                             usage += alignment_increase;
  70.                         }
  71.                         char* ptr = &buffer[usage];
  72.                         usage += size;
  73.                         return ptr;
  74.                     }
  75.                     return AllocateForNext<T>();
  76.                 }
  77.             };
  78.             std::unique_ptr<MemoryBuffer> initial_buffer;
  79.             MemoryBuffer* tail;
  80.             void UpdateListForNewOwner() {
  81.                 MemoryBuffer* head = initial_buffer.get();
  82.                 while(head) {
  83.                     head->mem_arena = this;
  84.                     head = head->next.get();
  85.                 }
  86.             }
  87.             template<typename T> struct destructor {
  88.                 T* ptr;
  89.                 void operator()() {
  90.                     ptr->T::~T();
  91.                 }
  92.                 destructor(T* other) {
  93.                     ptr = other;
  94.                 }
  95.             };
  96.         public:
  97.             void empty() {
  98.                 std::for_each(destructors.begin(), destructors.end(), [](std::function<void()>& destruct) {
  99.                     destruct();
  100.                 });
  101.                 destructors.empty();
  102.                 MemoryBuffer* buf = initial_buffer.get();
  103.                 buf->usage = 0;
  104.                 while(buf = buf->next.get()) {
  105.                     buf->usage = 0;
  106.                 }
  107.             }
  108.             Arena() {
  109.                 initial_buffer = MakeUnique<MemoryBuffer>(this);
  110.             }
  111.             Arena(Arena&& other)
  112.                 : initial_buffer(std::move(other.initial_buffer))
  113.                 , destructors(std::move(other.destructors))
  114.                 , tail(other.tail) 
  115.             {
  116.                 UpdateListForNewOwner();
  117.             }
  118.             Arena& operator=(Arena other) {
  119.                 this->swap(other);
  120.                 return *this;
  121.             }
  122.             void swap(Arena& other) {
  123.                 std::swap(initial_buffer, other.initial_buffer);
  124.                 std::swap(destructors, other.destructors);
  125.                 std::swap(tail, other.tail);
  126.  
  127.                 UpdateListForNewOwner();
  128.                 other.UpdateListForNewOwner();
  129.             }
  130.             void* Allocate(std::size_t size, std::size_t alignment = 16) {
  131.                 return tail->AllocateFor(size, alignment);
  132.             }
  133.             template<typename T> T* Allocate() {
  134.                 T* ret = new (tail->AllocateFor<T>()) T();
  135.                 destructors.push_back(destructor<T>(ret));
  136.                 return ret;
  137.             }
  138.             template<typename T, typename Arg1> T* Allocate(Arg1&& other) {
  139.                 auto mem = tail->AllocateFor<T>();
  140.                 T* ret = new (mem) T(std::forward<Arg1>(other));
  141.                 destructors.push_back(destructor<T>(ret));
  142.                 return ret;
  143.             }
  144.             ~Arena() {
  145.                 std::for_each(destructors.begin(), destructors.end(), [](std::function<void()>& destruct) {
  146.                     destruct();
  147.                 });
  148.             }
  149.         };
  150.         template<typename T> struct ArenaAllocator {
  151.             ArenaAllocator(Arena* ptr) {
  152.                 m = ptr;
  153.             }
  154.             template<typename Other> ArenaAllocator(const ArenaAllocator<Other>& other) {
  155.                 m = other.m;
  156.             }
  157.             template<typename Other> ArenaAllocator& operator=(const ArenaAllocator<Other>& other) {
  158.                 m = other.m;
  159.             }
  160.             Arena* m;
  161.             typedef T* pointer;
  162.             typedef T& reference;
  163.             typedef const T* const_pointer;
  164.             typedef const T& const_reference;
  165.             typedef T value_type;
  166.             typedef std::size_t size_type;
  167.             typedef std::size_t difference_type;
  168.  
  169.             pointer address(reference val) const {
  170.                 return std::addressof(val);
  171.             }
  172.             const_pointer address(const_reference val) const {
  173.                 return std::addressof(val);
  174.             }
  175.             template<typename Other> struct rebind {
  176.                 typedef ArenaAllocator<Other> other;
  177.             };
  178.             pointer allocate(size_type count) {
  179.                 return reinterpret_cast<pointer>(m->Allocate(count * sizeof(T), std::alignment_of<T>::value));
  180.             }
  181.             template<typename Other> pointer allocate(size_type count, const Other* hint = 0) {
  182.                 return m->Allocate(count * sizeof(T), std::alignment_of<T>::value);
  183.             }
  184.             template<typename Arg> void construct(pointer p, Arg&& arg) {
  185.                 new (p) T(std::forward<Arg>(arg));
  186.             }
  187.             void deallocate(pointer p, size_type count) {
  188.                 // NOP
  189.             }
  190.             void destroy(pointer p) {
  191.                 p->T::~T();
  192.             }
  193.             size_type max_size() const {
  194.                 return Arena::BufferSize / sizeof(T);
  195.             }
  196.         };
  197.     };
  198. };
  199.  
  200. int nofunc(int count) {
  201.         return (char)count;
  202. }
  203.  
  204. Wide::Memory::Arena arena;
  205. int allocatorfunc(int count) {
  206.     auto mem = arena.Allocate(count, 1);
  207.     auto a = (char*)mem;
  208.     a[count-1] = (char)count;
  209.     int nocheat = a[count-1];
  210.     arena.empty();
  211.     return nocheat;
  212. }
  213.  
  214. int allocafunc(int count) {
  215.         char* a = (char*)alloca(count);
  216.         a[count-1] = (char)count;
  217.         int nocheat = a[count-1];
  218.         return nocheat;
  219. }
  220. int main() {
  221.  
  222.     int count= 10000000;
  223.     int nocheat = 0;
  224.     clock_t begin = 0;
  225.  
  226.     typedef int (*funcptr)(int);
  227.     funcptr functions[3] = {nofunc, allocatorfunc, allocafunc};
  228.     char* names[3] = {"nofunc", "allocator", "alloca"};
  229.     for(int j=0; j<3; ++j) {
  230.         srand(0);
  231.         begin = clock();
  232.         nocheat = 0;
  233.         for(int i=0; i<count; ++i) {
  234.             auto size = (1+rand() % 4000);
  235.             nocheat += functions[j](size);
  236.         }
  237.         double overhead = double(clock()-begin)/CLOCKS_PER_SEC;
  238.         std::cout << names[j] << " took " << overhead << " (" << nocheat << ")\n";
  239.     }
  240.  
  241.     return 0;
  242. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In member function 'T* Wide::Memory::ArenaAllocator<T>::address(T&) const':
prog.cpp:170:24: error: 'addressof' is not a member of 'std'
prog.cpp: In member function 'const T* Wide::Memory::ArenaAllocator<T>::address(const T&) const':
prog.cpp:173:24: error: 'addressof' is not a member of 'std'
prog.cpp: In function 'int main()':
prog.cpp:228:54: warning: deprecated conversion from string constant to 'char*'
prog.cpp:228:54: warning: deprecated conversion from string constant to 'char*'
prog.cpp:228:54: warning: deprecated conversion from string constant to 'char*'
stdout 
Standard output is empty
https://ideone.com/avahI
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!