Implementing and optimizing a simple graph metric
Joseph Rushton Wakeling
joseph.wakeling at webdrake.net
Thu Sep 26 13:43:38 PDT 2013
On Tuesday, 24 September 2013 at 22:14:30 UTC, bearophile wrote:
> minimallyInitializedArray is not stupid, if the specified type
> has no indirections, it's equivalent to using
> uninitializedArray, but it's safer if you later change the
> type. So in general it's not a good idea to use
> uninitializedArray, unless you have special needs. The two
> functions are not equivalent, one of them is for normal
> performance tuning, and the other is for special usages.
I have not found this -- using minimallyInitializedArray for the
arrays of built-in types is slower than if I use
These arrays have their values initialized immediately -- this is
the actual code from inside the betweenness centrality function:
size_t stack = uninitializedArray!(size_t)(g.vertexCount);
T sigma = uninitializedArray!(T)(g.vertexCount);
T delta = uninitializedArray!(T)(g.vertexCount);
long d = uninitializedArray!(long)(g.vertexCount);
auto q = VertexQueue(g.vertexCount);
Appender!(size_t) p =
sigma = to!T(0);
delta = to!T(0);
d = -1L;
... so I don't see the safety problem here. uninitializedArray
is used only for arrays of built-in types,
minimallyInitializedArray is used otherwise.
>> On the other hand, if inside the VertexQueue implementation, I
>> replace the "new" declaration with an uninitializedArray call,
>> the code gets slower by a noticeable amount.
>> Very odd -- any ideas why that might be?
> See above, use uninitializedArray only in special situations
> and when you know what you are doing. Here you do not know what
> you are doing, so use minimallyInitializedArray.
uninitializedArray or minimallyInitializedArray, using either
inside the VertexQueue creates a significant slowdown.
> uninitializedArray creates random pointers, and aliases that
> could increase the work done by the GC and cause (temporary if
> you initialized all your data) memory leaks. Try to totally
> disable the GC and time the two versions of the code, with and
> without uninitializedArray. If the GC is the cause of speed
> differences and you disable it, you will see no performance
> difference any more.
You seem to be suggesting that using uninitializedArray could
cause general slowdown, but in general it results in a speedup
compared to minimallyInitializedArray.
In the one case where it causes a slowdown,
minimallyInitializedArray does too, and by a similar amount.
More information about the Digitalmars-d-announce