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 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: a07f3367d7,3a6a9f1d654285ba X-Google-Attributes: gida07f3367d7,public,usenet X-Google-NewGroupId: yes X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news2.google.com!news.glorb.com!feed.news.qwest.net!mpls-nntp-05.inet.qwest.net!216.196.98.141.MISMATCH!border2.nntp.dca.giganews.com!nntp.giganews.com!backlog2.nntp.dca.giganews.com!nntp.sun.com!news.sun.com.POSTED!not-for-mail NNTP-Posting-Date: Tue, 01 Sep 2009 07:11:38 -0500 Newsgroups: comp.lang.ada Subject: Re: Ada Shootout program for K-Nucleotide (patches) References: <4a743343$0$32674$9b4e6d93@newsspool2.arcor-online.net> <0c18b36c-7af0-454c-8208-9b0416111a1f@w41g2000yqb.googlegroups.com> <4a758ce2$0$31338$9b4e6d93@newsspool4.arcor-online.net> <4a967b33$0$32671$9b4e6d93@newsspool2.arcor-online.net> <4a9d06b9$0$30234$9b4e6d93@newsspool1.arcor-online.net> From: Ole-Hjalmar Kristensen Organization: Sun Microsystems Date: 01 Sep 2009 14:11:37 +0200 Message-ID: User-Agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/21.2 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cache-Post-Path: news1nwk!unknown@khepri42.norway.sun.com X-Cache: nntpcache 3.0.1 (see http://www.nntpcache.org/) X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-BKQrIEgLZhcsFH24YkemmqWP2otHOu3icqGHcGSoio6xizaCqMbHpKwcPfu9xwEtyfM+4wCrBvZRauK!TW4nyFWkmip69JglgnNx2ogybxiVPco6e808AhYmsF4pbmmEyw+KBO1x X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.39 Xref: g2news2.google.com comp.lang.ada:8099 Date: 2009-09-01T14:11:37+02:00 List-Id: >>>>> "GB" == Georg Bauhaus writes: I think the problem is not the explicit copy which happens when we hit the end of the buffer (easily verified, just increase the buffer size 10 times, the copying will happen 1/10 of the time, but execution time stays the same), but the implicit copy which seems to happen in the statement return In_Buf(Start..I-1); I do not know if this copy is unavoidable, or if the compiler could have optimized it away. The idea of using a storage pool is an interesting one, since it could allow you to avoid copying when you want to return a string from a function. But how would you overlay the string on top of the read buffer? An Ada string is not a C string, you would need to put the descriptor somewhere as well. GB> Ole-Hjalmar Kristensen schrieb: >> astra06:~/ada/div-ada> uname -a >> SunOS astra06 5.10 Generic_137137-09 sun4u sparc SUNW,Sun-Fire-V440 >> astra06:~/ada/div-ada> ls -l x.txt >> -rw------- 1 ok145024 clustra 60000000 Sep 1 12:03 x.txt >> astra06:~/ada/div-ada> time ./get_line_test < x.txt >> 0.49u 0.09s 0:00.59 98.3% >> GB> Comparing the two programs, they are on a par, almost GB> exactly. GB> However, yours is IMHO less messy. It also has GB> return Copy & Get_Line; GB> which, I guess, solves the problem of long lines, even GB> at the expense of copying. GB> Can we reduce the copying overhead? GB> The copying would be have O(f(Item'Length)) with GB> f(n) ~= s*(s+1)/2 where s = n/BUFSIZ, so it is in O(n**2). GB> We could, I think, use a storage pool: GB> - whenever copying is needed, allocate another buffer GB> right next to the current buffer. Use the newly allocated GB> buffer for the recursive call. GB> - on reaching of line/file, reinterpret the sequence of GB> buffers in the storage pool as a String. Finally, Free. GB> Can this be done? GB> (This won't make a Shootout program any smaller, but GB> seems good for the general case...) -- C++: The power, elegance and simplicity of a hand grenade.