Implementing and optimizing a simple graph metric

[Joseph Rushton Wakeling]

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 
uninitializedArray.

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 = 
minimallyInitializedArray!(Appender!(size_t[])[])(g.vertexCount);

     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.