Heap's algorithm

[Julian Fondren]

Hello clf,

The following thread on reddit /r/Forth may interest you. The poster
has some difficulty with showing permutations in Forth, but powers
through it, and then asks for feedback on his code. There's another
implementation of the task among the replies.

https://www.reddit.com/r/Forth/comments/6fzpkd/applying_forths_principles_in_practice/

Here's mine:

: third 2 pick ;

: permute-start ( addr u -- addr u permute-state )
align here dup third cells dup allot erase ;

: permute-free ( addr u permute-state -- )
drop nip 1+ cells negate allot ;

: switch ( a1 a2 -- )
over @ over @ swap rot ! swap ! ;

: next-permute ( addr u permute-state -- addr u permute-state f )
over 0 do
dup i cells + @ i < if
i 2 mod 0= if
third dup i cells + switch
else
third dup i cells + swap
third i cells + @ cells + switch
then
1 over i cells + +!
true unloop exit
then
0 over i cells + ! loop false ( no more permutations ) ;

create blah 1 , 2 , 3 , 4 , 5 ,
: show ( -- ) blah 5 cells bounds cr do i ? 1 cells +loop ;
: show-blahs ( -- )
blah 5 permute-start
begin show next-permute 0= until permute-free ;

ALLOCATE and FREE variants of PERMUTE-START and PERMUTE-FREE could
easily be supplied; NEXT-PERMUTE won't care either way. I don't really
like all the repetitions of I CELLS + and at a glance the inner stack
manipulation could probably be simplified by swapping ( addr u ) ahead
of time. Another option: assume the caller has his own convenient
access to the array -- as is actually the case above with BLAH -- and
include ADDR U in the temporary array.

This is an implementation of the non-recursive version of Heap's
algorithm, which is written as a self-contained function with an
output(A) to supply the permutations. By taking an xt you could write
a Forth word that more closely mirrors the pseudocode, but I like
NEXT-PERMUTE as its own factor, since that lets you be a little bit
more clever with the temporary array.

Another place to hold the 'temporary array' is in the actual array
that you're generating permutations for, if you've bits to spare. You
need at least enough to represent the length of the array. I can't
think of use for that though... maybe if there's a lot of permutation
done with DNA strings?

(Unrelatedly, I have now a 159-line definition in Forth. I may post
about it later. After slaying the beast, of course.)

[Raimond Dragomir]

This looks to me as a very write-only code. At least I cannot read it.
Using locals would have been great. Just a simple example, of the
switch:
: switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

'third' is an example of an egocentric word. It's names descibe the stack
effect. But although it's so much used inside the next-permute, it
doesn't show what it is for. It's like there is a 'third' thing envolved
there. Is that definition about the (forth) stack or about a sorting
algorithm? If you didn't hide '2 pick' in the 'third', at least things
would have been more clear.

Too much forth code is this kind of egocentric. It looks like it wants
to show/demonstrate some stack mechanics at any price. And the human
must need to 'decode' the intended functionality from this stack mechanics.

Sorry for my comments if this post is intended for discussing the real
functionality/implementation strategies. But I feel that it's about
"is this good forth style?".

[Julian Fondren]

On Friday, June 9, 2017 at 1:21:59 AM UTC-5, Julian Fondren wrote:
> : permute-free ( addr u permute-state -- )
> drop nip 1+ cells negate allot ;

An earlier version of PERMUTE-START included an extra cell.

This should be:

: permute-free ( c-addr u permute-state -- )
drop nip cells negate allot ;

A nice feature that some languages have is a way to run code depending
on how a library is loaded. Python can test __main__ I believe; Perl
can use caller() outside of a function. Usually the aim is for a file
to normally run as a script, as a standalone program, and to *not* do
that if loaded as a library, or into an interactive session.

It's interesting that these aren't 'first class' features in those
languages. Python doesn't have a builtin run_if_script: syntax;
instead people just know to write

if __main__ == '__file__':

or something similar to that. Even though it's awkward and looks
hackish, it's so useful you'll see it frequently enough.

iForth has NESTING and this idiom:

NESTING @ 1 = [IF]
\ this is run only if you directly included the enclosing file
\ nothing happens if another file includes this one
[THEN]

Which allows me to add some tests to the above code that'll run if I
type 'include perms.fs', but not if some application loads it as a
library.

nesting @ 1 = [IF]
needs -ttester

0 value orig-here
align here to orig-here
show-blahs
T{ orig-here here = -> true }T
[THEN]

This probably doesn't sound like a big deal. Obviously, you could just
have tests in another file, and load that when you want them. But if
you have the feature, you'll probably use it.

[Julian Fondren]

On Friday, June 9, 2017 at 2:27:08 AM UTC-5, Raimond Dragomir wrote:
> This looks to me as a very write-only code. At least I cannot read it.
> Using locals would have been great. Just a simple example, of the
> switch:
> : switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

This code reaches a depth of three instead of the original depth of
four. Why is that such an significant change for you?

Ths is how I read the original:

( a1 a2 -- )

over @ over @ ( a1 a2 x1 x2 )
swap ( a1 a2 x2 x1 )
rot ! \ x1 -> a2
swap ! \ x2 -> a1

Maybe with SWAP as part of the first phrase and not as an indepedent
phrase.

I actually originally wrote NEXT-PERMUTE with locals (before I
realized that pseudocode 'i' didn't need to be preserved; that was the
additional cell accounted for by PERMUTE-FREE). It wasn't that nice.

>
> 'third' is an example of an egocentric word. It's names descibe the stack
> effect. But although it's so much used inside the next-permute, it
> doesn't show what it is for.

The first DUP in NEXT-PERMUTE also doesn't show what it's for.
Obviously, you have to know what's on the stack to understand the
point of a stack-effect word.

> If you didn't hide '2 pick' in the 'third', at least things
> would have been more clear.

Eh, OK. I would say exactly the opposite of any 2 PICK found in Forth
code. 2 PICK is only present here because optimizers have as easy or
an easier time with it as they would with alternatives.

> Too much forth code is this kind of egocentric. It looks like it wants
> to show/demonstrate some stack mechanics at any price. And the human
> must need to 'decode' the intended functionality from this stack mechanics.

Sorry, but 'egocentric' means nothing to me, as a word. The desire
behind most of this code is to accomplish a given task, not to show
off stack mechanics or anything else. Of someone who can't read it, I
would just say that this is a person who can't read Forth. Or code at
all: the pseudocode also doesn't "say what it's for", it's a lot of

for i := 0; i < n; i += 1 do
c[i] := 0
end for

and more of

c[i] := 0
i += 1

And I reckon, as I've found of Forth given such treatment, that after
you twist "c[i] := 0" to the point that it "reads like English", the
main result will be that it's now harder to understand what's actually
happening. When memory fades a bit, you can

1. piece things back together from multiple directions, from on high,
from the English meanings of words, but also but also from down low,
from what you can clearly see from mundane pushing-bits-around code,
or you can

2. read a 80k word treatise (that was never written--so actually you
can't read it, and this option is a lie) to completely restore to you
the original context of GLEEBLE and FWIPSLUSH and DECIMATE? and all
the other cute once-off pseudofactors that made sense at the time.

Take this code from the reddit thread:

: odd? ( n i -- n f ) over 1+ 1 and ;
: switch ( n i -- ) odd? if drop 0 then exch ;

"odd? if" reads nicely in the definition of SWITCH. But what the hell
is it doing? It certainly isn't doing

: odd? ( n -- f ) 1 and ;

It's doing something that makes sense *only* in the context of
SWITCH. That stack comment was originally ( n - n f ); on reddit it
was pointed out that OVER is obviously assuming more on the stack, so
this was 'fixed' -- and the new stack comment is still wrong. Because
this isn't a real factor.

I don't have a good metaphor for this, but: it's OK for the inside of
your body to look, in some areas, like a muscle that pushes blood
through tubes. That part of your body doesn't have to meet the beauty,
dryness, emotive, and other standards of your face. In its own way it
supports you having something like a face.

> Sorry for my comments if this post is intended for discussing the real
> functionality/implementation strategies. But I feel that it's about
> "is this good forth style?".

It's fine by me, even if I don't agree with you. The reddit thread had
a similar focus.

[Raimond Dragomir]

> Ths is how I read the original:
>
> ( a1 a2 -- )
> over @ over @ ( a1 a2 x1 x2 )
> swap ( a1 a2 x2 x1 )
> rot ! \ x1 -> a2
> swap ! \ x2 -> a1

Given the task: "swap the content of two memory addresses",
if besides the obvious two stores and two fetches you need
two SWAPs, two OVERs and a ROT, something may not be ok,
at least to me.

Note that I was using the stack in a "clever" way, even with
the locals:

: switch { a1 a2 -- }
a1 @
a2 @ a1 !
a2 !
;

In a variables-only language you will need a temp variable.

Maybe you are right: I can't read forth code. At least not
next-permute one. I was able to read 'switch' in my mind
although at the ROT moment it was quite hard to visualize the
order of the parameters on the stack. Maybe I'm not good
at blind chess also. And from what I've read, three parameters
on the stack are manageable, four are not. It's not my
saying however. Even three are sometimes hard, especially
when they hide in a longer definition. In my short definition of
switch the parameters are almost named (because of the local
names) and consumed immediately.

What's funny is that in the original post, the guy admits his
limit in writing "forth" code (although tried hard with the 'switch'):

: 3dup { a b c } a b c a b c ;

Otherwise, he's not using locals in any other definition.

[Julian Fondren]

On Friday, June 9, 2017 at 4:15:44 AM UTC-5, Raimond Dragomir wrote:
> Given the task: "swap the content of two memory addresses",
> if besides the obvious two stores and two fetches you need
> two SWAPs, two OVERs and a ROT, something may not be ok,
> at least to me.

You have two addresses.
You have @ and ! , which both consume an address.
You need to call @ twice and ! twice -- consuming a total of four
addresses.

You have two addresses but must consume four of them?
Two OVERs supply the two additional addresses that you need.

@ takes an address from the top of the stack and puts the value at
that address back on the top of the stack. If you consume two copies
of addresses, and leave two values on the stack -- where will those
values be?
On the top of the stack of course, until you move them.

! takes an address from the top of the stack, and a value from the
next on the stack. In other words it expects addresses to be above
values on the stack.
At this point though, your values are above your addresses.
ROT and SWAP rectify that.

So if something is wrong, apparently it's @ and !

Or rather, why don't you try it? You can use 2DUP , or DUP and THIRD ,
or >R R@ OVER . You need two copies and you need @'s return to be
deeper in the stack.

Or do you prefer this?

: switch ( a1 a2 -- )
dup pad 1 cells move
2dup 1 cells move
drop pad swap 1 cells move ;

[Coos Haak]

Op Thu, 8 Jun 2017 23:21:57 -0700 (PDT) schreef Julian Fondren:

> Hello clf,
>
> The following thread on reddit /r/Forth may interest you. The poster
> has some difficulty with showing permutations in Forth, but powers
> through it, and then asks for feedback on his code. There's another
> implementation of the task among the replies.
>
> https://www.reddit.com/r/Forth/comments/6fzpkd/applying_forths_principles_in_practice/
>
> Here's mine:
>
> : third 2 pick ;
>
> : permute-start ( addr u -- addr u permute-state )
> align here dup third cells dup allot erase ;

I don't like PICK at all. Why not
align dup cells here swap allot erase
or
aligh here over cells dup allot erase

groet Coos

[Raimond Dragomir]

I try it, here it is again:

: switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

Some things just don't fit to the stack model. They are more
random access than ordered in some way. The traditional forth
doesn't want to admit this reality and solves everything by
stack juggling, no matter how awfull the code looks (and
probably is).

I don't like stack juggling at all. In this respect, PICK is
my friend not my enemy but I prefer named access (locals)
rather than numbered (PICK).

[Lars Brinkhoff]

Julian Fondren wrote:
> "odd? if" reads nicely in the definition of SWITCH. But what the hell
> is it doing? It certainly isn't doing
>
> : odd? ( n -- f ) 1 and ;
>
> It's doing something that makes sense *only* in the context of SWITCH.

Yes, that's right. I put some emphasis on making words that make sense
in the context of the call site. That's how I write Forth code that is
easy for me to read. It wasn't intended as an example of good Forth
style.

[Julian Fondren]

On Friday, June 9, 2017 at 5:33:01 AM UTC-5, Coos Haak wrote:
> Op Thu, 8 Jun 2017 23:21:57 -0700 (PDT) schreef Julian Fondren:

> > : permute-start ( addr u -- addr u permute-state )
> > align here dup third cells dup allot erase ;

> I don't like PICK at all. Why not

I'm not using PICK. I'm using THIRD. The definition there is "in case
you don't have this". On SwiftForth THIRD's a CODE word. On iForth and
VFX it compiles identically to PICK-averse code.

> align dup cells here swap allot erase

create box 100 allot

box 100
align dup cells here swap allot .s

Outputs:

Data: 270663760 100 270666160 ---
System: ---
Float: --- ok

I don't want to go on to ERASE that...

> or
> aligh here over cells dup allot erase

box 100
align here over cells dup allot erase .s

Data: 270663760 100 ---
System: ---
Float: --- ok

You've done this before :-)

But it's a different word.

[Julian Fondren]

On Friday, June 9, 2017 at 5:50:31 AM UTC-5, Raimond Dragomir wrote:
> I try it, here it is again:
> : switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;

> Some things just don't fit to the stack model.

This is a word that consumes two items on the stack, and only goes to
a depth of four on the stack. Its only stack manipulation words are
OVER SWAP and ROT

You say it doesn't fit the stack model and aren't willing to write it.

Occasionally I'm annoyed when people pass off knowledge they gained by
reading about it in a blog (or worse, a news report) as if it were an
opinion drawn from their personal professional experience. Like a fan
of webMD not saying "oh no I read about this on webMD, you should--"
but rather "I'm a doctor, I've seen this hundreds of times, and you
need to--". People hesitate before claiming to be doctors but on
technology a CNET article is enough to authoritatively declare that
the OS is dead, whatever CNET specifically meant by that.

Here I'm annoyed by someone making a presumptuous claim on a matter of
taste.

So, good start to the weekend :-)

[Andrew Haley]

Raimond Dragomir <raimond....@gmail.com> wrote:
>
> I try it, here it is again:
> : switch { a1 a2 -- } a1 @ a2 @ a1 ! a2 ! ;
>
> Some things just don't fit to the stack model. They are more
> random access than ordered in some way. The traditional forth
> doesn't want to admit this reality and solves everything by
> stack juggling, no matter how awfull the code looks (and
> probably is).

If you're going to insist on traditional, Forth would do something
like this:

code switch ( a1 a2)
0 [ebp] eax mov ( a1 -> eax)
0 [eax] ecx mov ( n1 -> ecx)
0 [ebx] ecx xchg ( n1 -> a2, n2 -> ecx)
cell [ebp] ebx mov
ecx 0 [eax] mov ( n2 -> a1)
2 cells # ebp add ( pop a1 and a2)
ret
end-code

This is a semi-serious point: when it was commonplace to write fiddly
low-level definitions like this in code, there wasn't much of a
perceived problem.

Andrew.

[rickman]

This is the sort of stack juggling that my stack processor gets around
(somewhat) by using the return stack for memory addresses. I sometimes call
it the address stack for this reason.

In this case the addresses are not known to be literals (which are also
generated on the return stack) so on entry to the routine they are on the
data stack and must be moved to the return stack which is not so convenient
but it seems to be pretty brief.

: switch ( a1 a2 -- ) >R >R ROVER @ RDUP ! @ ! ;

These are all machine instructions including the call and return. The
return can not be combined with the ! because they both use the return
stack... unless a pathway is added to allow the next instruction address to
be fetched from the second on the return stack. I've tried to minimize the
machine size so I didn't implement this path.

I've never dug into how local variables are implemented. Does it require
the use of separate memory, space on the return stack or is there a special
stack? I'm curious how efficient local variables could be. Are they worthy
of dedicated hardware (which might be as simple as a data path somewhere)?

--

Rick C

[Julian Fondren]

On Friday, June 9, 2017 at 10:18:10 AM UTC-5, rickman wrote:
> : switch ( a1 a2 -- ) >R >R ROVER @ RDUP ! @ ! ;

Does this actually work? It looks like it sets both addresses to the
same value instead of swapping their values. Just look at the
store/fetch words: @ ! @ ! instead of @ @ ! !

I would think you'd need

: switch ( a1 a2 -- ) >R >R ROVER @ RDUP @ SWAP ! ! ;

Or more neatly:

: switch ( a1 a2 -- ) >R >R RDUP @ ROVER @ ! ! ;

That saves a SWAP , which is also what the locals version saves.

[hughag...@gmail.com]

On Friday, June 9, 2017 at 12:27:08 AM UTC-7, Raimond Dragomir wrote:
> This looks to me as a very write-only code. At least I cannot read it.
> Using locals would have been great.

My heap-sort in the novice-package uses locals. Also, I support arrays of structs --- the ANS-Forth crowd seems to be obsessed with forcing everybody to use arrays of cells.

This is my code:
---------------------------------------------------------------------------

SwiftForth? [if] \ SwiftForth's optimization is so bad that no Forth version is any good

icode exchange ( adrX adrY size -- ) \ the size of the record must be a multiple of W
0 [ebp] edx mov w [ebp] ecx mov \ EDX<>ECX, with EBX being the size
begin non-zero? while
0 [ecx] eax mov
0 [edx] eax xor eax 0 [edx] xor 0 [edx] eax xor
eax 0 [ecx] mov
w # edx add w # ecx add
w # ebx sub repeat
w 2 * [ebp] ebx mov
w 3 * # ebp add ret end-code

[else]

macro: exchange ( adrX adrY size -- ) \ the size of the record must be a multiple of W
begin dup while \ -- adrX adrY remaining
-rot \ -- remaining adrX adrY
dup @ rover @ \ -- remaining adrX adrY Y X
rover ! rover ! \ -- remaining adrX adrY
w + swap w + rot w - \ -- adrY adrX remaining \ adrY and adrX change places
repeat
3drop ;

\ Under VFX the SWAP to get adrY and adrX back to how they were doesn't cost anything.
\ Having them change places might help on a non-optimizing compiler though.

[then]

\ If FIELD is used to define records, the size of the records will be a multiple of W, as required by EXCHANGE.


\ ******
\ ****** This is our array sort. We are using the heap-sort because it provides consistent times and it is not recursive.
\ ****** This code was ported from C++ at: http://www.snippets.24bytes.com/2010/06/heap-sort.html
\ ****** Our array record size must be a multiple of W. This is assured if FIELD is used for creating the record.
\ ****** The easiest way to speed this up is to rewrite EXCHANGE in assembly language.
\ ******

\ All of these macros use the locals from SORT, and can only be called from SORT.
\ Because they access locals, they have to be defined with LATE-MACRO: --- this is something MACRO: can't do.

late-macro: adr ( index -- adr )
recsiz * array + ;

late-macro: left ( x -- y ) 2* 1+ ;

late-macro: right ( x -- y ) 2* 2 + ;

late-macro: heapify ( x -- )
dup >r begin \ r: -- great
dup left dup limit < if dup adr rover adr 'comparer execute if rdrop dup >r then then drop
dup right dup limit < if dup adr r@ adr 'comparer execute if rdrop dup >r then then drop
dup r@ <> while
adr r@ adr recsiz exchange
r@ repeat
drop rdrop ;

late-macro: build-max-heap ( -- )
limit 1- 2/ begin dup 0>= while dup heapify 1- repeat drop ;

: sort { array limit recsiz 'comparer -- }
recsiz [ w 1- ] literal and abort" *** SORT: record size must be a multiple of the cell size ***"
build-max-heap
begin limit while -1 +to limit
0 adr limit adr recsiz exchange
0 heapify repeat ;

\ The SORT locals:
\ array \ the address of the 0th element
\ limit \ the number of records in the array
\ recsiz \ the size of a record in the array \ this must be a multiple of W (FIELD assures this)
\ 'comparer \ adrX adrY -- X>Y?

\ Note for the novice:
\ This code was originally written with colon words rather than macros, and using items rather than local variables.
\ After it was debugged, it was changed to use macros and locals so that it would be fast and reentrant.
\ One of the reasons why the heap-sort was chosen is because it is not recursive, which allows macros to be used.
\ Using macros allows the data (array, limit, recsiz, 'comparer) to be held in locals rather than items, which is reentrant.
\ See the file SORT.4TH for an early version.

[hum9]

My take (GForth 0.7.3 tested):

\ Helper words
: r'@ ( S: -- a R: a b -- a b)
postpone 2R@ postpone drop ; immediate
: cell- ( n -- n-cell) cell - ;
: exch ( a a' -- ) dup @ -rot over @ swap ! ! ;

\ Vector words
: v@ ( a -- a+cell u ) dup cell+ swap @ ;
: ?+ ( a -- a+cell ) dup ? cell+ ;
: show ( a -- ) v@ 0 DO ?+ LOOP drop cr ;

: permute ( a N -- )
dup 2 < IF drop cell- show EXIT THEN
1- 2>r 0
BEGIN ( u R: a N-1)
dup r@ <=
WHILE
2r@ recurse
2r@ cells +
r@ 1+ 2 mod
IF over cells r'@ + ELSE r'@ THEN
exch
1+
REPEAT
drop 2RDROP
;

create Ar 5 ( cells count) , 1 , 5 , 10 , 100 , 1000 ,
Ar v@ permute .s bye


Have a nice day,
hum9

[rickman]

Let's try it one instruction at a time...

: switch ( a1 a2 -- ) >R >R ROVER @ RDUP ! @ ! ;

( a1 a2 -- ) (R: -- ) ( a1:x1 a2:x2 )
>R ( a1 a2 -- a1 ) (R: -- a2 ) ( a1:x1 a2:x2 )
>R ( -- ) (R: a2 -- a2 a1 ) ( a1:x1 a2:x2 )
ROVER ( -- ) (R: a2 a1 -- a2 a1 a2 ) ( a1:x1 a2:x2 )
@ ( -- x2 ) (R: a2 a1 a2 -- a2 a1 ) ( a1:x1 a2:x2 )
RDUP ( -- x2 ) (R: a2 a1 -- a2 a1 a1 ) ( a1:x1 a2:x2 )
! ( -- ) (R: a2 a1 a1 -- a2 a1 ) ( a1:x2 a2:x2 ) oops!
@
!
;

Yes, your final word looks good.

I've also looked at an addressable stack machine that allows a very small
offset into the stack to retrieve operands which saves a *lot* more stack
juggling. It would require a compiler to be aware of operand positions to
be able to use this effectively. I haven't done much other than to code up
an example app, but it was much more instruction efficient. The variations
on instruction set use between 103 and 60 instructions with the 103 being my
basic stack processor and 60 being the stack indexed instruction set.

The app for this comparison is an interrupt routine for a software DDS which
generates the value to feed a DAC on the fly. Maybe I'll get around to
working on this and produce an FPGA design. I think it could produce
significantly more compact code than a straight stack design. Not sure what
it would take to write an optimizing compiler for it.

--

Rick C

[Alex]

XCHG LOCKs for memory operands.

see exchange
code exchange ( 2 -- 0 )
\ exchange is defined in src/kernel/gkernel32.fs at line 1288
\ call compiled
\ code=$401D0F len=17 type=129
( $0 ) mov ecx dword { $0 ebp } \ 8B4D00
( $3 ) mov edx dword { eax } \ 8B10
( $5 ) mov edi dword { ecx } \ 8B39
( $7 ) mov dword { eax } edi \ 8938
( $9 ) mov dword { ecx } edx \ 8911
( $B ) mov eax dword { $4 ebp } \ 8B4504
( $E ) add ebp $8 \ 83C508
( $11 ) ret \ C3 ( end ) ok

EAX is cached TOS, EBP is stack.

--
Alex

[Coos Haak]

Op Fri, 9 Jun 2017 07:37:26 -0700 (PDT) schreef Julian Fondren:

your follow-ups are stronly mixed up

> On Friday, June 9, 2017 at 5:33:01 AM UTC-5, Coos Haak wrote:

<snip>

>> align dup cells here swap allot erase

I forgot a dup
align dup cells here swap dupa allot erase

groet Coos

[Julian Fondren]

On Friday, June 9, 2017 at 12:50:23 PM UTC-5, Coos Haak wrote:
> Op Fri, 9 Jun 2017 07:37:26 -0700 (PDT) schreef Julian Fondren:
>
> your follow-ups are stronly mixed up

Mixed up how?

>
> > On Friday, June 9, 2017 at 5:33:01 AM UTC-5, Coos Haak wrote:
> <snip>
> >> align dup cells here swap allot erase
> I forgot a dup
> align dup cells here swap dupa allot erase

OK, but this is still not the same word.

The word you're replacing has this stack effect:

[hum9]

Not needed '1+' on testing oddity for 'N-1':
> r@ 1+ 2 mod


hum9

[Julian Fondren]

On Friday, June 9, 2017 at 11:35:35 AM UTC-5, hughag...@gmail.com wrote:
> Also, I support arrays of structs --- the ANS-Forth crowd seems to be obsessed with forcing everybody to use arrays of cells.

cells: 3.475 seconds elapsed.
structs: 21.650 seconds elapsed.

cells: 3.672 seconds elapsed.
structs: 22.101 seconds elapsed.

cells: 3.680 seconds elapsed.
structs: 22.145 seconds elapsed. ok

It's just malice I guess.

'cells' is a permutation benchmark using code above.

'structs' is the same but MOVEing 10 cells:

: structs 10 cells * ;
1 structs buffer: pad

: switch ( a1 a2 -- )

dup pad 1 structs move
2dup 1 structs move
drop pad swap 1 structs move ;
: next-permute ( c-addr u permute-state -- c-addr u permute-state f )
over 0 do
dup i structs + @ i < if

i 2 mod 0= if

third dup i structs + switch
else
third dup i structs + swap
third i structs + @ cells + switch
then
1 over i structs + +!
true unloop exit
then
0 over i structs + ! loop false ( no more permutations ) ;

[hum9]

On Friday, June 9, 2017 at 9:21:59 AM UTC+3, Julian Fondren wrote:

I modified a little your version. Looks that impediments to use return
stack for temporary storage makes 'DO..LOOP' version more unreadable.

I don't like to much stack effects of 'permute-start' and 'permute-free':
they doesn't consume their parameters.

Presentation part I preserved mostly unchanged:


: r'@ postpone 2r@ postpone drop ; immediate

: perm-state ( u -- permute-state )
align cells here dup rot dup allot erase ;

: state-free ( permute-state -- )
HERE - allot ;

: switch ( a a' -- )

dup @ -rot over @ swap ! ! ;

: next-perm ( addr u permute-state -- addr u permute-state f )
2>r 0
BEGIN ( A u R:N P )
dup r'@ <
WHILE
r@ over cells + @ over <
IF ( A u R:N P )
2dup cells + >r
dup 2 mod
IF ( A u R:N P A[u] )
2dup cells r'@ + @ cells +
ELSE
over
THEN
r> switch ( A u R:N P )
1 over cells r@ + +!
drop 2r> TRUE EXIT
THEN
0 over cells r@ + !
1+
REPEAT
drop 2r> FALSE ;

create blah 1 , 2 , 3 , 4 , 5 ,
: show ( -- ) blah 5 cells bounds cr do i ? 1 cells +loop ;
: show-blahs ( -- )

blah 5 dup perm-state
BEGIN show next-perm 0= UNTIL
state-free 2drop ;

HERE show-blahs cr HERE swap - . .s cr bye

[Julian Fondren]

On Saturday, June 10, 2017 at 5:07:11 AM UTC-5, hum9 wrote:
> I modified a little your version. Looks that impediments to use return
> stack for temporary storage makes 'DO..LOOP' version more unreadable.
>
> I don't like to much stack effects of 'permute-start' and 'permute-free':
> they doesn't consume their parameters.

I've come to dislike that as well. But also of NEXT-PERMUTE

This NEXT-PERM is a lot busier than your last--I wonder if that's
due to the stack effect or due to the data structure.

[hum9]

On 10.06.2017 15:41, Julian Fondren wrote:
> On Saturday, June 10, 2017 at 5:07:11 AM UTC-5, hum9 wrote:
>> I modified a little your version. Looks that impediments to use return
>> stack for temporary storage makes 'DO..LOOP' version more unreadable.
>>
>> I don't like to much stack effects of 'permute-start' and 'permute-free':
>> they doesn't consume their parameters.
>
> I've come to dislike that as well. But also of NEXT-PERMUTE
>
> This NEXT-PERM is a lot busier than your last--I wonder if that's
> due to the stack effect or due to the data structure.

Previous version, 'PERMUTE', is a recursive one. This version is derived
directly from your 'NEXT-PERMUTE', but using 'BEGIN WHILE REPEAT'. :)

I checked parameters usage, then distributed accordingly with priorities
between data stack and return stack.

[hughag...@gmail.com]

This is not my code.

[Julian Fondren]

No, that's QUITE OBVIOUSLY my code, seeing as it's almost identical to
the cell-permuting code that I claimed as my own in the very first
post of the thread. What's your point? Do you think you have code
that shows that moving more data is faster than moving less data?

It's actually possible for that to be the case, since contiguous
access to memory is faster than random access to it, but you would
still need an apples-to-oranges comparison somewhere. Where's your
struct-sorter that's faster than the equivalent cell-sorter?

[hughag...@gmail.com]

Alex McDonald has spent four years (it will be four years in June) bashing my array SORT in the novice package. Now Julien Fondren has begun, and will presumably continue for another four years.

ANS-Forth is a cult! They just continue with this utterly stupid nonsense year after year --- they think they are beating me down, and convincing the world that I don't know what pointers are --- they are just making the ANS-Forth cult look stupid, which is why nobody is volunteering to become an ANS-Forth programmer.

I never actually said: "moving more data is faster than moving less data."

I've said dozens of times already that my array definers and my array SORT support elements of any size (they have to be a multiple of the cell size for SORT to work, but FIELD assures this anyway). It is possible to have an array of pointers to structs, and it is also possible to have an array of structs.

My novice-package is general-purpose code! This is not like Wil Baden's code that forces the user to have an array of cells. I support, for example, an array of floats. With Wil Baden's code, what you would likely do is cut-and-paste-and-modify the array of cells so that it is an array of floats --- cut-and-paste-and-modify is typical Forth Inc. programming style --- afaik, Wil Baden was a Forth Inc. employee.

The novice-package user can decide if he wants to have an array of pointers to structs or an array of structs. It never occurred to me when I wrote the code that I should take this choice away from the user --- I would assume that anybody using the novice-package must be reasonably smart and capable of making choices such as this --- there are a lot of choices involved in the design of application programs, and this is one of them.

If you have an array of pointers to structs, then where are the structs? If they are in the heap, then the cost of ALLOCATE and FREE is going to be significant. This is an argument for having an array of structs.

Sometimes you may have a lot of structs in an array, and want it sorted by various keys. In this case, you would have various arrays of pointers to these structs each sorted by a different key.

I don't actually care whether people have an array of pointers to structs or an array of structs.. As for myself, I almost never use arrays --- I would use LIST.4TH or ASSOCIATION.4TH generally.

[Julian Fondren]

On Saturday, June 10, 2017 at 8:56:25 PM UTC-5, hughag...@gmail.com wrote:

Timeline:

> On Saturday, June 10, 2017 at 2:44:07 PM UTC-7, Julian Fondren wrote:
> > On Saturday, June 10, 2017 at 4:28:59 PM UTC-5, hughag...@gmail.com wrote:
> > > On Friday, June 9, 2017 at 11:31:45 PM UTC-7, Julian Fondren wrote:
> > > > On Friday, June 9, 2017 at 11:35:35 AM UTC-5, hughag...@gmail.com wrote:
> > > > > Also, I support arrays of structs --- the ANS-Forth crowd seems to be obsessed with forcing everybody to use arrays of cells.

Hugh: these idiots like arrays of cells for some reason.

> > > >
> > > > cells: 3.475 seconds elapsed.
> > > > structs: 21.650 seconds elapsed.
> > > >
> > > > cells: 3.672 seconds elapsed.
> > > > structs: 22.101 seconds elapsed.
> > > >
> > > > cells: 3.680 seconds elapsed.
> > > > structs: 22.145 seconds elapsed. ok
> > > >

Me: gosh, I wonder why.

> Alex McDonald has spent four years [blah blah blah]

Hugh: I made a claim and somebody responded to it. That person is
CULTISH and OBSESSED for responding to topics that I brought up
completely on my own!

>
> I support, for example, an array of floats. With Wil Baden's code, what you would likely do is cut-and-paste-and-modify the array of cells so that it is an array of floats

What I'd prefer to do for stuff like floats is have conditional code
generation at compile time, and then you would load the library
multiple times to get multiple sorts for multiple types. Manually
doing the kind of type specialization that you see in some other
languages.

That's certanly better than writing a struct-sorter that's always
significantly slower than the cell or float specializations, even when
given 1 CELLS or 1 FLOATS as the length.

But if your defense is, "this is 'generic', I know it's slower", you
could at least stop pretending that people are insane or filled with
evil for wanting code that's like 7x faster.

> If you have an array of pointers to structs, then where are the structs? If they are in the heap, then the cost of ALLOCATE and FREE is going to be significant. This is an argument for having an array of structs.

Having an array of pointers to structs doesn't require that you not
also have an array of structs. You just use the array of pointers when
you want to sort, permute, etc. Especially if you'll be doing that a
lot.

This is a pretty weird thing for you to say.

> Sometimes you may have a lot of structs in an array, and want it sorted by various keys. In this case, you would have various arrays of pointers to these structs each sorted by a different key.
>
> I don't actually care whether people have an array of pointers to structs or an array of structs.. As for myself, I almost never use arrays --- I would use LIST.4TH or ASSOCIATION.4TH generally.

OK. How would you sort a list? If you wanted to walk the keys of an
association in an ordered way, how would you do that?

One way is, generate an array of addresses into either, sort that,
and then iterate over it.

[hughag...@gmail.com]

On Saturday, June 10, 2017 at 7:19:44 PM UTC-7, Julian Fondren wrote:
> But if your defense is, "this is 'generic', I know it's slower", you
> could at least stop pretending that people are insane or filled with
> evil for wanting code that's like 7x faster.

ANS-Forth is a cult --- Elizabeth Rather claims to be the "leading expert" of Forth, which is just a gross insult to Forthers such as myself --- all of her sycophants make wild claims about how their code is "like 7x faster" than anybody else's.

Why claim that your code is only 7x faster than mine? Why not claim that it is 700x faster? Go big or go home! LOL

[Julian Fondren]

On Saturday, June 10, 2017 at 11:04:30 PM UTC-5, hughag...@gmail.com wrote:
> On Saturday, June 10, 2017 at 7:19:44 PM UTC-7, Julian Fondren wrote:
> > But if your defense is, "this is 'generic', I know it's slower", you
> > could at least stop pretending that people are insane or filled with
> > evil for wanting code that's like 7x faster.
>

> Why claim that your code is only 7x faster than mine?

Because of the benchmark above.

>Why not claim that it is 700x faster? Go big or go home! LOL

Since moving more data is slower than moving less that, a benchmark
like this is probably possible. A near 7x difference was seen with
just 10-cell structs.

[Ron Aaron]

He doesn't believe in measuring or (apparently) empirical data. Don't
waste your time

[hughag...@gmail.com]

On Saturday, June 10, 2017 at 7:19:44 PM UTC-7, Julian Fondren wrote:
> OK. How would you sort a list?

I have merge-sort now.

If you wanted to walk the keys of an
> association in an ordered way, how would you do that?

ASSOCIATION.4TH is a binary-tree, dumb-ass!

You are criticizing my ASSOCIATION.4TH without having ever looked at it, and without knowing anything about it --- I wrote this way back in 2010 --- you've had time to look at it.

> One way is, generate an array of addresses into either, sort that,
> and then iterate over it.

I had BIG-SORT in LIST.4TH that did this --- that was also written in 2010 --- I used that prior to writing merge-sort last year.

I still have LIST>ARRAY and ARRAY>LIST for converting a list into an array and back again, although they aren't really needed anymore.

The advantage of merge-sort over BIG-SORT is primarily that the comparer function is simpler because the pointers are only one level of indirection rather than two --- this isn't a big deal though --- there is actually no practical difference in speed between the insertion-sort of a list, heap-sort of an array and merge-sort of a list.

All of this talk about how your code is 7x faster than my code, is baloney. You don't actually have any code (I suppose you could trot out Wil Baden's SORT function that he wrote in the 1980s, but it is not general-purpose and it is not fast). I have multiple versions, using various algorithms, and all of them are pretty close in speed. If there was some whiz-bang algorithm that provided a 7x boost in speed, or even a 2x boost in speed, I would use it --- but there isn't --- your gigantic leaps in performance, due to your supposedly superior knowledge, are just fantasy.

[Julian Fondren]

On Saturday, June 10, 2017 at 11:30:34 PM UTC-5, hughag...@gmail.com wrote:
> If you wanted to walk the keys of an
> > association in an ordered way, how would you do that?
>
> ASSOCIATION.4TH is a binary-tree, dumb-ass!

OK, now walk over it according to an arbitrary, user-supplied order.

> You are criticizing my ASSOCIATION.4TH

Quote the criticism. What did I say about it?

> I still have LIST>ARRAY and ARRAY>LIST for converting a list into an array and back again, although they aren't really needed anymore.

Convert? As in, the array's its own independent data structure? I'm
talking about creating temporary arrays as views into other data
structures.

> All of this talk about how your code is 7x faster than my code, is baloney. You don't actually have any code

Both NEXT-PERMUTEs are in the thread. Remember when you said "this
isn't my code"? That was one of the NEXT-PERMUTEs.

You've anyway already agreed that moving more data is obviously slower
than moving less data. You just have too much of a grudge against Alex
I guess to take that thought to its conclusions.

> If there was some whiz-bang algorithm that provided a 7x boost in speed, or even a 2x boost in speed,

The whole point is that IT IS THE SAME ALGORITHM. JUST USING CELLS
INSTEAD OF LARGER SPANS OF DATA. The *same* algorithm with @/! cells
is enormously faster than the *same* algorithm MOVEing 10-cell
structs. Operating on cells is so much faster that even if your aim
was to sort structs, you could probably do that faster by sorting
cells and then rebuilding the array of structs according to the sorted
array of cells.

[Alex]

The list of things Hugh doesn't understand is very large, and as I've
said before, it includes pointers and sorting. He keeps repeating this
nonsense about sorting arrays by moving the contents. He's never going
to understand.

--
Alex

[minf...@arcor.de]

Well I try to never pronounce sentence over someone who is honestly
trying, but comes up with a not yet optimal solution.

I don't read his posts because he had been unpolite too often, not
because he hasn't got a science degree.

[Alex]

Good on you.

But I do. There's no honesty. It's Hugh's way or the highway. And this
isn't about trying; it's about...

>
> I don't read his posts because he had been unpolite too often, not
> because he hasn't got a science degree.
>

... this. He is fine as long as you don't disagree with him. Then he is,
to be frank, not someone you would ever want to be in the same room with.

I don't have a science degree either, but I read & listen to others who
have. Hugh doesn't do any of the latter, by his own admission.

The combination of the two toxic behaviours is getting him this; you
can't blame me (or others here) for Hugh's stupidity on these counts,
nor our reaction to his technically incompetent and near insane posts.

--
Alex

[rickman]

Formal education is rather overrated and this is from someone with a masters
degree, so I have some basis for knowing what I'm talking about. Even with
a masters degree I only left school with a basic education in engineering
and learned much more on the job than I came to work with.

When I started as an engineer a degree was not required, good thing as my BS
was in Biochemistry. I worked on my degree while working as an associate
engineer and when I graduated I was told there would be no raise for
obtaining the degree... so I found another job where the MS degree was
valued. The MS degree has been a profitable flag to have on my resume ever
since.

I'm not saying I didn't learn anything in graduate school, just the
opposite. I think I learned much more quickly than I would have on the job.
But for the most part I didn't gain much that I wouldn't or couldn't have
picked up in a few years of working in the field. Mostly I learned an
appreciation for doing the work in a structured manner which was only
promoted by employers some 10 or more years later.

> The combination of the two toxic behaviours is getting him this; you can't
> blame me (or others here) for Hugh's stupidity on these counts, nor our
> reaction to his technically incompetent and near insane posts.

I'm pretty over trying to have any useful communication with people like
that. There are far too many of them on the Internet and far too little
time. I want to try to spend some time on useful projects.

--

Rick C

[Alex]

On 6/11/2017 17:32, rickman wrote:

>
> Formal education is rather overrated and this is from someone with a
> masters degree, so I have some basis for knowing what I'm talking
> about. Even with a masters degree I only left school with a basic
> education in engineering and learned much more on the job than I came to
> work with.

I've been in this industry for (jeez I'm old) over 40 years. I learned
on the job, but what I learned was important; there are smarter people
out there than me, but I can be as smart as them if I listen, read and
use what they know.

>> The combination of the two toxic behaviours is getting him this; you
>> can't
>> blame me (or others here) for Hugh's stupidity on these counts, nor our
>> reaction to his technically incompetent and near insane posts.
>
> I'm pretty over trying to have any useful communication with people like
> that. There are far too many of them on the Internet and far too little
> time. I want to try to spend some time on useful projects.

The disinformation they spread is toxic. It's like green slime; it gets
everywhere. I'm afraid I sometimes can't stop myself from pointing out
how it gunges up everything, including brains.


--
Alex

[krishna...@ccreweb.org]

On Sunday, June 11, 2017 at 4:36:00 AM UTC-5, minf...@arcor.de wrote:
...

> I don't read his posts because he had been unpolite too often, not
> because he hasn't got a science degree.

Having a science degree is certainly not a basis for judging whether someone's contribution is useful or not -- what's required is a willingness to experiment, to learn from others, and to communicate in a socially acceptable way.

Krishna

[Robert L.]

On 6/10/2017, Julian Fondren wrote:

> If you wanted to walk the keys of an
> association in an ordered way, how would you do that?

That makes as much sense as saying "If you wanted to
taste a color, how would you do that?"

By definition, an associative array is unordered.

It merely associates keys with values.

--
[E]verything that happens in the world is for the benefit of the Jewish
People.... G-D ... created the world for the sake of the Jewish People, and it
is our responsibility to implement the Torah---absolute morality and the
blueprint of creation---in it.
www.IsraelNationalNews.com/Articles/Article.aspx/2125#.UUnBZxx4xn8

[Julian Fondren]

On Sunday, June 11, 2017 at 9:24:20 PM UTC-5, Robert L. wrote:
> On 6/10/2017, Julian Fondren wrote:
>
> > If you wanted to walk the keys of an
> > association in an ordered way, how would you do that?
>
> That makes as much sense as saying "If you wanted to
> taste a color, how would you do that?"
>
> By definition, an associative array is unordered.
>
> It merely associates keys with values.
>

Wow. You really do no other programming than what you post here.

[Robert L.]

On 6/9/2017, Julian Fondren wrote:

> : third 2 pick ;
>
> : permute-start ( addr u -- addr u permute-state )
> align here dup third cells dup allot erase ;
>
> : permute-free ( addr u permute-state -- )
> drop nip 1+ cells negate allot ;
>

> : switch ( a1 a2 -- )

> over @ over @ swap rot ! swap ! ;
>

> : next-permute ( addr u permute-state -- addr u permute-state f )
> over 0 do
> dup i cells + @ i < if

> i 2 mod 0= if

> third dup i cells + switch
> else

> third dup i cells + swap

> third i cells + @ cells + switch
> then
> 1 over i cells + +!
> true unloop exit
> then
> 0 over i cells + ! loop false ( no more permutations ) ;

>
> create blah 1 , 2 , 3 , 4 , 5 ,
> : show ( -- ) blah 5 cells bounds cr do i ? 1 cells +loop ;
> : show-blahs ( -- )

> blah 5 permute-start
> begin show next-permute 0= until permute-free ;

OCaml:

let printv vec =
Array.iter (fun n -> print_int n; print_string " ") vec;
print_newline ();;

let swap i j v =
let tmp = v.(i) in v.(i) <- v.(j) ; v.(j) <- tmp ;;

let rec gen_perm n func vec =
if 1 = n then
func vec
else
( for i = 0 to (n - 2) do
gen_perm (n-1) func vec ;
swap (if (0 = (1 land n)) then i else 0) (n-1) vec ;
done ;
gen_perm (n-1) func vec );;

let perm_iter func vec = gen_perm (Array.length vec) func vec ;;

perm_iter printv [|2;3;4|];;

===>
2 3 4
3 2 4
4 2 3
2 4 3
3 4 2
4 3 2


let t = Sys.time () in
perm_iter ignore [|2;3;4;5;6;7;8;9;10|];
Sys.time() -. t ;;

===>
float = 0.125


3.475 /. 0.125 ;;

===>
float = 27.8

It's over 27 times as fast as your unposted Forth code!
On an old winXP laptop!


--
Jews totally run Hollywood.... But I don't care if Americans think we're
running the news media, Hollywood, Wall Street, or the government. I just care
that we get to keep running them. --- Joel Stein
articles.latimes.com/2008/dec/19/opinion/oe-stein19
archive.org/download/DavidDukeTv/DoJewsControlTheMediaTheLaTimesSaysYes.flv

[Robert L.]

Racket:

(define (swap i j v)
(let ((tmp (vector-ref v i)))
(vector-set! v i (vector-ref v j))
(vector-set! v j tmp)))

(define (gen-perm n func vector)
(cond ((= 1 n) (func vector))
(else
(for ((i (- n 1)))
(gen-perm (- n 1) func vector)
(swap (if (even? n) i 0) (- n 1) vector))
(gen-perm (- n 1) func vector))))

(define (for-each-perm func vector)
(gen-perm (vector-length vector) func vector))


> (for-each-perm displayln (vector 2 3 4))
#(2 3 4)
#(3 2 4)
#(4 2 3)
#(2 4 3)
#(3 4 2)
#(4 3 2)

> (time (for-each-perm (lambda(_) #f) (vector 2 3 4 5 6 7 8 9 10)))
cpu time: 109 real time: 109 gc time: 0

That's 109 milliseconds.

--
[A]n unholy alliance of leftists, capitalists, and Zionist supremacists has
schemed to promote immigration and miscegenation with the deliberate aim of
breeding us out of existence in our own homelands.... [T]he real aim stays the
same: the biggest genocide in human history.... --- Nick Griffin
(https://www.youtube.com/watch?v=K0hD7IffTJs)

[Melzzzzz]

He haven't used languages where `associative array` is called `map`,
represented by tree ;)


--
press any key to continue or any other to quit...

[Robert L.]

Using operators that handle only fixnums:


(require racket/unsafe/ops)

(define (gen-perm n func vector)

(cond ((unsafe-fx= 1 n) (func vector))
(else
(for ((i (unsafe-fx- n 1)))
(gen-perm (unsafe-fx- n 1) func vector)
(swap (if (even? n) i 0) (unsafe-fx- n 1) vector))
(gen-perm (unsafe-fx- n 1) func vector))))

> (time (for-each-perm (lambda(_) #f) (vector 2 3 4 5 6 7 8 9 10)))

cpu time: 78 real time: 78 gc time: 0

--
In Jerusalem, the United Nations (a truly United Nations) will build a Shrine
of the Prophets to serve the federated union of all continents; this will be
the seat of the Supreme Court of Mankind to settle all controversies among the
federated continents, as prophesied by Isaiah.
--- David Ben Gurion (Look, 16 January 1962)

[Julian Fondren]

On Sunday, June 11, 2017 at 10:32:37 PM UTC-5, Robert L. wrote:
> let t = Sys.time () in
> perm_iter ignore [|2;3;4;5;6;7;8;9;10|];
> Sys.time() -. t ;;
>
> ===>
> float = 0.125
>
>
> 3.475 /. 0.125 ;;
>
> ===>
> float = 27.8
>
> It's over 27 times as fast as your unposted Forth code!
> On an old winXP laptop!
>

And that doesn't fill you with any doubt?

When the point is only to compare cell vs. struct permutations, how
many permutations do you think my benchmark had? Obviously it had as
many as needed to make for good numbers. Lots of benchmarks would
conclude that "0 is as good as 0" otherwise.

On my machine:

# let t = Sys.time () in

perm_iter ignore [|2;3;4;5;6;7;8;9;10|];
Sys.time() -. t ;;

- : float = 0.0672789999999999916

vs.

: cell-bench ( n -- )
cr ." cells: " timer-reset 0 do
cell-array 10 permute-start begin next-permute 0= until permute-free
loop .elapsed ;

FORTH> 1 cell-bench
cells: 0.073 seconds elapsed. ok

And then there's this:

: 1bench ( -- )
cr ." cells: " cell-array 10 permute-start timer-reset
begin next-permute 0= until
.elapsed permute-free ;
: magic ( -- ) 100 0 do 1bench loop ;

FORTH> magic
cells: 0.078 seconds elapsed.
cells: 0.034 seconds elapsed.
cells: 0.033 seconds elapsed.
cells: 0.033 seconds elapsed.
cells: 0.033 seconds elapsed.
cells: 0.033 seconds elapsed.

Similar O'Caml settles at 26ms.

[Julian Fondren]

On Sunday, June 11, 2017 at 11:14:34 PM UTC-5, Julian Fondren wrote:
> On Sunday, June 11, 2017 at 10:32:37 PM UTC-5, Robert L. wrote:
> > let t = Sys.time () in
> > perm_iter ignore [|2;3;4;5;6;7;8;9;10|];
> > Sys.time() -. t ;;

Oh I didn't notice that this was only a 9-element array.

# let t = Sys.time () in for i = 1 to 100 do perm_iter ignore [|2;3;4;5;6;7;8;9;10;11|]; done; Printf.printf "omg: %f\n" (Sys.time() -. t);;
omg: 26.502621

FORTH> 100 cell-bench
cells: 3.217 seconds elapsed. ok

So that's a 8x difference in speed in Forth's favor.

[Melzzzzz]

[bmaxa@maxa-pc haskell]$ /home/bmaxa/ghc/bin/ghc -O2 permute.hs
[1 of 1] Compiling Main ( permute.hs, permute.o )
Linking permute ...
[bmaxa@maxa-pc haskell]$ time ./permute
[11,10,9,8,7,6,5,4,3,2]
720

real 0m0.722s
user 0m0.715s
sys 0m0.007s
[bmaxa@maxa-pc haskell]$ cat permute.hs
import Data.List
import System.Time

selections [] = []
selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]
permutations :: [a] -> [[a]]
permutations (x:[]) = [[x]]
permutations xs =
[ y : zs
| (y,ys) <- selections xs
, zs <- Main.permutations ys
]
main = do
(TOD sec pico) <- getClockTime
print $ last $ Main.permutations [2..11]
(TOD sec' pico') <-getClockTime
let diff = (pico' `quot` 10^9 + sec'*1000) - (pico `quot` 10^9 + sec*1000)
print diff

Heh, Haskell is winner ;)

[Julian Fondren]

Are you aware that you're comparing a single run through the
permutations of a 10-element array with a hundred runs through those
permutations?

[Melzzzzz]

Haskell is lazy language computations are performed on demand and in
this case 100 runs would make no difference as computation is peformed
only once ;)
Yeah, that would be about 100*700msecs.

[Robert L.]

Chicken Scheme, permuting a larger vector.


;; Compile with
;; csc -O5 try.scm

(define (swap i j v)
(let ((tmp (vector-ref v i)))
(vector-set! v i (vector-ref v j))
(vector-set! v j tmp)))

(define (gen-perm n func vector)

(cond ((fx= 1 n) (func vector))
(else
(do ((i 0 (fx+ 1 i)))
((fx> i (fx- n 2)))
(gen-perm (fx- n 1) func vector)
(swap (if (fxodd? n) 0 i) (fx- n 1) vector))
(gen-perm (fx- n 1) func vector))))


(define (vector-each-perm func vector)

(gen-perm (vector-length vector) func vector))

(vector-each-perm print (vector 2 3 4))

(time (vector-each-perm (lambda(_) #f) #(1 2 3 4 5 6 7 8 9 10)))

=== output: ===

#(2 3 4)
#(3 2 4)
#(4 2 3)
#(2 4 3)
#(3 4 2)
#(4 3 2)

0.547s CPU time, 0.187s GC time (major)

--
It is extremely gratifying to ... achieve membership in an elite that is going
to make history.... The only drawback is that the self-appointed shepherds are
likely to find eventually that they were only sheepdogs and herded the flock
toward a destination of which they knew nothing. --- R. P. Oliver

[hughag...@gmail.com]

You're Marcel Hendrix, aren't you?

This was my first-ever contact with Marcel Hendrix:
https://groups.google.com/forum/#!topic/comp.lang.forth/wP5nw1ClzsM%5B1-25%5D

You seem to be concealing your name now --- you have a different username that doesn't include your real name.

[hughag...@gmail.com]

On Sunday, June 11, 2017 at 9:32:17 AM UTC-7, rickman wrote:
> Alex wrote on 6/11/2017 5:45 AM:

> > ...you can't

> > blame me (or others here) for Hugh's stupidity on these counts, nor our
> > reaction to his technically incompetent and near insane posts.
>
> I'm pretty over trying to have any useful communication with people like
> that. There are far too many of them on the Internet and far too little
> time. I want to try to spend some time on useful projects.

Alex McDonald and Julien Fondren are obviously attacking me for the purpose of impressing Elizabeth Rather with their loyalty, in the hope that she will appoint them to the Forth-200x committee.

I don't think this is going to work. She already has the Forth-200x committee packed with sycophants. What would be the point of adding two more sycophants --- she already controls every vote on the committee.

Rickman has never done any programming in Forth --- he can't get appointed to the Forth-200x committee because he doesn't understand even the most basic aspects of Forth --- he is just attacking me because he enjoys it. He says:

On Monday, May 13, 2013 at 8:07:20 PM UTC-7, rickman wrote:
> He doesn't bother me so much as others. But I realize I have been
> feeding him again. It's just that he's so *cute* when you give him a
> cookie and he does the little dance.

Does this post of mine count as a "little dance" in Rickman's world? Maybe so --- he is hoping for an emotional response, and this post was wasn't --- he is presumably happy with any kind of response though...

[rickman]

But in doing so, you also spread some of the green slime as well. I
recently saw a photo of a Roomba that encountered a fresh dog pile and
spread it around the room rather than picking it up.

Some things are best left untouched.

--

Rick C

[Gerry Jackson]

On 09/06/2017 07:21, Julian Fondren wrote:
> Hello clf,
>
> The following thread on reddit /r/Forth may interest you. The poster
> has some difficulty with showing permutations in Forth, but powers
> through it, and then asks for feedback on his code. There's another
> implementation of the task among the replies.
>
> https://www.reddit.com/r/Forth/comments/6fzpkd/applying_forths_principles_in_practice/
>
> Here's mine:

> ALLOCATE and FREE variants of PERMUTE-START and PERMUTE-FREE could
> easily be supplied; NEXT-PERMUTE won't care either way. I don't really
> like all the repetitions of I CELLS + and at a glance the inner stack
> manipulation could probably be simplified by swapping ( addr u ) ahead
> of time. Another option: assume the caller has his own convenient
> access to the array -- as is actually the case above with BLAH -- and
> include ADDR U in the temporary array.
>
> This is an implementation of the non-recursive version of Heap's
> algorithm, which is written as a self-contained function with an
> output(A) to supply the permutations. By taking an xt you could write
> a Forth word that more closely mirrors the pseudocode, but I like
> NEXT-PERMUTE as its own factor, since that lets you be a little bit
> more clever with the temporary array.
>
> Another place to hold the 'temporary array' is in the actual array
> that you're generating permutations for, if you've bits to spare. You
> need at least enough to represent the length of the array. I can't
> think of use for that though... maybe if there's a lot of permutation
> done with DNA strings?
>
> (Unrelatedly, I have now a 159-line definition in Forth. I may post
> about it later. After slaying the beast, of course.)
>

I implemented Heap's algorithm last December to solve a logic puzzle. I
used the recursive solution from Wikipedia :
https://en.wikipedia.org/wiki/Heap%27s_algorithm

: permute ( n -- ) \ n assumed > 0
1- ?dup 0= if use-perm exit then
dup 0
do
dup recurse
dup over 1 and negate i and exchange
loop
recurse
;

where:
EXCHANGE ( i1 i2 -- ) is fed the two indices of the elements to exchange
in a global array and USE-PERM ( -- ) does just that. The array is
preloaded with the items to permute.

The bit after the first recurse avoids an IF and calling EXCHANGE in 2
places.

That was fine for the problem I had but I thought I would generalise it
for use as a library function, passing in XTs for the two user
operations, EXCHANGE and USE-PERM. With two xt's the stack juggling
without locals was horrible so with locals it becomes:

: permute ( n xt1 xt2 -- ) \ xt1 is exchange, xt2 is use-permutation
{: xchg-xt use-xt :}
1- ?dup 0= if use-xt execute exit then
dup 0
do
dup xchg-xt use-xt recurse
dup dup 1 and negate
i and xchg-xt execute
loop
xchg-xt use-xt recurse
;

Alternatively if the user functions are methods XCHG and USE-PERM in,
say, a mini-oof object called ops, a version not using locals is

: permute ( n ops -- ops )
swap 1- ?dup 0= if dup use-perm exit then
tuck 0
do ( -- n' ops )
over swap recurse ( -- n' ops )
over dup 1 and negate ( -- n' ops n' 0|-1 )
i and 2 pick xchg ( -- n' ops )
loop
recurse
;


--
Gerry

[hughag...@gmail.com]

On Saturday, June 10, 2017 at 7:19:44 PM UTC-7, Julian Fondren wrote:
> But if your defense is, "this is 'generic', I know it's slower", you
> could at least stop pretending that people are insane or filled with
> evil for wanting code that's like 7x faster.

My array sort is getting attacked pretty hard! Why the array sort, rather than some other aspect of the novice-package? The array sort is very basic code, so it seems an unlikely target for attack.

I think the reason why it is targeted in particular is because EXCHANGE shows up the weakness of SwiftForth.

Here is the EXCHANGE code:
-----------------------------------------------------------------------
SwiftForth? [if] \ SwiftForth's optimization is so bad that no Forth version is any good

icode exchange ( adrX adrY size -- ) \ the size of the record must be a multiple of W
0 [ebp] edx mov w [ebp] ecx mov \ EDX<>ECX, with EBX being the size
begin non-zero? while
0 [ecx] eax mov
0 [edx] eax xor eax 0 [edx] xor 0 [edx] eax xor
eax 0 [ecx] mov
w # edx add w # ecx add
w # ebx sub repeat
w 2 * [ebp] ebx mov
w 3 * # ebp add ret end-code

[else]

macro: exchange ( adrX adrY size -- ) \ the size of the record must be a multiple of W
begin dup while \ -- adrX adrY remaining
-rot \ -- remaining adrX adrY
dup @ rover @ \ -- remaining adrX adrY Y X
rover ! rover ! \ -- remaining adrX adrY
w + swap w + rot w - \ -- adrY adrX remaining \ adrY and adrX change places
repeat
3drop ;

[then]
-----------------------------------------------------------------------

Is SwiftForth's optimization bad?

Well, here is EXCHANGE in VFX:

: test exchange ; ok
see test
TEST
( 004E0A20 85DB ) TEST EBX, EBX
( 004E0A22 0F8425000000 ) JZ/E 004E0A4D
( 004E0A28 8B5500 ) MOV EDX, [EBP]
( 004E0A2B 8B0A ) MOV ECX, 0 [EDX]
( 004E0A2D 8B4504 ) MOV EAX, [EBP+04]
( 004E0A30 8B00 ) MOV EAX, 0 [EAX]
( 004E0A32 8902 ) MOV 0 [EDX], EAX
( 004E0A34 8B4504 ) MOV EAX, [EBP+04]
( 004E0A37 8908 ) MOV 0 [EAX], ECX
( 004E0A39 83C204 ) ADD EDX, 04
( 004E0A3C 8B4D04 ) MOV ECX, [EBP+04]
( 004E0A3F 83C104 ) ADD ECX, 04
( 004E0A42 83C3FC ) ADD EBX, -04
( 004E0A45 894D00 ) MOV [EBP], ECX
( 004E0A48 895504 ) MOV [EBP+04], EDX
( 004E0A4B EBD3 ) JMP 004E0A20 TEST
( 004E0A4D 8B5D08 ) MOV EBX, [EBP+08]
( 004E0A50 8D6D0C ) LEA EBP, [EBP+0C]
( 004E0A53 C3 ) NEXT,
( 52 bytes, 19 instructions )
ok

Here is EXCHANGE in SwiftForth (name changed to FORTH-EXCHANGE to distinguish it from my ICODE version):

see forth-exchange
4908CF EBX EBX OR 09DB
4908D1 490944 JZ 0F846D000000
4908D7 EBX ECX MOV 8BCB
4908D9 4 [EBP] EAX MOV 8B4504
4908DC 0 [EBP] EBX MOV 8B5D00
4908DF EAX 0 [EBP] MOV 894500
4908E2 ECX 4 [EBP] MOV 894D04
4908E5 4 # EBP SUB 83ED04
4908E8 EBX 0 [EBP] MOV 895D00
4908EB 0 [EBX] EBX MOV 8B1B
4908ED 4 # EBP SUB 83ED04
4908F0 EBX 0 [EBP] MOV 895D00
4908F3 8 [EBP] EBX MOV 8B5D08
4908F6 0 [EBX] EBX MOV 8B1B
4908F8 4 # EBP SUB 83ED04
4908FB EBX 0 [EBP] MOV 895D00
4908FE 8 [EBP] EBX MOV 8B5D08
490901 0 [EBP] EAX MOV 8B4500
490904 EAX 0 [EBX] MOV 8903
490906 4 [EBP] EBX MOV 8B5D04
490909 8 # EBP ADD 83C508
49090C 4 # EBP SUB 83ED04
49090F EBX 0 [EBP] MOV 895D00
490912 8 [EBP] EBX MOV 8B5D08
490915 0 [EBP] EAX MOV 8B4500
490918 EAX 0 [EBX] MOV 8903
49091A 4 [EBP] EBX MOV 8B5D04
49091D 8 # EBP ADD 83C508
490920 4 # EBX ADD 83C304
490923 0 [EBP] EAX MOV 8B4500
490926 EBX 0 [EBP] MOV 895D00
490929 EAX EBX MOV 8BD8
49092B 4 # EBX ADD 83C304
49092E EBX ECX MOV 8BCB
490930 4 [EBP] EBX MOV 8B5D04
490933 0 [EBP] EAX MOV 8B4500
490936 EAX 4 [EBP] MOV 894504
490939 ECX 0 [EBP] MOV 894D00
49093C 4 # EBX SUB 83EB04
49093F 4908CF JMP E98BFFFFFF
490944 48369F ( 3drop ) JMP E9562DFFFF ok

SwiftForth optimization is pretty bad! This is why I have so much SwiftForth-specific assembly-language in the novice-package. This is my hand-written version:

see exchange
48689F 0 [EBP] EDX MOV 8B5500
4868A2 4 [EBP] ECX MOV 8B4D04
4868A5 EBX EBX OR 09DB
4868A7 4868BE JZ 7415
4868A9 0 [ECX] EAX MOV 8B01
4868AB 0 [EDX] EAX XOR 3302
4868AD EAX 0 [EDX] XOR 3102
4868AF 0 [EDX] EAX XOR 3302
4868B1 EAX 0 [ECX] MOV 8901
4868B3 4 # EDX ADD 83C204
4868B6 4 # ECX ADD 83C104
4868B9 4 # EBX SUB 83EB04
4868BC 4868A5 JMP EBE7
4868BE 8 [EBP] EBX MOV 8B5D08
4868C1 C # EBP ADD 83C50C
4868C4 RET C3 ok

EXCHANGE shines a spotlight on the poor code quality of SwiftForth. This is why Elizabeth Rather's sycophants say that I know my code is 7x slower than their code. They want to ban EXCHANGE so nobody sees what a bad job SwiftForth does of compiling it. They want me to stop writing Forth code --- it is Elizabeth Rather's way or the highway!

[Ron Aaron]

On 06/15/17 08:15, hughag...@gmail.com wrote:
> On Saturday, June 10, 2017 at 7:19:44 PM UTC-7, Julian Fondren wrote:
>> But if your defense is, "this is 'generic', I know it's slower", you
>> could at least stop pretending that people are insane or filled with
>> evil for wanting code that's like 7x faster.
>
> My array sort is getting attacked pretty hard! Why the array sort, rather than some other aspect of the novice-package? The array sort is very basic code, so it seems an unlikely target for attack.
>
> I think the reason why it is targeted in particular is because EXCHANGE shows up the weakness of SwiftForth.

I doubt anyone gives two shits about the purported performance problems
of an ancient version of SwiftForth's "EXCHANGE" word.

The reason your code gets "attacked" is that you persist in ignoring
empirically sound advice. Specifically, that moving pointers is *much*
faster than moving around data (if the data size is bigger than the
pointer size, obviously). Even assuming, arguendo, that EXCHANGE is
slow as molasses.

It's not just the posters here who've responded to you who say this.

It's easy enough to find this information in any online discussion of
sorting. Literally hundreds of such discussions.

It's easy enough to SIMPLY MEASURE THE PERFORMANCE and convince yourself
that yes, perhaps there is a point here. But you don't believe in
measuring things, you believe that assertions of fact make the "facts"
miraculously true.

So paranoia aside (and you really do need some meds or psych advice, but
I've said that before) --- nobody is attacking *you* over the code you
posted. They're criticising a bad implementation. If anyone else had
posted it, they too would have been criticised.

It matters, if you want to write good code. You need to be able to
accept criticism of your code, and decide rationally whether the
critiques are valid or not, and whether or not it makes sense for you to
modify your code.

Sometimes, "good enough" really is. But sometimes, it's just pushing
the pain point a few days/months/years down the road. When you write
customer-facing code (as I do) then it can make a huge difference as to
whether you get hired again.

Get help, or at least just shut up about your inane conspiracies.

[Alex]

On 6/15/2017 06:29, Ron Aaron wrote:
>
>
> On 06/15/17 08:15, hughag...@gmail.com wrote:
>> On Saturday, June 10, 2017 at 7:19:44 PM UTC-7, Julian Fondren
>> wrote:
>>> But if your defense is, "this is 'generic', I know it's slower",
>>> you could at least stop pretending that people are insane or
>>> filled with evil for wanting code that's like 7x faster.
>>
>> My array sort is getting attacked pretty hard! Why the array sort,
>> rather than some other aspect of the novice-package? The array
>> sort is very basic code, so it seems an unlikely target for
>> attack.
>>
>> I think the reason why it is targeted in particular is because
>> EXCHANGE shows up the weakness of SwiftForth.
>
> I doubt anyone gives two shits about the purported performance
> problems of an ancient version of SwiftForth's "EXCHANGE" word.
>
> The reason your code gets "attacked" is that you persist in ignoring
> empirically sound advice. Specifically, that moving pointers is
> *much* faster than moving around data (if the data size is bigger
> than the pointer size, obviously). Even assuming, arguendo, that
> EXCHANGE is slow as molasses.

Just as one of those data points, here's a table from this website
https://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html. It documents
for three well known sorts the average number of compares and the number
of exchanges.

n Quick Heap Insert
comp exch comp exch comp exch
100 712 148 2,842 581 2,595 899
200 1,682 328 9,736 1,366 10,307 3,503
500 5,102 919 53,113 4,042 62,746 21,083

Is exchanging two records going to have a significant impact? Would
exchanging two pointers be cheaper? Especially when doing it in a loop
one cell at a time? The data here suggests that it's a yes; it does.

(Apart from which, doing it with pointers allows the data to be
scattered rather than all arranged in rectangular arrays; variable
length records, data in other structures like trees where swapping it
destroys the structure etc. I don't get this particular obsession with
arrays. What is also striking is the average number of compares.
Optimizing that will also pay benefits; even with quicksort it's around
5 times as many compares as exchanges.)

--
Alex

[Alexander Wegel]

<hughag...@gmail.com> wrote:

> On Saturday, June 10, 2017 at 7:19:44 PM UTC-7, Julian Fondren wrote:
> > But if your defense is, "this is 'generic', I know it's slower", you
> > could at least stop pretending that people are insane or filled with
> > evil for wanting code that's like 7x faster.
>
> My array sort is getting attacked pretty hard! Why the array sort,
> rather than some other aspect of the novice-package? The array sort
> is very basic code, so it seems an unlikely target for attack.

It's because of that:
It's very basic code, and you managed to screw it up.

Let me show you:

> Here is the EXCHANGE code:
> -----------------------------------------------------------------------
> SwiftForth? [if] \ SwiftForth's optimization is so bad that no
> Forth version is any good

Let's ignore the dumb rant for now..

>
> icode exchange ( adrX adrY size -- ) \ the size of the record must be a
> multiple of W
> 0 [ebp] edx mov w [ebp] ecx mov \ EDX<>ECX, with EBX being the size
> begin non-zero? while
> 0 [ecx] eax mov
> 0 [edx] eax xor eax 0 [edx] xor 0 [edx] eax xor
> eax 0 [ecx] mov
> w # edx add w # ecx add
> w # ebx sub repeat
> w 2 * [ebp] ebx mov
> w 3 * # ebp add ret end-code
>
> [else]
>
> macro: exchange ( adrX adrY size -- ) \ the size of the record must
> be a multiple of W
> begin dup while \ -- adrX adrY remaining
> -rot \ -- remaining adrX adrY
> dup @ rover @ \ -- remaining adrX adrY Y X
> rover ! rover ! \ -- remaining adrX adrY
> w + swap w + rot w - \ -- adrY adrX remaining
> \ adrY and adrX change places
> repeat
> 3drop ;
>
> [then]

Considering that the record size is known to the sort function that is
using your exchange, there's no real need to pass it around for every
call to exchange.

More significantly, if your records are small (one or a few cells),
including a loop in exchange is overkill, messes up the stack, and makes
exchange significantly slower than it has to be on *any* system.
(Additionally, the "w + swap w +" part gets executed once too often at
any record size!)

Trying to optimize this code by inlining it is just ridiculous - just
the kind of marketing lie that you habitually accuse others of.

You accused me of "screwing up" by using an IF for a conditional when it
wasn't even about optimization, so by comparison you *royally* screwed
up, and you don't even seem to have a clue.

Alex W.

[Ron Aaron]

On 15/06/2017 14:24, Alex wrote:

> Just as one of those data points, here's a table ...

You don't understand, Alex! T

The method Hugh's madness takes is to reinvent everything from scratch.
Because... of the wonderful wiz he was, or something.

Empirical data, reasoned arguments, testing in the real world, seeking
advice of those who've been in the field... nah.

Gotta invent that wheel myself! And if you don't like my icosagon
wheel, it's because you're an idiot who can't understand how much
superior it is to the ridiculous circular and inefficient one you prefer
for some reason.

[hughag...@gmail.com]

For a general-purpose array sort, I think it is a bad idea to pass in an xt for the exchange function. You are going to end up functions like these:
EXCHANGE-ONE-CELL
EXCHANGE-TWO-CELLS
EXCHANGE-THREE-CELLS
EXCHANGE-FOUR-CELLS
...
Then you will pass in the xt of one of these exchange functions.

Lets say that you have an array of structs of type MY-EFFING-STRUCT --- how do you know which exchange function to use? Well, you could write a note down on a yellow sticky note that you attach to your monitor:
"For MY-EFFING-STRUCT use EXCHANGE-FOUR-CELLS."

But wait! What if a design change in the cause the size of MY-EFFING-STRUCT to change from 4 to 3 cells? No problem! This is why pencils have an erasure. You just change the note on your yellow sticky note.

But wait! What if you can't remember where in your program you did a sort of this array. No problem! This is why the 5-hour-energy drinks were invented. You just laboriously search through your program line by line looking for a sort of this array.

But wait! What if you don't know at compile-time what type of struct is in your array? You know that your array either holds MY-EFFING-STRUCT structs, or holds structs of a child type. Your compare function is good, because it works on MY-EFFING-STRUCT and hence will work on any child class. But your exchange functions is not good because it won't work on structs of a child class due to the fact that they are bigger than their parent class. No problem! You convince the Forth-200x committee to ban my ALLOCATION function from the Forth standard, so there is no easy way to determine the size of a struct at run-time.

Yes, it looks like Gerry has a solution to every possible problem!

BTW: Recursion is a terrible idea. You have a lot of parameters (especially because you have a compare-function xt). You want to put these parameters in local variables rather than do a lot of stack-juggling. With an iterative sort function, this is done once, and the locals remain valid throughout. With a recursive sort function, this has to be redone at every level. This is why my SORT is iterative rather than recursive!

But don't worry! So long as you accept Elizabeth Rather as your "leading expert," all of the ANS-Forth sycophants will hail you as a great ANS-Forth programmer --- they will say that your code is 7x better than mine!

[hughag...@gmail.com]

On Wednesday, June 14, 2017 at 10:30:12 PM UTC-7, Ron Aaron wrote:
> The reason your code gets "attacked" is that you persist in ignoring
> empirically sound advice. Specifically, that moving pointers is *much*
> faster than moving around data (if the data size is bigger than the
> pointer size, obviously).

All of this is a straw-man argument. I'm not preventing anybody from having an array of pointers to structs --- my SORT works fine for that --- it also works fine for an array of structs.

The novice-package is general-purpose code --- it is supposed to support any reasonable usage --- an array of structs is going to be reasonable in some programs.

[Alex]

On 6/16/2017 09:16, hughag...@gmail.com wrote:
> Yes, it looks like Gerry has a solution to every possible problem!

> But don't worry! So long as you accept Elizabeth Rather as your
> "leading expert," all of the ANS-Forth sycophants will hail you as a
> great ANS-Forth programmer --- they will say that your code is 7x
> better than mine!

That's Gerry off the Christmas card list.

--
Alex

[hughag...@gmail.com]

On Thursday, June 15, 2017 at 5:09:01 AM UTC-7, Alexander Wegel wrote:
> Considering that the record size is known to the sort function that is
> using your exchange, there's no real need to pass it around for every
> call to exchange.

Alex Wegel knows little or nothing about OOP --- the record size is not necessarily known at compile-time.

> More significantly, if your records are small (one or a few cells),
> including a loop in exchange is overkill, messes up the stack, and makes
> exchange significantly slower than it has to be on *any* system.
> (Additionally, the "w + swap w +" part gets executed once too often at
> any record size!)

Alex Wegel knows little or nothing about VFX compilation.

Here is a new Forth version that is slightly faster than my previous version --- it is still not as fast as my assembly-language version --- note that I did not follow Alex Wegel's advice:

macro: exchange ( adrX adrY size -- ) \ the size of the record must be a non-zero multiple of W
begin

-rot \ -- remaining adrX adrY
dup @ rover @ \ -- remaining adrX adrY Y X
rover ! rover ! \ -- remaining adrX adrY

w + swap w + rot W - \ -- adrY adrX remaining \ adrY and adrX change places
dup 0= until
3drop ;

> Trying to optimize this code by inlining it is just ridiculous - just
> the kind of marketing lie that you habitually accuse others of.

So, every time that I use my early-binding MACRO: this is a "marketing lie" --- but you didn't like my late-binding MACRO: either --- you don't like any code that I write!

https://groups.google.com/forum/#!topic/comp.lang.forth/92KNs8p4J6Y%5B1-25%5D

Alex Wegel only likes Forth Inc. --- he is a brown-noser --- there is no code that I could ever write that he would say anything positive about.

[Gerry Jackson]

Why do you persist in bringing an array sort into this discussion?
Heap's algorithm is nothing to do with sorting - look it up. But Heap's
algorithm does exchange items so I'll excuse your confusion.

> I think it is a bad idea to pass in an xt for the exchange function. You are going to end up functions like these:
> EXCHANGE-ONE-CELL
> EXCHANGE-TWO-CELLS
> EXCHANGE-THREE-CELLS
> EXCHANGE-FOUR-CELLS
> ...
> Then you will pass in the xt of one of these exchange functions.
>
> Lets say that you have an array of structs of type MY-EFFING-STRUCT --- how do you know which exchange function to use? Well, you could write a note down on a yellow sticky note that you attach to your monitor:
> "For MY-EFFING-STRUCT use EXCHANGE-FOUR-CELLS."
>
> But wait! What if a design change in the cause the size of MY-EFFING-STRUCT to change from 4 to 3 cells? No problem! This is why pencils have an erasure. You just change the note on your yellow sticky note.

I'm glad you told me that. Up to now I've been tattooing that sort of
information on the back of my hand and am running out of space. Yours is
a much superior technique, can I use blue sticky notes instead as I only
have those.

>
> But wait! What if you can't remember where in your program you did a sort of this array. No problem! This is why the 5-hour-energy drinks were invented. You just laboriously search through your program line by line looking for a sort of this array.

Nah, I look for the name on the back of my hand and use a text editor to
search a file for it. Mind you the back of my hand needs reorganising as
it can take significant time to locate a name.

>
> But wait! What if you don't know at compile-time what type of struct is in your array? You know that your array either holds MY-EFFING-STRUCT structs, or holds structs of a child type. Your compare function is good,

Er, what compare function? (I'm being serious here in case you can't tell)

because it works on MY-EFFING-STRUCT and hence will work on any child
class. But your exchange functions is not good because it won't work on
structs of a child class due to the fact that they are bigger than their
parent class. No problem! You convince the Forth-200x committee to ban
my ALLOCATION function from the Forth standard, so there is no easy way
to determine the size of a struct at run-time.
>
> Yes, it looks like Gerry has a solution to every possible problem!

Wow, does that mean I can oust Elizabeth Rather as the leading expert on
Forth - I'd aiming to take her job of appointing people to the Forth
200X committee.

>
> BTW: Recursion is a terrible idea.

(Serious mode on) Well it solved my problem in a flash, please tell me
how solving it in half a flash or using fewer bytes of the Gbytes
available would have improved my life.

You have a lot of parameters (especially because you have a
compare-function xt).

No I don't have a compare function xt, I'm not comparing anything just
testing something for zero.

> You want to put these parameters in local variables rather than do a lot of stack-juggling.

I did use locals for that very reason in one alternative - I'm getting
the impression that you haven't looked at my code beyond the word RECURSE

> With an iterative sort function, this is done once, and the locals remain valid throughout. With a recursive sort function, this has to be redone at every level. This is why my SORT is iterative rather than recursive!
>
> But don't worry! So long as you accept Elizabeth Rather as your "leading expert," all of the ANS-Forth sycophants will hail you as a great ANS-Forth programmer --- they will say that your code is 7x better than mine!
>

(Serious mode off) Only 7 times I'll have to do better - have you
benchmarked it?

--
Gerry

[Gerry Jackson]

Bugger, I'm mortified.

--
Gerry

[Alexander Wegel]

<hughag...@gmail.com> wrote:

> On Thursday, June 15, 2017 at 5:09:01 AM UTC-7, Alexander Wegel wrote:
> > Considering that the record size is known to the sort function that is
> > using your exchange, there's no real need to pass it around for every
> > call to exchange.
>
> Alex Wegel knows little or nothing about OOP
> --- the record size is not necessarily known at compile-time.

Hint: nobody wrote anything about compile-time.

> > More significantly, if your records are small (one or a few cells),
> > including a loop in exchange is overkill, messes up the stack, and makes
> > exchange significantly slower than it has to be on *any* system.
> > (Additionally, the "w + swap w +" part gets executed once too often at
> > any record size!)
>
> Alex Wegel knows little or nothing about VFX compilation.

Well, enough to verify that a non-looping version can be much faster for
small record sizes (2.5 times faster for single-cell records), and to
verify that making exchange a macro does NOT have any significant impact
on speed.

> Here is a new Forth version that is slightly faster than my previous version
> --- it is still not as fast as my assembly-language version --- note that I
> did not follow Alex Wegel's advice:

I tried to give you an advice? I'm troubled.
Anyway - the code looks, works and performs just like the old one -
nothing new here.

> macro: exchange ( adrX adrY size -- ) \ the size of the record must
> be a non-zero multiple of W
> begin
> -rot \ -- remaining adrX adrY
> dup @ rover @ \ -- remaining adrX adrY Y X
> rover ! rover ! \ -- remaining adrX adrY
> w + swap w + rot W - \ -- adrY adrX remaining
> \ adrY and adrX change places
> dup 0= until
> 3drop ;
>
> > Trying to optimize this code by inlining it is just ridiculous - just
> > the kind of marketing lie that you habitually accuse others of.

Guess what: Using MACRO: doesn't make a difference with this new version
too (it just bloats everything).

> So, every time that I use my early-binding MACRO: this is a "marketing lie"

No, probably not every time.

> --- but you didn't like my late-binding MACRO: either

I didn't like the way you used it.

> --- you don't like any code that I write!

Is this some kind of conclusion, or a cry for love?

> https://groups.google.com/forum/#!topic/comp.lang.forth/92KNs8p4J6Y%5B1-25%5D

From that thread i love this excerpt (posted on 2016/12/27):

>> ... the novice-package (to be released in a few days).

Still waiting (years and fortnights pass by..).

> Alex Wegel only likes Forth Inc. --- he is a brown-noser

You're fantasizing.

> --- there is no code that I could ever write that he would say anything
> positive about.

I'm afraid you're gonna explode if i do.

[hughag...@gmail.com]

On Friday, June 16, 2017 at 12:14:45 PM UTC-7, Gerry wrote:
> On 16/06/2017 09:16, hughag...@gmail.com wrote:
> > For a general-purpose array sort,
>
> Why do you persist in bringing an array sort into this discussion?
> Heap's algorithm is nothing to do with sorting - look it up. But Heap's
> algorithm does exchange items so I'll excuse your confusion.

I had assumed that we were talking about a Heap Sort function.