News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests

Main Menu

Fast Sorting algo help

Started by guga, September 23, 2014, 05:10:13 AM

Previous topic - Next topic

qWord

Quote from: jj2007 on September 24, 2014, 04:17:16 AMThat was also my idea, but Michael (#6) says no ::)
You need a stable algorithm if you sort something that has already been sorted.

Quote from: jj2007 on September 24, 2014, 04:17:16 AMWhat do you think of Jim Dempsey's idea to make qsort stable?
I can't see how that should work - an element might be swapped several times and each time the address change.
MREAL macros - when you need floating point arithmetic while assembling!

guga

I`m trying to use qsort, but it is crashing, because the internal pointers of the comparefunction are not being correctly achieved.


; equates usedof the structure DFMScript
[DFMScript.pLabelNameDis 0
DFMScript.pSigLabelDis 4
DFMScript.pExtentionDis 8
DFMScript.pSignatureDataLenDis 12
DFMScript.pSignatureDataDis 16
DFMScript.pSigSizeDis 20]

[Size_of_DFMScript 24]
[ScriptData2: D$ 0] ; <----- This is a pointer to the actual file data. It is zero only before precomputing the scrypt...but, below, the pointer is already retrieved.

    c_call 'msvcrt.qsort' D$ScriptData2, 9, Size_of_DFMScript, CompareFunc




Proc CompareFunc:
    Arguments @Arg1, @Arg2
    Uses esi, edi, edx, esi

    mov ecx D@Arg1
    mov edx D@Arg2

    mov esi ecx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | move edi D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, edi, DecodedData1
    mov esi edx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | mov ecx D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, ecx, DecodedData2
    If ecx > edi;D@DataLen2
        mov ecx edi;D@DataLen2
    End_If

    c_call 'msvcrt._mbsnbcmp' DecodedData1, DecodedData2, ecx

; To sort an array in decreasing order, reverse the sense of
; greater than and less than in the comparison function :
;
   neg     eax

L0:

EndSTD




Proc BinaryDecode:
    Arguments @Input, @InputSize, @Output
    Uses esi, edi, ecx, ebx, edx

    ; EncodeSignature
    mov esi D@Input
    mov edi D@Output
    mov ebx D@InputSize

    ;..While B$esi <> 0
    ..While ebx <> 0

        .If B$esi = SIG_TYPE_BYTE
            inc esi
            movsb
            dec ebx
        .Else_If B$esi = SIG_TYPE_WORD
            inc esi
            movsw
            sub ebx 2
        .Else_If B$esi = SIG_TYPE_DWORD
            inc esi
            movsd
            sub ebx 4
        .Else_If B$esi = SIG_TYPE_REPEAT_BYTES
            ;mov eax eax
            inc esi
            movzx ecx B$esi | inc esi | mov edx ecx
            movzx eax B$esi | inc esi
            rep stosb
            sub ebx edx

        .Else_If B$esi = SIG_TYPE_BYPASS_BYTES
            inc esi
            movzx ecx B$esi | inc esi | mov edx ecx
            mov al 0FF
            rep stosb
            sub ebx edx
        .Else
            ; error when decoding
            mov eax eax
        .End_If

    ..End_While

EndP


I have no idea why it is crashing.
The structure is 24 bytes long, and the file contains 9 structures. So it should suppose to work, but....it isn´t :(


I have no idea what is happenning. The debugger shows me that on the 1st loop of the call back CompareFunc, Arg1 and Arg2 points inside the strcture array....but, on the 2nd loop Arg1 points outside the structure array :(:(:(


Btw: ENDSTD macro is a simple ret instruction. It is to simulate a stdcall function return
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

KeepingRealBusy

Quote from: qWord on September 24, 2014, 05:26:08 AM
Quote from: jj2007 on September 24, 2014, 04:17:16 AMThat was also my idea, but Michael (#6) says no ::)
You need a stable algorithm if you sort something that has already been sorted.

Quote from: jj2007 on September 24, 2014, 04:17:16 AMWhat do you think of Jim Dempsey's idea to make qsort stable?
I can't see how that should work - an element might be swapped several times and each time the address change.

That is why you need an indirect Qsort - where there are pointers to each of the structures, the structures remain static in memory (same address always), and the indirect pointers are swapped.

Dave.

qWord

Quote from: KeepingRealBusy on September 24, 2014, 06:25:36 AMThat is why you need an indirect Qsort - where there are pointers to each of the structures, the structures remain static in memory (same address always), and the indirect pointers are swapped.
yes. (but this wouldn't be in-place of course)

However, guga doesn't need a stable sorting algorithm at all, because it can be done in one pass (AFAICS).
MREAL macros - when you need floating point arithmetic while assembling!

guga

OK, i guess i fixed it. It was crashing due to a mistake on the push/pop register ("Uses macro)). Vortex´s example that JJ gave works like a gem  :t

Now it sorts properly on descending order.
[Trilobyte's JPEG graphics Library:||jpg|84 10 FF FF FF FF 1E 00 01 10 08 00 00 00 00 00
[Trilobyte's JPEG graphics Library:||jpg|84 10 F1 F2 F3 F4 1E 00 01 10 08 09 07 06 05 04
[Wavelet compressed bitmap:||wvl|057 049
[Bitmap(PBM):||pbm|050 036 0A
[Delphi ImageList:||iml|049 04C
[TImageList:|TImageList|iml|049 04C
[TBitmap:|TBitmap|bmp|042 04D ???? ?? ?? ???? 028
[Cursor:||cur|00 00 00 02 00
[Icon:||ico|00 00 00 01 00



The corrected code is as folows:
Proc CompareFunc:
    Arguments @Arg1, @Arg2
    Uses esi, edi, edx, ecx, ebx

    mov ecx D@Arg1
    mov edx D@Arg2

    mov esi ecx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | mov edi D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, edi, DecodedData1
    mov esi edx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | mov ecx D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, ecx, DecodedData2
    If ecx > edi;D@DataLen2
        mov ecx edi;D@DataLen2
    End_If

    c_call 'msvcrt._mbsnbcmp' DecodedData1, DecodedData2, ecx

; To sort an array in decreasing order, reverse the sense of
; greater than and less than in the comparison function :
;
   neg     eax

L0:
EndSTD


c_call 'msvcrt.qsort' D$ScriptData2, 9, Size_of_DFMScript, CompareFunc


Since it seems to be working, then the qsort algorithm seems to be the proper choice.

The question now is....How fast is crt qsort ? Does we have an algo that have the exact same functionality but, faster ?

Also.....what about strncmp does we have an faster algo with the same functionality ?


The better would be have faster algos for qsort and strncmp since, i´ll deal with a large database
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

guga

JJ, does your Algo works for the structure i´m making ?
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

jj2007

Quote from: guga on September 24, 2014, 07:03:15 AMThe better would be have faster algos for qsort and strncmp since, i´ll deal with a large database

Your BinaryDecode needs to be fast. Maybe inlined instead of called.

QuickSort can be beaten only in rare circumstances. ArraySort is faster but not applicable here, as it does not use a callback.

Quote from: guga on September 24, 2014, 08:32:05 AM
JJ, does your Algo works for the structure i´m making ?

QSort() could be used only if you translated your strucs into strings, i.e. criteria 1+2 would be expressed as something sortable, the other members added behind. E.g. if crit 1=123, 99 and crit 2=777, 444:
00000123#777#other members#
00000099#444#more data....#


Feasible and probably fast but would require quite a bit of RAM.

Gunther

Quote from: jj2007 on September 24, 2014, 10:35:23 AM
QuickSort can be beaten only in rare circumstances.

Yes, QuickSort is mostly the way to go. I think that's true in Gustavo's special case, too.

Gunther
You have to know the facts before you can distort them.

jj2007

Quote from: Gunther on September 24, 2014, 07:11:03 PM
Quote from: jj2007 on September 24, 2014, 10:35:23 AM
QuickSort can be beaten only in rare circumstances.

Yes, QuickSort is mostly the way to go. I think that's true in Gustavo's special case, too.
Why that, in this "special case"?

Gunther

Jochen,

Quote from: jj2007 on September 24, 2014, 07:50:36 PM
Why that, in this "special case"?

I had better written: in his case (nothing is special). No offense.

Gunther
You have to know the facts before you can distort them.

FORTRANS

Quote from: jj2007 on September 24, 2014, 04:17:16 AM
Quote from: qWord on September 24, 2014, 03:56:54 AM
Not sure if I interpret that correct, but I guess you can just use qsort whereby comparing the secondary keys only if the primary keys are equal.

That was also my idea, but Michael (#6) says no ::)

What do you think of Jim Dempsey's idea to make qsort stable?

Hi,

   Basically there are two (simple) ways to do a sort on two (or
more) keys.

   What Jim, qWord, and you are doing, is sort on the primary key,
and if two entries are equal, sort on the secondary key.  This will
work until you have more than one equal key value.  Then things
can rapidly go down the tubes if not well thought out.  (Yes, it
does work, but it can be more complicated because you are doing
two sets of comparisons at once, rather than one at a time.)

   What Michael is saying, I think, is that the standard way to do it
is to use a stable sort, sort on the secondary key, and then sort
on the primary key.  At least that is what I remember from most
discussions.  It can be simpler to do it that way, at least in theory.
Particularly when sorting on many keys.  You just sort the data
from least significant key to most significant key, one at a time.

YMMV,

Steve N.

jj2007

Quote from: FORTRANS on September 24, 2014, 11:52:04 PMWhat Jim, qWord, and you are doing, is sort on the primary key, and if two entries are equal, sort on the secondary key.

Steve,

I have a suspicion that there is a misunderstanding:

- option 1 is to do TWO sorts, first on crit 1, then on crit 2; this is what I use e.g. in the Excel-stylespreadsheet viewer, and it requires a stable sort.

- option 2 is to do ONE sort, where both criteria are checked in the comparison function; this is what (I assume) qWord and myself suggested in Gustavo's case.

The latter should work fine with an unstable sort.

guga

Ok, the crt qsort works fine, but it is slow.

I´m analyzing the msvcrt function, and found out that it is, in fact, a arraysort as described here:

http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html

The source code of qsort accordying to the windows sources i have is extremely old. Last revision is from 11/19/1991 by GJF - Do the swap one character at a time to avoid alignment woes.

It seems similar to one in posix and gnu lib
https://github.com/luciang/haiku/blob/master/src/system/libroot/posix/stdlib/qsort.c

But..i´m starting to get confused here. In my case, i presume the qsort algorithm does not need to be stable, since, i´m basicaly sorting the array biased in 1 of it´s elements, right ?

just to try to understand...is the lik below that is trying to make qsort stable really worthfull in terms of speed (for my case)?
http://nullprogram.com/blog/2014/08/29/


JJ.
Quote- option 2 is to do ONE sort, where both criteria are checked in the comparison function; this is what (I assume) qWord and myself suggested in Gustavo's case.

The changes i made in the code are correct ?
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

FORTRANS

Quote from: jj2007 on September 25, 2014, 12:58:23 AM

Steve,

I have a suspicion that there is a misunderstanding:

Hi,

   Not really.  As per usual, I was perhaps unclear.  What I was
trying to say is what you then said.  Use a stable sort with
multiple passes.  Or compare everything, either all at once, or
test the first key and then test the second if the first tests equal.
With any sort.  Sorry about that.  The "textbook" way is to use
multiple passes in my experience.

Regards,

Steve

guga

One of the things that makes qsort a bit slow is a byte by byte scan on a routine i isolated and named as:


Proc Swap:
    Arguments @Struct1, @Struct2, @Width, @compare
    Local @Distance
    Uses ebx, ecx, edx

    mov ebx D@Struct1 | sub ebx D@Struct2 | jz L1> | mov D@Distance ebx ;< distance may not be necessary, as long the user preserved ebx in his comparefunction
    call D@compare D@Struct1, D@Struct2
    .If eax >s 0
        mov ebx D@Distance
        mov eax D@Struct2
        mov ecx D@width ; <--- size of the structure (3rd parameter of qsort function)
        L1:
            mov dh B$eax+ebx
            mov dl B$eax | mov B$eax+ebx dl
            mov B$eax dh
            inc eax
        dec ecx | jne L1<
    .End_If
L1:

EndP




If someone can help building a variation of this function that makes it a bit faster, i´ll appreciate it. Then, once it is done, i´ll reinsert it on the main function to try to optimize the crt qsort a bit more. (Decoding it is a pan, but it is possible to do)
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com