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.68.191.137 with SMTP id gy9mr3083702pbc.6.1343099289748; Mon, 23 Jul 2012 20:08:09 -0700 (PDT) Path: b9ni44054588pbl.0!nntp.google.com!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!novia!feeder3.cambriumusenet.nl!feed.tweaknews.nl!85.12.40.138.MISMATCH!xlned.com!feeder5.xlned.com!feed.xsnews.nl!border-3.ams.xsnews.nl!border4.nntp.ams.giganews.com!border2.nntp.ams.giganews.com!border3.nntp.ams.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!news.nobody.at!news.glorb.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Keean Schupke Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Wed, 18 Jul 2012 01:10:03 -0700 (PDT) Organization: http://groups.google.com Message-ID: <9d4d4463-4c7e-40f4-a167-933eb056c6a5@googlegroups.com> References: <4c86d54d-dfeb-44f1-9638-3c416ea51d74@googlegroups.com> <9b134675-b217-4a62-beb1-8b044029aa61@googlegroups.com> <9s89w8awedu5.r6kl7s7vwvx9$.dlg@40tude.net> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1342599097 10939 127.0.0.1 (18 Jul 2012 08:11:37 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Wed, 18 Jul 2012 08:11:37 +0000 (UTC) Cc: mailbox@dmitry-kazakov.de In-Reply-To: <9s89w8awedu5.r6kl7s7vwvx9$.dlg@40tude.net> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=82.44.19.199; posting-account=T5Z2vAoAAAB8ExE3yV3f56dVATtEMNcM User-Agent: G2/1.0 X-Original-Bytes: 6077 X-Received-Bytes: 6425 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-07-18T01:10:03-07:00 List-Id: On Tuesday, 17 July 2012 10:01:59 UTC+1, Dmitry A. Kazakov wrote: > On Mon, 16 Jul 2012 23:40:21 -0700 (PDT), Keean Schupke wrote: >=20 > > The real problem is that each element needs to be addressed spatiall= y (say > > as a 2D grid) so that all 4 direct, and 4 diagonal neighbours can be > > quickly found (using indexed-addressing), another is that we need to= be > > able to tell if any two elements are in the same group (using disjoi= nt-set > > union-find), and another is that we need to be able to iterate throu= gh all > > the members of a group given any element in that group. > >=20 > > If there is a faster data structure that meets all those requirement= s, then I am listening. >=20 > Depends on details. >=20 > k-d trees might be worth looking. >=20 > Less known are "pyramid" structures (used in image processing, = filtering, > compression). >=20 > For image segmenting, e.g. by area growing (8th-neighbourhood), one > sometimes uses recursive elements permutations like (1,1) (1,2) (2,1) (2,= 2) > (1,3) (1,4) (2,3) (2,4). That allows to perform segmenting in strictly > consequent order visiting each pixel once. I remember it was popular in > PDP-11 days when integer multiplication was indeed expensive. >=20 > --=20 > Regards, > Dmitry A. Kazakov > http://www.dmitry-kazakov.de A tree structure is going to be slower than an array for the spatial lookup= part. Indexing is faster than links (I think you said so yourself). So why= suggesting a linked structure to replace the array? One reason we use links to represent the groups is that by using a cirular = list we can join two groups together very quickly using an exchange. If X i= s any element from the first circular list, and Y any element from the seco= nd circular list we can join the two into a single circular list by doing: T :=3D X.Next; X.Next =3D Y.Next; Y.Next :=3D T; -- or Swap(X.Next, Y.Next) And yes, joining groups is the most frequent operation on the groups, so co= pying one group into the other using arrays is slower. So 2D spatial indexing (array structure) is optimal for spatial lookup. Cir= cular lists between element is optimal for joining groups. The link to the = canonical element from the eager-union algorithm is optimal for lookup domi= nated disjoint set. So you can see the data structure is already optimal for the operations fre= quently required. It is an array of elements that contain a next element po= inter to implement a circular linked list and a canonical element pointer t= o identify the sub-set. So we have the algorithm, and the data structure, which is optimal from an = analytical perspective. Some observations: - The data structure and algorithm is optimal from a machine operation pers= pective (if we consider the relative speeds of the machine code operations) - If the language cannot encode this structure, it cannot get the fastest p= erformance as the language cannot be faster than the machine code operation= s. - I may have misdirected people by looking at the loop behaviour of index o= ptimisation. In my tests it is just as fast as pointer arithmetic. The real= problem is that we need to combine the circular linked list into the array= and allow addressing of neighbours from the resulting pointer dereference. All this is fine, the problem in Ada is this: - When we lookup an element spatially by index, and then iterate through th= e subset members (following the next links) we lose the ability to index sp= atially from the next element. - 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 an = absolute one. - The compiler cannot use any optimisation of the array indexing because th= e index comes from main-memory. It is not stepping through in sequence so i= t cannot use strength reduction. There is no point in reading compiler docu= mentation, this is beyond any current optimisation technology to do this, a= nd no amount of shuffling the code about will change this. - doing a division to convert the address of the next node back into an ind= ex to address the neighbours does not make any sense as division is slower = than multiplication. - The conclusion is the optimal way to do this is to access the neighbours = by using the 'access' stored in the next pointer, and calculate the memory = location of the neighbours by address arithmetic. - We need to package this into an ADT to hide all the address stuff so it c= an be unit tested and validated in isolation from the rest of the applicati= on. Does that make sense? Cheers, Keean.