From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id AAA04829 for caml-redistribution; Mon, 11 Oct 1999 00:30:13 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA12188 for ; Sun, 10 Oct 1999 23:44:06 +0200 (MET DST) Received: from babbage.ececs.uc.edu (babbage.ececs.uc.edu [129.137.8.2]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id XAA26032 for ; Sun, 10 Oct 1999 23:44:00 +0200 (MET DST) Received: from artemis.ececs.uc.edu (artemis.ececs.uc.edu [129.137.10.46]) by babbage.ececs.uc.edu (8.9.3/8.9.3) with ESMTP id RAA11205; Sun, 10 Oct 1999 17:43:54 -0400 (EDT) Received: from localhost (hwxi@localhost) by artemis.ececs.uc.edu (8.9.1b+Sun/8.9.1) with SMTP id RAA05320; Sun, 10 Oct 1999 17:43:49 -0400 (EDT) X-Authentication-Warning: artemis.ececs.uc.edu: hwxi owned process doing -bs Date: Sun, 10 Oct 1999 17:43:48 -0400 (EDT) From: Hongwei Xi Reply-To: Hongwei Xi To: William Chesters cc: caml-list@inria.fr Subject: Re: Stdlib regularity In-Reply-To: <24938.199910102044@buckie> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE Sender: weis Yes, I agree with the argument. It is not clear to me that there is a significant amount of efficiency lost on array initialization, which is always a one-time thing. Is there any convincing data to support otherwise? However, there is one case which could result in some significant loss of efficency (I learned this from Robert Harper). The case is where you represent a sparse array using an (ordinary) array representation (for quick access). This means O(n^2) time is to be spent on initialization, which may contribute to a significant portion of the entire running time of some program. Cheers, --Hongwei \~~~~/ \\ // \\ // @ Mail: hwxi@ececs.uc.edu C-o^o, ))__|| \\__//_ // \\ Url: http://www.ececs.uc.edu/~hwxi ( ^ ) ))__|| \--/-\\ \\ Tel: +1 513 871 4947 (home) / \V\ )) || // \\ \\ Tel: +1 513 556 4762 (office) ------ // || o // \\ \\//Fax: +1 513 556 7326 (department) Rhodes Hall 811-D Department of ECE & CS University of Cincinnati P. O. Box 210030 Cincinnati, OH 45221-0030 On Sun, 10 Oct 1999, William Chesters wrote: > skaller writes: > > =09No. This isn't necesarily the case. There are other > > solutions. In C++, the philosophy is to provide as much protection > > as possible, without costing at run time, and with protection > > that does cost at run time being optional. > > Are you sure that initialising arrays etc. carries enough cost to be > worth avoiding? After all, one of the two problems, namely the > requirement to keep legal values in slots at all times, is quite easy > to work around when you have to---my basic Vector is about 100 lines, > generously spaced---while the other, performance, worry seems a priori > likely to be misplaced, because if you are constructing an array then > your time complexity is presumably at least k=D7n for some nontrivial k, > so that the extra few instructions =D7 n are unlikely to make a big > difference to the overall program, however annoying they look "in the > small". > > ocaml already goes some way beyond what C++ considers acceptible > inefficiency. That's fine for a vast number of applications on modern > desktop hardware. >