"Stack overflow" как обойти?

@SEVI · Регистрация: 26.01.2010

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

Доброго времени суток!
Дело в том, что при объявлении массива размером 10⁶

C++
1
int a[1000000];

выскакивает при запуске (после компиляции даже) stack overflow, еще до того как туда будут заноситься элементы. Дебаггер указывает именно сюда... Тем более если сделать 10⁵, то все работает... Прошу объяснить как это обойти... Заранее спасибо.
Вот весь код (без кода функции двоичной сортировки quickSortR)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    int n, k, i, s=0;
    int a[100000];
    ifstream f1("E.dat");
    ofstream f2("E.sol");
    f1 >> n >> k;
    for (i = 0; i < n; i++) {
        f1 >> a[i];
    }
    quickSortR(a,n-1);
    for (i = k; i < n; i++) {
        s = s + a[i];
    }
    f2 << s;
}

Tulosba · 27.01.2014, 16:14

1. стек должен быть непрерывным, в то время как для кучи такого требования нет. Непрерывный кусок памяти заданного размера найти иногда просто невозможно в силу фрагментирования памяти.
2. со стеком не реализовать логику случайного освобождения памяти (в терминалогии стека, есть только адрес его вершины). Нельзя освободить память из середины стека, не тронув вершину.
3. про скорость довольно сомнительно. Если есть много мелких объектов, которые нужно создавать/уничтожать, можно выделить пул и работать с ним.

@mustimur · 27.01.2014, 17:41

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

то для повышения быстродействия можно было бы использовать увеличенный стек, повысив тем самым скорость работы в 2 раза, по сравнению с кучей

Это хорошо если ты заранее знаешь свой предел, а если он переменен? Заранее объявлять с запасом и оттягивать на свою программу излишние ресурсы, тогда с каким запасом? Да кстати проблемы начнутся уже на 2Гб под win32 (по умолчанию)... Плюс если я правильно понимаю то основная потеря времени это на выделение и освобождение памяти, тогда не создавайте и освобождайте память многократно, а сделайте это единожды, тогда потери скорости не должно быть существенной (если вообще будет).

@h8er · 27.01.2014, 18:02

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

основная потеря времени это на выделение и освобождение памяти

Не только на выделение и освобождение, а в принципе доступ к ячейке на стеке в 2 раза быстрее, чем на куче. На ячейку на стеке указывает регистр и адрес уже известен, тогда как для доступа к ячейке в куче требуется высчитывать местоположение: адрес начало блока памяти + смещение до этой ячейки.

@mustimur · 27.01.2014, 18:48

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

Не только на выделение и освобождение, а в принципе доступ к ячейке на стеке в 2 раза быстрее, чем на куче. На ячейку на стеке указывает регистр и адрес уже известен, тогда как для доступа к ячейке в куче требуется высчитывать местоположение: адрес начало блока памяти + смещение до этой ячейки.

Допустим, но что то сомнительно это, если ссылка где проводится сравнение? там что я видел нет однозначного ответа на быстродействие.

Убежденный · 27.01.2014, 18:51

Ко всему написанному хотелось бы добавить, что в Windows ситуацию с
переполнением стека можно отловить через SetUnhandledExceptionFilter.
Вот только радости от этого немного, т.к. в обработчике ничего
серьезного выполнить не выйдет, ибо стековой памяти уже нет...

ValeryS · 27.01.2014, 18:56

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

int a[1000000];

итого выделяем 4000000 байт памяти примерно 4МБайта
а размер стека 1 Мб

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

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

Не только на выделение и освобождение, а в принципе доступ к ячейке на стеке в 2 раза быстрее, чем на куче. На ячейку на стеке указывает регистр и адрес уже известен, тогда как для доступа к ячейке в куче требуется высчитывать местоположение: адрес начало блока памяти + смещение до этой ячейки.

хоть раз смотрел на листинги?
[ebp+x] или [esp-x] для стека
[esi+x] для кучи
где тут быстрее?

@mustimur · 27.01.2014, 19:00

Так какой вывод? для я себя сделал выбор в пользу кучи и динамической памяти (как и советует Tulosba), но по скорости я все таки проигрываю?

Добавлено через 47 секунд

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

хоть раз смотрел на листинги?
[ebp+x] или [esp-x] для стека
[esi+x] для кучи
где тут быстрее?

вот я это тоже видел!!

ValeryS · 27.01.2014, 19:01

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

для я себя сделал выбор в пользу кучи и динамической памяти

правильно

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

но по скорости я все таки проигрываю?

с чего бы? посмотри листинг и увидишь что нет
а при последовательном доступе даже выиграешь

@mustimur · 27.01.2014, 19:10

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

с чего бы? посмотри листинг и увидишь что нет
а при последовательном доступе даже выиграешь

Смутил на храп h8er-а, думал новичок проглядел что-то...

Добавлено через 5 минут
в смысле я новичок, проглядел чего-то)

@h8er · 27.01.2014, 19:30

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

хоть раз смотрел на листинги?
[ebp+x] или [esp-x] для стека
[esi+x] для кучи
где тут быстрее?

Что этим куском коды вы хотели доказать, я так и не понял, но я хотел донести всего лишь мысль, что для доступа к ячейки на стеке в общих чертах требуется один такт, для кучи - 2. Вот и вся моя мысль.

@mustimur · 27.01.2014, 19:38

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

Что этим куском коды вы хотели доказать, я так и не понял, но я хотел донести всего лишь мысль, что для доступа к ячейки на стеке в общих чертах требуется один такт, для кучи - 2. Вот и вся моя мысль.

Это код на ассемблере, видно же что одинаково по тактам

@h8er · 27.01.2014, 19:47

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

Это код на ассемблере, видно же что одинаково по тактам

Ну да, точно же, а адреса в этих регистрах всю жизнь были.
В общем, я просто хотел обратить внимание на то, что доступ к SS:SP был бы быстрее, чем к записи смещения для кучи в регистр и только потом чтения адреса оттуда, и просто поинтересовался, почему же в таком случае не делают просто шире стек. И ни с кем спорить вообще-то не планировал.

ValeryS · 27.01.2014, 19:54

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

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

не надо в общих чертах давай конкретно

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

Ну да, точно же, а адреса в этих регистрах всю жизнь были.

т.е в регистр ebp , который используется для стековых переменных,адреса всегда лежат?
сколько тактов занимает такая вот например команда
lea eax,[esi+4*ecx]?????????

@h8er · 27.01.2014, 20:05

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

т.е в регистр ebp , который используется для стековых переменных,адреса всегда лежат?

Вообще-то это был сарказм, очевидно стоило бы это написать в скобочках.

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

lea eax,[esi+4*ecx]

Ну вот видите, вы уже на одну команду больше тратите, для того, чтобы загрузить сначала адрес в eax.

ValeryS · 27.01.2014, 20:17

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

Ну вот видите, вы уже на одну команду больше тратите, для того, чтобы загрузить сначала адрес в eax.

ты кроме 8086 процессора более старшие знаешь?
растактовку можешь по командам дать?
или просто так говоришь?
так кстати и не ответил сколько тактов занимает команда?

Добавлено через 4 минуты
кстати так ради смеха я не адрес записал
а рассчитал значение ecx умноженное на 5 ( для этого правда значения из ecx в esi надо скопировать)

@h8er · 27.01.2014, 20:25

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

ты кроме 8086 процессора более старшие знаешь?
растактовку можешь по командам дать?
или просто так говоришь?
так кстати и не ответил сколько тактов занимает команда?

Добавлено через 4 минуты
кстати так ради смеха я не адрес записал
а рассчитал значение ecx умноженное на 5 ( для этого правда значения из ecx в esi надо скопировать)

Что вы ко мне пристали? Вы что-то конкретное хотите от меня?
Все что я хотел сказать по этому поводу, я сказал, что вы мне пытаетесь сейчас доказать - ума не приложу. Какие-то куски псевдо асм кода кидаете не понятные, откуда-то с потолка взятые.
По поводу тактов - да погорячился, назвав их тактами, но я имел ввиду именно шаги обращения, команды, если хотите.
И причем тут 8086? Мы разве об архитектуре речь ведем или о том, что для доступа к памяти на стеке нужно всего лишь к sp обратиться, а к куче - сначала получить адрес, а потом с ним работать? Не понимаю ваших претензий, честное слово.

ValeryS · 27.01.2014, 20:44

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

. Какие-то куски псевдо асм кода кидаете не понятные, откуда-то с потолка взятые.

хочешь реальный листинг?
могу

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

для доступа к памяти на стеке нужно всего лишь к sp обратиться,

а сформировать переменные, тот же массив не надо? или это не считается ?

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

к куче - сначала получить адрес, а потом с ним работать?

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

@castaway · 27.01.2014, 20:45

Раз уж начали офтопить и холиварить..

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

для этого правда значения из ecx в esi надо скопировать

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
 
int main()
{
    register int r;
    __asm__ __volatile__ (
        "       .intel_syntax noprefix  \n"
        "mov    eax, 3                  \n"
        "lea    eax, [eax + eax * 4]    \n"
        "       .att_syntax             \n" : "=a" (r) );
    printf( "%d\n", r ); // 15
}

Я к тому, что можно не копировать..

@h8er · 27.01.2014, 20:58

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

хочешь реальный листинг?
могу

а сформировать переменные, тот же массив не надо? или это не считается ?

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

Уф... Вот тут мысль выражена более яснее, я надеюсь.
http://answerstop.org/question... allocation

ValeryS · 27.01.2014, 21:15

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

Вот тут мысль выражена более яснее,

здесь идет разговор не о работе с массивом а о выделении его

I was always under the impression that growing the stack was constant time, and heap allocation's performance depended on the current complexity of the heap for both allocation (finding a hole of the proper size) and de-allocating (collapsing holes to reduce fragmentation, as many standard library implementations take time to do this during deletes if I am not mistaken).

C++
1
2
for (int i = 0; i < 100000; ++i)
        empty e;

и

C++
1
2
3
4
 for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };

разумеется выделение в куче медленней никто с этим и не спорил
но зато здесь нет ограничений (в смысле они гораздо больше чем у стека)
а в работе они практически одинаковы
в нормальной программе никто не будет создавать и удалять массив миллион раз подряд

Новые блоги и статьи Все статьи Все блоги /
Программный отбор значения справочника Maks 21.03.2026 Процедура ВодителиНачалоВыбора(Элемент, ДанныеВыбора, ВыборДобавлением, СтандартнаяОбработка) / / Отключаем стандартную обработку (стандартное открытие формы выбора без фильтров) . . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	27.01.2014, 16:14
	Сообщение было отмечено Убежденный как решение Решение 1. стек должен быть непрерывным, в то время как для кучи такого требования нет. Непрерывный кусок памяти заданного размера найти иногда просто невозможно в силу фрагментирования памяти. 2. со стеком не реализовать логику случайного освобождения памяти (в терминалогии стека, есть только адрес его вершины). Нельзя освободить память из середины стека, не тронув вершину. 3. про скорость довольно сомнительно. Если есть много мелких объектов, которые нужно создавать/уничтожать, можно выделить пул и работать с ним. 5

Убежденный Ушел с форума 16481 / 7444 / 1187 Регистрация: 02.05.2013 Сообщений: 11,616 Записей в блоге: 1
	27.01.2014, 18:51
	Ко всему написанному хотелось бы добавить, что в Windows ситуацию с переполнением стека можно отловить через SetUnhandledExceptionFilter. Вот только радости от этого немного, т.к. в обработчике ничего серьезного выполнить не выйдет, ибо стековой памяти уже нет... 1

"Stack overflow" как обойти?

Решение