Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #53087
| Newsgroups | comp.lang.forth |
|---|---|
| Date | 2016-12-05 09:11 -0800 |
| Message-ID | <532480f9-4588-490a-b238-e77157face7a@googlegroups.com> (permalink) |
| Subject | how to not be an idiot |
| From | hughaguilar96@gmail.com |
This is from FFL:
--------------------------------------------------------------------------
: scl-execute ( i*x xt scl -- j*x = Execute xt for every cell data in list )
snl-first@ \ walk = first
BEGIN
nil<>? \ while walk<>nil do
WHILE
dup >r scn-cell@
swap
dup >r execute \ execute xt with cell
r> r>
snn-next@ \ walk = walk->next
REPEAT
drop
;
--------------------------------------------------------------------------
Notice that SNN-NEXT@ is done after executing the xt. This is a bug (I brought this up in 2010, but has never been fixed). If the xt-function clobbers the node, then the link field will no longer be valid and the next node can't be fetched. This is from the novice-package:
--------------------------------------------------------------------------
macro: next>r ( node -- node ) \ r: -- next-node
dup .fore @ >r ;
macro: each[ \ toucher: i*x node -- j*x
begin dup while
next>r ;
macro: ]each
r> repeat drop ;
: each ( i*x head 'toucher -- j*x ) \ toucher: i*x node -- j*x
>r
begin dup while \ -- node \r: -- 'toucher
r@ over .fore @ >r \ -- node 'toucher \r: -- 'toucher next
execute r> repeat drop
rdrop ;
--------------------------------------------------------------------------
Here is an example that takes advantage of this feature:
--------------------------------------------------------------------------
: reverse ( head -- new-head ) \ reverses the order of all the nodes
nil swap each[ init-list swap link ]each ;
--------------------------------------------------------------------------
Here the node gets inserted into another list, which obviously changes the link field.
On Tuesday, February 18, 2014 at 9:21:13 AM UTC-7, Alex McDonald wrote:
> on 18/02/2014 04:48:51, wrote:
> > On Monday, February 17, 2014 7:53:18 AM UTC-7, Alex McDonald wrote:
> >> on 16/02/2014 11:21:59, wrote:
> >> > On Sunday, February 16, 2014 2:48:34 AM UTC-7, Alex McDonald wrote:
> >> >> You and I have had a long discussion about the poor quality of the
> >> >> implementation of popular sorts you wrote in your novice package, where
> >> >> you have serious misunderstandings of how pointers work.
> >
> >> > My SORT works fine (it uses the HeapSort algorithm by default,
> >> > although I also have a QuickSort version), and I'm pretty sure that I
> >> > know how pointers work.
> >
> >> We had a long discussion about how your sorts moved records (fixed length
> >> areas of memory) rather than adjusted a list of pointers, and was going
> >> to be slow on anything other than a small number of short records due to
> >> the amount of data being moved.
> >
> > SORT works for either an array of records or an array of pointers to
> > record s --- the user has the option to do either.
> >
> > For example, in LIST.4TH I have BIG-SORT that converts a list into an
> > array of pointers to the nodes of the list, does SORT on that array of
> > pointers, then converts the array of pointers back into a sorted list
> > again.
>
> Sigh. I really can't be arsed finding all the replies I made to you on
> the subject of sorting. As with your symtab nonsense, you claimed
> performance that you weren't willing to test. Others did it for you.
> And you have been told before that a merge sort is much faster and much
> easier for lists. Only an idiot would do what you suggest, but apparently
> you are that idiot.
In the above, Alex McDonald called me an "idiot" because I didn't have a MergeSort in my LIST.4TH package. I had this (notice that it depends upon the same feature that REVERSE depended upon):
----------------------------------------------------------------------------
\ comparer: i*x new-node node -- j*x new-node flag \ insert new-node prior to node?
: insert-ordered ( head 'comparer node -- new-head 'comparer )
init-list rover rover \ -- head 'comparer node head 'comparer
find-prior \ -- head 'comparer node -1|prior|false
dup 0= if drop rot swap link swap exit then \ append
dup -1 = if drop rot link swap exit then \ prepend
insert ;
: sort-list ( head 'comparer -- new-head )
nil swap rot each[ insert-ordered ]each drop ;
\ If the comparer provides a TRUE on node > new-node, then the list will be sorted in ascending order.
\ The following is a typical comparer function:
\ : int> ( new-node node -- new-node flag ) \ assumes that we are sorting on a W field called .N
\ .n @ over .n @ u> ;
----------------------------------------------------------------------------
In my ongoing and futile effort at not being an idiot, here is a first attempt at MergeSort:
----------------------------------------------------------------------------
: merge-sorted-lists { headA headB 'comparer -- head } \ merge headA into headB
nil begin \ -- head
headA 0= if headB link exit then \ if headA is done, append headB and exit
headB 0= if headA link exit then \ if headB is done, append headA and exit
headA headB 'comparer execute nip \ -- head flag
if headA delink-one to headA \ headA < headB
else headB delink-one to headB then \ headA => headB
link again ;
7 constant short-list \ any list with a length <= SHORT-LIST will be sorted with SORT-LIST
: mergesort-list ( head 'comparer -- new-head )
>r dup dup length \ -- head head length
dup short-list u<= if 2drop r> sort-list exit then
2/ nth delink \ -- headB headA \ split list into halves
r@ recurse swap r@ recurse \ -- new-headA new-headB \ sort each half
r> merge-sorted-lists ; \ merge the halves together
----------------------------------------------------------------------------
MERGE-SORTED-LISTS uses locals. This makes it very slow in SwiftForth because SwiftForth doesn't have a register for the local-frame, but uses a user-variable instead, so every local-variable access is quite slow. Also, the initialization code for locals is hugely over-complicated and inefficient. All in all, calling MERGE-SORTED-LISTS repeatedly inside of a recursive function is going to be slow. So I'm still an idiot. :-(
Here is a second attempt at writing MERGE-SORTED-LISTS this time sans locals:
----------------------------------------------------------------------------
: merge-sorted-lists ( headA headB 'comparer -- head ) \ merge headA into headB
>r
nil >r begin \ -- headA headB
over 0= if nip r> swap link rdrop exit then \ if headA is done, append headB and exit
dup 0= if drop r> swap link rdrop exit then \ if headB is done, append headA and exit
2dup rr@ execute nip
if swap delink-one r> rot link >r swap \ headA < headB
else delink-one r> rot link >r then \ headA => headB
again ;
----------------------------------------------------------------------------
This version should be faster, but it is much less readable. It was written to appease SwiftForth where locals are inefficient --- loss of readability is just the price that you pay for using SwiftForth --- this version is still written by an idiot, just like the last one, but it is idiotic in a different way.
Locals are much more efficient under VFX than SwiftForth. Locals are still inefficient on VFX as compared to stack-juggling. Stephen Pelc apparently recognized the fact that all ANS-Forth programmers were going to eschew the use of locals because Elizabeth Rather hates locals, and consequently he put minimal effort into generating fast code for acessing locals. The locals are never held in registers temporarily; they are unoptimized; you get a memory-access every time --- by comparison, the data-stack values are held in registers (EAX and/or EDX) temporarily, so a lot of stack-juggling gets optimized away and there is no memory access needed.
I'm using the return-stack rather than locals, so I have R@ and RR@ rather than named locals. Note that RDROP and RR@ are both in the novice-package:
----------------------------------------------------------------------------
macro: rdrop ( -- ) \ r: a --
r> drop ;
macro: rr@ ( -- b ) \ r: a b -- a b
2r@ drop ;
----------------------------------------------------------------------------
My MERGESORT-LIST is recursive. This is inefficient. The use of >R inside both MERGESORT-LIST and MERGE-SORTED-LISTS screws up the RET prediction on the x86, so every RET is unpredicted and the trace-cache can't be loaded in parallel with the function executing, but instead must execute when RET executes because the destination isn't known until that time, which causes a major delay. RET gets executed quite a lot in a recursive function, so it is going to be slow.
It should be possible to write MERGESORT-LIST to be iterative rather than recursive. I could figure this out, but I have lost patience with the whole thing. Even if I did invest the time and effort to write an iterative version of MERGESORT-LIST, everybody on comp.lang.forth would still call me an idiot, which I can get for free right now, so there is no need to invest time and effort for the same result. In general, recursive functions are a lot simpler and easier to write than iterative functions --- I did write SORT though, which uses iteratin rather than recursion, but the only result was for Alex McDonald to call me an idiot.
Above, Alex McDonald said: "merge sort is much faster and much easier." I didn't find it to be particularly easy. Alex McDonald apparently doesn't consider it to be easy either, because he hasn't done it. I'm not aware of anybody other than myself who is putting any effort into writing a code-library, so apparently everybody agrees with me that doing so is not easy.
I doubt that MERGESORT-LIST is any faster either. It has a lot of overhead! If the comparer function is short and fast (it usually is just comparing two strings or two floats), then SORT-LIST may be faster than MERGESORT-LIST for short lists --- MERGESORT-LIST isn't going to pull ahead until you begin working with pretty big lists --- analyzing this is complicated though, and I don't have the time to do so (and, honestly, I'm not interested enough in the question to spend any time on it).
The upshot of all of this, is that I don't think it is possible to program in ANS-Forth and not be an idiot. I'm mostly spending my time on Straight Forth nowadays. I will release a new novice-package upgrade in a few days, but that will likely be the last ANS-Forth code that I write --- it is pointless to write ANS-Forth code when I can't ever become an ANS-Forth programmer.
Back to comp.lang.forth | Previous | Next — Next in thread | Find similar | Unroll thread
how to not be an idiot hughaguilar96@gmail.com - 2016-12-05 09:11 -0800
Re: how to not be an idiot hughaguilar96@gmail.com - 2016-12-05 19:02 -0800
Re: how to not be an idiot hughaguilar96@gmail.com - 2016-12-05 23:00 -0800
Re: how to not be an idiot hughaguilar96@gmail.com - 2016-12-06 10:16 -0800
Re: how to not be an idiot hughaguilar96@gmail.com - 2016-12-06 12:30 -0800
Re: how to not be an idiot hughaguilar96@gmail.com - 2016-12-10 18:45 -0800
Re: how to not be an idiot hughaguilar96@gmail.com - 2016-12-08 22:35 -0800
Re: how to not be an idiot polymorph self <jackvanc3@gmail.com> - 2016-12-11 06:18 -0800
csiph-web