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

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

Baden's recursive Quicksort revisited

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

Contents

  Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-11 01:31 +1000
    Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-10 15:49 +0000
    Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-10 17:42 +0000
      Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-18 15:16 +1000
      Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-20 03:18 -0500
        Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-21 16:33 +0000
    Re: Baden's recursive Quicksort revisited Hans Bezemer <the.beez.speaks@gmail.com> - 2013-10-11 12:03 +0200
      Re: Baden's recursive Quicksort revisited Alex McDonald <blog@rivadpm.com> - 2013-10-11 05:15 -0700
        Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-13 12:25 +1000
          Re: Baden's recursive Quicksort revisited "Alex McDonald" <blog@rivadpm.com> - 2013-10-13 08:59 +0100
            Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-13 04:50 -0500
              Comparing addresses (was: Baden's recursive Quicksort revisited) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-15 15:17 +0000
                Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-15 14:34 -0500
                  Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-16 14:15 +0000
                    Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-20 02:51 -0500
                      Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-22 11:18 +0000
                        Re: Comparing addresses albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-22 13:26 +0000
                          Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-22 13:39 +0000
                        Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-22 13:30 -0500
                          Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-23 07:48 +0000
                            Re: Comparing addresses m.a.m.hendrix@tue.nl - 2013-10-23 23:49 -0700
                              Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-24 09:01 +0000
          Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-13 12:06 +0000
            Re: Baden's recursive Quicksort revisited all2001@spambog.com (Wolfgang Allinger) - 2013-10-13 11:42 -0400
      Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-13 12:27 +1000
        Re: Baden's recursive Quicksort revisited Hans Bezemer <the.beez.speaks@gmail.com> - 2013-10-16 10:35 +0200
          Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-16 03:51 -0500
          Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-16 10:50 +0000
            Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-16 14:27 +0000
          Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-18 15:37 +1000

Page 2 of 2 — ← Prev page 1 [2]

#26669 — Re: Comparing addresses

On Wednesday, October 23, 2013 9:48:18 AM UTC+2, Anton Ertl wrote:
[..]
> Even for a cell array, a dfloat array, etc., the address beyond 
> the last element is also the address beyond the last byte of the
> memory area. So it's adequate for everything.

What if memory is allocated with a granularity less than the size
of a float (4/8/10/16bytes), a complex double (8/16/20/32), or an
xmmm type?

-marcel

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

#26670 — Re: Comparing addresses

m.a.m.hendrix@tue.nl writes:
>On Wednesday, October 23, 2013 9:48:18 AM UTC+2, Anton Ertl wrote:
>[..]
>> Even for a cell array, a dfloat array, etc., the address beyond 
>> the last element is also the address beyond the last byte of the
>> memory area. So it's adequate for everything.
>
>What if memory is allocated with a granularity less than the size
>of a float (4/8/10/16bytes), a complex double (8/16/20/32), or an
>xmmm type?

E.g., if the complex doubles are 32 bytes, and you allocate, say 95
bytes (from A to A+94)?  Then your the address beyond the last complex
double is A+64, and the proposed MAX-U restriction is not necessary.
If you are thinking about A+96, that is two bytes beyond the end of
the area, but accessing A+64 as a 32-byte complex double would access
A+95, which is beyond the end of the allocated area.

If you are thinking of a different scenario, what is it?

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

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

#26465

In article <l3csts$39h$1@speranza.aioe.org>, Ed <invalid@invalid.com> wrote:
>Alex McDonald wrote:
>> On Friday, 11 October 2013 11:03:20 UTC+1, The Beez  wrote:
>> > Ed wrote:
>> >
>> >
>> >
>> > > \ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
>> > > \ buggy (try it!).
>> >
>> > Ed, this code (in some form or another) is still very much in use with
>> > KForth, SwitftForth and 4tH. I never found any problem with it, but if you
>> > have an example me and I assume the maintainers of other compilers would
>> > very much like to know.
>>
>> Ed's code uses U< and U< NOT instead of Wil's < and >. Systems that
>permit signed addresses,
>> or systems that run under an OS that permits signed addresses, may
>find problems. That won't
>> include Window's Forths that run in user space.
>
>I'm not familiar with Windows programming but I'm told DLL's can pose
>problems because they load anywhere (?)  Apart from tempting fate, it would
>be an error to use signed operators on systems with unsigned addresses.

The problem is not whether addresses are signed or unsigned.
(They are in fact always unsigned).
It is a matter whether your are worried about addresses above
0x8000,0000,0000,0000 or 0x8000,0000 or 0x8000.
Except for the latter case, I don't bother with U<.

While MS-windows would use addresses that give true on 0< for code,
I very much doubt that this would be the case for buffers where
data is stored.

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

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

#26485

 On 13 Oct 13 at group /comp/lang/forth in article 525a8cc0$0$1706$e4fe514c@dreader35.news.xs4all.nl
 <albert@spenarnc.xs4all.nl>  (Albert van der Horst)  wrote:

>The problem is not whether addresses are signed or unsigned.
>(They are in fact always unsigned).

No, e.g. with the Motorolas (HC16...) they are signed!
That byte me a long time ago and I will never forget!
Accessing an address with more than $7fff as offset will shoot your  
feet. And hopefully that targeted address is error-trapped because of  
this page is not declared in use. If it`s in use (=enabled), weird  
things happens.

BTDT, will never forget and forgive this crappy design.

I think the 68000 have the same Problem, but it will show up with  
offsets of more than 31 bit.


Saludos (an alle Vernünftigen, Rest sh. sig)
Wolfgang

-- 
Wolfgang Allinger, anerkannter Trollallergiker :) reply Adresse gesetzt!
Ich diskutiere zukünftig weniger mit Idioten, denn sie ziehen mich auf
ihr Niveau herunter und schlagen mich dort mit ihrer Erfahrung! :p
(lt. alter usenet Weisheit)      iPod, iPhone, iPad, iTunes, iRak, iDiot

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

#26439

Hans Bezemer wrote:
> Ed wrote:
>
> > \ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
> > \ buggy (try it!).
>
> Ed, this code (in some form or another) is still very much in use with
> KForth, SwitftForth and 4tH. I never found any problem with it, but if you
> have an example me and I assume the maintainers of other compilers would
> very much like to know.
> ...

The statement in Wil's "qsort.txt" which causes it to fail (dramatically) is:

    1 CELLS INVERT CONSTANT  -CELL

Perhaps it was a simple oversight and what he intended was:

     1 CELLS 1- INVERT CONSTANT  -CELL

The other problems in "qsort.txt" relate to using signed operators on addresses
and unsigned numbers which typically affects 16-bit Forths sooner.  Curiously
his original FD code (essentially what I posted) was mostly correct.

It highlights the difficulty (folly?) of writing "portable code".  32-bit Forth users
are more likely to make such errors because the bugs rarely bite *them*.

Another bug is the use of  2/ .  This is wrong for the reasons given above but
curiously still works.  The only ill-effect seems to be a few more iterations.
Ideally  2/  should be replaced with  U2/  (or  1 RSHIFT  if you don't have it).

Lastly I note some implementations of Wil's code posted online comment
out the statement:

    2OVER 2OVER  - + > IF  2SWAP  THEN

In the aforementioned FD article Wil specifically warns against this.  A quick
test I did indicates including the line can reduce data stack usage by almost half.
Again, unlikely to affect 32-bit Forths.

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

#26573

 "Ed" <invalid@invalid.com> Wrote in message: 
> Perhaps it was a simple oversight and what he intended was:
> 
>      1 CELLS 1- INVERT CONSTANT  -CELL
<snip>
> The other problems in "qsort.txt" relate to using signed operators on addresses
> and unsigned numbers. <snip> 
> Another bug is the use of  2/. 
<snip>
Thank you, Ed, for going into so much detail. You're obviously
 right although fortunately none of this affects 4tH, since it
 uses virtual addresses (as a matter of fact: array indexes) and
 those are always positive (or 4tH will give an error). Yes, the
 -CELL error is the most interesting one. I'm not sure why he
 tries to do a binary NEGATE here. CELLS does accept negative
 values. For that reason I used the snippet "-1 CELLS CONSTANT
 -CELL". Which makes -CELL AND completely useless (renders -1 in
 4tH), but whatever ;-)

> Lastly I note some implementations of Wil's code posted online comment
> out the statement:
> 
>     2OVER 2OVER  - + > IF  2SWAP  THEN
Yes, interesting thingy. But in field tests I found a speedup of
 5-10% in 4tH. So, I left it to the programmer to decide what he
 wants - using [PRAGMA].

Hans Bezemer

-- 




----Android NewsGroup Reader----
http://www.piaohong.tk/newsgroup

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

#26575

Hans Bezemer <the.beez.speaks@gmail.com> wrote:
> "Ed" <invalid@invalid.com> Wrote in message: 
>> Perhaps it was a simple oversight and what he intended was:
>> 
>>      1 CELLS 1- INVERT CONSTANT  -CELL
> <snip>
>> The other problems in "qsort.txt" relate to using signed operators on addresses
>> and unsigned numbers. <snip> 
>> Another bug is the use of  2/. ^M<snip>
> Thank you, Ed, for going into so much detail. You're obviously
> right although fortunately none of this affects 4tH, since it
> uses virtual addresses (as a matter of fact: array indexes) and
> those are always positive (or 4tH will give an error). Yes, the
> -CELL error is the most interesting one. I'm not sure why he
> tries to do a binary NEGATE here.

It just gets you a properly aligned cell address.

Andrew.

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

#26579

In article <525e4f7d$0$15946$e4fe514c@news2.news.xs4all.nl>,
Hans Bezemer  <the.beez.speaks@gmail.com> wrote:
> "Ed" <invalid@invalid.com> Wrote in message:
>> Perhaps it was a simple oversight and what he intended was:
>>
>>      1 CELLS 1- INVERT CONSTANT  -CELL
><snip>
>> The other problems in "qsort.txt" relate to using signed operators on
>addresses
>> and unsigned numbers. <snip>
>> Another bug is the use of  2/.
<snip>
>Thank you, Ed, for going into so much detail. You're obviously
> right although fortunately none of this affects 4tH, since it
> uses virtual addresses (as a matter of fact: array indexes) and
> those are always positive (or 4tH will give an error). Yes, the
> -CELL error is the most interesting one. I'm not sure why he
> tries to do a binary NEGATE here. CELLS does accept negative
> values. For that reason I used the snippet "-1 CELLS CONSTANT
> -CELL". Which makes -CELL AND completely useless (renders -1 in
> 4tH), but whatever ;-)
>
>> Lastly I note some implementations of Wil's code posted online comment
>> out the statement:
>>
>>     2OVER 2OVER  - + > IF  2SWAP  THEN
>Yes, interesting thingy. But in field tests I found a speedup of
> 5-10% in 4tH. So, I left it to the programmer to decide what he
> wants - using [PRAGMA].

It is interesting to speculate how this comes about.
It surely is more code to be executed.
Would it be caused by better locality, i.e. less cache misses?
>
>Hans Bezemer
>
>--
>
>
>
>
>----Android NewsGroup Reader----
>http://www.piaohong.tk/newsgroup
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#26584

albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
>>> Lastly I note some implementations of Wil's code posted online comment
>>> out the statement:
>>>
>>>     2OVER 2OVER  - + > IF  2SWAP  THEN
>>Yes, interesting thingy. But in field tests I found a speedup of
>> 5-10% in 4tH. So, I left it to the programmer to decide what he
>> wants - using [PRAGMA].
>
>It is interesting to speculate how this comes about.
>It surely is more code to be executed.
>Would it be caused by better locality, i.e. less cache misses?

Yes.  I did the same thing in my quicksort implementation, but there
was no overall win.

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

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

#26625

Hans Bezemer wrote:
> "Ed" <invalid@invalid.com> Wrote in message:
> ...
> > Lastly I note some implementations of Wil's code posted online comment
> > out the statement:
> >
> >     2OVER 2OVER  - + > IF  2SWAP  THEN
> Yes, interesting thingy. But in field tests I found a speedup of
>  5-10% in 4tH. So, I left it to the programmer to decide what he
>  wants - using [PRAGMA].

BTW the code above which tests partition length and puts the shorter
on TOS can fail too.  It's a trade-off between speed/accuracy.

\  2over 2over - + > if 2swap then ( Baden, fast)
\  2over 2over - -rot - < if 2swap then ( good, slower)
\  2dup swap - >r 2over swap - r> u< if 2swap then ( best, slowest)

Any of the above would do as the routine is non-critical.  The second
one gets it right for all but exceptional cases (when a partition is
greater than half the address range).

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web