# Storing sortedness for numeric vectors
**URL:** https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381
**Category:** Internals & Design
**Tags:** vector
**Created:** [January 2, 2025, 5:52pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381 "2025-01-02T17:52:32Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@ajinkya-k](https://discourse.julialang.org/u/ajinkya-k)
#### Post date: [January 2, 2025, 5:52pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/1 "2025-01-02T17:52:32Z")
Hello!
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](https://svn.r-project.org/R/branches/ALTREP/ALTREP.html#some_implementation_details)) of R vectors and stored sortedness as a property of the vector object. (Sources: [1](https://svn.r-project.org/R/branches/ALTREP/ALTREP.html#some_implementation_details), [2](https://blog.revolutionanalytics.com/2017/09/altrep-preview.html))
My question is would this be useful and desirable in Julia?
EDIT: apologies for the typo in the title
---
### Author:  [@JonasWickman](https://discourse.julialang.org/u/JonasWickman)
#### Post date: [January 2, 2025, 6:01pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/2 "2025-01-02T18:01:57Z")
There is a pretty recent package that might do what you want: [GitHub - tpapp/SortedVectors.jl: Lightweight wrapper to declare that a vector is sorted.](https://github.com/tpapp/SortedVectors.jl)
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [January 2, 2025, 6:19pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/4 "2025-01-02T18:19:58Z")
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.
---
### Author:  [@ajinkya-k](https://discourse.julialang.org/u/ajinkya-k)
#### Post date: [January 2, 2025, 6:23pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/5 "2025-01-02T18:23:44Z")
> [@Oscar\_Smith](#):
>
> 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?
---
### Author:  [@ajinkya-k](https://discourse.julialang.org/u/ajinkya-k)
#### Post date: [January 2, 2025, 6:24pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/6 "2025-01-02T18:24:29Z")
> [@JonasWickman](#):
>
> There is a pretty recent package that might do what you want: [GitHub - tpapp/SortedVectors.jl: Lightweight wrapper to declare that a vector is sorted.](https://github.com/tpapp/SortedVectors.jl)
Thanks I will check it out
---
### Author:  [@Mason](https://discourse.julialang.org/u/Mason)
#### Post date: [January 2, 2025, 6:28pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/7 "2025-01-02T18:28:17Z")
> [@Oscar\_Smith](#):
>
> 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.
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
> [@ajinkya-k](#):
>
> 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?
Oscar isn’t comparing to the overhead of storing, the comparison is to a single index mutation of the array.
e.g.
```julia
x[1] = 2
```
would need to set `x.sorted = false`.
---
### Author:  [@aplavin](https://discourse.julialang.org/u/aplavin)
#### Post date: [January 2, 2025, 7:46pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/8 "2025-01-02T19:46:06Z")
There are a lot of operations that could utilize “sortedness”, and it’s most natural to encode as a separate type.
See [GitHub - andyferris/AcceleratedArrays.jl: Arrays with acceleration indices](https://github.com/andyferris/AcceleratedArrays.jl) for related approaches as well.
---
### Author:  [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)
#### Post date: [January 3, 2025, 8:57pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/9 "2025-01-03T20:57:32Z")
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.
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [January 4, 2025, 6:40am UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/10 "2025-01-04T06:40:36Z")
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.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [January 4, 2025, 7:09am UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/11 "2025-01-04T07:09:14Z")
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:
1. 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.
2. 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.
3. 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.
4. 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 `Vector`s 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.
> [@sumiya11](#):
>
> unsetting the flag will be hoisted out of critical loops
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.
---
### Author:  [@ajinkya-k](https://discourse.julialang.org/u/ajinkya-k)
#### Post date: [January 4, 2025, 7:52am UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/12 "2025-01-04T07:52:53Z")
Thanks for the great explanation! ❤
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [January 4, 2025, 11:36am UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/13 "2025-01-04T11:36:50Z")
> [@Benny](#):
>
> 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.
Ah, I perhaps had a simpler implementation in mind than what you have outlined :^)
That is: any mutation unsets the flag with no additional checks, only `sort` sets the flag.
---
### Author:  [@Sukera](https://discourse.julialang.org/u/Sukera)
#### Post date: [January 4, 2025, 12:10pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/14 "2025-01-04T12:10:32Z")
> [@sumiya11](#):
>
> That is: any mutation unsets the flag with no additional checks, only `sort` sets the flag.
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.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [January 4, 2025, 3:14pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/15 "2025-01-04T15:14:22Z")
> [@sumiya11](#):
>
> That is: any mutation unsets the flag with no additional checks, only `sort` sets the flag.
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.
> [@Benny](#):
>
> This is a good example of how formative API design can help developers provide good performance to users more easily.
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.
> [@Sukera](#):
>
> Nothing protects an `issorted` flag in an array from being set manually
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 `Array`s stop us from setting the `size` field.
---
### Author:  [@sumiya11](https://discourse.julialang.org/u/sumiya11)
#### Post date: [January 4, 2025, 11:07pm UTC](https://discourse.julialang.org/t/storing-sortedness-for-numeric-vectors/124381/16 "2025-01-04T23:07:17Z")
> [@Benny](#):
>
> 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.
You are right, trade-offs depend on the application and one must measure.