Re: Stdlib regularity

[Hongwei Xi <hwxi@ececs.uc.edu>]

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:
>  > 	No. 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×n for some nontrivial k,
> so that the extra few instructions × 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.
>