Optimization of a sorting algorithm

[Olli]

I m again on ! I m digging...

1) addresses bug
2) unable to select a map element by address

[Kurzer]

Can you explain in more detail the value range that `Entry` can have? ... etc

Hello Nic,

it's best if I explain exactly what this is about. Again I used the wrong data type for my example, because it didn't matter for my solution approach.

First of all, a little overview of what it's about:
I need the sorting for a module that manages the resizing and positioning of windows and gadgets.

You don't have to specify absolute positions when designing the window and placing the gadgets, but you can anchor certain gadgets to the window or to other gadgets.
This anchoring ensures that the gadget realigns itself to its reference gadget every time the window is resized.

Let's take a calculator as a fictitious example.



Here you could anchor the "9" button (highlighted in green) in the center of the window.

This one button, which is the only one aligned to the window, would be enough to hold everything together. The other buttons then reference this button "9" or other gadgets that in turn reference button "9".

I made this clear with the red arrows.

Button "8" always sticks to the left of button "9". Button "7" always sticks to the left of button "8", button "4" always sticks below button "7"... and so on.

If now the window size is changed, button "9" will be re-centered and after that all other gadgets which are related to button "9" will be re-positionied.

BUT: The management of the gadget data I have realized with a map, because I access within the module almost with random access to the elements.

But this also means that the elements in the map are not sorted (you cannot sort a map). I only need sorted access to this map in one place in the whole module. And that is, in the function that realigns and/or resizes all the gadgets on a resize event.

So my idea was to leave the gadget management in the maps, but in parallel create a list where the MapKeys are listed in correctly sorted order. If the gadgets are aligned in the wrong order, positioning errors will occur.

The gadgets are addressed in this module using unique string identifiers rather than numbers. The mapkey is the string identifier of a gadget.

In the calculator example, the map entries might look like this:

Code: Select all

"Button 1" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 2" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 3" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 4" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 5" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 6" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 7" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 8" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)
"Button 9" -> (Gadget ID, Reference Gadget, X, Y, Widht, Height ... etc)

etc.

The alphanumeric string identifier of the referenced gadget is noted in the "Reference Gadget" field of each map entry.

Code: Select all

[...]
"Button 7" -> (3950003483, "Button 8", ... etc)
"Button 8" -> (3950003484, "Button 9", ... etc)
"Button 9" -> (3950003485, "", #Win_Center_Hor, #Win_Center_Vert, ... etc)

So the list to be sorted should contain the string identifier of the gadget and the string identifier of a possibly referenced gadget.

Which brings us to your first question

Q1: Is it definitely an integer and can it have a value from -2^63 to 2^63-1? Or is that range much smaller?
A1: The range of values is not numeric in the real use case, but a string.

Q2: Is it allowed to use double the memory as the original list consumes while sorting?
A2: Yes, it is possible and I think the idea is excellent. At least I just have a vague idea of a completely different sorting algorithm based on two lists. I will try that out later.

Entry: 100 - Ref to: 0
Entry: 700 - Ref to: 0
Entry: 800 - Ref to: 700
Entry: 600 - Ref to: 800
Entry: 300 - Ref to: 600
Entry: 200 - Ref to: 300
Entry: 400 - Ref to: 0
Entry: 500 - Ref to: 600

Q3: Why is Entry 500 at the end not before Entry 400 or even before Entry 300?
A3: Because the requirement only says that a referenced entry must be BEFORE the entry it is referenced from. Entry "500" references entry "600" and the "600" is sorted before the entry "500". Condition met.

Why entry "500" is at the very end depends on how the sort algorithm works. It is not intentionally planned for this entry to be at the end - it doesn't matter where it is as long as the condition is met. The list must be worked through completely anyway when resizing the window. Therefore it does not matter at which position the entry "500" is processed. The main thing is that the sorting of the reference entries is correct.

I will have a look at your link to the "topological sorting", if I am not at work later.

[wilbert]

But this also means that the elements in the map are not sorted (you cannot sort a map). I only need sorted access to this map in one place in the whole module. And that is, in the function that realigns and/or resizes all the gadgets on a resize event.

Can't you just give the map entries a sequential number at creation time and sort on that?
It looks like you only reference elements which are created in the past.

Another idea might be a LinkedHashMap which is a combination of hash table and linked list.

[Olli]

I failed two times to code anything. The 1st time with a strange bug where the pointers of the list elements were chaotic, and I did not want to investigate to know if it was a native behaviour, or if it was from my bad.

The 2nd time, I was stopped when I have discovered a map element selection function from a pointer did not exist :

Code: Select all

SelectMapElement(myMap(), *elementAddress)

.

A failure causes a code reset, and new start from zero, with more sub-functions creations to bypass a feature miss. Now, as juergenkulow and nicTheQuick said, I am with a homemade map (It is published, and use prime numbers).

But... Now, kurzer, you open our eyes with a concrete example, and the UI goal, I hesitate to continue to this optimization (more than 200 lines to try to execute quicker than your own clear algo).

I do not like this point of view : it is not by miss of own source code. But it is how Windows executes your interface displaying update. Even on best computers, it flickers. I have an example optimized enough : I use only arrays ! Plus, these arrays are fixed ! (in this example, it is a 3*3 cases array, the quickest data object we can use...)

You can look the testIt is ugly : it flickers...

It is on a level, where I ask myself if, when you want to update window elements positions, if it is not better to recreate a whole hidden window, and swap the two windows (old versus new), without glittering animation.

So, in the point of view, my next small project of UI will have an other data architecture : a tree of grids based on dynamic linear arrays :

Code: Select all

structure grid
   array x.d(0) ; pointed by position indices
   array y.d(0)
 endStructure
 
 structure gridTree
    *first
    *previous
    *parent
    *next
    *last
    
    *grid.grid
    
    array x.i(0) ; indices pointed by position
    array y.i(0)
    array w.d(0) ; pointed by size
    array h.d(0)
 endStructure
 
 structure uiObject
  gadget.i
  gadgetType.i
  *gridTree
  position.i
  size.i
 endstructure

x,y integers are indices to x,y doubles.

Now, if I am not too tired I continue to explode my brain with your algo, without imagining it is for UI, but for the contest game. There is any very interesting things to understand in solving your question. I was very near just prevented from success by this miss of map element selection... (!)

[Kurzer]

Can't you just give the map entries a sequential number at creation time and sort on that?
It looks like you only reference elements which are created in the past.

This would mean that the user of my module has to consider the order of the gadgets himself. This is exactly what I wanted to avoid and equip the module with the ability to automatically put the gadget-entries in the gadget management map in an optimal order internally.

Another idea might be a LinkedHashMap which is a combination of hash table and linked list.

How do you envision this in concrete terms?
The list I want to use (or have already used in my test code) would be filled automatically anyway when the gadgets are created - quasi parallel to the gadget management map.

However, also in the list the entries would initially be in exactly the order in which the user created the gadgets. Therefore the following sorting is necessary.

The sorting function already exists. The question now is whether another implementation (e.g. with a LinkedHashMap) can do the sorting of my test data in less than 23 list/map accesses.

[wilbert]

Okay, I understand it a bit better now.
Below is my attempt with the help of a temporary map.

Code: Select all

Structure MyStruct
  Entry.i
  RefEntry.i
  Done.i
EndStructure

NewList StructList.MyStruct()

AddElement(StructList()) : StructList()\Entry = 100
AddElement(StructList()) : StructList()\Entry = 200 : StructList()\RefEntry =300
AddElement(StructList()) : StructList()\Entry = 300 : StructList()\RefEntry =600
AddElement(StructList()) : StructList()\Entry = 400
AddElement(StructList()) : StructList()\Entry = 500 : StructList()\RefEntry =600
AddElement(StructList()) : StructList()\Entry = 600 : StructList()\RefEntry =800
AddElement(StructList()) : StructList()\Entry = 700
AddElement(StructList()) : StructList()\Entry = 800 : StructList()\RefEntry =700

; SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\RefEntry), TypeOf(MyStruct\RefEntry))

ForEach StructList()
  Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
Next
Debug "----------------------------"


NewMap Reference.i()
j = ListSize(StructList()) - 1
For i = 0 To j
  SelectElement(StructList(), i)
  EntryKey.s = Str(StructList()\Entry)
  If Not StructList()\RefEntry
    MoveElement(StructList(), #PB_List_First)
    Debug "Entry " + EntryKey + " moved to front of list"
  Else	  
    RefEntryKey.s = Str(StructList()\RefEntry)
    If Not Reference(RefEntryKey)
      Reference(RefEntryKey) = @StructList()
    EndIf
    If Reference(EntryKey)
      MoveElement(StructList(), #PB_List_Before, Reference(EntryKey))
      Debug "Entry " + EntryKey + " moved before referenced entry"
    Else
      Debug "Entry " + EntryKey + " not moved"
    EndIf
  EndIf
Next
FreeMap(Reference())	


Debug ""
Debug "--------------" + Str(ProcessCounter) + " entries processed ----------------------------"
Debug ""

ForEach StructList()
  Debug "Entry: " + Str(StructList()\Entry) + " - Ref to: " + Str(StructList()\RefEntry)
Next

Edit:
I seem to have made a mistake.
It works for the test list but I could also construct a list where it fails.

[Olli]

Edit:
I seem to have made a mistake.
It works for the test list but I could also construct a list where it fails.

Welcome to the club Wilbert ! ! ! A try and... Then nop ! Do not worry, you can see I did the same circuit !

The success is born in the fails also.

So sure you will reach a successful source code before my own mind.

But this problem gives me any solve technics.

It seems that the algo is :

(in a list)
each entry has the status flag :
- already read

the algo has three variables :
- handling mode (on/off)
- alpha, a place in the list
- beta, a place in the list

Implicite variable :
- current entry

Code: Select all

[0] record the place before the first entry in the list, and stores it in "alpha"
[1] read the next entry (so, on start, it is the first entry)
[2] Set it as status "already read"
[3] has it reference ? Yes : Go to (8)
[4] Is the handling mode on ? No : Go to (7) 
[5] Set the alpha place as current.
[6] Set the handling mode off. Go to (1)

[7] Record the list place in alpha. Go to (1)

[8] Set the handling mode on
[9] Record place to beta.
[10] Set the referring entry as current
[11] Has the entry already read ? No : Go to  (13)
[12] Yes ? Set the beta entry as current. Go to (1)

[13] Move the entry before beta, and consider this entry moved as current. Go to (2)

[Kurzer]

Hello Olli and Wilbert,

sorry for the delay, but I am (as mentioned before) busy with other work most of the day.

But... Now, kurzer, you open our eyes with a concrete example, and the UI goal, I hesitate to continue to this optimization (more than 200 lines to try to execute quicker than your own clear algo).

I do not like this point of view : it is not by miss of own source code. But it is how Windows executes your interface displaying update. Even on best computers, it flickers. I have an example optimized enough : I use only arrays ! Plus, these arrays are fixed ! (in this example, it is a 3*3 cases array, the quickest data object we can use...)

You can look the testIt is ugly : it flickers...

I absolutely do not share these concerns. Your example you linked and also my code (WinHandler) run absolutely smooth and flicker free for me. See the GIF screennrecording below.

It is on a level, where I ask myself if, when you want to update window elements positions, if it is not better to recreate a whole hidden window, and swap the two windows (old versus new), without glittering animation.

Um, absolutely no.
This is about realigning the gadgets in case of a resize action to a window by the user (using the mouse e.g. on the right bottom corner of the window).

I really can't just destroy the window and reopen it while the user is resizing the window with the mouse. That would be completely crazy and the mouse would immediately lose the window focus.

To return to your objection from above. Here is a screengrab of a window managed by my code. All gadgets are kept in a map, which is completely cycled on every size event of the window to recalculate all gadget sizes and positions.

There is absolutely no flickering. What might look jerky here is due to the 8 frames per second with which the screengrabbing was done. In reality it is buttery smooth.




And to get a real impression of why I need this sorting, here is my code with a few gadgets that I intentionally put in the wrong order.

You can see here exactly that some gadgets are aligned to a position that was current at the previous size event. If several gadgets are chained together, then these positioning errors add up.



That is why it is absolutely necessary that the gadgets that refer to other gadget positions are processed in the correct order.

PS: Maybe it makes sense here not to measure the number of accesses to a list/map as a "quality feature" of the algorithm, but the actual execution time (ElapsedMilliSeconds)?

I am glad that you participate in the considerations, thank you very much. Unfortunately I won't be able to work on the code until tomorrow evening, but I think I'll use my sorting in the module like this for now. Maybe it will be exchanged for something more performant later.

[Olli]

My brain flickers anyway
edit: Jes... Again a mistake... A "Set done" before a question "Is done?"...
Edit #2 : pardon, it is good a "CuRrenT = REFering" is between the previous "Set Done" step and the "Is done ?". So...
It is my last word, kurzer !
I m going to pounce... Apologize for the source code... Plus, I have to let Wilbert approach who is penalized by a late arrival...

[Olli]

equivalent source code ("done" fields are not reset) :

Code: Select all

Structure entry
 value.i
 *ref
 done.i
EndStructure

Structure entryList
 List e.entry()
EndStructure

Procedure entryListSortLinks(*this.entryList)
 Protected hnd ; HaNDling status flag
 Protected alpha, beta ; pointers
 With *this\e()
  FirstElement(*this\e() )
  Repeat
   If \ref
    If hnd = 0
     alpha = *this\e()
     hnd = 1
    EndIf
    beta = *this\e()
    \done = 1
    ChangeCurrentElement(*this\e(), \ref)
    If \done
     ChangeCurrentElement(*this\e(), beta)
     \done = 1
    Else
     MoveElement(*this\e(), #PB_List_Before, beta)
     \done = 1
     PreviousElement(*this\e() ) ; "Continue" statement cannot bypass "Until" test ! Forced to go back ! ! !
     Continue
    EndIf
   Else
    If hnd
     hnd = 0
     ChangeCurrentElement(*this\e(), alpha)
    EndIf
    \done = 1
   EndIf
  Until NextElement(*this\e() ) = 0
 EndWith
EndProcedure

[Olli]

You can see I ignore the user referencies : I replaced them with the list element pointers referenced. That is not good...

Let's imagine there won't be more than 4000 gadgets, and let's create a homemade map 16384-cells array :

Code: Select all

Procedure hash(*a.unicode, r = 0)
 While *a\u
  r >> 1 ! ($2000 * ((r & 1) ! 1) ) ! *a\u
  *a + 2
 Wend
 ProcedureReturn r
EndProcedure

Debug hash(@"hello")
Debug hash(@"homemade")
Debug hash(@"map")

Dim _map($3FFF)

_map(hash("100") ) = 600
_map(hash("200") ) = 300

Instead of 600 and 300 you could store the list element addresses of your referencies.

In the algo draw more above, you have a stick :

Code: Select all

[  Crt = Ref  ]     ; CuRrenT element = REFerency

I translated it with :

Code: Select all

ChangeCurrentElement(*this\e(), \ref)

But, for your case, "ref" is not an address, but a real referency. So, I should advice you to write :

Code: Select all

ChangeCurrentElement(*this\e(), _map(hash(\ref) ) )

With a real ref variable value which should be really 100, 200, or other...

Now, all is good... All is good, until the day when you come back with a bug request, because a gadget #177 has destroyed an other gadget #190.

Why ?

Code: Select all

Debug hash(@"177")
Debug hash(@"190")

Respond : the two different strings give, through our hashing algo example, give the same code : 2080.

So, the same array cell is used by two different gadgets, to store their own list element address. This bug, in a hash map, is name a collision.

To solve this problem, 2 ways :
- find a slower hash algo which better blends the string character combinations, it digests.
- manage the collision, by allocating more memory, and create more levels than only one.

[Kurzer]

I think I have now found a very satisfactory solution through the symbiosis of list and map.

I have now measured the performance of my three different sorting functions using a high-resolution performance timer and no longer in the number of list accesses, since a map is now also involved.

With the sort function "V3" I could achieve a speedup by a factor of 53 (with the debugger switched on).

Here are the timings for a list with 1000 entries and 500 references.

[21:16:05]
[21:16:05] [Debug] V1: 46320 microseconds.
[21:16:05] [Debug] V2: 46322 microseconds.
[21:16:05] [Debug] V3: 870 microseconds.

Attached is the heavily modified test framework. Sorting is now realized in separate procedures, so it is very easy to add new sort functions for comparison,

I will now work with version V3 in my project and thank all of you who have also racked their brains for me.

There were some good ideas that led to the fact that I could now developed algorithm V3. Thanks a lot!

Olli, thanks to you too for your diligent input. Your last example is hard for me to follow due to the not very speaking variable names, but maybe you have the musse to prepare your code as a procedure for the test framework posted here?

Kurzer

Code: Select all

EnableExplicit

Structure MyStruct
	Entry.s
	RefEntry.s
	Sort.i
EndStructure

Global NewList StructList.MyStruct()
Global NewMap StructMap.MyStruct()
Define i, StartTime, Duration

; -----------------------------------

; Procedure for high resolution time measurement, thanks go to Axolotl
; https://www.purebasic.fr/english/viewtopic.php?p=589086#p589086
Procedure.i ElapsedMicroseconds()
	Static frequency.q
	Protected count.q
	
	If frequency = 0 
		If QueryPerformanceFrequency_(@frequency)
			; frequency / 10000      ; .. divide frequency by 10000 for tenths of a millisecond 
			; frequency / 1000   		 ;:: in milli seconds 
			; frequency / 1000   		 ;:: in micro seconds 
			frequency / 1000000      ;:: in micro seconds 
		EndIf 
	EndIf
	
	If QueryPerformanceCounter_(@count)
		ProcedureReturn count / frequency 
	Else
		ProcedureReturn 0
	EndIf 
EndProcedure 

; The sorting procedures
Procedure Sortlist_V1()
	Protected i, j, SearchStart = 0, SearchEnd = ListSize(StructList()) - 1, *Entry
	Protected.s RefEntry
	
	For i = SearchStart To SearchEnd - 1
		SelectElement(StructList(), i)
		If StructList()\RefEntry <> ""
			*Entry = @StructList()
			RefEntry = StructList()\RefEntry
			For j = i + 1 To SearchEnd
				SelectElement(StructList(), j)
				If StructList()\Entry = RefEntry
					If StructList()\RefEntry <> ""
						i - 1
					EndIf
					MoveElement(StructList(), #PB_List_Before, *Entry)
					Break
				EndIf
			Next
		EndIf
	Next	
EndProcedure
Procedure Sortlist_V2()
	Protected i, j, SkipEntries, SearchStart = 0, SearchEnd = ListSize(StructList()) - 1, *Entry
	Protected.s RefEntry
	
	For i = SearchStart To SearchEnd - 1
		SelectElement(StructList(), i)
		If StructList()\RefEntry <> ""
			*Entry = @StructList()
			RefEntry = StructList()\RefEntry
			For j = i + 1 To SearchEnd
				SelectElement(StructList(), j)
				If StructList()\Entry = RefEntry
					If StructList()\RefEntry <> ""
						i - 1
						SkipEntries + 1
					Else	
						i + SkipEntries
						SkipEntries = 1
					EndIf
					MoveElement(StructList(), #PB_List_Before, *Entry)
					Break
				EndIf
			Next
		EndIf
	Next
EndProcedure
Procedure SortList_V3()
	Protected Sortvalue = 0	
	#Blocksize = 1000
	; We work through the list from beginning to end using the following logic:
	
	; 1) We sort the list in ascending order by RefEntry, so that all entries without RefEntry are at the beginning
	; 2) We go through the list once from beginning to end to get the sorted element names
	;    These represent the keys of the identical map. In this loop, only the entries of the map are processed.
	;    a) If the map entry does *not* reference any other entry and field sort = 0: 
	;       - The map entry gets in the field Sort = Sortvalue
	;       - Sortvalue = Sortvalue + #Blocksize (1000)
	;    b) If the map entry *does* reference any other entry:
	;       - If the referenced entry in the map has no Sortvalue yet:
	;         - The referenced map entry gets in the field Sort = Sortvalue
	;         - Sortvalue = Sortvalue + #Blocksize (1000)
	;         - After this:
	;           - If the map entry referencing the other element does not yet have a Sortvalue:
	;             - The map entry gets in the field Sort = Sortvalue
	;             - Sortvalue = Sortvalue + #Blocksize (1000)
	;       c) If the referenced(!) entry in the map already has a sortvalue:
	;            - The entry that references it gets the Sortvalue + 1 from the referenced entry 
	;            - Sortvalue = Sortvalue + #Blocksize (1000)
	; 3) We sort the list in ascending order by the field sort
	
	; 1)
	SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\RefEntry), TypeOf(MyStruct\RefEntry))
	
	With StructList()
		; 2)
		ForEach StructList()
			; 2b)
			If \RefEntry <> ""
				If StructMap(\RefEntry)\Sort = 0
					StructMap(\RefEntry)\Sort = Sortvalue
					Sortvalue + #Blocksize
					If StructMap(\Entry)\Sort = 0
						StructMap(\Entry)\Sort = Sortvalue
						Sortvalue + #Blocksize
					EndIf
					; 2c)
				Else
					StructMap(\Entry)\Sort = StructMap(\RefEntry)\Sort + 1
					Sortvalue + #Blocksize
				EndIf
				; 2a)	
			ElseIf StructMap(\Entry)\Sort = 0
				StructMap(\Entry)\Sort = Sortvalue
				Sortvalue + #Blocksize
			EndIf
		Next
		
		ForEach StructList()
			\Sort = StructMap(\Entry)\Sort
		Next	
	EndWith
	
	; 3)
	SortStructuredList(StructList(), #PB_Sort_Ascending, OffsetOf(MyStruct\Sort), TypeOf(MyStruct\Sort))
	
EndProcedure

; -----------------------------------

; Initializing the list and map
Procedure Init()
	Protected  i
	ClearList(StructList())
	ClearMap(StructMap())
	
	; We create a list of n entries to get enough runtime for a time measurement.
	For i = 1 To 1000 Step 10
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+1)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+2) : StructList()\RefEntry = "gadget_" + Str(i+5)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+3) : StructList()\RefEntry = "gadget_" + Str(i+4)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+4) : StructList()\RefEntry = "gadget_" + Str(i+2)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+5)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+6) : StructList()\RefEntry = "gadget_" + Str(i+8)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+7)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+8) : StructList()\RefEntry = "gadget_" + Str(i+7)
		AddElement(StructList()) : StructList()\Entry = "gadget_" + Str(i+9)
	Next i
	
	; Now we create a map with the same content as the list
	ForEach StructList()
		StructMap(StructList()\Entry)\Entry =StructList()\Entry
		StructMap(StructList()\Entry)\RefEntry =StructList()\RefEntry
	Next
	
	; All steps up to here can be realized in my use case by the code area responsible for registering a gadget in my module.
	; Therefore this code part must not be included in the time measurement.
EndProcedure

; -----------------------------------

; START

Init()

; Debug ""
; Debug "*** List - Unsorted:"
; ForEach StructList()
; 	Debug "Entry: " + StructList()\Entry + " - Ref to: " + StructList()\RefEntry + " - Sort: " + Str(StructList()\Sort)
; Next
; Debug "----------------------------"

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V1()
	Duration = ElapsedMicroseconds() - StartTime
	Debug "V1: " + Str(Duration) + " microseconds."
EndIf

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V2()
	Duration = ElapsedMicroseconds() - StartTime
	Debug "V2: " + Str(Duration) + " microseconds."
EndIf

If 1=1
	Init()
	StartTime = ElapsedMicroseconds()
	SortList_V3()
	Duration = ElapsedMicroseconds() - StartTime
	Debug "V3: " + Str(Duration) + " microseconds."
EndIf

; Debug ""
; Debug "*** Finally list - Sorted by Sort:"
; ForEach StructList()
; 	Debug "Entry: " + StructList()\Entry + " - Ref to: " + StructList()\RefEntry + " - Sort: " + Str(StructList()\Sort)
; Next

Edit: Added a missing init() in the source.

[yuki]

It sounds like a DAG suits your use case.

We can model the control anchoring scheme through a tree, and ensure proper hierarchy as elements are inserted/removed/changed, e.g.:

Code: Select all

EnableExplicit

Structure UIControlAnchorInfo
  ; Control which the relevant one depends on layout for.
  *parent.UIControl
  ; First of the controls which depend on the relevant one for layout.
  *firstChild.UIControl
  ; Next sibling of the relevant control within its layer.
  *nextSibling.UIControl
  ; Previous sibling of the relevant control within its layer.
  *prevSibling.UIControl
  ; Put other anchor/relative-positioning info here...
EndStructure

Structure UIControl
  name.s
  anchoring.UIControlAnchorInfo
  *window.UIWindow
  ; Put other control data here.
EndStructure

Structure UIWindow
  Map controlsByName.UIControl()
  root.UIControl
EndStructure

; This procedure would assumingly accept additional arguments specifying how anchoring is
; to be done.
Procedure AnchorControl(*control.UIControl, *anchorParent.UIControl)  
  Protected *currentParent.UIControl
  Protected *prevSibling.UIControl
  Protected *nextSibling.UIControl
  
  ; Before anything, do safety checking and ensure acyclicity.
  ; Catch the most trivial self:self case.
  If *control = *anchorParent
    DebuggerError("Attempted to produce control cycle with self: " + *control\name + " <-> " + *control\name)
    End
  EndIf
  ; Walk the tree to prevent making *control parented by one if its own children.
  ; This could instead be handled by restructuring the tree to invert the relationship.
  If *anchorParent
    *currentParent = *anchorParent\anchoring\parent
    While *currentParent
      If *currentParent = *control
        ; You could store the path walked to produce a better message here.
        DebuggerError("Attempted to produce control cycle with self: " + *control\name + " <-> " + *control\name + ", via: " + *anchorParent\name)
        End
      EndIf
      *currentParent = *currentParent\anchoring\parent
    Wend
  Else
    ; Default to window root if no anchor parent it set.
    *anchorParent = *control\window\root
  EndIf
  
  ; Handle un-linkage when a parent is already present.
  *currentParent = *control\anchoring\parent
  If *currentParent
    ; Bail early if attempting to anchor to the current anchor target.
    If *currentParent = *anchorParent
      ProcedureReturn *control
    EndIf
    
    ; Detach from siblings.
    *prevSibling.UIControl = *control\anchoring\prevSibling
    *nextSibling.UIControl = *control\anchoring\nextSibling
    If *prevSibling
      *prevSibling\anchoring\nextSibling = *nextSibling
    Else
      ; If no prior sibling exists, then this node was the head of its layer, in which
      ; case the next sibling should take its place.
      *currentParent\anchoring\firstChild = *nextSibling
    EndIf
    If *nextSibling
      *nextSibling\anchoring\prevSibling = *prevSibling
    EndIf
  EndIf
  
  ; Previous relations have been unlinked. Assign the new state.
  *control\anchoring\parent = *anchorParent
  *control\anchoring\prevSibling = #Null
  *nextSibling = *anchorParent\anchoring\firstChild
  *anchorParent\anchoring\firstChild = *control
  *control\anchoring\nextSibling = *nextSibling
  
  If *nextSibling
    *nextSibling\anchoring\prevSibling = *control
  EndIf
  
  ProcedureReturn *control
EndProcedure

Procedure.i CreateControl(*window.UIWindow, name.s)
  Protected *control.UIControl = FindMapElement(*window\controlsByName(), name)
  
  ; Treat reused control name as fatal error.
  ; Up to you to do something else.
  If *control
    DebuggerError("Attempted to reuse control name: " + name)
    End
  EndIf
  
  *control = AddMapElement(*window\controlsByName(), name)
  *control\window = *window
  *control\name = name
  
  ; Anchor to root.
  AnchorControl(*control, #Null)
  
  ProcedureReturn *control
EndProcedure

; Procedure for high resolution time measurement, thanks go to Axolotl
; https://www.purebasic.fr/english/viewtopic.php?p=589086#p589086
Procedure.i ElapsedMicroseconds()
	Static frequency.q
	Protected count.q
	
	If frequency = 0 
		If QueryPerformanceFrequency_(@frequency)
			; frequency / 10000      ; .. divide frequency by 10000 for tenths of a millisecond 
			; frequency / 1000   		 ;:: in milli seconds 
			; frequency / 1000   		 ;:: in micro seconds 
			frequency / 1000000      ;:: in micro seconds 
		EndIf 
	EndIf
	
	If QueryPerformanceCounter_(@count)
		ProcedureReturn count / frequency 
	Else
		ProcedureReturn 0
	EndIf 
EndProcedure 

Procedure Init_Tree(*window.UIWindow)
  Protected i
  
	ClearMap(*window\controlsByName())
	
	; We create a list of n entries to get enough runtime for a time measurement.
	For i = 1 To 1000 Step 10	  
	  ; Create all the controls.
	  CreateControl(*window, "gadget_" + Str(i))
	  CreateControl(*window, "gadget_" + Str(i + 1))
	  CreateControl(*window, "gadget_" + Str(i + 2))
	  CreateControl(*window, "gadget_" + Str(i + 3))
	  CreateControl(*window, "gadget_" + Str(i + 4))
	  CreateControl(*window, "gadget_" + Str(i + 5))
	  CreateControl(*window, "gadget_" + Str(i + 6))
	  CreateControl(*window, "gadget_" + Str(i + 7))
	  CreateControl(*window, "gadget_" + Str(i + 8))
	  CreateControl(*window, "gadget_" + Str(i + 9))
	  
	  ; Assign refs.
	  ; 2 ⟶ 5
	  AnchorControl(*window\controlsByName("gadget_" + Str(i+2)), *window\controlsByName("gadget_" + Str(i+5)))
	  ; 3 ⟶ 4
	  AnchorControl(*window\controlsByName("gadget_" + Str(i+3)), *window\controlsByName("gadget_" + Str(i+4)))
	  ; 4 ⟶ 2
	  AnchorControl(*window\controlsByName("gadget_" + Str(i+4)), *window\controlsByName("gadget_" + Str(i+2)))
	  ; 6 ⟶ 8
	  AnchorControl(*window\controlsByName("gadget_" + Str(i+6)), *window\controlsByName("gadget_" + Str(i+8)))
	  ; 8 ⟶ 7
	  AnchorControl(*window\controlsByName("gadget_" + Str(i+8)), *window\controlsByName("gadget_" + Str(i+7)))
	Next i
	
EndProcedure

Procedure FlattenControlTree(*control.UIControl, List *outControls.UIControl())
  Protected *currentControl.UIControl = *control\anchoring\firstChild
  While *currentControl
    AddElement(*outControls())
    *outControls() = *currentControl
    FlattenControlTree(*currentControl, *outControls())
    *currentControl = *currentControl\anchoring\nextSibling
  Wend
EndProcedure

Procedure PrintPrettyTree(*control.UIControl, depth.i = 0)
  If Not depth
    PrintN("Root(name = " + #DQUOTE$ + *control\name + #DQUOTE$ + ")")
  Else
    PrintN(Space(depth * 4) + *control\name)
  EndIf
  
  Protected *currentControl.UIControl = *control\anchoring\firstChild
  While *currentControl
    PrintPrettyTree(*currentControl, depth + 1)
    *currentControl = *currentControl\anchoring\nextSibling
  Wend
EndProcedure

If Not OpenConsole()
  MessageRequester("Fatal Error", "Failed to open console!", #PB_MessageRequester_Error)
  End
EndIf

Define window.UIWindow
Define startTime, elapsedTimeInit, elapsedTimeFlatten

startTime = ElapsedMicroseconds()
Init_Tree(window)
elapsedTimeInit = ElapsedMicroseconds() - startTime


PrintN("# controls: " + MapSize(window\controlsByName()))
PrintN("==================================================")

; Flatten tree into a new list.
; ═══════════════════════════════════════════════════════
; There's no need to sort it, since controls are sorted
; as they are inserted.
; Normally, when rendering, you'd walk the tree without
; this copying and simply render in proper order.
NewList *orderedControlsFlat.UIControl()

startTime = ElapsedMicroseconds()
FlattenControlTree(window\root, *orderedControlsFlat())
elapsedTimeFlatten = ElapsedMicroseconds() - startTime

; Print flattened list.
ForEach *orderedControlsFlat()
  If *orderedControlsFlat()\anchoring\parent <> window\root
    PrintN("Entry: " + *orderedControlsFlat()\name + " via: " + *orderedControlsFlat()\anchoring\parent\name)
  Else
    PrintN("Entry: " + *orderedControlsFlat()\name)
  EndIf
Next
PrintN("==================================================")

; Print structured tree.
; ═══════════════════════════════════════════════════════
PrintPrettyTree(window\root)
PrintN("==================================================")

; Print time taken.
; ═══════════════════════════════════════════════════════
PrintN("Time to init tree: " + elapsedTimeInit + "µs")
PrintN("Time to flat tree: " + elapsedTimeFlatten + "µs")
Input()

Note: run with executable format = console.

Results (PB 6.02 LTS – ASM, Windows 11 x64, 5800X):

Code: Select all

==================================================
Time to init tree: 356µs
Time to flat tree: 34µs

Results for your approach on the same system:

Code: Select all

Time to init: 419 microseconds
V1: 2460 microseconds.
V2: 1119 microseconds.
V3: 186 microseconds.

The approach I've taken has the set of controls always maintain proper hierarchy as they're updated. Thus, the "time to init tree" measures the combination of both creation and reordering like your sorting does; there's no need to sort this collection in bulk after the fact.

This is accomplished while initialising faster, taking less memory, and adding safety checks to prevent cycles and reused control names.

Since there's no bulk sort, and hierarchy setup is negligible during initialisation, I've measured a pass that loops over all controls and appends their references to a new flat list. You could instead skip initial anchoring, and measure this process separately to isolate the "sorting" cost.

Similarly, significant time is saved whenever controls are added/removed and/or relationships updated, as only needed controls are affected.

Notes: optimised Map usage and allocations would be massively beneficial here.

Offtopic: nice IDE colour scheme!

[Kurzer]

Hello Yuki,

yeah, I was hoping the experts would speak up at some point.

I have never heard of DAG* before (and had to google it), but your solution seems to be "industry standard". It is programmatically more complex, but much more flexible and secure than my approach. Therefore many thanks for your effort!

In my solution, I can only map 999 iterative gadget references by using the block size of 1000, but I think that is sufficient for my use case.

About removing and adding gadgets during the runtime of a program (which uses my WinHandler module), I haven't thought about it at all. So thank you for this food for thought, I have to consider this in my module.

I'm not sure yet if I need a DAG solution for my module, because except for the sorting everything else is completely done (the anchoring, the reading and saving of the gadget contents etc.). I would have to rebuild almost the whole module if I would change the gadget management to DAG.

Second, the DAG solution on my machine is about nine times slower than the V3 sort.
DAG: Init: 6579 uS + flatten: 1629 uS = 8208 uS
V3: 870 uS

For sure I will save your code as reference in my template folder.
Thanks again for your effort! Code releases like this are a great thing.

* There are so many terms where DAG stands for, I hope I found the correct one: "Directed Acyclic Graph" - LOL

[yuki]

yeah, I was hoping the experts would speak up at some point.

Ahah, I wouldn't go so far as "expert"

Second, the DAG solution on my machine is about nine times slower than the V3 sort.
DAG: Init: 6579 uS + flatten: 1629 uS = 8208 uS
V3: 870 uS

This seems like a side-effect of the debugger having a much greater performance impact as the number of source lines increase. The DAG approach will have a lot more time spent hitting each line (and updating debugger info) since much of the logic is contained within itself rather than PB library functions like SortStructuredList(…).

For this reason, I measured all approaches with debugger off (adapting the test code to use PrintN(…) instead of Debug).

I'm not sure yet if I need a DAG solution for my module, because except for the sorting everything else is completely done (the anchoring, the reading and saving of the gadget contents etc.). I would have to rebuild almost the whole module if I would change the gadget management to DAG.

Absolutely – your approach already seems quite fast given many gadgets! I wouldn't use the more complex DAG approach unless it seemed really necessary to cure a bottleneck.

* There are so many terms where DAG stands for, I hope I found the correct one: "Directed Acyclic Graph" - LOL

That's right! (I should've put that in parentheses, since woah Google does turn up loads of stuff for it)

Always happy to share some tricks! (and for a little challenge )