Submission: while / break / end while

Index > Compiler Internals > Submission: while / break / end while

Goto page 1, 2, 3 Next

Author

Thread

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 21 Jul 2005, 01:53

I have added WHILE, BREAK and END WHILE to the fasm syntax. It is my hope that the author will include the modifications into the standard package.

For a long time now I have been watching the assembler assemble my programs and take many tens of seconds on the larger sources. Recently I have been able to use some spare time to look into exactly why the process takes a long time. I discovered it is because of the EXPORT macro.

I analysed the EXPORT macro and can see that the sort routine could not be optimised without a loop structure that can be exited dynamically. Hence the desire for a WHILE / END WHILE loop.

I have now programmed this into fasm 1.63.1 and have uploaded to here for you to try.

Two directives have been added to X86_64.INC: WHILE and BREAK.

The basic structure is this:

Code:

while logical_condition
  ;...code
  ;optional break condition testting
  if exit_condition
    ;...code
    break
  end if
  ;...code
end while

The loop count is also available using the % character just the same as REPEAT.

Have a look at the file BinarySortExport.asm, I have updated the EXPORT macro using a binary sort alogrithm.

Now my sources assemble at 3 to 4 times faster depending on the number of exported functions.

Comments, bug reports etc. are welcome.

In the zip file:

FASM.EXE - win32 console executable
FASMW.exe - win32 IDE executable
ASSEMBLE.INC - the modified source
X86_64.INC - the modified source
BinarySortExport.asm - example showing faster export macro
WhileTest.asm - example showing interaction with REPEAT and IF

Last edited by revolution on 22 Jul 2005, 03:14; edited 1 time in total

21 Jul 2005, 01:53

decard

Joined: 11 Sep 2003
Posts: 1092
Location: Poland

decard 21 Jul 2005, 12:59

well.. I'm pretty sure that Tomasz won't include it in official release (read design principes article Wink

). But, I'm also sure that you could do the same using macros...

21 Jul 2005, 12:59

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 22 Jul 2005, 01:59

Quote:

But, I'm also sure that you could do the same using macros

Yes, this is true, using a combination of IF and REPEAT you can emulate WHILE, but in some instances this is not efficient.

Currently the only assembly time looping structure is REPEAT. We have to know in advance the maximum number of repeatitions before we enter the loop, and there is no way to have an early exit with REPEAT.

In the above example with the export macro there are two instances where WHILE is very useful. First in the outer loop where the loop count is CEILING(LOG2(count)). This is not convenient to calculate ahead of time for a repeat loop. Second the inner comparison of the strings has to know the length of the longest string before we enter to sort routine and then loop over every string based on the maximum length. Using WHILE solves both these problems and makes assembly more efficient. My assembly times now are much faster when I use WHILE.

There are other instances where WHILE is a better concept to use than REPEAT/IF, plus it is often easier to folllow when reading through code.

22 Jul 2005, 01:59

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 22 Jul 2005, 03:20

I have updated the attachment above. There was a minor bug in the binary sort routine affecting the speed. Now a little bit faster.

22 Jul 2005, 03:20

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 22 Jul 2005, 07:58

Here is a macro using repeat/if to do binary sorting (using the export macro again for example):

Code:

macro export_repeat_if dllname,[label,string]
 { common
    local module,addresses,names,ordinal,count
    count = 0
   forward
    count = count+1
   common
    dd 0,0,0,RVA module,1
    dd count,count,RVA addresses,RVA names,RVA ordinal
    addresses:
   forward
    dd RVA label
   common
    names:
   forward
    local name
    dd RVA name
   common
    ordinal: count = 0
   forward
    dw count
    count = count+1
   common
    module db dllname,0
    local maxstrlen,x,y,z,str1,str2,v1,v2,more
    maxstrlen = 0
   forward
    name db string,0
    if $-name > maxstrlen
     maxstrlen = $-name
    end if
   common
;binary sort using repeat/if
    x=count shr 1
    repeat 15
        if x>0
            y=x
            repeat count-y
                z=y
                repeat z/x
                    if (z-x)>=0
                        load v1 dword from names+z*4
                        str1=($-RVA $)+v1-1
                        load v2 dword from names+(z-x)*4
                        str2=($-RVA $)+v2-1
                        more=1
                        repeat maxstrlen
                            if more|(v1=v2)
                                load v1 from str1+%
                                load v2 from str2+%
                                more=0
                            end if
                        end repeat
                        if v1<v2
                            load v1 dword from names+z*4
                            load v2 dword from names+(z-x)*4
                            store dword v1 at names+(z-x)*4
                            store dword v2 at names+z*4
                            load v1 word from ordinal+z*2
                            load v2 word from ordinal+(z-x)*2
                            store word v1 at ordinal+(z-x)*2
                            store word v2 at ordinal+z*2
                        else
                            z=0
                        end if
                        z=z-x
                    end if
                end repeat
                y=y+1
            end repeat
            x=x shr 1
        end if
    end repeat
}

And for comparison the same but using while:

Code:

macro export_while dllname,[label,string]
 { common
    local module,addresses,names,ordinal,count
    count = 0
   forward
    count = count+1
   common
    dd 0,0,0,RVA module,1
    dd count,count,RVA addresses,RVA names,RVA ordinal
    addresses:
   forward
    dd RVA label
   common
    names:
   forward
    local name
    dd RVA name
   common
    ordinal: count = 0
   forward
    dw count
    count = count+1
   common
    module db dllname,0
   forward
    name db string,0
   common
;binary sort using while
        local x,y,z,str1,str2,v1,v2
        x=count shr 1
        while x>0
            y=x
            while y<count
                z=y
                while (z-x)>=0
                    load v1 dword from names+z*4
                    str1=($-RVA $)+v1-1
                    load v2 dword from names+(z-x)*4
                    str2=($-RVA $)+v2-1
                    while v1>0
                        load v1 from str1+%
                        load v2 from str2+%
                        if v1<>v2
                            break
                        end if
                    end while
                    if v1<v2
                        load v1 dword from names+z*4
                        load v2 dword from names+(z-x)*4
                        store dword v1 at names+(z-x)*4
                        store dword v2 at names+z*4
                        load v1 word from ordinal+z*2
                        load v2 word from ordinal+(z-x)*2
                        store word v1 at ordinal+(z-x)*2
                        store word v2 at ordinal+z*2
                    else
                        break
                    end if
                    z=z-x
                end while
                y=y+1
            end while
            x=x/2
        end while
}

There is still a large speed difference. export_repeat_if is faster than the current standard supplied macro and export_while is faster than both.

Perhaps if the while construct is not wanted/needed then I can instead persuade the author to change to the export_repeat_if macro.

22 Jul 2005, 07:58

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 22 Jul 2005, 08:29

Just now I have completed testing of the export macro and while/break. I have to move on to another task, but I will keep following this topic.

The last build of the project (1074 exported functions) showed the following results:

Using the standard export macro: Assembly time 37.4 seconds
Using export_repeat_if macro: Assembly time 9.7 seconds
Using export_while macro: Assembly time 1.9 seconds

From now on all our projects will be using the while/break.

I have quite enjoyed having an opportunity to extend the assembler functionality and even if it is not adopted at least the improvement of the export macro may help others.

22 Jul 2005, 08:29

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8354
Location: Kraków, Poland

Tomasz Grysztar 26 Jul 2005, 08:47

The problem with such extension is that it allows to hang the assembly process.

There should be other ways to make the export macro faster - like implementing the quick-sort-based method, etc.

26 Jul 2005, 08:47

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 26 Jul 2005, 09:19

Try this:

Code:

while 1
end while

I actually put in a maximum count and it will give an error that the code cannot be generated.

Code:

repeat (1 shl 31)-1
end repeat

is much the same concept except there is no way to break the repeat early. Maybe instead of WHILE, the BREAK can be inplemented to break a REPEAT loop early?

26 Jul 2005, 09:19

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 26 Jul 2005, 09:40

Here is my idea using repeat/break

Code:

macro export_repeat_break dllname,[label,string] 
 { common 
    local module,addresses,names,ordinal,count 
    count = 0 
   forward 
    count = count+1 
   common 
    dd 0,0,0,RVA module,1 
    dd count,count,RVA addresses,RVA names,RVA ordinal 
    addresses: 
   forward 
    dd RVA label 
   common 
    names: 
   forward 
    local name 
    dd RVA name 
   common 
    ordinal: count = 0 
   forward 
    dw count 
    count = count+1 
   common 
    module db dllname,0 
   forward 
    name db string,0 
   common 
;binary sort using repeat/if 
    local x,y,z,str1,str2,v1,v2
    x=count shr 1 
    repeat 9999
        if x<=0
            break
        end if 
        y=x 
        repeat count-y 
            z=y 
            repeat z/x 
                load v1 dword from names+z*4 
                str1=($-RVA $)+v1-1 
                load v2 dword from names+(z-x)*4 
                str2=($-RVA $)+v2-1 
                if v1>0
                    repeat 9999
                        load v1 from str1+% 
                        load v2 from str2+% 
                        if v1<>v2
                            break
                        end if
                    end repeat 
                end if
                if v1<v2 
                    load v1 dword from names+z*4 
                    load v2 dword from names+(z-x)*4 
                    store dword v1 at names+(z-x)*4 
                    store dword v2 at names+z*4 
                    load v1 word from ordinal+z*2 
                    load v2 word from ordinal+(z-x)*2 
                    store word v1 at ordinal+(z-x)*2 
                    store word v2 at ordinal+z*2 
                else
                    break 
                end if 
                z=z-x 
            end repeat 
            y=y+1 
        end repeat
        x=x shr 1 
    end repeat 
}

Quote:

the quick-sort-based method

Umm, I don't think the sort method while make a great deal of difference. The binary sory is comparable in speed to quick sort with a few percent change only. The major delay is the code that scans forward from the 'if' to find the 'end if', and that is repeated many times according to the variable 'maxstrlen' and also the 'repeat z/x' loop where 'if (z-x)>=0' must be skipped many times.

Anyhow, my company is very happy with WHILE/BREAK but even REPEAT/BREAK would still be a significant differnece in speed over REPEAT/IF.

26 Jul 2005, 09:40

MCD

Joined: 21 Aug 2004
Posts: 602
Location: Germany

MCD 26 Jul 2005, 14:35

I like the idea of revolutions repeat/while/break assembly syntax, but it is true that this will allow the assembly process to stop. But the following should do pretty much the same:

Code:

repeat 7FFFFFFF;editFFFFFFFFh
 repeat 7FFFFFFF;editFFFFFFFFh;just some nesting to spend even more time
  virtual; just to do some stuff without putting anything into the output  file:)
   db 0
  end virtual
 end repeat
end repeat

Well, that's garbage, but it shows how to stop assembly with current fasm.

Last edited by MCD on 27 Jul 2005, 07:29; edited 1 time in total

26 Jul 2005, 14:35

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 27 Jul 2005, 01:09

Quote:

that this will allow the assembly process to stop

Above I wrote this:

Quote:

I actually put in a maximum count and it will give an error that the code cannot be generated.

BTW: your repeat count will be rejected by FASM. The maximum count alowed is 7FFFFFFFh.

27 Jul 2005, 01:09

MCD

Joined: 21 Aug 2004
Posts: 602
Location: Germany

MCD 27 Jul 2005, 07:28

revolution wrote:

BTW: your repeat count will be rejected by FASM. The maximum count alowed is 7FFFFFFFh.

I actually didn't test the program. I thought that limit was 64bit, like most number calculations in fasm. But I was wrong Smile

27 Jul 2005, 07:28

Ancient One

Joined: 28 Feb 2005
Posts: 55

Ancient One 27 Jul 2005, 11:57

i really like the idea of 'break' inside a loop.. nice work rev. hope privalov will consider it as part of fasm next time.

27 Jul 2005, 11:57

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8354
Location: Kraków, Poland

Tomasz Grysztar 28 Jul 2005, 12:24

The "while" with the limit seems to be a good idea - but I will implement it myself from scratch - forgive me, but I prefer to maintain my own code only.

BTW, I once saw the "export" macro for fasm that used the quick sort and it really was much faster, however I cannot recall right now where it was...

28 Jul 2005, 12:24

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8354
Location: Kraków, Poland

Tomasz Grysztar 28 Jul 2005, 15:10

OK, the 1.63.2 contains my version (took about 2.5 hours, but there were also some bugfixes to be done in that time Wink

). The "break" in my implementation works for both "repeat" and "while" loops.

28 Jul 2005, 15:10

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 28 Jul 2005, 18:54

Good job,

. I don't mind you wanting your own code, I would probably do the same myself.

28 Jul 2005, 18:54

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20343
Location: In your JS exploiting you and your system

revolution 28 Jul 2005, 19:31

I have tried and everything is okay. Just one request, the export sort is still kind of slow. Any chance the standard package can using a binary sort? The code above (post no. 5 in this thread) has been throughly tested for correctness. The code using while is the fastest.

28 Jul 2005, 19:31

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8354
Location: Kraków, Poland

Tomasz Grysztar 28 Jul 2005, 22:11

Yes, I have nothing against - it was just the very quick fix to my old "export" to use the "while", I will analyze your macro and include it in standard package later.

28 Jul 2005, 22:11

Ancient One

Joined: 28 Feb 2005
Posts: 55

Ancient One 29 Jul 2005, 03:03

thanks a lot privalov..fasm is getting better in each release Smile

29 Jul 2005, 03:03

MCD

Joined: 21 Aug 2004
Posts: 602
Location: Germany

MCD 29 Jul 2005, 09:23

Tomasz Grysztar wrote:

OK, the 1.63.2 contains my version (took about 2.5 hours, but there were also some bugfixes to be done in that time ). The "break" in my implementation works for both "repeat" and "while" loops.

Cool! This new feature will actually speed up my Fractal-picture generating code a lot Cool

I will update it soon

29 Jul 2005, 09:23

Goto page 1, 2, 3 Next

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum