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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.