Куча или стек ?

← →
DevilDevil © (2008-08-09 12:14) [0]

Доброе время суток, уважаемые форумчане.

Есть задача, в которой необходимо заюзать неопределённое количество памяти с минимальной время-потерей.

Предположим, я имею возможность отхватить какой-то кусок стековой памяти. С другой стороны, я могу отхватить кусок из кучи, но это дольше по времени.

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

← →
Sergey Masloff (2008-08-09 12:21) [1]

Что значит отхватить?

← →
Zeqfreed © (2008-08-09 12:33) [2]

> Где граница (размер в байтах), превышая которую лучше (быстрее,
> безопаснее, ...) отхватить кусок из кучи ?

stacksize?

← →
DevilDevil © (2008-08-09 12:33) [3]

function OthvatitStek(Size: integer): pointer; asm // eax := esp - eax - 1024 add eax, 1024 neg eax add eax, esp end; function OnvatitKuchu(Size: integer): pointer; begin GetMem(Result, Size); end;

← →
DevilDevil © (2008-08-09 12:40) [4]

> Zeqfreed © (09.08.08 12:33) [2]

что есть "stacksize" ?

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

В общем, нужен человек, который про стек знает многое, который разъяснит ситуацию и подскажет решение.

← →
Loginov Dmitry © (2008-08-09 13:04) [5]

> В общем, нужен человек, который про стек знает многое...

А Рихтер не подходит?
:)

← →
DevilDevil © (2008-08-09 13:09) [6]

рихтер - это долго.

← →
Sergey Masloff (2008-08-09 14:02) [7]

>рихтер - это долго.
Зато навсегда.

>DevilDevil © (09.08.08 12:33) [3]
Ну так-то быстрее. Естественно двинуть указатель и все. Но кто мешает взять в куче сразу большую область и точно также двигать по ней указатели?

← →
DevilDevil © (2008-08-09 14:21) [8]

> Sergey Masloff (09.08.08 14:02) [7]
> Зато навсегда.

Если не заблуждаюсь, тема не о пользе прочтения рихтера.

> Но кто мешает взять в куче сразу большую область и точно также
> двигать по ней указатели?

Ну так-то проще - отписать ересь какую-нибудь вместо ответа на чётко сформулированный вопрос.

← →
Sergey Masloff (2008-08-09 15:02) [9]

DevilDevil © (09.08.08 14:21) [8]
Терминология на вашей совести.
Никакой четкости в вопросе нет.
Я описал вариант работы с кучей который не будет отличаться от работы со стеком. То есть никакой границы нет. Как в стеке никто (почти) не будет следить за безопасностью так и в куче. Скорость доступа к стеку и к куче может быть практически одинаковой.

← →
DevilDevil © (2008-08-09 15:06) [10]

вопрос открыт

← →
VirEx © (2008-08-09 15:16) [11]

для резервации больших объемов памяти - куча, для малых - стек
вопрос закрыт

← →
Zeqfreed © (2008-08-09 15:17) [12]

Есть вариант, что оптимизировать надо в другом месте.

← →
DevilDevil © (2008-08-09 15:18) [13]

> для резервации больших объемов памяти - куча, для малых
> - стеквопрос закрыт

золотые слова!!!
в том то и вопрос: "большой объём" - это сколько байт ?

← →
oxffff © (2008-08-09 15:22) [14]

> DevilDevil © (09.08.08 15:06) [10]
> вопрос открыт

Если ты можешь гарантировать что страницы стека будут гарантировано подгружены заранее,т.е. организовать unpageable pool, то стек естественно более предпочтительней поскольку вся операция Alloc это
sub esp, Size.
Однако в противном случае при работе со стеком тебе придется выделять постранично генерируя исключение процессора для выделения физической страницы. Что естественно очень накладно. Тогда предпочтение естественно куча.

НО!!! Я бы выбрал другой вариант

Никто не мешает организовать тебе свой менеджер памяти. VirtualAlloc тебе в помощь.

← →
DevilDevil © (2008-08-09 15:34) [15]

> oxffff © (09.08.08 15:22) [14]

для объёмов в 4, 10 или 100 байт свой или Delphi-йский менеджер памяти - дело относительно накладное. А вот пару мегабайт уже надо бы в куче делать. Вот и вопрос: где же эта граница ?

я не могу гарантировать, что страницы стека будут гарантированно подгружены.

← →
oxffff © (2008-08-09 15:36) [16]

> дело относительно накладное.

Относительно чего?

> где же эта граница ?

Граница у автора.

← →
VirEx © (2008-08-09 15:38) [17]

> [15] DevilDevil © (09.08.08 15:34)
> Вот и вопрос: где же эта граница
> ?

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

← →
DevilDevil © (2008-08-09 15:42) [18]

if (Size > SOME_CONST) then P := GetMem(Size) else asm push eax lea eax, esp-100 dec eax, Size mov P, eax pop eax end; if (Size > SOME_CONST) then FreeMem(P);

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

← →
DevilDevil © (2008-08-09 15:43) [19]

вопрос: чему равна SOME_CONST ?

> VirEx © (09.08.08 15:38) [17]
> так проверь свободную физическую память и выбирай

уточни, пожалуйста.

← →
oxffff © (2008-08-09 15:48) [20]

> DevilDevil © (09.08.08 15:42) [18]

У тебя код не правильный.

← →
DevilDevil © (2008-08-09 15:52) [21]

> oxffff © (09.08.08 15:48) [20]
опечатки в коде не имеют отношения к обсуждаемому вопросу.

← →
oxffff © (2008-08-09 16:01) [22]

> DevilDevil © (09.08.08 15:52) [21]

Это не опечатки.
Почему не изменяется ESP?

← →
DevilDevil © (2008-08-09 16:20) [23]

> oxffff © (09.08.08 16:01) [22]
> Почему не изменяется ESP?

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

← →
oxffff © (2008-08-09 16:45) [24]

> DevilDevil © (09.08.08 16:20) [23]

Явно ты можешь их не вызывать, за тебя это может сделать компилятор.
Однако представь, что будет с твоими данными, если возникнет исключение.

← →
Юрий Зотов © (2008-08-10 02:26) [25]

> DevilDevil © (09.08.08 15:18) [13]

> "большой объём" - это сколько байт?

Семь.

← →
Dimka Maslov © (2008-08-10 11:00) [26]

Для единичного зохавывания блока памяти разницы никакой нет, стек или куча. Если зохавывание выполняется в цикле - есть. Но если блок достаточно большой, то для его обработки потребуется куда как большее время нежели на выделение. Отсюда мораль - а не вынести ли выделение за пределы цикла, используя выделенный блок по новой в каждой итерации. Тогда "потери времени" станут незначительными.

> DevilDevil ©

ИМХО ты не стой стороны подходишь к оптимизации. К тому-же при использовании стека ты имеешь большой, даже огромный шанс, исчерпать его лимит при рекурссионном алгоритме. Я бы делал другим образом - выделял бы единовременно необходимый блок памяти с запасом и на него навернул бы некий механизм, реализующий одобную работу с размещенными данными.

SOME_CONST = 42 :)

> DevilDevil © (09.08.08 15:34) [15]
> для объёмов в 4, 10 или 100 байт свой или Delphi-йский менеджер
> памяти - дело относительно накладное

Штатный ВММ оптимизирован как раз для работы с блоками малого размера, кратными размеру указателя.

FastMM-менеджер как альтернатива ВММ ощутимо лучшим образом оптимизирует операции сборки мусора.

← →
Asteroid (2008-08-11 13:11) [30]

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

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

- низя, можешь промахнуться мимо GUARD страницы стека, с непредсказуемым результатом(точнее, с вполне предсказуемым - как пишет Рихтер, на AV система молча прибьет процесс, даже Stack overflow на прощание не скажет)... Компилятор Delphi для выделения больших буферов на стеке делает цикл <push DWORD; push DWORD;>...

> в том то и вопрос: "большой объём" - это сколько байт ?

Это больше, чем размер примитивных типов.

> DiamondShark (11.08.2008 15:34:32) [32]

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

> han_malign © (11.08.08 15:10) [31]

Есть улучшенная реализация fastStackAlloc в одном из стандартных модулей. Идея в sub esp до страницы-4 , далее push, далее опять sub,4092, push итеративно до нужного размера.

> han_malign © (11.08.08 15:10) [31]

т.е.: описанный мной метод действует только в рамках текущей страницы? ну или самому в нужное время вызывать push.

> oxffff © (11.08.08 15:57) [34]
у меня Delphi 6, fastStackAlloc не найден... но зато найден StackAlloc/StackFree в гребенях, в implementation секции модуля grids.pas:

{ StackAlloc allocates a "small" block of memory from the stack by decrementing SP. This provides the allocation speed of a local variable, but the runtime size flexibility of heap allocated memory. } function StackAlloc(Size: Integer): Pointer; register; asm POP ECX { return address } MOV EDX, ESP ADD EAX, 3 AND EAX, not 3 // round up to keep ESP dword aligned CMP EAX, 4092 JLE @@2 @@1: SUB ESP, 4092 PUSH EAX { make sure we touch guard page, to grow stack } SUB EAX, 4096 JNS @@1 ADD EAX, 4096 @@2: SUB ESP, EAX MOV EAX, ESP { function result = low memory address of block } PUSH EDX { save original SP, for cleanup } MOV EDX, ESP SUB EDX, 4 PUSH EDX { save current SP, for sanity check (sp = [sp]) } PUSH ECX { return to caller } end; { StackFree pops the memory allocated by StackAlloc off the stack. - Calling StackFree is optional - SP will be restored when the calling routine exits, but it"s a good idea to free the stack allocated memory ASAP anyway. - StackFree must be called in the same stack context as StackAlloc - not in a subroutine or finally block. - Multiple StackFree calls must occur in reverse order of their corresponding StackAlloc calls. - Built-in sanity checks guarantee that an improper call to StackFree will not corrupt the stack. Worst case is that the stack block is not released until the calling routine exits. } procedure StackFree(P: Pointer); register; asm POP ECX { return address } MOV EDX, DWORD PTR [ESP] SUB EAX, 8 CMP EDX, ESP { sanity check #1 (SP = [SP]) } JNE @@1 CMP EDX, EAX { sanity check #2 (P = this stack block) } JNE @@1 MOV ESP, DWORD PTR [ESP+4] { restore previous SP } @@1: PUSH ECX { return to caller } end;

Симпатичные функции, наверное ими и воспользуюсь.
Но напрашивается 2 вопроса:

1) до каких пор (до какого размера) я могу расширять стек.
2) может ли кто пролить свет на "слабые места" менеджера памяти... иначе говоря, за счёт чего происходят время-потери ?

одного не могу понять...

вот есть какой-то код... Ага, сейчас надо (как минимум) запушить eax, edx и ecx, а после вызова функции восстановить eax, edx и ecx... но не тут то было - esp уже изменил своё местоположение.

Не нахожу место в коде, благодаря которому ошибок юзания стека не произошло бы. Ткните носом плиз.

Скажите, насколько это опасно ???

В моём случае фишка со StackAlloc сработала без ошибок. Но что если компилятор запушит регистры перед вызовом функции, а после - постарается вернуть из стека.

Я провёл тест:

//P := StackAlloc(BufferingSize); asm push eax mov PUSH_DATA1, eax mov eax, BufferingSize call StackAlloc mov P, eax pop eax mov PUSH_DATA2, eax end;

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

Куча или стек ? Найти похожие ветки