SortStructuredList cannot handle >= 19999 Elements (3.93)

[IceSoft]

Please try it.
I belive a bug in SortStructuredList()
The MessageRequester isn't shown but debugger and program (itself) is aborted.

Code: Select all

Structure TestStructure 
  StringNummer.s 
EndStructure 
NewList EineListe.TestStructure() 

Debug "Erstelle..." 
For t=100000 To 119999 
  AddElement(EineListe()) 
  EineListe()\StringNummer=Str(t) 
Next 

Debug "Start..." 
StartTime = ElapsedMilliseconds()              
SortStructuredList(EineListe(),2,OffsetOf(TestStructure\StringNummer),#PB_Sort_String) 
Debug "ende" 
MessageRequester("",Str((ElapsedMilliseconds()-StartTime)/1000)) 

[MrMat]

It appears to be a stack overflow (probably caused by the highly recursive nature of a standard quick sort acting on an already sorted list). If i increase the stack size in PBCoffee it runs fine but that probably doesn't help you much.

[Rescator]

So Fred needs to add a stackcheck and automatic stack increase to fix this I assume?

[Froggerprogger]

...it really seems to be related to the underlying Quicksort-derivat.
Already presorted values took a very long time to sort, and if there are too much, a stack overflow occurs and let the program crash.
E.g. if you use :

Code: Select all

For t=0 To 111999
  AddElement(EineListe())
  EineListe()\StringNummer=Str(Random($7FFFFFFF))
Next

it sorts fast as hell, though there are 100000 elements more (but without an order)!

=> PB already HAS new sorting-procedures for sorting arrays, but it seems as if they were not yet implemented for sorting lists ?

[MrMat]

I don't think the stack size can be changed once the program is running (just at compile time). Maybe the sort algorithms could count how much they're putting on the stack and return an exit code if some limit is reached, or swap to a shell sort or some other algorithm when stack space is low.

Best bet would be to modify the sort algorithm to put less on the stack. For a basic quick sort the worst case is an already sorted list so i'm sure the algorithm can be tweaked. The default stack size is 1 meg and it seems to crash at around 10800 elements so thats around 97 bytes per element. Seems a bit high. I dunno, over to Fred

[Fred]

I modified the algo to use the same one than array (i hadn't fullly implemented it because of linked list iteration penalities) and it seems to work correctly without too much slowdown. You can test the new lib here: www.purebasic.com/beta/Sort

[MrMat]

Wow thats fast! Seems to work great, thanks!

[Rescator]

I don't think the stack size can be changed once the program is running (just at compile time).

Really?

When I programmed on the Amiga (used AmigaE still think it was the best language ever

I remember there was some stack increase code available.
Can't recall how it worked, but you did a stack error catch (or monitored the stack size and how much was used),
allocated new stack memory, copied the stack over and freed the old stack.
Someone turned that into a AmigaE module (lib) too if I recall.

If the same is possible on Windows and Linux I got no clue.

[MrMat]

Well i don't know for sure. Maybe there is some way but i've asked before on these forums and no-one said how to. I don't see the need now anyway because when you set the stack up you give it two values, one is the reserve (max stack size) and the other is the commit/allocation (initial stack size and increment amount, although that may vary from platform to platform). So if in your code you're willing to increase the stack size to say 10 megs in 1 meg jumps you may as well set the reserve to 10 megs and the allocation to 1 meg at linking time. Then the stack size will start at 1 meg and increase itself when necessary to 10 megs. At least thats my understanding of it which may be complete rubbish

[El_Choni]

Hi,

Try this to change stack size:

Code: Select all

OldStack.l
StackSize = 256000
NewStack = AllocateMemory(StackSize)+StackSize
MOV OldStack, esp
MOV esp, NewStack
; Program code
MOV esp, OldStack
FreeMemory(NewStack-StackSize)

Tested with very few code in the middle, seems to work.

EDIT: yes, your code works with StackSize set to 2560000:

Code: Select all

OldStack.l
StackSize = 2560000
NewStack = AllocateMemory(StackSize)+StackSize
MOV OldStack, esp
MOV esp, NewStack


Structure TestStructure
  StringNummer.s
EndStructure
NewList EineListe.TestStructure()

Debug "Erstelle..."
For t=100000 To 119999
  AddElement(EineListe())
  EineListe()\StringNummer=Str(t)
Next

Debug "Start..."
StartTime = ElapsedMilliseconds()             
SortStructuredList(EineListe(),2,OffsetOf(TestStructure\StringNummer),#PB_Sort_String)
Debug "ende"
MessageRequester("",Str((ElapsedMilliseconds()-StartTime)/1000)) 

MOV esp, OldStack
FreeMemory(NewStack-StackSize) 

Regards,

[MrMat]

Wow you make it look so simple! So we can check how much stack is free too by subtracting esp from NewStack. Thats really useful, thanks El_Choni! *goes off to learn asm*

[El_Choni]

Yep. BTW, I forgot to add a check for AllocateMemory, don't forget that

[MrMat]

Can the code to change the stack size be run from inside a procedure? I suppose the original stack would need to be copied over the new one? That would be really useful when you don't know how big the stack should be at the start of your program.

[Rescator]

A forum Mod may want to split this thread. (maybe at my post further up) and put it in Tips'n'Tricks
So that all this cool stack code don't get whiped out when Fred cleans up the Bugs section next time

[El_Choni]

I think if you change the stack inside a procedure, you must restore it before returning from the procedure, otherwise: crash (unless you copy the previous stack to the new one?).