Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #24376
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Simple Sort - the smallest sorting routine? |
| Date | 2013-07-10 23:05 +0200 |
| Organization | 1&1 Internet AG |
| Message-ID | <krkiaq$2sv$1@online.de> (permalink) |
| References | (9 earlier) <2013Jul7.141859@mips.complang.tuwien.ac.at> <wKKdnVVMtarQT0fMnZ2dnUVZ_vednZ2d@supernews.com> <2013Jul9.162517@mips.complang.tuwien.ac.at> <krhvve$mpr$1@online.de> <7xfvvnw7j9.fsf@ruckus.brouhaha.com> |
Paul Rubin wrote:
> Bernd Paysan <bernd.paysan@gmx.de> writes:
>> quicksort(a,n) has a pretty bad prediction rate (n/2 log n
>> mispredictions).
>
> Most stuff is still running under instruction sets designed in an era
> when cache effects weren't so important.
Or branch prediction. Cache behavior is good for quicksort, as it doesn't
do random walks, but linear walks - and then reiterates linear walks on the
two parts it just walked through; for caching, this is really good.
> With conditional moves, maybe
> quicksort isn't so bad. You'd do the conditional swap and pointer
> increments with conditional moves, then compare the two pointers which
> will usually be unequal. There would be a misprediction only when the
> pointers actually cross.
Yes, that should work somehow, but I'm not sure if conditional moves alone
are sufficient. It probably needs more general conditional operations, and
some non-substantial changes. I'm sure the Itanium can handle it, not sure
about ARM.
The inner loop for conditional execution would be something like that:
ValType lx=*l, rx=*r;
while (l <= r) {
if (lx < p) {
lx=*++l;
} else if (rx > p) {
rx=*--r;
} else {
*l++ = rx;
*r-- = lx;
lx=*l;
rx=*r;
}
}
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar
Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-25 13:12 -0700
Re: Simple Sort - the smallest sorting routine? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-06-25 23:48 -0700
Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-26 09:11 -0700
Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-06-26 02:03 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-26 11:25 -0500
Re: Simple Sort - the smallest sorting routine? the_gavino_himself <visphatesjava@gmail.com> - 2013-06-26 12:36 -0700
Re: Simple Sort - the smallest sorting routine? "Elizabeth D. Rather" <erather@forth.com> - 2013-06-26 09:49 -1000
Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:24 +0000
Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:23 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-26 13:35 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-26 16:37 -0700
Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-27 01:31 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-27 04:04 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:27 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 13:23 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-06-30 21:48 +0100
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 16:53 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-01 04:34 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-03 18:41 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 02:58 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-04 21:30 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-06 00:18 +0100
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-06 13:45 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 07:49 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-06 13:38 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 10:06 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 23:08 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:24 -0500
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 23:47 +0200
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 09:59 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:52 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 12:18 +0000
Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 00:06 -0700
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-08 09:50 +0000
Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 03:14 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 09:53 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-09 14:25 +0000
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-09 23:39 +0200
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-09 18:03 -0700
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-10 23:05 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 03:21 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:29 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:44 -0500
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 04:07 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:06 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 14:21 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 04:45 -0500
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 03:13 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:09 -0500
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-10 12:16 +0000
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:38 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:45 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:56 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:54 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-10 13:57 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 07:15 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:52 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:00 -0500
Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-10 16:13 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 17:07 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:53 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:40 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:17 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:54 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-12 03:07 -0500
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 00:43 +0200
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 00:21 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:32 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:38 -0500
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 07:05 -0500
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 13:00 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:47 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:22 +0100
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 19:25 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 21:58 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 02:27 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-08 21:18 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-09 04:20 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:30 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:13 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 13:57 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 16:57 -0500
Re: Simple Sort - the smallest sorting routine? Elizabeth D Rather <erather@forth.com> - 2013-07-10 13:00 -1000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 22:19 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:23 -0700
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 01:12 +0200
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 00:33 -0500
Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 11:48 +0200
Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-11 03:08 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 05:00 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:17 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 06:53 -0500
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 15:21 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 10:37 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:07 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:19 -0500
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:33 +0000
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 18:18 +0000
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:46 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 03:48 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-12 10:55 -0700
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-12 19:29 +0000
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-15 09:50 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 13:22 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-13 20:05 -0700
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 11:34 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-14 09:18 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 16:05 -0700
Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 06:12 +0300
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 22:17 -0700
Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 11:44 +0300
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-15 09:42 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 18:03 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-17 00:54 -0700
Re: Simple Sort - the smallest sorting routine? Howerd <howerdo@yahoo.co.uk> - 2013-07-14 10:09 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 15:35 -0700
Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:08 +0000
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:30 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 09:34 -0700
Re: Simple Sort - the smallest sorting routine? Michael Morris <morrimichael@gmail.com> - 2013-07-15 23:09 -0500
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 17:46 -0700
Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-17 03:14 -0500
Re: Simple Sort - the smallest sorting routine? "Rod Pemberton" <do_not_have@notemailnotq.cpm> - 2013-07-17 21:47 -0400
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-11 04:06 +0100
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:18 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 16:48 +0100
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:24 +0100
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-04 14:41 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-27 01:59 -0700
Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:30 -0700
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 12:59 -0700
Re: Simple Sort - the smallest sorting routine? awegel@arcor.de (Alex Wegel) - 2013-06-27 00:08 +0200
Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-26 19:31 -0400
Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-27 06:26 -0400
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-06-28 02:05 +0000
Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 07:33 -0700
Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-05 00:47 +0200
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 19:01 +0000
Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-15 01:28 +0000
Re: Simple Sort - the smallest sorting routine? Ian Osgood <iano@quirkster.com> - 2013-07-19 11:29 -0700
Re: Simple Sort - the smallest sorting routine? Brad Eckert <hwfwguy@gmail.com> - 2013-07-19 09:09 -0700
csiph-web