Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #15422
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | priority queue (was: Function Points) |
| Date | 2012-09-03 11:46 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2012Sep3.134639@mips.complang.tuwien.ac.at> (permalink) |
| References | (7 earlier) <7xwr0d8xab.fsf@ruckus.brouhaha.com> <2000935.ViCZX3HiHH@sunwukong.fritz.box> <7x8vctqvbh.fsf@ruckus.brouhaha.com> <3682218.RpYgJoRDKP@sunwukong.fritz.box> <5883549.frr9YTnbEn@sunwukong.fritz.box> |
Bernd Paysan <bernd.paysan@gmx.de> writes:
>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
[...]
>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 ;-).
How much memory do your 256 elements consume? I would expect that
they fit in the D-cache; if so, any spacial locality from the linear
algorithm should not play a role.
Inserts into the binary heap are equally expensive for 256 elements as
for 4096. Deletes slow down from 1594ns (10) through 1860ns (256) to
2944ns (4096); one would expect something like thi, but the constant
factor appears pretty bad; Gforth is not the fastest system around,
but why would deleting one element cost more than 2000 cycles?
- 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/
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web