Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #19201 > unrolled thread

Matrices

Back to article view | Back to comp.lang.forth

Contents

  Matrices mhx@iae.nl (Marcel Hendrix) - 2013-01-27 22:17 +0200
    Re: Matrices Ron Aaron <rambamist@gmail.com> - 2013-01-28 08:50 +0200
    Re: Matrices Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-01-28 03:11 -0600
      Re: Matrices m.a.m.hendrix@tue.nl - 2013-01-28 01:46 -0800
        Re: Matrices mhx@iae.nl (Marcel Hendrix) - 2013-02-03 12:48 +0200
          Re: Matrices "A. K." <akk@nospam.org> - 2013-02-03 13:27 +0100
          Re: Offline compilation of Forth mhx@iae.nl (Marcel Hendrix) - 2013-02-03 21:17 +0200
    Re: Matrices stephenXXX@mpeforth.com (Stephen Pelc) - 2013-01-28 10:39 +0000
      Re: Matrices m.a.m.hendrix@tue.nl - 2013-01-28 03:33 -0800
    Re: Matrices albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-01-28 14:31 +0000
    Re: Matrices Alex McDonald <blog@rivadpm.com> - 2013-01-28 07:48 -0800
    Re: Matrices Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-28 18:06 -0800
    Re: Matrices anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-29 09:49 +0000
      Re: Matrices Mark Wills <forthfreak@gmail.com> - 2013-01-29 04:08 -0800
        Re: Matrices m.a.m.hendrix@tue.nl - 2013-01-29 08:22 -0800

#19201 — Matrices

I have encountered a problem for which I don't immediately 
see a solution (maybe it won't need one in the Forth sense ;)

Sometimes it is advantageous to NOT compile a word immediately.
Is it possible to have 'delayed compilation?' 

An example is a word A* to multiply two dynamically allocated arrays.
Because the address of the data and the number of rows and columns is
unknown, the addressing of the matrix elements is very inefficient.
In Forth it should be possible to compile A* AFTER it is detected 
that the matrices have been allocated (e.g. the first time A* is
run). At that time many of the @s and !s will resolve to constant
addresses, or at least access fixed rows or columns, and it will be
known that the accesses are aligned or that the strides are 
powers of 2.

Problems: How to detect code is run for the first time? How to detect
that previously compiled code is still valid (no reallocate been done)?

Note that the addresses of the matrices may be passed in locals. 

Assuming that the array syntax is a{{ row column }} @, it is of course
possible to access a{{ efficiently by copying the addresses of rows
and columns into locals (or on the stack) and then access elements 
row- or columnwise. However, as this is for my OPG project I'd like 
to always access the matrices the same, like a{{ row column }} @.

Actually, in OPG the syntax will be a[r,c] where Forth doesn't even 
known if a is a vector or a (2D) matrix (the programmer knows, but 
does not know how to tell the compiler).

-marcel

[toc] | [next] | [standalone]

#19206

On 01/27/2013 10:17 PM, Marcel Hendrix wrote:
> I have encountered a problem for which I don't immediately
> see a solution (maybe it won't need one in the Forth sense ;)
..
>
> Problems: How to detect code is run for the first time? How to detect
> that previously compiled code is still valid (no reallocate been done)?

The way I would do it would be to make the A* a deferred word, whose 
initial value would set things up.  At the end, it would set A* to point 
at the 'final' version.

Determining that the compiled code hasn't changed could be done by 
having the accessor word !s (or whatever) set a flag (or, again, set A* 
to point to the set-things-up version).

[toc] | [prev] | [next] | [standalone]

#19210

Marcel Hendrix <mhx@iae.nl> wrote:
> I have encountered a problem for which I don't immediately 
> see a solution (maybe it won't need one in the Forth sense ;)
> 
> Sometimes it is advantageous to NOT compile a word immediately.
> Is it possible to have 'delayed compilation?' 

Whyever not?  If you keep threaded code around you can recompile it to
machine code whenever you want.

Andrew.

[toc] | [prev] | [next] | [standalone]

#19211

On Monday, January 28, 2013 10:11:32 AM UTC+1, Andrew Haley wrote:
>> Is it possible to have 'delayed compilation?' 
>
> Whyever not? If you keep threaded code around you can recompile
> it to machine code whenever you want. 

I should have stated more clearly that I am looking for a syntax that hides the mechanics as much as possible. Of course the task as such is possible -- everything is possible in Forth.

-marcel

[toc] | [prev] | [next] | [standalone]

#19381

m.a.m.hendrix@tue.nl wrote Re: Matrices

> On Monday, January 28, 2013 10:11:32 AM UTC+1, Andrew Haley wrote:
>>> Is it possible to have 'delayed compilation?' 
>>
>> Whyever not? If you keep threaded code around you can recompile
>> it to machine code whenever you want. 

> I should have stated more clearly that I am looking for a syntax 
> that hides the mechanics as much as possible. Of course the task 
> as such is possible -- everything is possible in Forth.

I thank everybody for their thoughtful replies.

I postponed the solution of this challenge and first looked at the 
main problem: inefficient array/matrix accesses.

A better but memory-wise more costly indexing scheme that has 
been discussed at least twice on CLF, is to build a table for the 
row addresses when the matrix/array is allocated. This prevents 
having to multiply the row-size with the row index at run-time. 
It also allows to 'reshape' an already allocated array, again 
without multiplication cost at run-time. When the row and/or
column index are known at compile time, the indexing collapses
dramatically (see xzcopy below).

An iForth particular trick is declare the array of row addresses
as CONST-DATA, allowing the optimized to access the table at compile
time. This manipulation is transparent to the user as it can be
hidden in the GMATRIX words.

With these trivial changes added to the XOPG source, I get results
like the below. For reference i have added the VFX result when
using the VFX-supplied fsl_util helper file.

-marcel

-- --------
.dfloat.p ( ask for double-precision float code [64 bits])

2 2 GMATRIX x 
2 2 GMATRIX z

: testx  ( -- ) x /rdim 0 DO x /cdim 0 DO  LET x[j,i]=fdouble[2*j+i]:  LOOP LOOP ;
: testrx ( -- )              x /cdim 0 DO  LET x[1,i]=fdouble[2*1+i]:  LOOP ;
: xzcopy ( -- ) LET z[0,0]=x[0,0]: LET z[1,1]=x[1,1]: LET z[0,1]=x[0,1]: LET z[1,0]=x[1,0]: ;

testx   x .gmat
testrx  x .gmat
xzcopy  z .gmat

\ output
FORTH> testx  x .gmat
[  0.0000000000000000000e+0000  1.0000000000000000000e+0000 ]
[  2.0000000000000000000e+0000  3.0000000000000000000e+0000 ] ok
FORTH> testrx x .gmat
[  0.0000000000000000000e+0000  1.0000000000000000000e+0000 ]
[  2.0000000000000000000e+0000  3.0000000000000000000e+0000 ] ok
FORTH> xzcopy z .gmat
[  0.0000000000000000000e+0000  1.0000000000000000000e+0000 ]
[  2.0000000000000000000e+0000  3.0000000000000000000e+0000 ] ok

\ code
FORTH> see testx
Flags: ANSI
$01480F00  : testx
$01480F0A  push          $01480A98 qword-offset
$01480F10  xor           rbx, rbx
$01480F13  pop           rcx
$01480F14  call          (DO) offset NEAR
$01480F1E  nop
$01480F1F  nop
$01480F20  push          rbx
$01480F21  push          $01480AA0 qword-offset
$01480F27  xor           rbx, rbx
$01480F2A  pop           rcx
$01480F2B  call          (DO) offset NEAR
$01480F35  mov           rax, rax
$01480F38  mov           rdi, [rbp #24 +] qword
$01480F3C  mov           rax, [rbp 0 +] qword
$01480F40  lea           rdi, [rax rdi*2] qword
$01480F44  push          rdi
$01480F45  fild          [rsp] qword
$01480F48  add           rsp, 8 b#
$01480F4C  mov           rdi, [rbp #24 +] qword
$01480F50  mov           rax, [rbp 0 +] qword
$01480F54  lea           rax, [rax*8 0 +] qword
$01480F5C  add           rax, [rdi*8 $06C07470 +] qword
$01480F64  fstp          [rax] qword
$01480F66  add           [rbp 0 +] qword, 1 b#
$01480F6B  add           [rbp 8 +] qword, 1 b#
$01480F70  jno           $01480F38 offset NEAR
$01480F76  add           rbp, #24 b#
$01480F7A  add           [rbp 0 +] qword, 1 b#
$01480F7F  add           [rbp 8 +] qword, 1 b#
$01480F84  jno           $01480F20 offset NEAR
$01480F8A  add           rbp, #24 b#
$01480F8E  push          rbx
$01480F8F  ;

FORTH> see testrx
Flags: ANSI
$0147EBC0  : testrx
$0147EBCA  push          $0147E6A0 qword-offset
$0147EBD0  xor           rbx, rbx
$0147EBD3  pop           rcx
$0147EBD4  call          (DO) offset NEAR
$0147EBDE  nop
$0147EBDF  nop
$0147EBE0  mov           rdi, [rbp 0 +] qword
$0147EBE4  lea           rdi, [rdi 2 +] qword
$0147EBE8  push          rdi
$0147EBE9  fild          [rsp] qword
$0147EBEC  add           rsp, 8 b#
$0147EBF0  mov           rdi, [rbp 0 +] qword
$0147EBF4  fstp          [rdi*8 $066B75B0 +] qword
$0147EBFB  add           [rbp 0 +] qword, 1 b#
$0147EC00  add           [rbp 8 +] qword, 1 b#
$0147EC05  jno           $0147EBE0 offset NEAR
$0147EC0B  add           rbp, #24 b#
$0147EC0F  push          rbx
$0147EC10  ;

FORTH> see xzcopy
Flags: ANSI
$01480FC0  : xzcopy
$01480FCA  fld           $069975A0 qword-offset
$01480FD0  fstp          $069975E0 qword-offset
$01480FD6  fld           $069975B8 qword-offset
$01480FDC  fstp          $069975F8 qword-offset
$01480FE2  fld           $069975A8 qword-offset
$01480FE8  fstp          $069975E8 qword-offset
$01480FEE  fld           $069975B0 qword-offset
$01480FF4  fstp          $069975F0 qword-offset
$01480FFA  ;

-- same for Vfx, using fsl_util --------------------
 VFX Forth for Windows IA32
 © MicroProcessor Engineering Ltd, 1998-2012 

 Version: 4.50 [build 3327]
 Build date: 17 April 2012

 Free dictionary = 7561806 bytes [7384kb]


include startup 
Including startup.fth
Including %NdpDir%\Ndp387.fth
Including %FslDir%\Vfx4Util.fth

2 2 double matrix x{{ 
2 2 double matrix z{{ 
  
: testx  ( -- ) 2 0 DO  2 0 DO  j 2* i + S>F  x{{ I I }} F!  LOOP LOOP ; 
: testrx ( -- )         2 0 DO  1 2* i + S>F  x{{ 1 I }} F!  LOOP ; 
: xzcopy ( -- ) x{{ 0 0 }} F@  z{{ 0 0 }} F! x{{ 0 1 }} F@  z{{ 0 1 }} F! x{{ 1 1 }} F@  z{{ 1 1 }} F! x{{ 1 0 }} F@  z{{ 1 0 }} F! ;

see testx 
TESTX 
( 004D0840    68B3084D00 )            PUSH      004D08B3
( 004D0845    68FEFFFF7F )            PUSH      7FFFFFFE
( 004D084A    6A00 )                  PUSH      00
( 004D084C    90 )                    NOP
( 004D084D    90 )                    NOP
( 004D084E    90 )                    NOP
( 004D084F    90 )                    NOP
( 004D0850    68A4084D00 )            PUSH      004D08A4
( 004D0855    68FEFFFF7F )            PUSH      7FFFFFFE
( 004D085A    6A00 )                  PUSH      00
( 004D085C    90 )                    NOP
( 004D085D    90 )                    NOP
( 004D085E    90 )                    NOP
( 004D085F    90 )                    NOP
( 004D0860    8B54240C )              MOV       EDX, [ESP+0C]
( 004D0864    D1E2 )                  SHL       EDX, 1
( 004D0866    8B0C24 )                MOV       ECX, [ESP]
( 004D0869    03CA )                  ADD       ECX, EDX
( 004D086B    8D6DFC )                LEA       EBP, [EBP+-04]
( 004D086E    895D00 )                MOV       [EBP], EBX
( 004D0871    8BD9 )                  MOV       EBX, ECX
( 004D0873    E838A6FFFF )            CALL      004CAEB0        S>F
( 004D0878    8B1424 )                MOV       EDX, [ESP]
( 004D087B    8B0D08044600 )          MOV       ECX, [00460408]
( 004D0881    0FAFCA )                IMUL      ECX, EDX
( 004D0884    03D1 )                  ADD       EDX, ECX
( 004D0886    0FAF1504044600 )        IMUL      EDX, [00460404]
( 004D088D    031500044600 )          ADD       EDX, [00460400]
( 004D0893    DB3A )                  FSTP      TBYTE 0 [EDX]
( 004D0895    83042401 )              ADD       [ESP], 01
( 004D0899    8344240401 )            ADD       [ESP+04], 01
( 004D089E    71C0 )                  JNO       004D0860
( 004D08A0    8D64240C )              LEA       ESP, [ESP+0C]
( 004D08A4    83042401 )              ADD       [ESP], 01
( 004D08A8    8344240401 )            ADD       [ESP+04], 01
( 004D08AD    71A1 )                  JNO       004D0850
( 004D08AF    8D64240C )              LEA       ESP, [ESP+0C]
( 004D08B3    C3 )                    NEXT,
( 116 bytes, 38 instructions )
 ok
see testrx 
TESTRX 
( 004D08E0    682A094D00 )            PUSH      004D092A
( 004D08E5    68FEFFFF7F )            PUSH      7FFFFFFE
( 004D08EA    6A00 )                  PUSH      00
( 004D08EC    90 )                    NOP
( 004D08ED    90 )                    NOP
( 004D08EE    90 )                    NOP
( 004D08EF    90 )                    NOP
( 004D08F0    8B1424 )                MOV       EDX, [ESP]
( 004D08F3    83C202 )                ADD       EDX, 02
( 004D08F6    8D6DFC )                LEA       EBP, [EBP+-04]
( 004D08F9    895D00 )                MOV       [EBP], EBX
( 004D08FC    8BDA )                  MOV       EBX, EDX
( 004D08FE    E8ADA5FFFF )            CALL      004CAEB0        S>F
( 004D0903    8B1424 )                MOV       EDX, [ESP]
( 004D0906    031508044600 )          ADD       EDX, [00460408]
( 004D090C    0FAF1504044600 )        IMUL      EDX, [00460404]
( 004D0913    031500044600 )          ADD       EDX, [00460400]
( 004D0919    DB3A )                  FSTP      TBYTE 0 [EDX]
( 004D091B    83042401 )              ADD       [ESP], 01
( 004D091F    8344240401 )            ADD       [ESP+04], 01
( 004D0924    71CA )                  JNO       004D08F0
( 004D0926    8D64240C )              LEA       ESP, [ESP+0C]
( 004D092A    C3 )                    NEXT,
( 75 bytes, 23 instructions )
 ok
see xzcopy 
XZCOPY 
( 004D0950    8B1500044600 )          MOV       EDX, [00460400]
( 004D0956    DB2A )                  FLD       TBYTE 0 [EDX]
( 004D0958    8B1540044600 )          MOV       EDX, [00460440]
( 004D095E    DB3A )                  FSTP      TBYTE 0 [EDX]
( 004D0960    8B1500044600 )          MOV       EDX, [00460400]
( 004D0966    031504044600 )          ADD       EDX, [00460404]
( 004D096C    DB2A )                  FLD       TBYTE 0 [EDX]
( 004D096E    8B1540044600 )          MOV       EDX, [00460440]
( 004D0974    031544044600 )          ADD       EDX, [00460444]
( 004D097A    DB3A )                  FSTP      TBYTE 0 [EDX]
( 004D097C    8B1508044600 )          MOV       EDX, [00460408]
( 004D0982    83C201 )                ADD       EDX, 01
( 004D0985    0FAF1504044600 )        IMUL      EDX, [00460404]
( 004D098C    031500044600 )          ADD       EDX, [00460400]
( 004D0992    DB2A )                  FLD       TBYTE 0 [EDX]
( 004D0994    8B1548044600 )          MOV       EDX, [00460448]
( 004D099A    83C201 )                ADD       EDX, 01
( 004D099D    0FAF1544044600 )        IMUL      EDX, [00460444]
( 004D09A4    031540044600 )          ADD       EDX, [00460440]
( 004D09AA    DB3A )                  FSTP      TBYTE 0 [EDX]
( 004D09AC    8B1504044600 )          MOV       EDX, [00460404]
( 004D09B2    0FAF1508044600 )        IMUL      EDX, [00460408]
( 004D09B9    031500044600 )          ADD       EDX, [00460400]
( 004D09BF    DB2A )                  FLD       TBYTE 0 [EDX]
( 004D09C1    8B1544044600 )          MOV       EDX, [00460444]
( 004D09C7    0FAF1548044600 )        IMUL      EDX, [00460448]
( 004D09CE    031540044600 )          ADD       EDX, [00460440]
( 004D09D4    DB3A )                  FSTP      TBYTE 0 [EDX]
( 004D09D6    C3 )                    NEXT,
( 135 bytes, 29 instructions )
 ok

[toc] | [prev] | [next] | [standalone]

#19384

On 03.02.2013 11:48, Marcel Hendrix wrote:
> m.a.m.hendrix@tue.nl wrote Re: Matrices
>
>> On Monday, January 28, 2013 10:11:32 AM UTC+1, Andrew Haley wrote:
>>>> Is it possible to have 'delayed compilation?'
>>>
>>> Whyever not? If you keep threaded code around you can recompile
>>> it to machine code whenever you want.
>
>> I should have stated more clearly that I am looking for a syntax
>> that hides the mechanics as much as possible. Of course the task
>> as such is possible -- everything is possible in Forth.
>
> I thank everybody for their thoughtful replies.
>
> I postponed the solution of this challenge and first looked at the
> main problem: inefficient array/matrix accesses.

IMO that's a question of defining the right operators for indexed matrix 
access. Simple Forths expect the indices on the stack at runtime:
A[3,2] --> 3 2 A[] @   (simple syntax)

However with
3 CONSTANT THIRDROW  ( known at compile-time)
A[THIRDROW,2] --> THIRDROW 2 A[] @   will "normally" generate identical 
code and not be faster.

So it boils down to make the compiler aware of the indexing scheme and 
select the most fitting assembler code.

IMO the simple Forth way is to define a big bunch (and probably ugly 
looking) operators beforehand and make them IMMEDIATE compiling words.

Anything else will blow the compiler out of proportion because the 
notion of bound and unbound variables is unknown to Forth.

[toc] | [prev] | [next] | [standalone]

#19407 — Re: Offline compilation of Forth

mhx@iae.nl (Marcel Hendrix) writes Re: Matrices

> m.a.m.hendrix@tue.nl wrote Re: Matrices
>
>> On Monday, January 28, 2013 10:11:32 AM UTC+1, Andrew Haley wrote:
>>>> Is it possible to have 'delayed compilation?' 
>>>
>>> Whyever not? If you keep threaded code around you can recompile
>>> it to machine code whenever you want. 

>> I should have stated more clearly that I am looking for a syntax 
>> that hides the mechanics as much as possible. Of course the task 
>> as such is possible -- everything is possible in Forth.

> I thank everybody for their thoughtful replies.

> I postponed the solution of this challenge and first looked at the 
> main problem: inefficient array/matrix accesses.

[..]

A first cut at delayed compilation.

Of course, this idea should not be used when compiling takes longer
than the delay caused by suboptimal optimization.

-marcel

-- -------
ANEW -idea

DOC
(*
-- LET ( "cccc<:>" -- ) 
   *at compile time*

	1) accepts a string 
	2) allocates mem, copies string there ( c-addr u -- addr2 )
	3) compiles a vectored call through memory, with stack-effect ( 'vector addr2 -- ) 
	   Vector is setup for do-LET-FIRST.

   *at FIRST runtime* does do-LET-FIRST ( 'vector taddr -- )

	1) compiles a :NONAME. 
	   The first instruction is 2DROP
	   The rest comes from the text at taddr ( taddr -- xt ). 
	2) sets the vector to the :NONAME's xt.
	3) deallocates the string at taddr

   *at OTHER runtimes* (automatically) does
   
   	1) a call to the :NONAME ( xt addr -- )

   BUGS
   ----
   The :NONAME is called with two parameters. They are useful for do-LET-FIRST,
   but on next calls they are useless and should be dropped.

   NON ANS words
   -------------
   MULTI-LINE    WORD COUNT
   ?ALLOCATE     THROW
   @+		 DUP CELL+ SWAP @
   ]] [[	 string of POSTPONE .. 's
   PACK DROP     PLACE
*)
ENDDOC

-- For discussion only, is tokenized source in the real thing
: (LET) ( c-addr u -- ) EVALUATE ;

: do-LET-FIRST ( 'xt taddr -- )
	>R :NONAME ] ]] 2DROP [[  R@ @+ (LET) ]] ; [[  ( 'xt xt ) DUP ROT !
	R> FREE ?ALLOCATE  ( xt) 0. ROT EXECUTE ;

: LET ( "ccc<:>" -- )
	':' MULTI-LINE ( -- c-addr u )
	DUP 1+ ALLOCATE ?ALLOCATE LOCAL addr 
	addr PACK DROP
	POSTPONE AHEAD  ['] do-LET-FIRST , HERE CELL- >R  POSTPONE THEN
	R>   POSTPONE LITERAL ( 'xt)
	addr POSTPONE LITERAL ( string)
	POSTPONE OVER POSTPONE @EXECUTE ; IMMEDIATE

: test  LET cr ." Hello, world! ":  33 . ;

[toc] | [prev] | [next] | [standalone]

#19213

On Sun, 27 Jan 2013 22:17:26 +0200, mhx@iae.nl (Marcel Hendrix) wrote:

>Problems: How to detect code is run for the first time? How to detect
>that previously compiled code is still valid (no reallocate been done)?
>
>Note that the addresses of the matrices may be passed in locals. 

Let's make two simplifying assumptions:
1) Two pass compilation is not permitted
2) You have some form of tokeniser

I will also assume that additional data has to be stored.

You could use a notation such as
delayed : A*    ...  ;
or
delayed: A*  ...  ;

DELAYED ( -- ) can set such switches as the code generator needs
and build any additional data structures. It can even disable direct
code generation and just enable tokenisation.

Stephen


-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#19215

On Monday, January 28, 2013 11:39:50 AM UTC+1, Stephen Pelc wrote:
> On Sun, 27 Jan 2013 22:17:26 +0200, mhx@iae.nl (Marcel Hendrix) wrote: >Problems: How to detect code is run for the first time? 
> How to detect >that previously compiled code is still valid 
> (no reallocate been done)? 
> Note that the addresses of the matrices may be passed in locals. 
[ delayed ]
As I use this with OPG, the keyword LET can easily save the tokenized 
text of the expression and compile a JIT stub in its place. The JIT
is allowed to evaluate the locals and assume that there are no 
unresolved references.

This might actually *easier* than what I have now :-)

-marcel

[toc] | [prev] | [next] | [standalone]

#19219

In article <09181308028434@frunobulax.edu>, Marcel Hendrix <mhx@iae.nl> wrote:
>I have encountered a problem for which I don't immediately
>see a solution (maybe it won't need one in the Forth sense ;)
>
>Sometimes it is advantageous to NOT compile a word immediately.
>Is it possible to have 'delayed compilation?'
>
>An example is a word A* to multiply two dynamically allocated arrays.
>Because the address of the data and the number of rows and columns is
>unknown, the addressing of the matrix elements is very inefficient.
>In Forth it should be possible to compile A* AFTER it is detected
>that the matrices have been allocated (e.g. the first time A* is
>run). At that time many of the @s and !s will resolve to constant
>addresses, or at least access fixed rows or columns, and it will be
>known that the accesses are aligned or that the strides are
>powers of 2.

I don't understand why this example has to be so complicated.
I encounter the problem in a very common circumstance: using
MS-Windows system calls.

In the context of a TRUNKEY program we have the following.
The address of a system call, say GetMessageBox is constant,
however it is not known until runtime. The solution is simple.
When run for the first time, GetMessageBox patches it codefield
with doconstant, and its datafield with the constant address.
A similar action is done by a loader of dll's.

In the following K32 and _gev server as an example.
With two one-liners and a two-liner, this is rather compact
code.

\ ---------------------------------------------------------
( LOAD-DLL: DLL-ADDRESS: K32 GET-ENV ) CF: ?WI \ AvdH B2aug9
( sc -- adr) : Z 0 , DROP ;
( n adr -- )
: make-constant
   BODY> >R    R@ >DFA  !   'BL >CFA @   R> >CFA ! ;
( sc -- u )
: LOAD-DLL: CREATE $, DROP DOES> DUP >R $@  LOAD-DLL
    DUP R> make-constant ;
( sc xt -- adr )
: DLL-ADDRESS:   CREATE , $, DROP     DOES> DUP >R   CELL+ $@
    R@ @ EXECUTE DLL-ADDRESS   DUP R> make-constant ;

"kernel32.dll" LOAD-DLL: K32
"GetEnvironmentVariableA" 'K32 DLL-ADDRESS: _gev
\ ---------------------------------------------------------

Contrast with the normal usage of LOAD-DLL and DLL-ADDRESS
(without the colon).
"kernel32.dll" LOAD-DLL CONSTANT K32
"GetEnvironmentVariableA" K32 DLL-ADDRESS CONSTANT _gev

>
>Problems: How to detect code is run for the first time? How to detect
>that previously compiled code is still valid (no reallocate been done)?

You need not detect. When it is run for the first time, it is run
for the first time. Just make sure the second time you do something
different.

<SNIP>

>-marcel
>

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#19224

On Jan 27, 8:17 pm, m...@iae.nl (Marcel Hendrix) wrote:
> I have encountered a problem for which I don't immediately
> see a solution (maybe it won't need one in the Forth sense ;)
>
> Sometimes it is advantageous to NOT compile a word immediately.
> Is it possible to have 'delayed compilation?'
>
> An example is a word A* to multiply two dynamically allocated arrays.
> Because the address of the data and the number of rows and columns is
> unknown, the addressing of the matrix elements is very inefficient.
> In Forth it should be possible to compile A* AFTER it is detected
> that the matrices have been allocated (e.g. the first time A* is
> run). At that time many of the @s and !s will resolve to constant
> addresses, or at least access fixed rows or columns, and it will be
> known that the accesses are aligned or that the strides are
> powers of 2.
>
> Problems: How to detect code is run for the first time? How to detect
> that previously compiled code is still valid (no reallocate been done)?
>
> Note that the addresses of the matrices may be passed in locals.
>
> Assuming that the array syntax is a{{ row column }} @, it is of course
> possible to access a{{ efficiently by copying the addresses of rows
> and columns into locals (or on the stack) and then access elements
> row- or columnwise. However, as this is for my OPG project I'd like
> to always access the matrices the same, like a{{ row column }} @.
>
> Actually, in OPG the syntax will be a[r,c] where Forth doesn't even
> known if a is a vector or a (2D) matrix (the programmer knows, but
> does not know how to tell the compiler).
>
> -marcel

Would using ... DOES> ( 1st time) DOES> ( subsequently) ; help?

[toc] | [prev] | [next] | [standalone]

#19234

On Jan 27, 1:17 pm, m...@iae.nl (Marcel Hendrix) wrote:
> Sometimes it is advantageous to NOT compile a word immediately.
> Is it possible to have 'delayed compilation?'

I did that in MFX. I had "ghost" functions that didn't "materialize"
until they were referenced. It was easy. I just saved the source-code
on the host computer and I had a flag in the header that indicated if
the code was assembled yet and there was a cfa, or if it still needed
to be assembled.

This was done to save memory in the code memory, which was small
compared to the data memory. This was only for assembly-language
primitives, and not colon words.

This kind of thing has to be intrinsic to the compiler, and part of
the standard --- it can't be pasted on top of a standard (ANS-Forth)
that doesn't support it. I'll make this a part of Straight Forth ---
it is pretty common to have big libraries, but for particular
application programs to only need a few of the functions in the
library (you don't want a gigantic numerical library taking up memory,
if all you need is the SQRT function that is buried in there
somewhere).

[toc] | [prev] | [next] | [standalone]

#19244

mhx@iae.nl (Marcel Hendrix) writes:
>I have encountered a problem for which I don't immediately 
>see a solution (maybe it won't need one in the Forth sense ;)
>
>Sometimes it is advantageous to NOT compile a word immediately.
>Is it possible to have 'delayed compilation?' 

For regular Forth code you need to do the name binding and stuff like
executing immediate words "immediately" (that's why VFX's old source
inliner did not work correctly), but you can delay the rest of the
compilation.  I.e., produce some intermediate form, and, some time
between then and execution, produce the executable code from that.

The experimental inliner we did for Gforth worked like that; there the
intermediate form was unoptimized threaded code, and it was
transformed into the executed code when the word or it's direct or
indirect caller was first EXECUTEd.

@InProceedings{gregg&ertl04euroforth,
  author =	 {David Gregg and M. Anton Ertl},
  title =	 {Inlining in {Gforth}: Early Experiences},
  booktitle =	 {EuroForth 2004 Conference Proceedings},
  pages =        {33--40},
  year =	 {2004},
  URL =          {http://www.complang.tuwien.ac.at/papers/gregg%26ertl04euroforth.ps.gz},
  OPTnote =	 {not refereed},
  abstract =	 {Many optimizations are easier or more effective for
                  straight-line code (basic blocks). Straight-line
                  code in Forth is limited mainly by calls and
                  returns. Inlining eliminates calls and returns,
                  which in turn makes the basic blocks longer, and
                  increases the effectiveness of other
                  optimizations. In this paper we present a first
                  prototype implementation of ininlining for Gforth.}
}

>An example is a word A* to multiply two dynamically allocated arrays.
>Because the address of the data and the number of rows and columns is
>unknown, the addressing of the matrix elements is very inefficient.
>In Forth it should be possible to compile A* AFTER it is detected 
>that the matrices have been allocated (e.g. the first time A* is
>run). At that time many of the @s and !s will resolve to constant
>addresses, or at least access fixed rows or columns, and it will be
>known that the accesses are aligned or that the strides are 
>powers of 2.
>
>Problems: How to detect code is run for the first time?

If you want to do that on the Forth level, make A* a deferred word (or
similar), and do the code generation when it is called the first time.

> How to detect
>that previously compiled code is still valid (no reallocate been done)?

You could include a validity check before running the generated code
for A*.  Whether the validity check is too costly depends on the
application, but I suspect that for matrx multiplication, you could
even check the contents of both matrices if necessary, and still gain.
You could also have different code versions for different inputs (a
form of memoization).

Of course in many other cases, if you need such a check, the whole
thing does not pay off anymore.

>Note that the addresses of the matrices may be passed in locals. 

How does this matter?

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2012: http://www.euroforth.org/ef12/

[toc] | [prev] | [next] | [standalone]

#19245

On Jan 29, 9:49 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:
>
> If you want to do that on the Forth level, make A* a deferred word (or
> similar), and do the code generation when it is called the first time.

Indeed.

variable 'A*

: build_A* <code to compile A*> ;

' build_A* 'A* !

: A* 'A* @ EXECUTE ;

So, the first time A* is called, it calls build_A* which examines the
array dimensions and compiles customised Forth code to efficiently
process the array. It will also execute that same code. It will set
the vector such that subsequent calls to A* call the newly compiled
code, rather than build_A*

Is this using a sledge hammer to crack an egg though? Perhaps, on
examination of the requirements, only a handful of different array
sizes are required? In that case, better to hand code them as normal
colon definitions, and at run time a dispatcher will determine which
matrix multiplication routine to call at run-time.

If using a modern state-of-the-art compiler like VFX, I would caution
against too much human-level optimisation. Just write the code and let
the compiler deal with it. Run the code. Are the run-times acceptable?
If so, move on to the next problem. Obssesive optimisation is a time
waster! Yeah, you shave off 1.5 seconds but it takes you a week to
write it!

[toc] | [prev] | [next] | [standalone]

#19251

On Tuesday, January 29, 2013 1:08:50 PM UTC+1, M.R.W Wills wrote:
[..]
> If using a modern state-of-the-art compiler like VFX, I would caution
> against too much human-level optimisation. Just write the code and let 
> the compiler deal with it. Run the code. Are the run-times acceptable?

I think there is an echo in this room, I hear myself talking ... :-)
No, a modern Forth compiler doesn't (yet) optimize these kind of 
problems. By an ugly rewrite, efficient code can be generated (using the 
BLAS etc.). What I am after is naive code that runs fast.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web