"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;
    };

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

Новые блоги и статьи Все статьи Все блоги /
Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

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" как обойти?

Решение