Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #15078 > unrolled thread
| Started by | visualforth@rocketmail.com |
|---|---|
| First post | 2012-08-21 21:43 -0700 |
| Last post | 2012-08-22 07:37 -0700 |
| Articles | 20 on this page of 163 — 19 participants |
Back to article view | Back to comp.lang.forth
Comparative Productivity of Programming Languages visualforth@rocketmail.com - 2012-08-21 21:43 -0700
Re: Comparative Productivity of Programming Languages "A. K." <akk@nospam.org> - 2012-08-22 07:07 +0200
Re: Comparative Productivity of Programming Languages Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-22 03:35 -0500
Re: Comparative Productivity of Programming Languages John Passaniti <john.passaniti@gmail.com> - 2012-08-22 14:06 -0700
Function Points (was: Comparative Productivity of Programming Languages) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-23 14:50 +0000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-23 11:43 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-25 14:13 +0000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-25 10:12 -0700
Re: Function Points Doug Hoffman <glidedog@gmail.com> - 2012-08-25 15:39 -0400
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-25 15:09 -0700
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-08-25 12:34 -1000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-25 16:43 -0700
Re: Function Points jacko <jackokring@gmail.com> - 2012-08-25 18:05 -0700
Re: Function Points jacko <jackokring@gmail.com> - 2012-08-25 20:34 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-26 03:24 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-25 22:44 -0700
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-08-25 21:19 -1000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-26 00:36 -0700
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-08-25 21:50 -1000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-26 01:08 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-26 23:20 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-26 19:33 -0700
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-27 13:34 -0500
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-27 22:38 +0200
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-28 02:45 -0500
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-27 18:14 -0700
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-27 18:24 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-30 14:22 +0000
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-28 03:07 -0500
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-28 08:18 -0700
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-28 12:15 -0500
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-28 23:05 -0700
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-29 03:55 -0500
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-27 22:28 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-27 20:26 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-28 23:17 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-29 01:13 -0700
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-29 02:23 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-30 02:59 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-29 22:18 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-30 20:44 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-31 01:29 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-31 09:33 +0000
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-30 02:58 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-29 19:39 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-30 14:10 +0000
Re: Function Points gavino_himself <visploveslisp@gmail.com> - 2012-08-30 20:08 -0700
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-08-30 17:47 -1000
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-08-27 13:43 -1000
Re: Function Points "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2012-08-27 12:14 +0100
Re: Function Points Mark Wills <markrobertwills@yahoo.co.uk> - 2012-08-27 05:12 -0700
Re: Function Points "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2012-08-27 15:52 +0100
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-26 13:09 +0000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-27 20:52 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-30 14:08 +0000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-30 10:43 -0700
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-08-30 08:25 -1000
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-30 22:42 +0200
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-31 01:23 -0400
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-31 03:08 -0500
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-31 18:56 -0400
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-01 02:35 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-31 23:52 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-01 14:27 +0000
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-01 14:18 +0000
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-01 17:45 +0200
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-01 16:14 +0000
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-01 19:13 +0200
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-09-02 03:19 -0500
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-01 16:18 -0400
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-02 03:04 +0200
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-02 04:02 -0400
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-02 17:40 +0200
Re: Function Points jim@rainbarrel.com - 2012-09-02 10:32 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-02 20:49 +0200
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-02 16:33 -0400
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-02 17:03 -0400
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-09-02 09:02 -1000
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-02 16:35 -0400
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-09-02 13:42 -1000
Re: Function Points jim@rainbarrel.com - 2012-09-02 16:54 -0700
Re: Function Points Mark Wills <markrobertwills@yahoo.co.uk> - 2012-09-03 00:29 -0700
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-03 01:30 -0400
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-09-02 21:21 -1000
Re: Function Points jim@rainbarrel.com - 2012-09-03 10:37 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-04 07:14 +0000
Re: Function Points Coos Haak <chforth@hccnet.nl> - 2012-09-03 21:12 +0200
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-03 17:32 -0400
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-03 17:51 -0400
Re: Function Points John Passaniti <john.passaniti@gmail.com> - 2012-09-03 22:37 -0700
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-04 04:25 -0400
Re: Function Points John Passaniti <john.passaniti@gmail.com> - 2012-09-04 07:35 -0700
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-05 02:13 -0400
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-09-04 20:18 -1000
Re: Function Points John Passaniti <john.passaniti@gmail.com> - 2012-09-05 10:56 -0700
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-05 16:11 -0400
Re: Function Points John Passaniti <john.passaniti@gmail.com> - 2012-09-05 14:07 -0700
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-02 16:27 -0400
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-03 00:52 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-02 16:28 -0700
Re: Function Points jim@rainbarrel.com - 2012-09-02 16:48 -0700
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-02 20:21 -0400
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-09-02 14:45 -1000
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-03 01:12 -0400
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-09-02 21:26 -1000
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-03 01:06 -0400
Re: Function Points Mark Wills <markrobertwills@yahoo.co.uk> - 2012-08-31 03:29 -0700
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-31 10:35 +0000
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-31 18:49 -0400
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-01 14:49 +0000
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-09-01 08:36 -1000
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-01 16:11 -0400
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-03 01:58 +0200
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-01 17:54 +0200
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-01 16:19 -0400
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-02 03:05 +0200
Re: Function Points Coos Haak <chforth@hccnet.nl> - 2012-08-31 23:10 +0200
Re: Function Points "Elizabeth D. Rather" <erather@forth.com> - 2012-08-31 15:50 -1000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-01 10:31 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-01 21:52 +0200
Re: Function Points "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-01 16:36 -0400
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-01 14:36 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-02 03:30 +0200
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-02 23:15 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-02 15:02 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-03 01:50 +0200
Re: Function Points jim@rainbarrel.com - 2012-09-02 16:57 -0700
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-03 23:11 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-04 14:30 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-04 10:14 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-04 22:10 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-06 00:19 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-06 17:48 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-06 12:01 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-06 22:02 +0200
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-09-06 14:19 -0700
Heap (was: Function Points) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-07 11:30 +0000
Re: Heap (was: Function Points) Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-07 18:12 +0200
Re: Heap (was: Function Points) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-07 16:48 +0000
Re: Heap (was: Function Points) Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-07 21:34 +0200
Re: Heap Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-09-07 22:04 +0100
Re: Heap anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-08 11:52 +0000
Re: Heap Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-08 22:48 +0200
Re: Heap (was: Function Points) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-08 12:11 +0000
priority queue (was: Function Points) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-03 11:46 +0000
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-03 15:03 +0200
Re: Function Points mhx@iae.nl (Marcel Hendrix) - 2012-09-03 22:36 +0200
Re: Function Points mhx@iae.nl (Marcel Hendrix) - 2012-09-06 20:27 +0200
Re: Function Points Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-09-02 04:00 -0500
Re: Function Points visualforth@rocketmail.com - 2012-09-03 10:40 -0700
Re: Function Points Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-03 20:26 +0200
Re: Function Points Doug Hoffman <glidedog@gmail.com> - 2012-08-27 11:49 -0400
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-27 09:16 -0700
Re: Function Points Josh Grams <josh@qualdan.com> - 2012-08-28 22:46 +0000
Re: Function Points jacko <jackokring@gmail.com> - 2012-08-28 16:06 -0700
Re: Function Points Doug Hoffman <glidedog@gmail.com> - 2012-08-28 20:50 -0400
Re: Function Points anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-26 12:59 +0000
Re: Function Points Paul Rubin <no.email@nospam.invalid> - 2012-08-26 22:24 -0700
Re: Function Points (was: Comparative Productivity of Programming Languages) John Passaniti <john.passaniti@gmail.com> - 2012-08-23 15:02 -0700
Re: Function Points (was: Comparative Productivity of Programming Languages) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-25 14:57 +0000
Re: Comparative Productivity of Programming Languages "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-22 08:07 -0400
Re: Comparative Productivity of Programming Languages visualforth@rocketmail.com - 2012-08-22 08:12 -0700
Re: Comparative Productivity of Programming Languages visualforth@rocketmail.com - 2012-08-22 07:37 -0700
Page 7 of 9 — ← Prev page 1 2 3 4 5 6 [7] 8 9 Next page →
| From | "Rod Pemberton" <do_not_have@notemailnot.cmm> |
|---|---|
| Date | 2012-09-01 16:36 -0400 |
| Subject | Re: Function Points |
| Message-ID | <k1trel$qi$1@speranza.aioe.org> |
| In reply to | #15372 |
"Bernd Paysan" <bernd.paysan@gmx.de> wrote in message
news:2000935.ViCZX3HiHH@sunwukong.fritz.box...
...
> which aren't prone to off-by-one errors like C's
>
> for(i=0; i<n; i++) {
> ...
> }
>
> statement
C's for() statement is not off-by-one. Who types the "i=0" and "i<n"? The
programmer does.
> (many people write "i<=n", because they count from 1..n,
>
Programmer's who expect 1...n when coding 0...n by using "i=0" and "i<=n"
are off-by-one. Those who want 1...n should do:
for(i=1; i<=n; i++) {
...
}
> [...] but in fact, C counts from 0..n-1).
That's not fact at all. C's for() doesn't count.
You're thinking of C's arrays which start indexing at zero. Some
programmers have mental problems understanding that the indexing doesn't
start at one.
But as for for(), it's the programmer who controls all aspects of for()'s
start and stop conditions. The programmer can select exactly what they
want:
0 ... n-1 i=0; i<n
0 ... n i=0; i<=n
1 ... n i=1; i<=n
1 ... n-1 i=1; i<n
x ... y i=x; i<=y
etc.
The third argument can be set to do all sorts of complex stuff, or simple
increment and decrement.
Rod Pemberton
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-09-01 14:36 -0700 |
| Subject | Re: Function Points |
| Message-ID | <7x8vctqvbh.fsf@ruckus.brouhaha.com> |
| In reply to | #15372 |
Bernd Paysan <bernd.paysan@gmx.de> writes: > C somewhat has NPEs, too, through signals and setsigjmp. C's exception > handling is not really up to date ;-). Well, it's the null pointer dereference that causes the problem; what I was getting at about Java NPE's is that Java also has null pointers (though it handles them with exceptions instead of undefined behavior). > Lisp-like languages always had a > NIL thing, which wasn't quite the same as a null pointer. Right, and that causes hassles and crashes all the time. It's almost as bad as a null pointer. It's very common in Lisp programs for programs to crash because they got nil when expecting a non-nil value. The Python equivalent is None and there's something like it in Ruby. The most common Haskell error of that sort is when you try to examine the first element of a list that is unexpectedly empty. You get something like an NPE. But Haskellers don't say "ok, this is the Haskell equivalent of NPE, just avoid it through vigilance". They hate the phenomenon and are constantly trying to invent ways to make it impossible, with varying results. > Yes, but that are sorted indices, which remain sorted all the time, so > all you need is to have a insert and delete operation into them which > isn't costly. What's a non-costly way of inserting or deleting an element into a sorted index? We're back to balanced trees, I think. > You might use a B-tree or some similar data structure to keep these > indices sorted, but you don't actually use them to search for elements, > because the hash is faster. Hmm, yeah, you could probably save some cycles that way in some situations, though it may be a premature optimization a lot of the time. > The small-N priority queue has a very small constant overhead, and > very small code size, so it is better for small Ns than a binary heap. Messing with the queue typically won't be a significant cpu burner when N is small, so optimizing for that case is again often likely to be premature. Binary heaps are likely to be pretty fast even for small N anyway. I agree balanced trees would likely have significantly worse overhead.
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-02 03:30 +0200 |
| Subject | Re: Function Points |
| Message-ID | <3682218.RpYgJoRDKP@sunwukong.fritz.box> |
| In reply to | #15378 |
Paul Rubin wrote: > Bernd Paysan <bernd.paysan@gmx.de> writes: >> C somewhat has NPEs, too, through signals and setsigjmp. C's >> exception handling is not really up to date ;-). > > Well, it's the null pointer dereference that causes the problem; what > I was getting at about Java NPE's is that Java also has null pointers > (though it handles them with exceptions instead of undefined > behavior). That's what you get in a POSIX environment with a signal handler and corresponding setjmp: defined behavior, even in C. Or in Gforth, where a 0 @ responds with a -9 throw. >> Yes, but that are sorted indices, which remain sorted all the time, >> so all you need is to have a insert and delete operation into them >> which isn't costly. > > What's a non-costly way of inserting or deleting an element into a > sorted index? We're back to balanced trees, I think. Yes. >> You might use a B-tree or some similar data structure to keep these >> indices sorted, but you don't actually use them to search for >> elements, because the hash is faster. > > Hmm, yeah, you could probably save some cycles that way in some > situations, though it may be a premature optimization a lot of the > time. If your have a million entries, your hash query is in the order of 20 times faster than your balanced binary tree. Most data bases have much more selects than inserts, so a faster select is a good idea. As my current "larger" project is net2o, I'm thinging about the following situation: You have a trillion objects (files, images), indexed by unique identifiers. You now want to query your distributed database for the whereabout of one of these objects. Distributed as in worldwide, i.e. the worst case timing for one single operation is in the few hundred millisecond range. I'd use a DHT, and a secure hash as unique identifier. I'm definitely sure I don't want a b-tree for that. I'm also quite sure I don't want any total order over the objects, only over small subsets of them. >> The small-N priority queue has a very small constant overhead, and >> very small code size, so it is better for small Ns than a binary >> heap. > > Messing with the queue typically won't be a significant cpu burner > when N is small, so optimizing for that case is again often likely to > be > premature. Binary heaps are likely to be pretty fast even for small N > anyway. I agree balanced trees would likely have significantly worse > overhead. I've written a binary heap now, it is considerably more code than the O(n) code. I'd like to make a few benchmarks, before I post comparisons. The main source of bugs was that all more detailed descriptions count from 1..n, while Forth of course counts from 0..n-1. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-02 23:15 +0200 |
| Subject | Re: Function Points |
| Message-ID | <5883549.frr9YTnbEn@sunwukong.fritz.box> |
| In reply to | #15382 |
Bernd Paysan wrote:
> I've written a binary heap now, it is considerably more code than the
> O(n) code. I'd like to make a few benchmarks, before I post
> comparisons.
Ok, here's the benchmarking stuff.
binary heap linear "heap"
10 inserts 17,666ns 9,287ns
10 deletes 15,941ns 6,960ns
256 inserts 164,048ns 452,609ns
256 deletes 476,276ns 251,134ns
4096 inserts 2,609,171ns 93,231,767ns
4096 deletes 12,061,005ns 55,881,857ns
The linear "heap" is really very simple stuff, just doing an insert into
a sorted array with a linear scan (not even a binary search!), and using
normal string operations (with resize for grow/shrink of the buffer).
The delete also uses string operations. I'm surprised that the binary
heap doesn't pay off significantly at 256 item, and I don't fully
understand why the deletes are so slow... bubble-down has two compares
instead of one in bubble-up, but the compares aren't that expensive.
You can look at the files here
https://fossil.net2o.de/net2o/dir?ci=tip
heap.fs is the binary heap, linearheap.fs is the linear one, and heap-
test.fs is for testing. Test run on a 1.6GHz AMD Bobcat (I prefer weak
CPUs to benchmark things), run with
gforth-fast -d 1M
because I push up to 4096 numbers on the stack (and that's too much for
the standard Gforth image).
The binary heap part has a bit more overhead by using mini-oof.fs to
improve possible code reusage (this *is* necessary, as you don't want to
use cut&paste "template" programming here), but that should only have a
small constant overhead - the compare and swap operations are
efficiently implemented.
The small set timing is pretty good for the binary heap.
It's a typical mildly disappointing result - the O(n log n) doesn't meet
its promise, due to the random memory access pattern. The O(n²)
algorithm shuffles a lot more memory around, but its access pattern is
predictable. Some people say that modern x86 CPUs are tuned to bad
code, and that seems to include bad algorithms ;-).
The O(n²) algorithm was much faster to write, did run first time (using
the same test program as for the other algorithm), and due to it being
significantly shorter, it is also easier to maintain. So what do we
really gain from the more complex algorithm? As long as we have less
than 256 elements in our priority queue, I would go with the O(n²)
algorithm. I'd say that using an O(n log n) algorithm for a data set
that you don't expect to be that large is premature optimization.
I do prefer quicksort over bubble sort, because quicksort is one of the
best-behaving O(n log n) algorithms: It is about as simple as bubble
sort, it has predictable memory access patterns (linear scans), and with
some minor tweaks, it even has an O(log n) stack depth bound (by doing
tail recursion on the larger sub-array), and you can make it well-
behaving on pre-sorted arrays (which is a "must-do", whereas the anti-
attack random pivot selection is a "nice to have").
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-09-02 15:02 -0700 |
| Subject | Re: Function Points |
| Message-ID | <7xsjb0krr2.fsf@ruckus.brouhaha.com> |
| In reply to | #15400 |
Bernd Paysan <bernd.paysan@gmx.de> writes: >> I've written a binary heap ... The main source of bugs was that all >> more detailed descriptions count from 1..n, while Forth of course >> counts from 0..n-1. Thanks, this is cool. Note the Python implementation I linked to also uses 0..n-1, IIRC. > here's the benchmarking stuff. > binary heap linear "heap" > 10 inserts 17,666ns 9,287ns > 10 deletes 15,941ns 6,960ns By now I've forgotten just what is being timed, what the expected and maximum plausible N's are in the application, and whether inserts are more common than deletes or vice versa. > 256 inserts 164,048ns 452,609ns > 256 deletes 476,276ns 251,134ns At N=256 assuming that there's one insert for each delete, the binary heap is using 640,234ns and the linear heap is using 703,743, so in that situation (don't know if it's realistic) the binary heap is winning slightly. > heap doesn't pay off significantly at 256 item, and I don't fully > understand why the deletes are so slow... Some profiling might help. > You can look at the files here > https://fossil.net2o.de/net2o/dir?ci=tip I'll look at it later, I can't easily right now. > The binary heap part has a bit more overhead by using mini-oof.fs to > improve possible code reusage (this *is* necessary, as you don't want to > use cut&paste "template" programming here), I'd expect it's possible to do automatic template-style instantiation with suitable Forth hackery but I don't have a sense of whether it would help. It might be interesting to run the benchmark with one of the optimizing Forth compilers that does inlining. > Some people say that modern x86 CPUs are tuned to bad code, and that > seems to include bad algorithms ;-). I typed "cache-oblivious priority queue" into a search engine and got a lot of promising-looking hits, but haven't looked at any yet. > As long as we have less than 256 elements in our priority queue, I > would go with the O(n²) algorithm. It's not just that N is small but also that comparisons are cheap. With more expensive comparisons (e.g. you are dealing with more complicated structures, like in external merge sorting) I'd expect the crossover to be at lower N. > I'd say that using an O(n log n) algorithm for a data set that you > don't expect to be that large is premature optimization. If you're writing a general purpose library, it has to be able to handle large N sensibly, so it needs to offer the O(log n) algorithm either way. So your choice is between using that algorithm for everything, or also having a separate one optimized for small N. In this case I'd say writing two implementations without a demonstrated need is premature optimization. > I do prefer quicksort over bubble sort, Since you've got a binary heap implementation now, the obvious sorting method is heapsort. ;-)
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-03 01:50 +0200 |
| Subject | Re: Function Points |
| Message-ID | <5614082.OTcIhnlFXo@sunwukong.fritz.box> |
| In reply to | #15402 |
Paul Rubin wrote: > Thanks, this is cool. Note the Python implementation I linked to > also uses 0..n-1, IIRC. Yes, but some details were better explained elsewhere. >> here's the benchmarking stuff. >> binary heap linear "heap" >> 10 inserts 17,666ns 9,287ns >> 10 deletes 15,941ns 6,960ns > > By now I've forgotten just what is being timed, what the expected and > maximum plausible N's are in the application, and whether inserts are > more common than deletes or vice versa. In a normal priority queue, you have as many inserts as deletes, i.e. in the long run, the queue doesn't grow. The typical N would be one-digit. >> As long as we have less than 256 elements in our priority queue, I >> would go with the O(n²) algorithm. > > It's not just that N is small but also that comparisons are cheap. > With more expensive comparisons (e.g. you are dealing with more > complicated structures, like in external merge sorting) I'd expect the > crossover to be at lower N. Well, the O(n²) algorithm could use a binary search. Only the insert would still be O(n). >> I'd say that using an O(n log n) algorithm for a data set that you >> don't expect to be that large is premature optimization. > > If you're writing a general purpose library, it has to be able to > handle large N sensibly, so it needs to offer the O(log n) algorithm > either way. The "large N" in this case are concurrent network connections. Since net2o is designed as P2P network, most nodes will rather not have many concurrent network connections. > So your choice is between using that algorithm for everything, > or also having a separate one optimized for small N. In this case I'd > say writing two implementations without a demonstrated need is > premature optimization. Yes. >> I do prefer quicksort over bubble sort, > > Since you've got a binary heap implementation now, the obvious > sorting method is heapsort. ;-) Would be worth a benchmark run to see how much slower it is due to the bad cache behavior ;-). -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | jim@rainbarrel.com |
|---|---|
| Date | 2012-09-02 16:57 -0700 |
| Subject | Re: Function Points |
| Message-ID | <4063195f-b835-4a1a-bb7a-94c96876394f@googlegroups.com> |
| In reply to | #15409 |
> >> I'd say that using an O(n log n) algorithm for a data set that you > > >> don't expect to be that large is premature optimization. > > > > > > If you're writing a general purpose library, it has to be able to > > > handle large N sensibly, so it needs to offer the O(log n) algorithm > > > either way. > Diaperglu Forth uses a binary insertion sort. I haven't benchmarked it but it currently seems slow...
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-09-03 23:11 -0700 |
| Subject | Re: Function Points |
| Message-ID | <7xa9x6fhb6.fsf@ruckus.brouhaha.com> |
| In reply to | #15409 |
Bernd Paysan <bernd.paysan@gmx.de> writes: > In a normal priority queue, you have as many inserts as deletes, i.e. in > the long run, the queue doesn't grow. The typical N would be one-digit. That's for concurrent internet connections--what about your logic simulator? > Well, the O(n²) algorithm could use a binary search. Only the insert > would still be O(n). Wait, the entries in the linear version are sorted? That sounds complicated. I haven't yet gotten to look at the code. > The "large N" in this case are concurrent network connections. Since > net2o is designed as P2P network, most nodes will rather not have many > concurrent network connections. Hmm, single digit N still sounds pretty small.
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-04 14:30 +0200 |
| Subject | Re: Function Points |
| Message-ID | <30611295.P17Atab4sr@sunwukong.fritz.box> |
| In reply to | #15441 |
Paul Rubin wrote: > Bernd Paysan <bernd.paysan@gmx.de> writes: >> In a normal priority queue, you have as many inserts as deletes, i.e. >> in >> the long run, the queue doesn't grow. The typical N would be >> one-digit. > > That's for concurrent internet connections--what about your logic > simulator? The logic simulator definitely needs a low-overhead O(1) priority queue, a few cycles per insert, cache-friendly. I.e. the table with arrays for each time slot, where the table-deltat is <= min(gate delay). The logic simulator can easily have 100k events or more in flight. >> Well, the O(n²) algorithm could use a binary search. Only the insert >> would still be O(n). > > Wait, the entries in the linear version are sorted? That sounds > complicated. I haven't yet gotten to look at the code. The array in the linear version is completely sorted all the time. So you can do a binary search for the insert point, which reduces the number of comparisons - the insert time itself is dominated by the MOVE time then. >> The "large N" in this case are concurrent network connections. Since >> net2o is designed as P2P network, most nodes will rather not have >> many concurrent network connections. > > Hmm, single digit N still sounds pretty small. Yes. That's where the constant factor kills O(n log n). I was really surprised that N=256 wasn't significantly slower with the O(n²) algorithm, because lb 256=8, i.e. a factor 32 more to do. But then, O(n²) is really always n²/2 (you have to do only half the comparisons, and your insert move has to move half the words), and everything is low- overhead and cache-friendly. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-09-04 10:14 -0700 |
| Subject | Re: Function Points |
| Message-ID | <7xobllhfs5.fsf@ruckus.brouhaha.com> |
| In reply to | #15450 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
> The logic simulator definitely needs a low-overhead O(1) priority queue,
I have to wonder if you're losing some useful precision from that.
> The array in the linear version is completely sorted all the time.
In this case, deletion (selection) should be O(1), I would have thought.
Just bump a pointer.
>> Hmm, single digit N still sounds pretty small.
> Yes. That's where the constant factor kills O(n log n).
I mean, single digit N sounds like a small number of concurrent network
connections. The small, not-very-busy machine I'm on right now has
around 180 connections ("netstat | wc"). I don't know how many is
typical for something like BitTorrent.
> O(n²) is really always n²/2 (you have to do only half the
> comparisons, and your insert move has to move half the words),
If you can choose between moving backwards or forwards in a circular
buffer, then on average you only have to do 1/4 of the moves.
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-04 22:10 +0200 |
| Subject | Re: Function Points |
| Message-ID | <2982698.zgFk63W3xs@sunwukong.fritz.box> |
| In reply to | #15456 |
Paul Rubin wrote:
> Bernd Paysan <bernd.paysan@gmx.de> writes:
>> The logic simulator definitely needs a low-overhead O(1) priority
>> queue,
>
> I have to wonder if you're losing some useful precision from that.
Since you like proof systems, what about doing a formal proof?
t1 is the minimum gate delay in a netlist.
t2 is the minimum granularity of the priority queue
t2 < t1.
Execution modell is: We first make all signal level changes
corresponding to events in queue[0] available, then we evaluate all
events in queue[0]. Delay precision is maintained, since every event
knows the exact time of signal arrival, and therefore can calculate the
exact time for the signal outputs. Once we are finished with queue[0],
we get rid of it (e.g. rotate it to the tail, because we also have a
maximum gate delay, and don't need to keep any longer delays).
By t2 < t1, all new events get scheduled into queue[1] or later, so the
total order of dependent events is maintained. The total order of
independent events isn't, but we don't need to care about.
There are certainly conditions where such a simulator is tricky, e.g.
glitches on XOR gates. Let's assume the XOR gate has identical delay
for both inputs (you can have that, it requires a few more transistors
than the standard XOR gate), and we change them both roughly at the same
time (but not exactly so). The usual way a simulator responds is by
generating a short glitch on the output, because both transitions
effectively toggle the output after the same delta-t. This short glitch
can't be simulated in a simulator as above.
However, this glitch is not real, as it is too short. You can't have
the XOR gate do a full-swing 010 or 101 transition in less time than a
minimum gate delay. Therefore, you have a "minimum pulse width"
constraint, and the simulator keeps track of the last change of each
output. If the next change happens earlier than the minimum pulse
width, the last change must be cancelled.
>> The array in the linear version is completely sorted all the time.
>
> In this case, deletion (selection) should be O(1), I would have
> thought. Just bump a pointer.
Yes, it could be done that way. The linear version still has ample
opportunities for tuning.
>>> Hmm, single digit N still sounds pretty small.
>> Yes. That's where the constant factor kills O(n log n).
>
> I mean, single digit N sounds like a small number of concurrent
> network
> connections. The small, not-very-busy machine I'm on right now has
> around 180 connections ("netstat | wc").
Active, TCP, not waiting? Local AF_UNIX socket connections don't count.
> I don't know how many is
> typical for something like BitTorrent.
Usually in the one-digit order. If you have a really really good
uplink, it might make sense to have a bit more, since a gigabit uplink
can saturate quite a few downlinks. However, the normal case is that
your uplink is slower than your peers downlink.
The point of P2P networks is to create copies quickly. How do you do
that? By run-to-finish. Every peer who has a complete chunk of data
can announce that and redistribute it. The algorithm to spead data
quickly is "fastest peer first". That way, you create more copies
quickly, and once you have served all fast peers, there are many copies
to serve the slow peers. Unlike in economy, the "trickle down effect"
works in P2P networks, it's because there, everybody shares all he has
;-).
>> O(n²) is really always n²/2 (you have to do only half the
>> comparisons, and your insert move has to move half the words),
>
> If you can choose between moving backwards or forwards in a circular
> buffer, then on average you only have to do 1/4 of the moves.
As I said, ample of opportunity to tune the O(n²) algorithm.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-09-06 00:19 -0700 |
| Subject | Re: Function Points |
| Message-ID | <7xzk53aa9n.fsf@ruckus.brouhaha.com> |
| In reply to | #15461 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
> By t2 < t1, all new events get scheduled into queue[1] or later, so the
> total order of dependent events is maintained. The total order of
> independent events isn't, but we don't need to care about.
Well, you may have to be careful about dependencies, but it's probably
doable. How many queue slots do you plan to have? I guess unlike OS
tasks, these gate operations won't schedule events far in the future, so
you can have small timeslices while still not needing a very large
queue.
> Yes, it could be done that way. The linear version still has ample
> opportunities for tuning.
I suspect the binary heap version also can be tuned. I did finally
manage to look at it and there may be considerable overhead from the OO
stuff and a few other things. You'd know better than me about that
though. Is there a reasonable way to profile it?
>> around 180 connections ("netstat | wc").
> Active, TCP, not waiting? Local AF_UNIX socket connections don't count.
Oh, good point, there are only around 27 connections.
>> I don't know how many is typical for something like BitTorrent.
> Usually in the one-digit order.
Numbers I've seen are higher, but I'm not very knowledgeable about this.
> The algorithm to spead data quickly is "fastest peer
> first". ... Unlike in economy, the "trickle down effect" works in P2P
> networks, it's because there, everybody shares all he has ;-).
"fastest peer" in that case should mean fastest uploader rather than
downloader, I guess.
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-06 17:48 +0200 |
| Subject | Re: Function Points |
| Message-ID | <1685763.6J3xUoe3rs@sunwukong.fritz.box> |
| In reply to | #15495 |
Paul Rubin wrote:
> Bernd Paysan <bernd.paysan@gmx.de> writes:
>> By t2 < t1, all new events get scheduled into queue[1] or later, so
>> the
>> total order of dependent events is maintained. The total order of
>> independent events isn't, but we don't need to care about.
>
> Well, you may have to be careful about dependencies, but it's probably
> doable. How many queue slots do you plan to have? I guess unlike OS
> tasks, these gate operations won't schedule events far in the future,
> so you can have small timeslices while still not needing a very large
> queue.
The worst gate delay you get is the "delay element", and you probably
have to calculate the queue size at netlist read (by the next power of
two). Without the delay element (which is difficult to calculate, as it
is deliberately constructed to be slow), 16 slots should be more than
enough.
>> Yes, it could be done that way. The linear version still has ample
>> opportunities for tuning.
>
> I suspect the binary heap version also can be tuned. I did finally
> manage to look at it and there may be considerable overhead from the
> OO stuff and a few other things.
heap1.fs is without OO stuff.
> You'd know better than me about that
> though. Is there a reasonable way to profile it?
ATM, gforth-prof doesn't build, but the net2o.fs code has a nice timing-
based profiler, which is intented to measure how much time different
activities in the same program consume - search for "timing
measurements".
>>> around 180 connections ("netstat | wc").
>> Active, TCP, not waiting? Local AF_UNIX socket connections don't
>> count.
>
> Oh, good point, there are only around 27 connections.
And most of them are probably just waiting, and therefore wouldn't have
a timeout queued.
>>> I don't know how many is typical for something like BitTorrent.
>> Usually in the one-digit order.
>
> Numbers I've seen are higher, but I'm not very knowledgeable about
> this.
>
>> The algorithm to spead data quickly is "fastest peer
>> first". ... Unlike in economy, the "trickle down effect" works in P2P
>> networks, it's because there, everybody shares all he has ;-).
>
> "fastest peer" in that case should mean fastest uploader rather than
> downloader, I guess.
I would mix it, something like download_time + 2*upload_time, lowest
number gets highest priority. As you usually upload and download at the
same time (leecher mode), you can measure both rates of your peers - how
fast do they upload to you, and how fast can you upload to them.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-09-06 12:01 -0700 |
| Subject | Re: Function Points |
| Message-ID | <7xharb6km0.fsf@ruckus.brouhaha.com> |
| In reply to | #15497 |
Bernd Paysan <bernd.paysan@gmx.de> writes: > heap1.fs is without OO stuff. OK. Is that the one you benchmarked? It still looks pretty painful, e.g. you have index cell / in the bubble-up loop on every insert, which must be painful in an interpreter. I don't know if iforth optimizes this stuff. There's also a word hsize@ that is never used. In the linear version, why is the list kept sorted? The simplest implementation would be an unsorted list, that you scan to find the smallest element. Insertion is then trivial (just append the new element). >> Oh, good point, there are only around 27 connections. > And most of them are probably just waiting, and therefore wouldn't have > a timeout queued. Hm, if TCP keepalive is active then there's a wakeup every 20 minutes or so on each connection, I think.
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-06 22:02 +0200 |
| Subject | Re: Function Points |
| Message-ID | <20108062.GoLiOyeb2o@sunwukong.fritz.box> |
| In reply to | #15500 |
Paul Rubin wrote: > Bernd Paysan <bernd.paysan@gmx.de> writes: >> heap1.fs is without OO stuff. > > OK. Is that the one you benchmarked? I've posted benchmarks of that here, yes. > It still looks pretty painful, e.g. you have > > index cell / > > in the bubble-up loop on every insert, which must be painful in an > interpreter. Unfortunately, there's no standard word that does the opposite of cells. However, index 2/ cell negate and should to it, too. > I don't know if iforth optimizes this stuff. There's > also a word hsize@ that is never used. It's used for the tests. > In the linear version, why is the list kept sorted? The simplest > implementation would be an unsorted list, that you scan to find the > smallest element. Insertion is then trivial (just append the new > element). Yes, but that adds a factor of 2, because you always have to scan the full list. With this insert function, you have to scan half of the list (on average), and scanning is way more expensive than the MOVE to shift the rest. As I said, the linear version has ample opportunities to tune it, and the point to write it is only to show that even though, it is almost as good for up to 256 elements, and it is much more likely to be correct. >>> Oh, good point, there are only around 27 connections. >> And most of them are probably just waiting, and therefore wouldn't >> have a timeout queued. > > Hm, if TCP keepalive is active then there's a wakeup every 20 minutes > or so on each connection, I think. Which is not really a performance-critical issue... -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2012-09-06 14:19 -0700 |
| Subject | Re: Function Points |
| Message-ID | <7xpq5y7sss.fsf@ruckus.brouhaha.com> |
| In reply to | #15502 |
Bernd Paysan <bernd.paysan@gmx.de> writes: > Unfortunately, there's no standard word that does the opposite of cells. > However, > index 2/ cell negate and > should to it, too. Best would be to generate a suitable inlined shift at compile time, I guess. > As I said, the linear version has ample opportunities to tune > it... it is almost as good for up to 256 elements, and it is much more > likely to be correct. The linear version can be tuned (as you mentioned) with binary search to find the insert point, plus O(1) deletion, plus choosing the move direction to average n/4 moves instead of n/2. The log n version can also be tuned a lot, though. I'm not sure what we have really learned. A tuned-vs-tuned version would be more interesting, as would be untuned-vs-untuned (i.e. both versions use OOF with generic ordering) but neither seems worth the effort. >> Hm, if TCP keepalive is active then there's a wakeup every 20 minutes >> or so on each connection, I think. > Which is not really a performance-critical issue... It may be more of an issue when there's a large number of connections.
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2012-09-07 11:30 +0000 |
| Subject | Heap (was: Function Points) |
| Message-ID | <2012Sep7.133003@mips.complang.tuwien.ac.at> |
| In reply to | #15502 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
>Paul Rubin wrote:
>> It still looks pretty painful, e.g. you have
>>
>> index cell /
>>
>> in the bubble-up loop on every insert, which must be painful in an
>> interpreter.
>
>Unfortunately, there's no standard word that does the opposite of cells.
Yes, strange that nobody has proposed CELL/ FLOAT/ SFLOAT/ DFLOAT/
yet. Even stranger that we have not implemented them in Gforth yet.
Concerning optimizations:
1) The IFs in BUBBLE-DOWN are hard to predict and could be replaced
with arithmetic, which might be faster (especially on native-code
systems).
2) It seems to me that the hysteresis of the HRESIZE words is to
tight. In the worst case you have one RESIZE per HINSERT or HDELETE.
>Yes, but that adds a factor of 2, because you always have to scan the
>full list. With this insert function, you have to scan half of the list
>(on average), and scanning is way more expensive than the MOVE to shift
>the rest.
If the list is not in the cache, memory costs dominate, and it's not
clear that scanning N elements is then more expensive than moving N/2
elements.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2012: http://www.euroforth.org/ef12/
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-07 18:12 +0200 |
| Subject | Re: Heap (was: Function Points) |
| Message-ID | <1919083.CyBz4HrjJV@sunwukong.fritz.box> |
| In reply to | #15509 |
Anton Ertl wrote: >>Unfortunately, there's no standard word that does the opposite of >>cells. > > Yes, strange that nobody has proposed CELL/ FLOAT/ SFLOAT/ DFLOAT/ > yet. Even stranger that we have not implemented them in Gforth yet. Yes, the latter is really strange. I have CELL/ in bigForth, but not the float versions. Looking at Gforth's sources, CELL / is used several times, 1 FLOATS / only once. > Concerning optimizations: > > 1) The IFs in BUBBLE-DOWN are hard to predict and could be replaced > with arithmetic, which might be faster (especially on native-code > systems). A native code system could translate an IF DROP somevalue THEN to a movcc. VFX doesn't. > 2) It seems to me that the hysteresis of the HRESIZE words is to > tight. In the worst case you have one RESIZE per HINSERT or HDELETE. The hysteresis is factor 2. Except for empty queues, not many RESIZEs needed. >>Yes, but that adds a factor of 2, because you always have to scan the >>full list. With this insert function, you have to scan half of the >>list (on average), and scanning is way more expensive than the MOVE to >>shift the rest. > > If the list is not in the cache, memory costs dominate, and it's not > clear that scanning N elements is then more expensive than moving N/2 > elements. Move operations are highly optimized. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2012-09-07 16:48 +0000 |
| Subject | Re: Heap (was: Function Points) |
| Message-ID | <2012Sep7.184809@mips.complang.tuwien.ac.at> |
| In reply to | #15513 |
Bernd Paysan <bernd.paysan@gmx.de> writes:
>Anton Ertl wrote:
>> 1) The IFs in BUBBLE-DOWN are hard to predict and could be replaced
>> with arithmetic, which might be faster (especially on native-code
>> systems).
>
>A native code system could translate an IF DROP somevalue THEN to a
>movcc. VFX doesn't.
I think the Forthier approach is to have a selection word, equivalent
to:
: select ( x1 x2 f -- x )
if drop else nip then ;
which would be implemented with movcc.
>> 2) It seems to me that the hysteresis of the HRESIZE words is to
>> tight. In the worst case you have one RESIZE per HINSERT or HDELETE.
>
>The hysteresis is factor 2. Except for empty queues, not many RESIZEs
>needed.
It looks to me that you check for the same size before and after doubling.
E.g., if you check for x before doubling, after doubling hmaxsize is
x*2, and you check for hmaxsize/2, which is x. So if the size wobbles
around x, you get very many RESIZEs.
>> If the list is not in the cache, memory costs dominate, and it's not
>> clear that scanning N elements is then more expensive than moving N/2
>> elements.
>
>Move operations are highly optimized.
If the stuff is not in the cache, memory operations dominate, and it
does not matter whether in-cache moves are highly optimized; they get
swamped by the memory operations.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2012: http://www.euroforth.org/ef12/
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2012-09-07 21:34 +0200 |
| Subject | Re: Heap (was: Function Points) |
| Message-ID | <3808175.85ienseKBW@sunwukong.fritz.box> |
| In reply to | #15514 |
Anton Ertl wrote: >>A native code system could translate an IF DROP somevalue THEN to a >>movcc. VFX doesn't. > > I think the Forthier approach is to have a selection word, equivalent > to: > > : select ( x1 x2 f -- x ) > if drop else nip then ; > > which would be implemented with movcc. We could add one into Gforth, let GCC do the movcc magic, and check if it is worth the effort... If f is a well formed flag, you can do : mux ( x1 x2 flag -- x ) tuck invert and >r and r> or ; and have highly predictable code. >>> 2) It seems to me that the hysteresis of the HRESIZE words is to >>> tight. In the worst case you have one RESIZE per HINSERT or >>> HDELETE. >> >>The hysteresis is factor 2. Except for empty queues, not many RESIZEs >>needed. > > It looks to me that you check for the same size before and after > doubling. > > E.g., if you check for x before doubling, after doubling hmaxsize is > x*2, and you check for hmaxsize/2, which is x. So if the size wobbles > around x, you get very many RESIZEs. Yes, probably. The benchmarks would not exhibit that behavior. >>Move operations are highly optimized. > > If the stuff is not in the cache, memory operations dominate, and it > does not matter whether in-cache moves are highly optimized; they get > swamped by the memory operations. Move operations are even highly optimized for out-of-cache, by having the apropriate prefetchers. You simply get all available bandwidth with a move, and you can't predict if you get the same bandwidth with a scan. Well, maybe you get it, because it's an easy enough to predict pattern. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
Page 7 of 9 — ← Prev page 1 2 3 4 5 6 [7] 8 9 Next page →
Back to top | Article view | comp.lang.forth
csiph-web