---
### Author:  [@paulmelis](https://discourse.julialang.org/u/paulmelis)
#### Post date: [June 15, 2022, 8:06am UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/4 "2022-06-15T08:06:01Z")
Ah, so it _is_ data-dependent. I didn’t think that would be a sensible explanation. Nice find.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [June 15, 2022, 8:07am UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/5 "2022-06-15T08:07:49Z")
That’s what made me check `length(unique(v1)), length(unique(v2))` across runs but I don’t see a pattern of the 1 allocation happening for “vectors of few unique integers” as commented over `sort_int_range!`. Sometimes a vector with 47 unique elements will allocate while the vector with 43 will not, and sometimes a vector with 41 will allocate while the vector with 44 will not. But maybe I’m just missing something, `if !o1 && !o2 && rangelen < div(n,2)` seems more complicated than just “few unique integers” at first glance.
---
### Author:  [@skleinbo](https://discourse.julialang.org/u/skleinbo)
#### Post date: [June 15, 2022, 8:09am UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/6 "2022-06-15T08:09:47Z")
It’s about the range in conjunction with the vector size. If `extrema(v)=(1,50)` _and_ `N=100`, _then_ the branch is missed and `sort!` used which does not allocate.
On the other hand, put `N=102` and `sort_int_range!` is hit every time. Make `N` smaller and the chances of hitting that branch diminish.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [June 15, 2022, 8:18am UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/7 "2022-06-15T08:18:48Z")
Well that probably explains it, unless someone debugs this and finds something else. I don’t like it, though. I know the `!`-named functions are conventionally promised to modify arguments, not promised to minimally allocate. But eliminating allocations _is_ a major reason people reach for `!` functions, and it’s strange to have something that is 0 allocation _sometimes._ The good news is that it looks like `counts` is fully contained in the method, so the work on escape analysis might mitigate that allocation one day (could be easily too big to go on the stack entirely, so maybe just freed upon return so the GC doesn’t need to work on it).
---
### Author:  [@paulmelis](https://discourse.julialang.org/u/paulmelis)
#### Post date: [June 15, 2022, 8:27am UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/8 "2022-06-15T08:27:03Z")
> [@Benny](#):
>
> The good news is that it looks like `counts` is fully contained in the method, so the work on escape analysis might mitigate that allocation one day (could be easily too big to go on the stack entirely, so maybe just freed upon return so the GC doesn’t need to work on it).
Curious, what the `counts` you are refering to? I thought it was the `where = fill(0, rangelen)` in `sort_int_range!` that caused the allocation?
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [June 15, 2022, 8:31am UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/9 "2022-06-15T08:31:15Z")
Ah my bad, I’m looking at master, where the line in `sort_int_range!` is written `counts = fill(0, rangelen)`.
---
### Author:  [@skleinbo](https://discourse.julialang.org/u/skleinbo)
#### Post date: [June 15, 2022, 11:15am UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/10 "2022-06-15T11:15:16Z")
Good news! On a somewhat recent `master (Commit 4bb6528bc0 (2022-05-09 09:13 UTC)`, count sort is almost three times as fast and allocation free 🎉 even though the implementation is identical. Seems the compiler has become quite a bit smarter.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [June 15, 2022, 6:35pm UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/11 "2022-06-15T18:35:11Z")
I read that eliding allocations happens usually by moving something from the heap to the stack, but surely that cannot be done for very large `count`. Maybe it allocates if the array gets too big? Or maybe an allocation is only counted if it has to be handled by the GC?
---
### Author:  [@paulmelis](https://discourse.julialang.org/u/paulmelis)
#### Post date: [June 15, 2022, 7:18pm UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/12 "2022-06-15T19:18:07Z")
> [@Benny](#):
>
> Maybe it allocates if the array gets too big? Or maybe an allocation is only counted if it has to be handled by the GC?
The latter is probably most likely. Since the array is only used locally and doesn’t contain any references it’s easy to generate code to allocate and free it within the function. Not sure if that falls under the definition of “allocation” as far as the profiling goes, though.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [June 15, 2022, 8:42pm UTC](https://discourse.julialang.org/t/understanding-allocation-pattern-when-using-sort/82794/13 "2022-06-15T20:42:07Z")
Really wish it was documented in detail what `@time` or `@benchmark` counts as an allocation, it’s not even stated explicitly that it’s only counting heap allocations (as opposed to stack). Also, people try to eliminate allocations for at least a couple reasons: 1) reducing or eliminating GC latency, 2) eliminating nondeterministic `malloc`/`free`. So it’s not ideal to not be sure how many of the allocations are being saddled on the GC, and important information is obscured if it’s not counting heap allocations freed by the compiler instead of the GC.