From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA08916; Sun, 12 Sep 2004 17:37:55 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA09787 for ; Sun, 12 Sep 2004 17:37:54 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i8CFbspg026265 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sun, 12 Sep 2004 17:37:54 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1C6WQL-0000oZ-CN for caml-list@inria.fr; Sun, 12 Sep 2004 15:37:53 +0000 From: Jon Harrop To: caml users Subject: Re: [Caml-list] Gripes with array Date: Sun, 12 Sep 2004 16:33:38 +0100 User-Agent: KMail/1.6.2 References: <200409090310.29295.jon@jdh30.plus.com> <200409111536.10902.jon@jdh30.plus.com> In-Reply-To: MIME-Version: 1.0 Content-Disposition: inline Message-Id: <200409121633.38389.jon@jdh30.plus.com> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 41446D52.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 2004:99 damien:01 run-time:01 slower:01 synthetic:99 extensible:01 amortized:01 amortized:01 dwt:99 non-float:01 initializing:01 optimising:01 ocamlopt:01 run-time:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Saturday 11 September 2004 21:53, Damien Doligez wrote: > ... Frankly, > I find it hard to imagine that it would give a noticeable run-time > improvement on any program. Most likely, it would make them all a > fraction > of a percent slower, except for the most synthetic of benchmarks. If it let you do extensible arrays safely then it could be used to reduce the asymptotic complexity of array append- or prepend-element from O(n) to amortized O(1) and "i"th insert from O(n) to amortized O(min{i, n-i}). > > No, I don't think the performance improvement would justify your time > > or the > > loss of safety. > > No loss of safety if we don't export that primitive and use it only in > Array.init. After all, it only breaks type safety, and only if you use > it wrong. I was assuming that you would export it. My discrete wavelet transform (DWT) code, for example, is easily proven to fill all array elements but it fills them out of order (I've considered ways to make it fill in-order but they all incur significant performance penalties elsewhere, e.g. lots of swapping). So I was thinking of using unsafe_make for that. Still, I don't think it would be worth your writing it. Having said that, it might be possible to abstract the array lookup and replace it with a clever function to work out where the "i"th element really is. Then you could give Array.init a continuation. Hmm... > > Could you add a memset to String.create though? :-) > > String.make I meant for safety reasons - either don't export String.create or make it safe, e.g. "let create n = make n '\000'". > > An array_init2 function which specialises the array type but uses an > > external > > "f" function betters the time taken by Array.init by ~36% (perhaps not > > significantly different): > > That's from getting rid of the float/non-float test. Nothing to do with > the cost of initializing twice. Yes. Optimising that would be much more productive. Am I right in thinking that ocamlopt doesn't hoist the test out of the loop? Such optimisations would be best done at run-time, e.g. by Basile's JIT. Where is he? ;-) Cheers, Jon. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners