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-Language: ENGLISH,ASCII Path: g2news2.google.com!postnews.google.com!c29g2000yqd.googlegroups.com!not-for-mail From: jonathan Newsgroups: comp.lang.ada Subject: Re: Ada Shootout program for K-Nucleotide (patches) Date: Fri, 21 Aug 2009 14:43:46 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <4a743343$0$32674$9b4e6d93@newsspool2.arcor-online.net> <4bc4b12d-40f8-4140-8ef6-326d9e6b8adf@k30g2000yqf.googlegroups.com> <4a897b61$0$30221$9b4e6d93@newsspool1.arcor-online.net> <4d48b846-bb2d-4126-86c2-487b2244c9ad@d4g2000yqa.googlegroups.com> <4a8c119d$0$31866$9b4e6d93@newsspool3.arcor-online.net> <9b7557ca-df60-4d70-b692-f077b71983eb@g10g2000yqh.googlegroups.com> <6f1c440c-9941-4aa7-a4cd-bf02a00db49a@g1g2000vbr.googlegroups.com> <4a8c8fc8$0$32678$9b4e6d93@newsspool2.arcor-online.net> <5581b105-4c1c-4772-8657-34c5bcfeb6f1@v20g2000yqm.googlegroups.com> <4a8dcb11$0$31873$9b4e6d93@newsspool3.arcor-online.net> NNTP-Posting-Host: 143.117.23.126 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1250891026 24440 127.0.0.1 (21 Aug 2009 21:43:46 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Fri, 21 Aug 2009 21:43:46 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: c29g2000yqd.googlegroups.com; posting-host=143.117.23.126; posting-account=Jzt5lQoAAAB4PhTgRLOPGuTLd_K1LY-C User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux x86_64; en-GB; rv:1.9.0.12) Gecko/2009072220 Iceweasel/3.0.6 (Debian-3.0.6-1),gzip(gfe),gzip(gfe) Xref: g2news2.google.com comp.lang.ada:7953 Date: 2009-08-21T14:43:46-07:00 List-Id: On Aug 20, 11:15=A0pm, Georg Bauhaus wrote: > jonathan wrote: > > =A0 Key.Data(1 .. Length) :=3D Buffer (I-Length+1 .. I); > > > The string Key.Data already contains most of the desired > > data. Since Buffer may be in slower memory, and Key.Data > > in very fast memory, it makes sense to update > > Key.Data from itself whenever possible: > > Maybe, then, it is worthwhile loading a page worth > of characters from the big string for the next round > of fill-up completions? =A0If this loading doesn't happen > perfectly anyway, that is. > > Or if we are at it, we might experiment with slice renamings > or pointer artihmetic; requires a rewrite, I'd think. > If the rules permit this at all ;-) I did make another attempt here. I made the string: type Bounded_String is record Data : String(1 .. Max_String_Length); First : Natural; Last : Natural; end record; Now make Max_String_Length large, and if you want to slide array Data a distance Shift_Length all you have to do in most cases is increment First and Last by Shift_Length. This essentially removed all the overhead in sliding array Data. I was very pleased with myself. (And again astonished at how much an Ada compiler can do to help you get it right.) Unfortunately, it slowed the program down quite a bit. I think it just made the string "=3D" more complicated and slower. SO I've happily dropped that approach. I'll be off-line for a few days, so let me summarize what we have. The program is in good shape and very fast. Martin Krischik wrote a good program, and we've now added a light-weight string, inlined a few things by hand, and worked around a GNAT 4.3.3 problem by using unbound strings. Here's a rough speed estimate, single-core version. My Intel quad core is similar to the benchmarking machine, just more MHz. knucleotide.adb runs in ~33 sec on my machine (either GNAT 4.3.2 or GNAT 4.3.4). I would expect it to run a bit above 40 sec on the benchmarking machine. On the benchmarking machine the top entries have running times of: 20 sec, 43 sec, 48 sec, and 55 sec. Most entries are much slower. So knucleotide.adb is very respectible by my estimate. Here's how I made that speed estimate. I took the faster-than-light (20 second) entry and compiled it on my quad-core: g++ -O3 -I ../boost/boost_1_36_0 -fopenmp knucleotide.c++ It ran in 16 sec on my machine, 20 sec on the benchmarking machine. If that ratio holds, knucleotide.adb runs in 40 sec on the benchmarking machine. (By the way, I can't make head or tails of the source code of knucleotide.c++. It doesn't help that I don't know c++;) It seems to be designed to make good use of OpenMP style multiprocessing, but resemblance to the original benchmark is somewhat obscure. Still I am very impressed, and I wonder how it works so well.) Anyone who wants to report bugs or offer improvements can find my single-core only version (knucleotide_3.adb) at http://web.am.qub.ac.uk/users/j.parker/ in directory bench_depository. Georg has given his site in the 1st post in this thread. Jonathan