mutable objects, aliasing, and code patterns

[simonster]

I noticed there's a lot of sparse matrix code that does things like:

for col = 1:n, p = A.colptr[col]:(A.colptr[col+1]-1)
    C.nzval[p] = A.nzval[p] * b[A.rowval[p]]
end

The compiler presently assumes that the contents of C.nzval, A.nzval, and A.rowval can alias the parts of C and A that contain the pointers to the array objects, and thus needs to reload those pointers on each loop iteration. The performance cost depends on how much is in cache, but for medium-sized sparse matrices this can be ~30% faster on my system:

Anzval = A.nzval
Arowval = A.rowval
Cnzval = C.nzval
for col = 1:n, p = A.colptr[col]:(A.colptr[col+1]-1)
    Cnzval[p] = Anzval[p] * b[Arowval[p]]
end

If @inbounds is added, the performance difference is even larger, since the optimizer can hoist the loads of both the pointer to the array object and the pointer to the array data in the second case but not the first.

Since #8867, I suspect the performance gap would disappear if SparseMatrixCSC were made immutable. However, there is code that relies on its mutability, and code patterns like this are probably also present outside of Base. Thus, I wonder whether we could place some restrictions on when array pointers and mutable objects can alias each other, so that extracting variables isn't necessary to achieve optimal performance.

I wonder whether it ever happens that arrays alias objects. This is possible using pointer_to_array(convert(Ptr{T}, pointer_from_objref(x)), ...) but probably isn't common. It would also be sufficient to tell TBAA that arrays never alias portions of objects that contain pointers.

[ArchRobison]

I also find the need for hand-hoisting irksome. I ran into something like this for my own types in the Al Zimmerman contest. The optimization good of the many should outweigh the abusive type-punning needs of the few.

I saw this issue decades ago in C++. The "2nd-level indirect" problem was common in scientific C++ codes that used user-defined array objects. KAI C++ had a rule that a pointer load never had a flow dependency on a floating-point store. We still allowed anti-dependencies and output dependencies, since C++ has unchecked union types. I don't remember a user ever reporting a problem with our scheme. We occasionally had users complain about a similar rule for int/float (even though in the reported contexts it was not standard conforming, and there was a standard-conforming way that worked.)

[ArchRobison]

Going down the TBAA route, we could have two disjoint subsets of tbaa_user, like this (comment indentation indicates inclusion relationship):

static MDNode* tbaa_user;           // User data that is mutable
static MDNode* tbaa_user_ptr_free;      // User data with no pointers
static MDNode* tbaa_user_ptr_tainted;   // User data with pointers in it

The aliasing rule would be that objects with pointers cannot alias objects that are pointer-free.

The tainted subset could be further subdivided according to where the pointers are laid out, but that seems like a lesser gain for significantly more work.

[ViralBShah]

@simonster I always try to write sparse matrix code in the pattern you suggested above.

I am guessing that we can make SparseMatrixCSC immutable, and only values in the various arrays contained in it will change - in operations like setindex and various in-place operations.

[ViralBShah]

The real challenge would be setindex! cases tha cause nzval and rowval to grow.

[simonster]

Growing nzval and rowval is not a problem with an immutable SparseMatrixCSC as long as it is done with push!, append!, or resize! rather than by constructing an entirely new array. However, I still think it's worthwhile to consider putting some restrictions on aliasing here, since this affects user code as well and sometimes immutability is not feasible.