PureBasic Forums - English

http://www.purebasic.com
https://www.purebasic.fr/english/

SortStructuredList cannot handle >= 19999 Elements (3.93)

https://www.purebasic.fr/english/viewtopic.php?t=14226

Page 2 of 2

Posted: Thu Mar 03, 2005 8:14 pm
by MrMat
Yes i think i got it working ok by copying the used portion of the old stack over the new. Here's an example:

Code: Select all

Global *NewStack.l, NewStackSize.l, *OldStack.l, *StartStack.l, *OrigStack.l

MOV *NewStack, esp ; Start of stack
NewStackSize = 1024 * 1024 ; Default stack size is 1 mb
*OldStack = 0
*OrigStack = *NewStack ; Store original stack position to return to at code exit

Procedure.l ReallocateStack(StackSize.l) ; Set new stack size (in bytes)
; Get position in current stack
  MOV *StartStack, esp
  
; Calculate stack free
  CurrentFree = NewStackSize - *NewStack + *StartStack

; Need a few bytes spare
  If CurrentFree < 256
    ProcedureReturn 1 ; Not enough (1 = stack free space too small)
  EndIf

; Calculate stack used
  NewStackSize = *NewStack - *StartStack

; Check new stack size is bigger than current size in use + 1k
  If StackSize < NewStackSize + 1024
    ProcedureReturn 2 ; No it isn't (2 = new stack size too small)
  EndIf

; Allocate space for new stack
  *NewStackPos = AllocateMemory(StackSize)

; Could we allocate memory for new stack?
  If *NewStackPos = 0
    ProcedureReturn 3 ; Nope we couldn't (3 = not enough free memory to allocate new stack)
  EndIf

; Calcaulate position in new stack
  *NewStack.l = *NewStackPos + StackSize - NewStackSize

; Temporarily shift stack so as not to interfere with CopyMemory
  *TempStack = *StartStack - 128
  MOV eax, *TempStack
  MOV esp, eax

; Copy used stack across to new stack
  CopyMemory(*StartStack, *NewStack, NewStackSize)

; Update stack with new position
  MOV eax, *NewStack
  MOV esp, eax

; Previous stack no longer needed, so free it
  If *OldStack
    FreeMemory(*OldStack)
  EndIf

; Update new stack position and size and old stack position
  *NewStack = *NewStackPos + StackSize
  NewStackSize = StackSize
  *OldStack = *NewStack - NewStackSize

; Phew, we made it to the end (0 = good)
ProcedureReturn 0
EndProcedure

Procedure.l StackFree() ; Return free stack space
  *CurrentStack.l
  MOV *CurrentStack, esp
ProcedureReturn NewStackSize - *NewStack + *CurrentStack
EndProcedure

Procedure.l StackUsed() ; Return used stack space
  *CurrentStack.l
  MOV *CurrentStack, esp
ProcedureReturn *NewStack - *CurrentStack
EndProcedure

Procedure.l flop(count.l) ; Iterative example procedure
; Update every 2000 calls
  If count % 2000 = 0
    Debug("Count: " + Str(count) + " Stack free (kb): " + Str(StackFree() / 1024) + " Stack used (kb): " + Str(StackUsed() / 1024))
    Delay(200)
; Check if less than 100 kb stack space
    If StackFree() < 1024 * 100
      Debug("Less than 100 kb stack space; increasing stack size by 1 mb:")
      result = ReallocateStack(StackUsed() + 1024 * 1024) ; Increase stack by 1 mb
      Debug("Stack free (kb): " + Str(StackFree() / 1024) + " Stack used (kb): " + Str(StackUsed() / 1024))
      Select result
        Case 0 : Debug("Stack space allocated successfully")
        Case 1 : Debug("Not enough space on stack") : End
        Case 2 : Debug("New stack size must be greater than previous amount in use") : End
        Case 3 : Debug("Could not allocate memory for new stack") : End
      EndSelect
    EndIf
  EndIf
  If StackUsed() < 1024 * 1024 * 2 ; Go up to 2 mb stack size
    flop(count + 1)
  EndIf
  If count % 2000 = 0 ; Check count is decreasing as procedure exits
    Debug(count)
  EndIf
EndProcedure

; Output initial free and used stack space
Debug("Initial stack details:")
Debug("Stack free (kb): " + Str(StackFree() / 1024) + " Stack used (kb): " + Str(StackUsed() / 1024))

; Set stack size to 200 kb
Debug("Setting stack size to 200 kb:")
result = ReallocateStack(1024 * 200)
Select result
  Case 0 : Debug("Stack space allocated successfully")
  Case 1 : Debug("Not enough space on stack") : End
  Case 2 : Debug("New stack size must be greater than previous amount in use") : End
  Case 3 : Debug("Could not allocate memory for new stack") : End
EndSelect
Debug("Stack free (kb): " + Str(StackFree() / 1024) + " Stack used (kb): " + Str(StackUsed() / 1024))

; Call recursive procedure
Debug("Calling iterative procedure:")
flop(0)

; Return to original stack and free previous stack
If *OldStack
  MOV eax, *OrigStack
  MOV esp, eax
  FreeMemory(*OldStack)
EndIf

Debug("Finished")
Which gives the output:

Code: Select all

Initial stack details:
Stack free (kb): 1023 Stack used (kb): 0
Setting stack size to 200 kb:
Stack space allocated successfully
Stack free (kb): 199 Stack used (kb): 0
Calling iterative procedure:
Count: 0 Stack free (kb): 199 Stack used (kb): 0
Count: 2000 Stack free (kb): 129 Stack used (kb): 70
Count: 4000 Stack free (kb): 59 Stack used (kb): 140
Less than 100 kb stack space; increasing stack size by 1 mb:
Stack free (kb): 1023 Stack used (kb): 140
Stack space allocated successfully
Count: 6000 Stack free (kb): 953 Stack used (kb): 211
Count: 8000 Stack free (kb): 883 Stack used (kb): 281
Count: 10000 Stack free (kb): 813 Stack used (kb): 351
Count: 12000 Stack free (kb): 742 Stack used (kb): 421
Count: 14000 Stack free (kb): 672 Stack used (kb): 492
Count: 16000 Stack free (kb): 602 Stack used (kb): 562
Count: 18000 Stack free (kb): 531 Stack used (kb): 632
Count: 20000 Stack free (kb): 461 Stack used (kb): 703
Count: 22000 Stack free (kb): 391 Stack used (kb): 773
Count: 24000 Stack free (kb): 320 Stack used (kb): 843
Count: 26000 Stack free (kb): 250 Stack used (kb): 914
Count: 28000 Stack free (kb): 180 Stack used (kb): 984
Count: 30000 Stack free (kb): 109 Stack used (kb): 1054
Count: 32000 Stack free (kb): 39 Stack used (kb): 1125
Less than 100 kb stack space; increasing stack size by 1 mb:
Stack free (kb): 1023 Stack used (kb): 1125
Stack space allocated successfully
Count: 34000 Stack free (kb): 953 Stack used (kb): 1195
Count: 36000 Stack free (kb): 883 Stack used (kb): 1265
Count: 38000 Stack free (kb): 813 Stack used (kb): 1336
Count: 40000 Stack free (kb): 742 Stack used (kb): 1406
Count: 42000 Stack free (kb): 672 Stack used (kb): 1476
Count: 44000 Stack free (kb): 602 Stack used (kb): 1546
Count: 46000 Stack free (kb): 531 Stack used (kb): 1617
Count: 48000 Stack free (kb): 461 Stack used (kb): 1687
Count: 50000 Stack free (kb): 391 Stack used (kb): 1757
Count: 52000 Stack free (kb): 320 Stack used (kb): 1828
Count: 54000 Stack free (kb): 250 Stack used (kb): 1898
Count: 56000 Stack free (kb): 180 Stack used (kb): 1968
Count: 58000 Stack free (kb): 109 Stack used (kb): 2039
58000
56000
54000
52000
50000
48000
46000
44000
42000
40000
38000
36000
34000
32000
30000
28000
26000
24000
22000
20000
18000
16000
14000
12000
10000
8000
6000
4000
2000
0
Finished
The example initially sets the stack to 200 kb then calls an iterative procedure which monitors the free stack space. When it goes below 100 kb it calls a procedure to increase the stack by 1 mb and then it continues iterating. I set it to stop when the stack size reached 2 mb. The decreasing numbers at the end show the stack was preserved correctly so i think it's all working.

Thanks again El Choni! :D

Posted: Thu Mar 03, 2005 8:47 pm
by Rescator
wow awsome.
I bet anyone using really large (data handling wise) programs with thousands of operations will love this,
as those are usually the ones that do run out of stack space heh.

Altough it also prevent stack overflow crashes/exploits.
And with a check on allocmem or a limit on max newstack size one can avoid using up all the system memory too.

Would love to see something like this implemented in the PB compiler itself.
Or maybe just a ASM pb lib ?

Posted: Fri Mar 04, 2005 3:07 am
by Froggerprogger
OK lets try to calculate ack(4,2) now ! (ack = Ackermann-function)
If we just would increase the stack all the time we could perhaps manage it...
:lol:

Anyway, nice code!
All times are UTC+01:00
Page 2 of 2

Powered by phpBB® Forum Software © phpBB Limited