Joseph Rushton Wakeling:

> As an experiment I tried something along these lines -- using uninitializedArray for most of the arrays here and minimallyInitializedArray for p.

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.


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

Bye,
bearophile

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.

Joseph Rushton Wakeling:

> I have not found this -- using minimallyInitializedArray for the arrays of built-in types is slower than if I use uninitializedArray.

Then minimallyInitializedArray should be improved :-)


> You seem to be suggesting that using uninitializedArray could cause general slowdown,

I am saying that in general uninitializedArray is less safe.

Bye,
bearophile

On Thursday, 26 September 2013 at 20:56:39 UTC, bearophile wrote:
> Joseph Rushton Wakeling:
>
>> I have not found this -- using minimallyInitializedArray for the arrays of built-in types is slower than if I use uninitializedArray.
>
> Then minimallyInitializedArray should be improved :-)

It's odd, because the two actually use the same underlying function, with minimallyInitializedArray potentially triggering this section:

    else static if(minimallyInitialized && hasIndirections!E)
    {
        ret[] = E.init;
    }

... but if E is (say) an int, or a size_t, or any other built-in type, this should not be triggered -- right?

So it's bizarre that there is a performance difference here.

Incidentally, this was why I felt safe using uninitializedArray for arrays of e.g. long, size_t, etc., because the only difference at the end of the function could be whether the values contained in the array have been set or not.  As I do ensure that any array entry used also has its value set, it should be OK.

Joseph Rushton Wakeling:

> So it's bizarre that there is a performance difference here.

Bizarre findings deserve more experiments and studies :-)


> Incidentally, this was why I felt safe using uninitializedArray for arrays of e.g. long, size_t, etc., because the only difference at the end of the function could be whether the values contained in the array have been set or not.  As I do ensure that any array entry used also has its value set, it should be OK.

You also have arrays of T. Someday T could be something with indirections :-) So minimallyInitializedArray is safer regarding future changes in your code.

Bye,
bearophile

On Thursday, 26 September 2013 at 21:29:42 UTC, bearophile wrote:
> You also have arrays of T. Someday T could be something with indirections :-) So minimallyInitializedArray is safer regarding future changes in your code.

T is qualified via isFloatingPoint :-)

Joseph Rushton Wakeling:

> T is qualified via isFloatingPoint :-)

I know, but that qualification could change in future evolutions of your code. Strong type safety means that if you change a type in your code, with a localized change (like removing isFloatingPoint at the top of your function) the whole code that depends on that type (like the body of this function of yours) will keep working as safely as before :-)

Bye,
bearophile

On Thursday, 26 September 2013 at 22:03:12 UTC, bearophile wrote:
> Joseph Rushton Wakeling:
>
>> T is qualified via isFloatingPoint :-)
>
> I know, but that qualification could change in future evolutions of your code. Strong type safety means that if you change a type in your code, with a localized change (like removing isFloatingPoint at the top of your function) the whole code that depends on that type (like the body of this function of yours) will keep working as safely as before :-)

OK, I accept your argument :-)

As things stand I'm inclined to leave the code using "new" for now. I'll see if I can work out anything about why minimallyInitializedArray might be problematic -- at a guess, perhaps it accidentally gets in the way of some potential optimizations?