Contributed to the public domain by Chad McQuinn & Joe Strout
Updated Jun 6, 2004
When working
with arrays, which is faster: Dim or Append?
Chadd McQuinn writes:
There are several
factors to consider here. The first is that your redim(-1) might not really do
anything behind the scenes; the array might still hold onto whatever memory it
had allocated for storing its contents (all behind your back).
As for Append not coming out that much different in an amortized test; that doesn't
surprise me. A common technique in this situation is for the implementation of
array to start out with a certain amount of internal memory allocated; when it
needs more, it doubles that internal capacity. This gives amortized constant time
for an operation like Append; the key word is "amortized". In this case there
is a single Append operation that is going to take a long time, and the rest will
be rather quick (up to the next necessary reallocation).
For such implementations, there might not be a big performance difference overall
between appending each element, and preallocating space for all of them. The functional
difference is that with the first method, you pay your penalties at multiple unknown
times, and with the second, you pay up front at a known time.
As for why the results are so different on Macintosh vs. Windows, there are several
things that could explain this. The first is that memory allocation on Mac OS
X is still *very, very* slow compared to virtually every other operating system.
Another might be internal differences in the way arrays are implemented on each
platform.
I ran tests on a dual 1GHz Macintosh G4, and got significantly better numbers
than the 1.3GHz Athlon for all but the Dim test; you were comparing a 400MHz G4
so there might not really be any cross-platform difference at all (again, except
for Dim). Someone with a G5 could probably blow the doors off this test, since
it's memory bound and the G5 has memory bandwidth that is through the roof.
Joe Strout responds:
I
was going to post some comments on this thread, but then found that Chad had already
said everything I was going to say and more. (And Chad's guess about how Array.Append
works is quite correct, as of RB 5.5.)