From h.wickham at gmail.com  Sun Mar 25 15:43:22 2007
From: h.wickham at gmail.com (hadley wickham)
Date: Sun, 25 Mar 2007 08:43:22 -0500
Subject: [Rd] [R] How to create a list that grows automatically
In-Reply-To: <Pine.LNX.4.64.0703251133310.1260@gannet.stats.ox.ac.uk>
References: <9a2a73210703090808x2fd9ce77i4537d3428045c061@mail.gmail.com>
	<f8e6ff050703091121u4fb3d109yf5eeac6bfdd9661@mail.gmail.com>
	<Pine.LNX.4.64.0703251133310.1260@gannet.stats.ox.ac.uk>
Message-ID: <f8e6ff050703250643r4a578289m19ad9dc2cd8c7757@mail.gmail.com>

On 3/25/07, Prof Brian Ripley <ripley at stats.ox.ac.uk> wrote:
> [Moved to R-devel for a technical comment.]
>
> On Fri, 9 Mar 2007, hadley wickham wrote:
>
> >> I would like to know if there is a way to create a list or an array (or
> >> anything) which grows automatically as more elements are put into it. What I
> >> want to find is something equivalent to an ArrayList object of Java
> >> language. In Java, I can do the following thing:
> >>
> >> // Java code
> >> ArrayList myArray = new ArrayList();
> >> myArray.add("object1");
> >> myArray.add("object2");
> >> ....
> >> // End of java code
> >
> > As others have mentioned, you can do this with lists in R.
> >
> > However, there is an important difference between ArrayLists in Java
> > and Lists in R.  In Java, when an ArrayList grows past its bound, it
> > doesn't allocate just enough space, it allocates a lot more, so the
> > next time you allocate past the end of the array, there's space
> > already reserved.  This gives (IIRC) amortised O(n) behaviour.  R
> > doesn't do this however, so has to copy the entire array every time
> > giving O(n^2) behaviour.
>
> In fact this is an implementation detail.  R has both 'length' and
> 'truelength' fields in its headers for vectors (including lists) and could
> grow the allocation in the same way as you report Java does.  When I asked
> Ross what the intention had been (the 'truelength' field is almost unused)
> he mentioned this potential usage.  Given that these structures are opaque
> to all but R internal code it should not be hard to change R's scheme to
> over-allocate: to decide how much to do would be harder (but say rounding
> vectors in the large allocation class up to a VM page would get a
> noticeable benefit in some usages with a negligible impact on memory
> footprint).  Backwards compatibility of save() format would be an issue.

Interesting - it would be fascinating (but difficult!) to find out how
much such a change would affect the average running time of all R
code.

> It seems the really inefficient uses are of the type
>
> x <- NULL
> for(i in 1:10000) x <- c(x, fn(i))
>
> and those would be unaltered.

Does R do any manipulations of the AST after the code has been parsed?
 If it did, wouldn't it be fairly easy to recognise this idiom and
optimise it to x[length(x) + 1] <- fn(i) ?  It has something of the
flavour of tail recursion optimisation.  Maybe this is something that
Luke is working on in his byte-code compiler.

Hadley



[Rd] [R] How to create a list that grows automatically
hadley wickham