Why is _ArraySort so broken? Updated 1/9/22 630pm g2g

[markyrocks]

Updated 1/4/2022: added pointer sort test, float sort test, double sort test, insort test, enums and a few other utility functions.  The .ccp is kinda messy rn.  Not too worried about it. 

Updated 1/9/22 ... I totally missed the fact that the dll wasn't actually included in the files. Duh.  Been so busy sry.  Its in there now.  The files originally on this page are gone

It's an obsolete test anyways.  I've move far beyond it.  Its been replaced with the latest test/example.  Sorry I suck and files and editing posts apparently.

So what got me started down this road is from another recent thread i'm sure you've all seen it.   I don't use autoit that much anymore except for trying to break it or make it do stuff that it doesn't want to, in an effort to improve it if I can.  Writing this actually just gave me an idea which is pretty cool. Anyways.  It seems that theres a fear of using arraysort bc its so amazingly slow which it is.  I was wondering if i could fix that and well.... I did to a small degree.  It would need to get alot more complicated from here to actually fix it the write way so that it would be full featured and recognize autoit datatypes and pass that information along and on the dll end it would need some overloads or a "more elegant" solution.  That being said all this does is work on integers atm.  ## copying the array to a dllstruct takes about 1500 ms ... the dll sort takes about 25 ms.  (on my pos 5 year old laptop) copying the resulting sorted struct to a autoit array takes about 1500 miliseconds ## The built in arraysort takes roughly 10x longer of those combined.  So simply accessing from the resulting dllstruct will deffinitly save some time.  

I played around with this for a few hours, tested it many times so that I made sure its all working correctly.

anyways I'll post the test script here and attach the source.cpp and header if anyone wants to build it themselves and the dll.

Spoiler

expandcollapse popup

#include <Array.au3>
Global Enum $INT32_,$INT64_,$FLOAT_,$DOUBLE_,$HANDLE_,$POINTER_,$HWND_,$STRUCT_,$BINARY_,$BOOL_,$STRING_,$ARRAY_
Global Const $TYPE_[12]=["int","int64","Float","double","handle","ptr","Hwnd","Struct","byte","int","char","Array"]
Global Const $size = 10
Global $array[$size]


;~  GenerateArrayInt($array)
;~  for $i in $array
;~   ConsoleWrite($i & @CRLF)
;~  Next
;~  GenerateArrayDouble($array)
;~  GenerateArrayFloat($array)
 GenerateArrayPointer($array)



;~

ArraysortTest()




func ArraysortTest()
;~ $timer=TimerInit()\

$dll=DllOpen(@ScriptDir& "\autoitdll.dll")
if $dll=-1 then Exit

    $struct=ArrayToStruct($array)
;~  ConsoleWrite(DllStructGetPtr($struct & @CRLF))

        $result = DllCall($dll,"handle:cdecl","test","ptr",DllStructGetPtr($struct),"int",$size,"int",ArrayTypeToEnum($array[0]))
        if IsArray($result) Then
;~          ConsoleWrite("sucess" & @CRLF)
;~          _ArrayDisplay($result)

;~          for $i=1 to $size
;~              ConsoleWrite(DllStructGetData($struct,1,$i) & @CRLF)
;~              Next

            $struct=StructToArray($struct,$size)

        for $i in $struct
            ConsoleWrite($i & @CRLF)
            Next
        Else

        ConsoleWrite("faile")

    EndIf



DllClose($dll)




EndFunc

Func GenerateArrayInt(ByRef $a)
  For $i = 0 To UBound($a) - 1
    $a[$i] = Random(-1000000, +1000000,1)
  Next
EndFunc

func GenerateArrayDouble(ByRef $a)
  For $i = 0 To UBound($a) - 1
    $a[$i] = Random(-1000000, +1000000)
  Next
EndFunc

func GenerateArrayFloat(ByRef $a)
  For $i = 0 To UBound($a) - 1
    $a[$i] = number("" & Random(-1000000, +1000000,1) & "." & Random(0,99,1),3)
  Next
EndFunc

func GenerateArrayPointer(ByRef $a)
    For $i = 0 To UBound($a) - 1
    $a[$i] = ptr( Random(0, 0x5FFFFFFF,1))

  Next
EndFunc

;the below function has not been implemented yet..............super slow
Func ArrayToStringStruct(Const ByRef $a)             ;basically turns everything into a string..... this is probably trash shoudld just allocate and read and write to process memory directly
    $pStruct=DllStructCreate("ptr[" & UBound($a)-1 & "]")      ;test result= ~7000ms on 100000 int elements boooooooooo
    $x=1
    for $i in $a
        $string="" & $i
        $sStruct=DllStructCreate("char[" & StringLen($string) & "]")
        DllStructSetData($sStruct,1,$string)                        ;------------might need to add termination character
        DllStructSetData($pStruct,1,DllStructGetPtr($sStruct),$x)
        $x+=1
    Next
    return $pStruct
EndFunc




func ArrayToStruct(Const ByRef $arr)
    $sType=ArrayTypeToEnum($arr[0])
;~  ConsoleWrite($sType & @crlf)
;~  ConsoleWrite(EnumToType($sType) & @CRLF)
    $sz=UBound($arr)-1
 $s=DllStructCreate("" & EnumToType($sType) & "[" & $sz+1 & "]")
 For $i=0 to $sz
    DllStructSetData($s,1,$arr[$i],$i+1)
;~  ConsoleWrite(DllStructGetData($s,1,$i+1) & @crlf)
 Next
 return $s
EndFunc

func StructToArray($str,$s)
    local $a[$s]
    for $i=0 to $s-1
        $a[$i]=DllStructGetData($str,1,$i+1)
    Next
    return $a
EndFunc

func TypeToEnum($type)
    for $i=0 to ubound($TYPE_)-1
        if $TYPE_[$i]=$type Then
            return $i
        endif
    Next
    return -1
EndFunc

func EnumToType($Enum)
    if $Enum>0 And $Enum<12 Then
        return $TYPE_[$Enum]
        EndIf
    return -1
EndFunc

func ArrayTypeToEnum(Const ByRef $data)     ;$INT32=1,$INT64,$FLOAT,$DOUBLE,$HANDLE,$POINTER,$HWND,$STRUCT,$BINARY,$BOOL,$STRING,$ARRAY
    $type=VarGetType($data)
;~      ConsoleWrite(VarGetType($type))
    Select
        Case $type="Bool"
            Return $BOOL_
        Case $type="Int32"
            Return $INT32_
        Case $type="Int64"
            Return $INT64_
        Case $type = "String"
            Return $STRING_
        Case $type="Double"
            Return $DOUBLE_
        Case $type="Float"
            Return $FLOAT_
        Case $type = "Handle"
            Return $HANDLE_
        Case $type = "Ptr"
            Return $POINTER_
        Case $type = "Struct"
            Return $STRUCT_
        Case $type = "Binary"
            Return $BINARY_
        Case $type = "Array"
            Return $ARRAY_
        Case $type = "Hwnd"
            Return $HWND_
        Case Else
            return -1
        EndSelect
    EndFunc

 

 

 

 

 

 

 

 

Edited January 14, 2022 by markyrocks
bc im an idiot

[jchd]

You're right, _ArraySort is an arthritic teethless sleepy dog with only one eye and three legs.

I wanted to write a sort function in AutoIt working similar to C qsort(), that is: relying on a user-supplied collation function. That's the correct approach since only the user can write such collation suited to the array dimensions, datatypes and possibly complex collation (sort) criterions he needs to deal with. Else we see a number of useless parameters, endless variations of the _ArraySort function itself where users have to implant their collation right in the middle of the sort functions inside his own derivation of _ArraySort().

More worrisome is the fact that all this has to be done again for arrays with 1, 2, 3, ..., 24 dimensions. And done again if one column changes from string to integer, or any type change. And done again if the multi-column sort criterion change.

Experienced users have learn to be hurt be these limitations and often have to write weird code and use unnatural way to store their data just because they know in advance how sorting an array the way they would have found natural is painful.

That's why the dog badly needs a surgeon.

For an AutoIt qsort() to work efficiently (in AutoIt), we need:

• an efficient way to declare an array programmatically regardless of its dimensions,
• an efficient way to extract/replace a multidimensional row of an array regardless the dimensions of the array.

Ideally we'd love to have a way to extract/replace a multidimensional block out of an array regardless the dimensions of the array.

We have none of these features.

 

The way to circumvent the issue is either to convert back and forth every indivudual data cell to something a decent language can process, just like you did, or leave the dead body spoil rotten.

It's a pity as it would only need few additions to completely change the game, for instance:

Execute("Local $aNew[$n0][$n1][$n2][$n3][$n4]")   ; create a new 5D array
Local $aExtract = $aBigOne[{$i}]    ; extract multidimentional row $i off array
...    ; deal with $aExtract
$aBigTwo[{$k}] = $aExtract   ; assign multidimentional row in array row $k

 

[markyrocks]

lol it doesn't need a surgeon... that dog needs an undertaker.  It's been awhile since I had a good reason to play with autoit.  Putting in a userdefined function in the outsourcing of the sort shouldn't be that difficult.  We do have dllcallbackregister and the ability to easily pass that pointer to a dll so I'm sure I could probably get that working no problemo.  That is a good idea.  Tho. One that I hadn't thought of.  

Edit..I just threw a template over top of the comparison function so getting all of the number sorting (at least within numerical limits) should be pretty easy to put together

Edited January 2, 2022 by markyrocks

[jchd]

Yeah but dllcallbackregister can't accept arguments nor return a result. Of course that can be bypassed by using global variables but that's one more avoidable complexity.

[markyrocks]

2 hours ago, jchd said:

Yeah but dllcallbackregister can't accept arguments nor return a result. Of course that can be bypassed by using global variables but that's one more avoidable complexity.

I was studying the example and it sure looks like it's accepting arguments and returning a result.   If I'm the one writing the function that uses the callback I should be able to make it do whatever I need it to.  I haven't had a chance to mess with it yet.  I have to do my chores b4 I can play anymore... 😞

https://www.autoitscript.com/autoit3/docs/functions/DllCallbackRegister.htm

[jchd]

Oops, I spoke too fast without thinking twice. Of course it does work in this context, my bad.

I too have a number of VERY urgent things to do.

[junkew]

There are enough alternatives arround. 

 

and probably when its a bigger data set its probably in database  that you easily can sort and filter on with a query.

Edited January 2, 2022 by junkew
link corrected

[AspirinJunkie]

I'm not quite sure what problem of ArraySort is trying to address here.
Is it the performance that should be increased or the fact that you cannot pass a user-defined comparison function?

For the latter, I once wrote a corresponding function (see attachment). With this, you can pass your own comparison function and 2D arrays can also be sorted with this.
The performance, however, does not really increase compared to the normal _ArraySort. In my opinion, this is algorithmically already quite optimised and close to the limit of what AutoIt is capable of. So for larger data sets with more complex sorting rules, a database would probably be worth a look then.

1D-Array example:

#include "DynArray.au3"

$a_Array = StringSplit("image20.jpg;image1.jpg;image11.jpg;image2.jpg;image3.jpg;image10.jpg;image12.jpg;image21.jpg;image22.jpg;image23.jpg", ";", 2)
_ArrayDisplay($a_Array, "the unsorted array")

; sort normal with _ArraySort
_ArraySort($a_Array)
_ArrayDisplay($a_Array, "sorted with _ArraySort")

; sort like the explorer with a natural comparison function
_ArraySortFlexible($a_Array, __MyNaturalCompare)
_ArrayDisplay($a_Array, "natural sorted with _ArraySortFlexible")


; own comparison function as a wrapper for StrCmpLogicalW
Func __MyNaturalCompare(Const ByRef $A, Const ByRef $B)
    Local Static $h_DLL_Shlwapi = DllOpen("Shlwapi.dll")
    Local $a_Ret = DllCall($h_DLL_Shlwapi, "int", "StrCmpLogicalW", "wstr", $A, "wstr", $B)
    If @error Then Return SetError(1, @error, 0)
    If Not IsString($A) Or Not IsString($B) Then Return $A > $B ? 1 : $A < $B ? -1 : 0
    Return $a_Ret[0]
EndFunc   ;==>MyCompare

 

2D-Array example:
 

#include "DynArray.au3"

; create random 2D array
Global $Array[1000][10]
For $i = 0 To 999
    For $j = 0 To 9
        $Array[$i][$j] = Chr(Random(65, 90, 1))
    Next
Next
_ArrayDisplay($Array, "unsorted array", "", 64)

; sort over rows and all columns
_ArraySortFlexible($Array, _SortByColumns)
_ArrayDisplay($Array, "sorted 2D array", "", 64)


; own comparison function which compares stepwise the single columns
Func _SortByColumns(ByRef $A, ByRef $B)
    For $i = 0 To UBound($A) -1
        If $A[$i] > $B[$i] Then Return 1
        If $A[$i] < $B[$i] Then Return -1
    Next
    Return 0
EndFunc

 

DynArray.au3

[markyrocks]

22 minutes ago, AspirinJunkie said:

I'm not quite sure what problem of ArraySort is trying to address here.
Is it the performance that should be increased or the fact that you cannot pass a user-defined comparison function?

For the latter, I once wrote a corresponding function (see attachment). With this, you can pass your own comparison function and 2D arrays can also be sorted with this.
The performance, however, does not really increase compared to the normal _ArraySort. In my opinion, this is algorithmically already quite optimised and close to the limit of what AutoIt is capable of. So for larger data sets with more complex sorting rules, a database would probably be worth a look then.

The problem is that my grandmother is faster at grocery shopping.   I haven't bothered to look into how exactly the ArraySort function operates but the majority of what AutoIt does is accomplished by system calls.  To believe that the mother of all cpu intensive tasks is or should be handled by pure autoit code is just pure malarkey.   As I stated in my original post I was able to speed it up 10 fold and that disparity actually grows as the size gets larger.  I mean damn don't make excuses for it.  It's honestly bs that the devs haven't fixed it by now.  They should be embarrassed.

[junkew]

Its not part of the core AutoIt to do the sorting and as with any UDF there are many different versions of it and if you look around on the forum you will find multiple other UDF's to do the array sorting stuff.

The main question is for which purposes do you need speed for sorting arrays as basically when you need speed you should not be using AutoIt or scripting language but switch to compiled implementation (just like you did with the dll)

See 

 

[pseakins]

1 hour ago, markyrocks said:

They should be embarrassed

I wouldn't be so critical of a FREE and excellent product. @Jonhas no time to work on development and@Josdoes an excellent job of syncing the product with the latest updates to Scite apart from actively supporting this forum responding to many brain dead newbie queries.

[Jos]

Hé, everybody is entitled to their opinion and for sure don't feel personally attacked by somebody wanting to make those kind of statements..   
The last time I worked on any of these UDFs was when there wasn't any option for sorting arrays so just converted some standard Basic Sort routines to AutoIt3, and that's about it....  nothing more nothing less and it has worked for me thus far as I never process larger arrays with AutoIt3 myself as they always go into a SQL server.       Last time I worked on this was probably 15 years ago?  Others have added other sorting routines to make it faster nd maintained it since then.

So all I can say to the person making these kind of statements:  Love you too. 😘

 

Edited January 2, 2022 by Jos

[Nine]

38 minutes ago, Jos said:

Love you too.

I already known that.  But it is good when you recall it.  And Happy New Year to you too.

[markyrocks]

5 hours ago, junkew said:

Its not part of the core AutoIt to do the sorting and as with any UDF there are many different versions of it and if you look around on the forum you will find multiple other UDF's to do the array sorting stuff.

The main question is for which purposes do you need speed for sorting arrays as basically when you need speed you should not be using AutoIt or scripting language but switch to compiled implementation (just like you did with the dll)

See 

 

I'm not trying to stir the pot but If this is a drastic improvement over what is included already why hasn't it replaced the standard?  This is the type of stuff that drives me crazy.  When I'm using other languages I don't have to go sifting endlessly to find some random udf... the good stuff is already included in the language by default.

to respond to the peanut gallery   I understand that every person involved doesn't have an unlimited amount of time to devote to this but like a crazy idea would be to like recruit some of the more talented members and have them volunteer some of their time.  I don't claim to be a pro but i think i've just stumbled onto something that could possibly blow the doors off this thing.  I'm not going to get into it but you can't claim that theres not enough time to do everything if the powers that be aren't asking for volunteers to actively work on small projects.   I mean send me a list of 10-20 functions they need to do a specific thing... I'll gladly help.   .... theres literally a bazillion free options for every language so the fact that its free means literally nothing.  I get my c++ for free aswell.... and ummm its pretty complete you should check it out.

Edited January 3, 2022 by markyrocks

[AspirinJunkie]

I still don't see exactly what your point is.
You want the sorting function to be a built-in function of AutoIt and therefore speed up the actual sorting?
Currently, the function is not part of the language but only (as in most languages) part of the standard library.
Therefore, the sorting itself is written in (slowly) to be interpreted AutoIt code.

Your current example deals with the case of converting the data of an AutoIt array into C form and sorting it there with a firmly compiled comparison function.
For the example here, where 1,000,000 integers are to be sorted, your approach achieves a speed-up of a factor of 10 for me. To be fair, you could still switch to the dual pivot quicksort in _ArraySort, but even then it would still be a factor of at least 8x.

Currently, I only see the proof that you can speed up the case of sorting a large integer array in this way - so currently still a very concrete case.
I don't see a general replacement of the functionality of _ArraySort here yet.
However, _ArraySort swallows all AutoIt data types and yes, you also try to cover all data types in principle via the void pointers.
However, the approach with the dll becomes exciting at the latest when it comes to sorting an array of strings. Because there, a void pointer is no longer sufficient, but a length specification per element is also required. Anyway - that would still be solvable under certain circumstances. Whether it still brings the performance gain is another question.
However, at the latest when it comes to sorting an array with a mixture of different data types - and yes, _ArraySort can of course do this - you end up in the situation of having to implement the variant type in the DLL.

So far(!) I don't see any approach for a general replacement of _ArraySort in the example shown, but only an acceleration potential for special cases. The possibility of using own user-defined (i.e. written in AutoIt) comparison functions is also not yet available. You want to achieve this through DLLCallBackRegister - I know. However, I see massive problems with regard to the data types here as well. The real sticking points have not yet been solved, which is why I can't quite understand the vehemence and emphasis with which what is shown is being touted as the ultimate solution in this early phase. 

Build the DLL in such a way that it covers about 90% of the use cases of _ArraySort (i.e. first of all all data types - not even 2D arrays). If the performance advantage is then still so constant, then I would share your current euphoria.

I therefore understand the post more as a call to the devs to implement a sorting function internally built into AutoIt?
Sure: A sorting function as part of the language could handle the variant type more elegantly than an external dll. The connection to own sorting functions could also be better realised there.

However, if you look at the speed of development of AutoIt in the last few years, I don't assume that the implementation effort required for this is even considered.
Probably also because the user community has not yet expressed a corresponding need. Most see AutoIt as a scripting language with which their needs can be implemented quickly and easily. High performance is simply not expected by the users and if it is, other tools are used.
If there are quick and easy ways to increase the performance in individual areas of AutoIt, no one will stubbornly refuse. However, I do not consider the concrete case here to be quick and easy.

[markyrocks]

Wow I'm impressed.  I expected to be flamed.  Ok so you covered alot of topics and I'll address them relatively quickly.   So as I had previously said I have already updated this newborn project to use a template over my comparison function that handles all of the number sorting within numerical limits.   I've also got the dllcallbackregister part for a user defined function working.   The nature of strings is irrelevant bc you don't pass around strings by value you pass around char pointers that actually point to the string.  The size is also irrelevant provided a termination character is used.... ummmm 2d arrays... cmon bro I can easily implement sorting through an array in every different direction and search pattern you could dream of.  Lol.  Really the biggest bottle neck of the whole thing is copying from one place to another in autoit (that includes the callback bc that is also slow bc its passing through the great wall of autoit inefficiency).  I realize in this particular bubble low performance is kind of the expectation but this isn't the only interpreted language on the block...but for some reason it is the slowest one that I know.   The point of this example is I'm no super guru when it comes to computers and I got an idea in my head the other day about a problem that is relatively well known and I was able to demolish the built in function with very little effort.   Like you said my example is 10x faster.  ##!! The mass majority of the time is from copying into the struct and back to the autoit array.   The sort on the dll end takes up less than 1% of the time.  Imagine how fast it would be if they would allow directly reading and writing to the auto it variables... its wouldn't be 10x fast it would be closer to a 1000.

[markyrocks]

O I'd also like to add that I figured out a way to write directly to a autoit variable from the dll by  making a custom user defined callback proc function which I was excited about but it's actually slower than the method of copying back and forth the way the example is set up.  ... 😞

[Melba23]

Hi,

13 hours ago, markyrocks said:

They should be embarrassed

As the author of the last major review of the Array library (already 8 years ago!) when among other things 2D support was added, I feel absolutely no embarrassment at all for having done no further work on the library.

Jon has often expressed his dissatisfaction with the way he implemented arrays in AutoIt - a major factor in the slowness of their manipulation - but at the time that was what he came up with and we have to live with it. As a result, and like many others, I only use the _ArraySort function to sort smallish arrays - anything of any size gets put into a SQLite database which even with my low level of SQL knowledge is quite fast enough for me.

One of the major assets of AutoIt has always been its portability and the "stand-alone" nature of its compiled scripts. I would be very loath to see any additional requirement such as a DLL solely for array sorting. Not to mention the problem of getting such a file to install on machines without an existing AutoIt installation - there are  already enough problems getting the standard files accepted.

Quote

but like a crazy idea would be to like recruit some of the more talented members and have them volunteer some of their time

Remembering the very limited amount of support and testing (with some notable exceptions) I got during the library rewrite mentioned above I feel you are whistling in the dark here. But good luck with your efforts.

M23

[junkew]

@markyrocks I can imagine you have some good reason you need a faster arraysort but consider all the existing alternatives in the forum that can be found before you spent a lot of time. It is very usefull to enhance AutoIt but I feel the core language will not be quickly extended as a lot of usefull stuff is in the UDF libraries either as part of the package or searchable in the forum (where many great libraries are references in help, faq, wiki faq or just by asking in the forum quickly referenced by other people)

With ObjCreate you can already reach a lot of usefull alternatives including these from .NET

System.Collections.ArrayList
System.Collections.CaseInsensitiveComparer
System.Collections.CaseInsensitiveHashCodeProvider
System.Collections.Generic.KeyNotFoundException
System.Collections.Hashtable
System.Collections.Queue
System.Collections.SortedList
System.Collections.Stack

As an example a 100.000 random strings in an arraylist

example()
func example()
    $list=ObjCreate("System.Collections.arraylist")

    for $i=1 to 100000
        $string=Chr(Random(65, 90, 1)) & Chr(Random(65, 90, 1)) & Chr(Random(65, 90, 1)) & Chr(Random(65, 90, 1)) & Chr(Random(65, 90, 1))
        $list.add($string)
    Next
    Local $hTimer = TimerInit() ; Begin the timer and store the handle in a variable.

    ConsoleWrite("test: "&$list.count&@crlf)

    Local $hTimer = TimerInit()
    $LIST.SORT
    Local $fDiff = TimerDiff($hTimer)
    ConsoleWrite("sorting time: " & $fDiff &@crlf)

;~  for $i=1 to 1000
;~      consolewrite($list.item($i) & @CRLF)
;~  Next

EndFunc

 

My advice

would be to take a look at array.au3 and see if you can improve that and discuss with the maintainer of that udf @Melba23 I assume.
if your proposed changes speed up significantly (without dll) probably it will be taken over in that udf. If not then put your stuff in the forum examples section like many other UDF writers have done that are not part of the core installation.

 

[pixelsearch]

@markyrocks 

Hi, I'm probably doing something wrong when using your dll because the resulting sorted array always shows a non-existant element = 0 when using your initial script (with fewer elements in the array for the pics to come). For example :

Global $size = 10

;~ Global $array[$size]
;~ GenerateArray($array)
Global $array[$size] = [-5, 5, -4, 4, -3, 3, -2, 2, -1, 1]

_ArrayDisplay($array, "$array unsorted")

ArraysortTest()

...

    $struct = StructToArray($struct, $size)  ;<=======  uncomment this

    For $i In $struct ;<======================= to use this loop
        ConsoleWrite($i & @CRLF)
    Next
    _ArrayDisplay($struct, "$struct sorted")

Same element 0 appears when using GenerateArray :

Global $size = 14

Global $array[$size]
GenerateArray($array)
;~ Global $array[$size] = [-5, 5, -4, 4, -3, 3, -2, 2, -1, 1]

_ArrayDisplay($array, "$array unsorted")

If a reader who tested the dll faces this strange behavior, please be kind to report here.
Thanks.