(no subject)

[@ 2012-07-26 0:48 UTC (permalink / raw)]

Wed, 25 Jul 2012 17: 48:05 -0700 (PDT)
Path: a15ni101900513qag.0!nntp.google.com!q21no4608003qas.0!news-out.google.com!p10ni52925434pbh.1!nntp.google.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!q21no4607968qas.0!news-out.google.com!b9ni60031287pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!ctu-peer!ctu-gate!news.nctu.edu.tw!usenet.stanford.edu!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
From: Shark8 <onewingedshark@gmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Efficient Sequential Access to Arrays
Date: Wed, 18 Jul 2012 21:50:20 -0700 (PDT)
Organization: http://groups.google.com
Lines: 36
Message-ID: <67643edb-88e9-4fb3-b753-bfc8729f27fe@googlegroups.com>
References: <4c86d54d-dfeb-44f1-9638-3c416ea51d74@googlegroups.com>
 <ju2496$988$1@speranza.aioe.org> <9b134675-b217-4a62-beb1-8b044029aa61@googlegroups.com>
 <9s89w8awedu5.r6kl7s7vwvx9$.dlg@40tude.net> <9d4d4463-4c7e-40f4-a167-933eb056c6a5@googlegroups.com>
NNTP-Posting-Host: 69.20.190.126
Mime-Version: 1.0
X-Trace: posting.google.com 1342673750 27526 127.0.0.1 (19 Jul 2012 04:55:50 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Thu, 19 Jul 2012 04:55:50 +0000 (UTC)
Cc: mailbox@dmitry-kazakov.de
In-Reply-To: <9d4d4463-4c7e-40f4-a167-933eb056c6a5@googlegroups.com>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=69.20.190.126;
 posting-account=lJ3JNwoAAAAQfH3VV9vttJLkThaxtTfC
User-Agent: G2/1.0
Bytes: 2802
X-Received-Bytes: 3041
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On Wednesday, July 18, 2012 2:10:03 AM UTC-6, Keean Schupke wrote:
>=20
> All this is fine, the problem in Ada is this:
>=20
> - When we lookup an element spatially by index, and then iterate through =
the subset members (following the next links) we lose the ability to index =
spatially from the next element.
>=20
> - If we instead store the index of the next element instead of the link, =
it is slower because we have to use a relative addressing mode instead of a=
n absolute one.

Then perhaps you should have things laid out a bit differently?
Would dividing things along the group & space help?
ex: Type Space is array( [Indices] ) of Group;

Or, like someone else posted, you could have nodes store their own indices.=
=20

>=20
> - The compiler cannot use any optimisation of the array indexing because =
the index comes from main-memory. It is not stepping through in sequence so=
 it cannot use strength reduction. There is no point in reading compiler do=
cumentation, this is beyond any current optimisation technology to do this,=
 and no amount of shuffling the code about will change this.

Why can't you put the indexing-portion into a subprogram?

procedure Index( Memory_Location : Index_type_or_whatever ) Return Index_Ty=
pe is=20
begin
  Return Result : Index_Type:=3D [calculations];
end Index;

In that case the function should be optimizable and inlinable, right?