I was wondering if it would be a good idea to store whether a numeric Vector is sorted in the vector struct itself. The current implementation Vector has the fields (:ref,:size), what I am suggesting for numeric vectors is to have fields is something like this (:ref, :size, :order) where order can take one of three values :lt which means its sorted in ascending order, :gt which means its sorted in descending order, and maybe :none which means the array is unsorted. Then once an array is sorted, the order filed can be modified accordingly, and sort or issorted would subsequently be instantaneous. I realize this cannot be done if we want to sort based on some function of the data, but just for the natural ordering (for lack of a better phrase). I had this thought when looking at the quantile function code in Statistics and thought this might be useful when many quantiles need to be computed.
In fact such a change was done in R3.5.0 which introduced an alternative representation (ALTREP, see 1) of R vectors and stored sortedness as a property of the vector object. (Sources: 1, 2)
My question is would this be useful and desirable in Julia?
The big downside of this would be that mutation would then be much slower (~2x) since it would also have to unset the sorted-ness. This would almost certainly be way too big a performance hit to justify.
Interesting! I thought since we are only storing a small symbol, that cost would be negligible compared to the cost of sorting itself. Why would it be 2x slower?
For cases like that you’d probably just want to unwrap, work on the underlying vector and then rewrap at the end. Though, I assume that the branch predictor would make it so that the impact of this is much less than 2x
Oscar isn’t comparing to the overhead of storing, the comparison is to a single index mutation of the array.
I would add that this is a very different trade off in Julia than in R. In R any kind of scalar code is slow so the overhead of unsetting the sorted flag on each indexing operation doesn’t really matter—if you’re writing code that does individual indexing operations you are already hosed performance-wise. In Julia people can and do write native-efficiency scalar code and this would massively penalize that. Since most Julia array code is written in Julia, that would penalize everyone. The SortedVector approach avoids that problem by not affecting core vectors and can instead restrict the operations you’re allowed to do on sorted vectors.
I guess the actual work for unsetting the sorted flag will typically be done at most once per array within a single function, when lucky with compiler optimizations such as inlining and aliasing analysis. For example, unsetting the flag will be hoisted out of critical loops. In that case I bet it won’t make a measurable regression.
Let’s check a few ways a sorted vector would be implemented, the only rule being that we’re trying to make issorted as cheap as checking a flag:
It’s always sorted, there is no flag to unset. Instead, all mutation has an overhead to check the nearest elements, and if order wouldn’t be preserved, an error is thrown. This is how SortedVector works.
Unset the flag if mutation ruins the order, again we could just check the nearest elements. However, this risks unexpected correctness issues because you’re not checking order to reset the flag. You can end up with 2 equal sequences that have 2 different flags; the flag is not indicating current sortedness but whether it was ever unsorted.
Unset the flag if mutation ruins the order like (2), but reset the flag if a mutation restores order. The latter isn’t saving work anymore, you have to check the whole sequence like issorted(::Vector) in every setindex! when the flag is unset. This sort of overhead is why SortedVector doesn’t do it.
It’s immutable, so whether it’s sorted or not is known at instantiation. This is how the R vector ALTREP works. If mutation is needed, then it falls back to the typical vector implementation and potentially gives up on tracking sortedness. So why bother? The ALTREP article and blog explicitly mentions this would optimize “compact sequences” like loop ranges that are semantically equivalent to arbitrary vectors but could be implemented much more cheaply over most of their lifetimes.
So even ignoring the point about R’s interpreted overhead, Julia already has “compact sequences” as separate types from dense Vectors with none of this overhead and hoops to jump through; issorted(::AbstractRange) is pretty cheap. R only experimented with this internally because they didn’t make such a distinction on the language level and didn’t want to force users to change their code (like Python2 making cheap xrange to replace the full range) or go through a major release (like Python 3 turning range cheap and requiring manual type conversions to full lists). This is a good example of how formative API design can help developers provide good performance to users more easily.
No, we can’t hoist an action that is conditional on the runtime values of the actions inside that loop. We don’t know until runtime whether the sortedness survives all the mutations in the loop (which may have 0 iterations), so neither does the compiler.
At that point, you’re really better off just returned a SortedVector object from sort and let dispatch handle the rest. Nothing protects an issorted flag in an array from being set manually, so checking that flag doesn’t actually imply that the underlying data is sorted.
If the loop is written so that the compiler knows it has >=1 iterations and the method with the flag-setting gets inlined, then yes it could be hoisted. A bigger issue than the iffy conditions is that a sorted sequence can have a misleading flag that can differ from the flag of another equivalent sequence, like what I laid out in (2) but at least the expensive methods like sort! get to reset the flag. The flag would have to be documented to mean “not mutated since instantiation or supported sorting function calls”, and that’s still not reliable for optimization, especially in the context of ALTREP.
The ALTREP blog mentions that something like sorted_x < cutoff can compute the location of the cutoff efficiently (binary search) and return a logical vector that actually consumes little memory (just stores the index where 0s switch to 1s and in which direction). Again, that is only possible because it’s not exposed to the language level. While Julia prefers to expose different structures as separate types for simpler optimization, that is too late for this particular optimization; 1:5 .< 3 returns a dense BitArray{1} instead of a special compact type. It’s not worth complicating the internals of BitArray for this niche case we’re already doing in other ways, but point is R isn’t alone in having to work within its API.
Presumably that is considered internal behavior and it’s the user’s fault if misuse breaks something. It can also be guarded against in setproperty! like how Arrays stop us from setting the size field.
