relative benefit of .reserve and .length
Steven Schveighoffer via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Thu Apr 28 07:08:26 PDT 2016
On 4/28/16 8:56 AM, Jay Norwood wrote:
> I timed some code recently and found that .reserve made almost no
> improvement when appending. It appears that the actual change to the
> length by the append had a very high overhead of something over 200
> instructions executed, regardless if the .reserve was done. This was a
> simple append to an integer array.
.reserve should make an improvement for large amount of appending, since
you pre-allocate the data.
However, the operation to append is still quite slow, it involves
calling a druntime function that cannot be inlined, and must do a bunch
of operations to lookup the current defined length in the array. The way
I look at it is a compromise between efficiency and convenience (the
fact that you can simply append to any slice anywhere is liberating). In
my experience, the appending operation was slower before my changes to
the runtime (and .reserve was added at that time). What .reserve does is
prevent the incremental allocation growth and copying the data from one
block to another (not to mention less strain on the GC). It does not
reduce the function calls or the lookup of metadata.
Let's say you are appending 100,000 integers to an array. At 50,000, it
cannot extend any more, so it must allocate a new block. This means the
GC must find a larger block (in addition to the ones it has already
incrementally allocated to get to 50,000) to accommodate the data, and
then copy all the data over. This is the operation that is saved with
.reserve.
> The only way I found to avoid this was to set the length outside the
> loop and update the array values by index. That was on the order of 10x
> faster.
This is ALWAYS going to be much faster, as setting an element is 2
instructions at the most. That vs. a runtime call is always going to win.
If you can do it this way, I'd recommend doing so. Array appending
operation is for convenience, at a reasonable performance.
-Steve
More information about the Digitalmars-d-learn
mailing list