From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: a07f3367d7,56525db28240414a X-Google-Attributes: gida07f3367d7,public,usenet X-Google-NewGroupId: yes X-Google-Language: ENGLISH,ASCII-7-bit Received: by 10.66.85.71 with SMTP id f7mr1356404paz.39.1343264649595; Wed, 25 Jul 2012 18:04:09 -0700 (PDT) Path: b9ni60139614pbl.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: Keean Schupke Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Thu, 19 Jul 2012 03:41:08 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <9d4d4463-4c7e-40f4-a167-933eb056c6a5@googlegroups.com> NNTP-Posting-Host: 91.143.78.202 Mime-Version: 1.0 X-Trace: posting.google.com 1342694871 16737 127.0.0.1 (19 Jul 2012 10:47:51 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Thu, 19 Jul 2012 10:47:51 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=91.143.78.202; posting-account=T5Z2vAoAAAB8ExE3yV3f56dVATtEMNcM User-Agent: G2/1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-07-19T03:41:08-07:00 List-Id: On Wednesday, 18 July 2012 19:11:14 UTC+1, (unknown) wrote: > > - The data structure and algorithm is optimal from a machine operati= on > > perspective (if we consider the relative speeds of the machine code = operations) > Taking into account all the fancy pipelining and multiple arithmetic u= nits > of the machine you are targeting? How fast does this run in hand optimiz= ed > asm code? In terms of algorithm analysis yes. An O(1) algorithm is going to be faster= than an O(N) algorithm no matter what fancy pipelining is involved. Array = index lookup is O(1), tree lookup is O(log(n)). For the groups the complexi= ty of joining groups is O(1) for a linked list and O(N) for an array. For e= ager disjoint set the complexity of finding if two nodes are in the same se= t is O(1). So what we have is a data structure that allows all the dominant operations= to be executed in O(1) time. It is not going to be faster to move to an O(log(N)) tree structure for the= spatial lookup no matter what pipelining the CPU has. >=20 > > If we instead store the index of the next element instead of the li= nk, it > > is slower because we have to use a relative addressing mode instead= of an > > absolute one. > How about storing not only links to other nodes, but have each node als= o > store a copy of its own index. This is a good idea. It will be slower because we have to read an extra val= ue from memory, but we might be able to live with that. What is more of a problem is that the node structure is 32 bytes long, so t= wo nodes fit in a 64bit cache line, and the index operation is shift left b= y 5. Adding the extra Index word will probably slow things down significant= ly, unless we can save some space elsewhere in the structure. I may be able to replace one Integer with a Short_Int, and use a Short_Int = for the index. I think this could be worth trying. >=20 > > to address the neighbours does not make any sense as division is slo= wer > > than multiplication. > That depends. If the divisor is a power of two you can shift. No, it is very unlikely to be a power of two. Besides which turning an acce= ss into an address, and then turning this into an index seems worse than us= ing offset addressing from the access address to find the neighbours. Cheers, Keean.