Пародия на стековый аллокатор

@tapochka · Регистрация: 25.04.2014

Студворк — интернет-сервис помощи студентам

здравствуйте, решил тут чуток поиграться... сделать аллокатор чтобы данные в статическом буфере размещал. в итоге долго поиграться не удалось - вылетает при первой же аллокации... честно, дебаггер не особо помогает в нахождении ошибки... что тут не так?

C++
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
#include <type_traits>
 
template<typename T, size_t size = 32>
struct stack_allocator {
    
    static_assert(size != 0, "oops");
 
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;
 
    template< class U >
    struct rebind { 
        typedef stack_allocator<U> other; 
    };
 
    stack_allocator() noexcept = default;
 
    stack_allocator(const stack_allocator& other) noexcept = default;
 
    template< class U >
    stack_allocator(const stack_allocator<U>& other) noexcept
    {
    }
 
    ~stack_allocator() noexcept = default;
 
    pointer address(reference x) const {
        return std::addressof(x);
    }
 
    const_pointer address(const_reference x) const {
        return std::addressof(x);
    }
 
    size_type max_size() const {
        return (size_t)(-1)/sizeof(value_type);
    }
 
    T* allocate(std::size_t n) {
        return (value_type*)(ptr + n);
    }
 
    void deallocate(T* p, std::size_t n) 
        {
    }
 
    void construct(pointer p, const_reference val) {
        ::new((void *)p) T(val);
    }
 
    template< class U, class... Args >
    void construct(U* p, Args&&... args) {
        ::new((void *)p) U(std::forward<Args>(args)...);
    }
    
    void destroy(pointer p) {
        p->~value_type();
    }
 
    template< class U >
    void destroy(U* p) {
        p->~U();
    }
private: 
    typename std::aligned_storage<sizeof(T), alignof(T)>::type ptr[size] = {};
};
 
template<size_t size>
struct stack_allocator<void, size>;
 
int main() {
    std::vector<int, stack_allocator<int>> vec;
    vec.emplace_back(1);
    return 0;
}

@Fulcrum_013 · 10.01.2017, 01:26

Сообщение от Fulcrum_013

в обратном и высвобождай.

Вернее если все выделил правильно при выходе из функции само в обратном порядке высвободится откатом SP назад на позицию до вызова.

Добавлено через 5 минут

Сообщение от tapochka

она один раз выделяется в конструкторе аллокатора и освобождается только в деструкторе аллокатора

Где она выделилась? Вот это главный вопрос. И насколько знает тот кто вызывал этого выделятора что он что то на стеке выделил? Указатель стека после выхода из любой функции откатывается на то положение в котором он был до ее вызова. А соответственно вся память после этого места считается свободной.

@tapochka · 10.01.2017, 01:30 **[ТС]**

Сообщение от Fulcrum_013

И насколько знает тот кто вызывал этого выделятора что он что то на стеке выделил?

я так понимаю, он ничего не знает где он выделил, да ему это и не нужно, он лишь дергает allocate/deallocate и все, а дальше уж само все

Сообщение от Fulcrum_013

Указатель стека после выхода из любой функции откатывается на то положение в котором он был до ее вызова. А соответственно вся память после этого места считается свободной.

мне это известно... в этом и соль - память освобождается - значит и умирает сам контейнер, а вместе с ним и аллокатор со своим буфером

@Fulcrum_013 · 10.01.2017, 01:52

Сообщение от tapochka

ачит и умирает сам контейнер, а вместе с ним и аллокатор со своим буфером

А поскольку аллокацию вызывает код вектора а не твой, который содержит несколько вложенных вызовов с этим ничего не поделаешь из аллокатора. Саму память на стеке нужно выделить до создания вектора и дать аллокатору указатель на нее. Аллокатор этот указатель подпихнет вектору и усе. причем сразу фиксированный максимальный размер. А если рассчитывать на реалоки ее придется выделять в 1,5 раза больше максимального размера с учетом того что при реалоке должны жить оба буфера пока идет копирование из старого в новый. НУ и никуда кроме функции в которой выделена память и вызовов из нее этот вектор потом девать нельзя. То бишь так распределить и оставить полем объекта который переживет функцию в скопе которой распределен буфер не получится.

@tapochka · 10.01.2017, 04:56 **[ТС]**

Сообщение от Fulcrum_013

НУ и никуда кроме функции в которой выделена память и вызовов из нее этот вектор потом девать нельзя. То бишь так распределить и оставить полем объекта который переживет функцию в скопе которой распределен буфер не получится.

хм, да - девать никуда этот вектор нельзя с таким подходом... что-то хрень у меня, а не аллокатор получился(

Добавлено через 2 часа 51 минуту
конечно исправить пытался, но все упирается в rebind - там идет каст к std::_Container_proxy и из-за этого ошибка

C++
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
template<typename T>
struct stack_allocator {
 
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;
 
    template< class U >
    struct rebind { 
        typedef stack_allocator<U> other; 
    };
 
    stack_allocator(T* ptr_) noexcept {
        begin = ptr_;
    }
 
    stack_allocator(const stack_allocator& other) noexcept = default;
 
    template< class U >
    stack_allocator(const stack_allocator<U>& other) noexcept
    {
        begin = other.begin;     //<---вот здесь ошибка
    } 
 
    ~stack_allocator() noexcept = default;
 
    pointer address(reference x) const {
        return std::addressof(x);
    }
 
    const_pointer address(const_reference x) const {
        return std::addressof(x);
    }
 
    size_type max_size() const noexcept {
        return (size_t)(-1)/sizeof(value_type);
    }
 
    T* allocate(std::size_t n) {
        value_type * ret = (value_type *)(begin + pos);
        pos += n;
        return ret;
    } 
 
    void deallocate(T* p, std::size_t n) {
        for (auto i = 0; i < n; ++n)
            reinterpret_cast<value_type*>(p + i)->~T();
        pos -= n;
    }
 
 
    void construct(pointer p, const_reference val) {
        ::new((void *)p) T(val);
    }
 
    template< class U, class... Args >
    void construct(U* p, Args&&... args) {
        ::new((void *)p) U(std::forward<Args>(args)...);
    }
    
    void destroy(pointer p) {
        p->~value_type();
    }
 
    template< class U >
    void destroy(U* p) {
        p->~U();
    }
private: 
    T* begin = nullptr;
    unsigned int pos = 0;
};
 
template<>
struct stack_allocator<void> {
 
    using _Not_user_specialized = void;
    using value_type = void;
    using pointer = void*;
    using const_pointer = const void*;
 
    template<class U>
    struct rebind
    {   
        typedef stack_allocator<U> other;
    };
 
    stack_allocator() noexcept = default;
 
    stack_allocator(const stack_allocator<void>&) noexcept
    {
    }
 
    template<class U>
    stack_allocator(const stack_allocator<U>&) noexcept
    {   
    }
 
    template<typename U>
    stack_allocator<void>& operator=(const stack_allocator<U>&)
    {   
        return (*this);
    }
};
 
int main() {
unsigned char buff[sizeof(int) * 32] = {};
stack_allocator<int> alloc((int*)buff);
        std::vector<int, stack_allocator<int>> vec(alloc);
return 0;
}

походу непоправимо...

@Fulcrum_013 · 10.01.2017, 12:43

Сообщение от tapochka

хм, да - девать никуда этот вектор нельзя с таким подходом...

Ну такой аллокатор может в принципе решать довольно важную задачу а именно использование данных не известной в момент компиляции длины на стеке что может увеличить производительность.
К примеру

C++
1
2
3
void Foo(size_t size){
      int a[size];/* что бывает очень удобно для промежуточных данный (и выделяется за один такт процессора  и удалится автматически)*/
}

По стандарту такая конструкция вызывает ошибку компиляции. Но некоторые компиляторы умеют и такие дела делать. В принципе средства распределить буфер в стеке который живет до выхода из создавшей функции есть еще со времен С. А вот подобный аллокатор может дать удобство работы с такими буферами как с современными контейнерами.

Сообщение от tapochka

что-то хрень у меня, а не аллокатор получился(

То не у вас, то у разработчиков STL хрень какая то получилась. Стоило им только сделать возможность указывать вектору при инициализации статический нереаллоцируемый буфер (ну или сделать совместимый с вектором контейнер под такой буфер) и все было бы тривиально просто и без всяких аллокаторов, тем более что реальную аллокацию нужно делать до создания инстанса аллокатора. А в общем тренироваться с аллокаторами лучше на других типах памяти которые допускают перевыделение. К примеру на файловой памяти или буферах DirectX.

@tapochka · 10.01.2017, 13:32 **[ТС]**

Сообщение от Fulcrum_013

void Foo(size_t size){
* * * int a[size];/* что бывает очень удобно для промежуточных данный (и выделяется за один такт процессора *и удалится автматически)*/
}

вот по поводу одного такта - это ж неправда

Сообщение от Fulcrum_013

По стандарту такая конструкция вызывает ошибку компиляции

есть же старый добрый alloca:

C++
1
2
3
void Foo(size_t s) {
    int* ptr = (int*)_alloca(s);
}

@Fulcrum_013 · 10.01.2017, 13:38

Сообщение от tapochka

вот по поводу одного такта - это ж неправда

Фактиически само выделение заключается в добавлении к SP размера буфера.

@tapochka · 10.01.2017, 13:38 **[ТС]**

Сообщение от Fulcrum_013

К примеру на файловой памяти или буферах DirectX

ну не всем же геймдев хлеб)

@Fulcrum_013 · 10.01.2017, 13:42

Сообщение от tapochka

есть же старый добрый alloca:

Есть. и приведенная выше конструкция именно через него и работает. Но естественно при этом все прелести сырого указателя и самостоятельного счета добавленных элементов и т.д. А зачастую оно нужно для пользования аки вектор с ограниченным максимальным числом элементов которое передается как аргумент функции.

Добавлено через 1 минуту

Сообщение от tapochka

ну не всем же геймдев хлеб)

Ну DirectX это не обязательно геймдев. Это еще и визуализация научных расчетов и САПР да и еще много чего, в том числе и GP GPU для хорошо распараллеливаемых задач.

@tapochka · 10.01.2017, 13:47 **[ТС]**

Сообщение от Fulcrum_013

Фактиически само выделение заключается в добавлении к SP размера буфера.

C++
1
2
3
decltype(auto) Foo(size_t size) {
    int b[4] = {};
}

Assembler
1
2
3
4
5
6
7
8
9
Foo(unsigned long):
        pushq   %rbp
        movq    %rsp, %rbp
        movq    %rdi, -24(%rbp)
        movq    $0, -16(%rbp)    //<--
        movq    $0, -8(%rbp)      //<--
        nop
        popq    %rbp
        ret

хотя это уже оффтоп

Новые блоги и статьи Все статьи Все блоги /
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .	Теория всего 12. ВГК на планете в стратегической игре "терра" anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .