Попадна ми едно предложение за новия стандарт (С++14), масив чиито размер не може да се променя след като бъде създаден, но пък размера се определя runtime – dynarray.
С две думи – идеята е да ползва stack memory (когато поисканата памет не е твърде много), а в другите случаи да се ползва heap memory. Целта е и всякакви други контейнери го ползват, а резултата ще е повишена ефективност.
Разбира се, всичко това да се случва само в рамките на scope на функция (защото това е lifetime-a на stack memory).
Възможно приложение на тази структура : да речем имате multithreaded scanline render engine и всяка нишка има нужа от pixel buffer. Ако картинката е малка и се rend-ва бързо можем да ползваме stack mem, ако е голяма и се ренди бавно – heap (overhead-а от new[] ще е пренебрежим). (а можем да алокираме pixel buffer преди rend-a и да ползваме него, но да речем че не ни се занимава с това).
Сега, възниква въпроса, можем ли да имплементираме dynarray в С++11.
Ето oпитите, които направих и заключенията до които стигнах.
Единственото, което не е много ясно е как да алокираме динамично памет на стека.
Опция 1.
Заделяме костантно памет в обекта, ползваме нея ако стига, в противен случай – heap-a.
|
1 2 3 4 5 6 7 8 9 10 11 |
template<typename T, size_t maxBytesOnStack> struct dyn_array { dyn_array(int elementsCount) { if (elementsCount*sizeof(T) > maxBytesOnStack) //use heap mem else //use stack mem } uint8 stackMemory[maxBytesOnStack]; T* heapMemory; }; |
Това работи. Проблема е, че дори и да ползваме heap memory, пак имаме overhead-a от maxBytesOnStack на стека. А това не е приемливо, защото се борехме за performance и memory.
Опция 2.
Заделяме споделене памет за всички dyn_array обекти, когато ползваме stack memory търсим в нея с custom allocator. Ако няма място – ползваме heap.
|
1 2 3 4 5 6 7 8 9 10 11 |
static const char sharedMemory[1024*1024*1024]; template<typename T, size_t maxBytesOnStack> struct dyn_array { dyn_array(int elementsCount):ptr(nullptr) { if (elementsCount*sizeof(T) <= maxBytesOntStack) ptr = customAllocatorGetMemory(elementsCount) if (!ptr) //use heap memory } T* ptr; }; |
Проблема тук е, че трябва да подържаме допълнителна структура от данни, за да може customAllocator-a да работи, имаме overhead от търсенето в него. От време на време трябва да извършваме “поддръжката” му и да сливаме парчетата които са едно до друго, може да получим фрагментация, имплементацията е сложна. Та трябва да има и по-добър начин.
Oпция 3.
Можем да ползваме функцията alloca(size_t bytesCount), която прави точно това – алокира памет на стека. Тази памет още повече не се освобождава при излизане от scope, а чак при излизане от функцията, която е направила извикването. Тоест, този код crash-ва със stackoverflow :
|
1 |
for (size_t i = 1; i < (1 << 31); ++i) alloca(i << 1); |
Ето и какво бихме написали с alloca
|
1 2 3 4 5 6 7 8 9 10 |
template <typename T, size_t maxBytesOnStack> struct dyn_array { dyn_array(int elementsCount) { if (elementsCount*sizeof(T) > maxBytesOnStack> ptr = (T*)malloc(elementsCount*sizeof(T)); else ptr = (T*)alloca(elementsCount*sizeof(T)); }//(1) T* ptr; } |
Това компилирано с clang3.1 и с прости тестове работи. Но работи заради чист късмет – dyn_array() освен конструктор е и функция, и в (1) заделената памет с alloca() спира да я има.
Опция 4.
Да се опитаме да ползваме С++11 за да излъжем компилатора 🙂
Ще оставим една член-данна на класа от тип функция, а нея ще инициализираме с ламбда, която заделя статична памет и връща указател към нея (tnx to Komitov за идеята).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
template<typename T, size_t maxBytesOnStack> struct dyn_array { dyn_array(int elementsCount) { if (elementsCount * sizeof(T) <= maxBytesOnStack) { f = [](){ T data[maxBytesOnStack];//(2) return (T*)data; }; ptr = f(); } else ptr = (T*)malloc(elementsCount * sizeof(T)); } T* ptr; std::function<T*()> f; }; |
Сега, ясно е че имаме overhead oт това че заделяме maxBytesOnStack всеки път, вместо elementsCount*sizeof(T). А и не можем да зачистим статичната памет (2).
Опитите да го излъжа с връщане на const&, ползването на extension-a на gcc (int i = 42; int arr[i]) и др. не завършиха успешно.
Но пък написах този ред код докато пробвах всякаквите там неща 🙂
std::function < const T(&())[maxBytesOnStack] > (lambda която връща ref към С масив).
Все още обаче имам някакви надежди, че е възможно да се напише hack с такава ламбда.
Опция 5.
Опция 5. е Опция 3., с тази разлика че статичната памет се заделя където трябва (в извикващата функция). Освен това кода е по обширен
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
namespace codebg { //kbytes to bytes constexpr size_t operator"" _kb(unsigned long long b) noexcept { return 1024*b; } //mbytes to bytes constexpr size_t operator"" _mb(unsigned long long b) noexcept { return 1024_kb*b; } //if more than this amount of mem is requested, heap will be used static const auto DYN_ARRAY_MAX_BYTES_ON_STACK = 1024_kb; //trying to mimic operator new() when using dyn_array struct dyn_array_throw_policy { static void check_bad_alloc(void* ptr) { if (!ptr) throw std::bad_alloc(); } }; //noexcept version struct dyn_array_no_throw_policy { static void check_bad_alloc(void* ptr) noexcept { } }; //simple array struct, that can use stack or heap memory. //Use as if it uses stack mem aways. //do *not* return this as a result (or out param) of a function or method. template<typename T, size_t maxBytesOnStack=DYN_ARRAY_MAX_BYTES_ON_STACK, typename exception_policy=dyn_array_no_throw_policy> struct dyn_array { //if memory is nullptr, heap mem will be used; //else, memory will be used - it should be stack allocated; //consider initalizer_list version and one without 3rd param. explicit dyn_array(T* memory, size_t elementsCount=1, const T& value=T()) noexcept( noexcept(exception_policy::check_bad_alloc(nullptr)) && noexcept(T()) && noexcept(T(T())) ) : ptr(memory), count(elementsCount) { allocMem(); for (auto i = 0; i < size(); ++i) new (ptr+i) T(value); } //move ctor so we can fast move the constructed object dyn_array(dyn_array&& rhs) noexcept { ptr = rhs.ptr; count = rhs.count; useHeap = rhs.useHeap; rhs.ptr = nullptr; rhs.count = size_t(0); rhs.useHeap = size_t(0); } //asure we call dtors ~dyn_array() { freeMem(); } size_t size() const noexcept { return count; } bool using_heap() const noexcept { return useHeap == 1; } T& operator[](size_t i) noexcept { return ptr[i]; } const T& operator[](size_t i) const noexcept { return ptr[i]; } dyn_array(const dyn_array& rhs)=delete; dyn_array& operator=(const dyn_array& rhs)=delete; dyn_array& operator=(const dyn_array&&)=delete; private: //calls d'tors and clears mem if heap is used void freeMem() noexcept { if (ptr) { for (auto i = 0; i < size(); ++i) (ptr+i)->~T(); if (using_heap()) free(ptr); } } //if heap is used, allocs memory void allocMem() noexcept(noexcept(exception_policy::check_bad_alloc(nullptr))) { if (ptr == nullptr) { size_t bytesNeeded = sizeof(T)*size(); ptr = (T*) malloc(bytesNeeded); exception_policy::check_bad_alloc(ptr); markUseHeap(); } } //raise the useHeap flag void markUseHeap() noexcept { useHeap = 1; } //ptr to memory chunk - heap or stack T* ptr; //if 0 stack is used, else if 1 - heap size_t useHeap:1; //63 bits for elements count, that should be enough size_t count:(sizeof(size_t)*8-1); }; //use this to create dyn_array. Example : //auto pixelBuffer = make_dyn_array(float, 640, 0.f); //std::cout << pixelBuffer[0]; #define make_dyn_array(TYPE, COUNT, VALUE) codebg::dyn_array<TYPE>(sizeof(TYPE)*(COUNT) > codebg::DYN_ARRAY_MAX_BYTES_ON_STACK ? nullptr : (TYPE*)(alloca(sizeof(TYPE)*(COUNT))), (COUNT), (VALUE)) } |
Можем да го ползваме почти като нормална функция :
|
1 |
auto myDynArray = codebg::make_dyn_array(float, 640, 0.f); |
Като заключение,
(1) std::dynarray ползвайки С++11 изглежда не може да се направи (имплементацията в clang e cheat&fake – ползва единствено malloc, това не нарушава стандарта, ама все пак ..), трябват промени в компилатора и/или да се пише на assembler.
(2) В С++11 един прост конструктор отнема над 200 символа – сигурен съм че с python с толкова мога да вдигна web server :). Изглежда пичовете от С++ комитета пружинките на клавиатурата за нищо ги нямат.
(3) Може би е добре да си отворя един github 🙂