Re: Stdlib regularity

From: Hongwei Xi (hwxi@ececs.uc.edu)
Date: Sun Oct 10 1999 - 23:43:48 MET DST


Date: Sun, 10 Oct 1999 17:43:48 -0400 (EDT)
From: Hongwei Xi <hwxi@ececs.uc.edu>
To: William Chesters <williamc@dai.ed.ac.uk>
Subject: Re: Stdlib regularity
In-Reply-To: <24938.199910102044@buckie>

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.
>



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:26 MET