From: Keean Schupke <keean.schupke@googlemail.com>
Cc: mailbox@dmitry-kazakov.de
Subject: Re: Efficient Sequential Access to Arrays
Date: Sun, 15 Jul 2012 13:03:12 -0700 (PDT)
Date: 2012-07-15T13:03:12-07:00 [thread overview]
Message-ID: <44f2bfd0-75ed-4b9c-982e-61d5308f9c01@googlegroups.com> (raw)
In-Reply-To: <kpltof5a8xvm.arygetd4esmc.dlg@40tude.net>
On Sunday, 15 July 2012 20:48:35 UTC+1, Dmitry A. Kazakov wrote:
> On Sun, 15 Jul 2012 11:40:08 -0700 (PDT), Keean Schupke wrote:
>
> > However in order to achieve this performance I needed to rework the arrays
> > as the use of Indexes was too slow.
>
> You have to measure it in order to know. Write two variants and compare
> their performance.
Have done, the difference is about 10k simulations per second.
>
> > An example of this is lets say we are
> > accessing element 5 from array A "A(5)" this requires a multiplication to
> > access (base_address + index * record_size).
>
> It does not, because 5 is constant.
Obviously the index is not actually a constant but the result of selecting a random element in the list. The multiplication is necessary for finding this first element, but the operations on relative elements (+/-1, +/-2 etc) can use addition with a pointer, not so with an index.
>
> > To access the neighbour A(6)
> > also requires a multiplication. Accessing the array sequentially requires
> > a multiplication per step.
>
> That depends on loop optimizations. I would expect GCC to optimize access
> to array elements per the loop's index.
It does not seem to, I'll see if I can post some assembly.
>
> > So assuming we need this level of performance, what would be the best (and
> > most idiomatic Ada)
>
> Indexing is unlikely to have a significant (>5%) influence on overall
> performance. Usually it is other things.
It seems to have an significant influence in the benchmarks I have run and has a particular influence when sequentially accessing elements.
>
> > way to package this type of usage pattern as an
> > abstract datatype?
>
> Array of aliased elements, to ensure elements independently addressable.
Yes, the type itself will need to have aliased elements, but I was assuming this would be hidden in a package as an ADT, and would expose an indexed-iterator that has '+' and '-' operations on the iterator (not just a forward or bidirectional iterator).
Cheers,
Keean.
next prev parent reply other threads:[~2012-07-22 23:29 UTC|newest]
Thread overview: 88+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-07-15 18:40 Efficient Sequential Access to Arrays Keean Schupke
2012-07-15 19:48 ` Dmitry A. Kazakov
2012-07-15 20:03 ` Keean Schupke [this message]
2012-07-15 20:56 ` Keean Schupke
2012-07-16 11:34 ` Jacob Sparre Andersen
2012-07-15 21:05 ` tmoran
2012-07-15 21:08 ` Keean Schupke
2012-07-16 1:19 ` tmoran
2012-07-15 21:44 ` Georg Bauhaus
2012-07-16 7:47 ` Dmitry A. Kazakov
2012-07-16 10:16 ` Keean Schupke
2012-07-16 14:57 ` Dmitry A. Kazakov
2012-07-16 16:39 ` Keean Schupke
2012-07-16 17:02 ` Georg Bauhaus
2012-07-16 18:48 ` Dmitry A. Kazakov
2012-07-16 19:12 ` Keean Schupke
2012-07-17 6:31 ` Dmitry A. Kazakov
2012-07-17 6:50 ` Georg Bauhaus
2012-07-17 8:42 ` Dmitry A. Kazakov
2012-07-17 7:24 ` Keean Schupke
2012-07-16 19:43 ` John B. Matthews
2012-07-16 20:44 ` Keean Schupke
2012-07-16 22:23 ` tmoran
2012-07-17 6:40 ` Keean Schupke
2012-07-17 9:01 ` Dmitry A. Kazakov
2012-07-18 8:10 ` Keean Schupke
2012-07-18 18:11 ` tmoran
2012-07-19 10:41 ` Keean Schupke
2012-07-19 11:18 ` Georg Bauhaus
2012-07-19 19:58 ` Keean Schupke
2012-07-21 8:24 ` Keean Schupke
2012-07-21 11:52 ` Georg Bauhaus
2012-07-21 16:14 ` Keean Schupke
2012-07-21 17:09 ` Keean Schupke
[not found] ` <i78m081tccmp078spmsei1l5vnj3k0kbkj@invalid.netcom.com>
2012-07-22 15:50 ` Keean Schupke
2012-07-22 5:13 ` Shark8
2012-07-15 21:35 ` J-P. Rosen
2012-07-15 19:52 ` Shark8
2012-07-15 20:16 ` Keean Schupke
2012-07-15 21:33 ` Georg Bauhaus
2012-07-17 18:16 ` Florian Weimer
2012-07-22 10:01 ` robin.vowels
2012-07-30 6:31 ` Jacob Sparre Andersen
2012-07-30 7:16 ` Keean Schupke
2012-07-30 9:20 ` Georg Bauhaus
2012-07-30 14:04 ` Keean Schupke
2012-07-22 10:09 ` robin.vowels
2012-07-22 16:02 ` Keean Schupke
2012-07-22 16:21 ` Florian Weimer
2012-07-22 16:46 ` Keean Schupke
2012-07-22 18:41 ` Florian Weimer
2012-07-24 8:21 ` Keean Schupke
2012-07-22 17:34 ` Niklas Holsti
2012-07-22 18:21 ` Keean Schupke
2012-07-30 14:18 ` Jacob Sparre Andersen
2012-07-24 16:00 ` robin.vowels
2012-07-25 7:09 ` Niklas Holsti
2012-07-25 9:03 ` Keean Schupke
2012-07-26 0:15 ` Randy Brukardt
2012-07-26 8:38 ` Keean Schupke
2012-07-26 10:10 ` Brian Drummond
2012-07-26 12:32 ` Keean Schupke
2012-07-26 13:46 ` Dmitry A. Kazakov
2012-07-26 17:40 ` Shark8
2012-07-26 18:56 ` Dmitry A. Kazakov
2012-07-27 5:25 ` Shark8
2012-07-27 6:28 ` Dmitry A. Kazakov
2012-07-27 7:01 ` Vasiliy Molostov
2012-07-27 8:48 ` Dmitry A. Kazakov
2012-07-27 12:01 ` Georg Bauhaus
2012-07-27 16:49 ` Vasiliy Molostov
2012-07-27 19:38 ` Dmitry A. Kazakov
2012-07-28 5:32 ` Shark8
2012-07-28 7:37 ` Dmitry A. Kazakov
2012-07-28 18:32 ` Shark8
[not found] ` <6ov218tnkbqu3vpkuo4t77rd7de0a3aesf@invalid.netcom.com>
2012-07-26 18:49 ` Dmitry A. Kazakov
[not found] ` <86d31898ne39maimbl24knds7rf38qg7vc@invalid.netcom.com>
2012-07-27 6:45 ` Dmitry A. Kazakov
2012-07-27 8:21 ` Keean Schupke
2012-07-27 8:50 ` Dmitry A. Kazakov
2012-07-27 9:17 ` Keean Schupke
2013-02-25 21:18 ` Eryndlia Mavourneen
2012-07-26 13:08 ` Georg Bauhaus
2012-07-26 19:37 ` stefan-lucks
2012-07-26 19:21 ` stefan-lucks
2012-07-31 3:12 ` Randy Brukardt
2012-07-26 7:11 ` Markus Schöpflin
2012-07-26 14:47 ` Robin Vowels
2012-07-26 15:18 ` Martin
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox