Abstract
TL; DR zeros_via_calloc is a potentially faster version of zeros that is comparable to Array{T}(undef, ...) and numpy.zeros.
function zeros_via_calloc(::Type{T}, dims::Integer...) where T
ptr = Ptr{T}(Libc.calloc(prod(dims), sizeof(T)))
return unsafe_wrap(Array{T}, ptr, dims; own=true)
end
# Windows benchmark
julia> @btime zeros_via_calloc(Float64, 1024, 1024);
12.400 ÎŒs (2 allocations: 8.00 MiB)
julia> @btime zeros(Float64, 1024, 1024);
1.652 ms (2 allocations: 8.00 MiB)
# Windows Subsystem for Linux 2 Benchmark
julia> @btime zeros_via_calloc(Float64, 1024, 1024);
24.300 ÎŒs (2 allocations: 8.00 MiB)
julia> @btime zeros(Float64, 1024, 1024);
474.500 ÎŒs (2 allocations: 8.00 MiB)
Introduction
In Julia, there are several ways to create large arrays. The fastest form is Array{T}(undef, dims...) where T is the element type of the array and dims is a series of integers describing the size of the array. There are also a few convenience constructors such as zeros and ones which use the fastest form followed by fill!(array, zero(T)) or fill!(array, one(T)), respectively. Below see that zeros and ones are much slower than array creation using Array{T}(undef, ...).
julia> @benchmark Array{Float64}(undef, 1024, 1024)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
Range (min ⊠max): 12.800 ÎŒs ⊠1.085 ms â GC (min ⊠max): 0.00% ⊠96.56%
Time (median): 13.900 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 104.670 ÎŒs ± 200.995 ÎŒs â GC (mean ± Ï): 85.28% ± 36.22%
julia> @benchmark zeros(1024, 1024)
BenchmarkTools.Trial: 2187 samples with 1 evaluation.
Range (min ⊠max): 1.661 ms ⊠6.932 ms â GC (min ⊠max): 0.00% ⊠60.38%
Time (median): 1.838 ms â GC (median): 0.00%
Time (mean ± Ï): 2.281 ms ± 1.010 ms â GC (mean ± Ï): 19.35% ± 21.94%
julia> @benchmark ones(1024, 1024)
BenchmarkTools.Trial: 2186 samples with 1 evaluation.
Range (min ⊠max): 1.657 ms ⊠6.561 ms â GC (min ⊠max): 0.00% ⊠58.89%
Time (median): 1.835 ms â GC (median): 0.00%
Time (mean ± Ï): 2.283 ms ± 1.021 ms â GC (mean ± Ï): 19.40% ± 21.87%
Above we see that on my Windows-based machine, uninitialized array creation takes a median time 13.9 microseconds. While ones and zeros takes a median of 1.8 milliseconds or 100 times as long as uninitialized array creation to execute.
However, if we compare to Numpy, we see that numpy.zeros takes a mean of 92 microseconds and is actually faster than numpy.ones as well as the Juliaâs zeros:
In [60]: %timeit numpy.zeros((1024,1024), dtype = np.float64)
92 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [61]: %timeit numpy.ones((1024,1024), dtype = np.float64)
2.5 ms ± 160 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
The reason that numpy.zeros is faster is that since 2013, numpy.zeros uses the C routine calloc which initializes the underlying memory to zero. Using calloc for Juliaâs zeros has been pending since 2011.
calloc can be faster than creating an uninitialized array and filling it with zeros. The operating system may be able to manage its memory such that it knows where chunks of zeros already exist in memory. If the zeroed memory does not exist, the operating system may choose to defer zero initialization until you actually start to use the memory. See this StackOverflow for a longer explanation.
In this post, we explore whether we can implement zeros based on calloc from Julia, right now and evaluate whether it actually has any performance benefits.
Developing a calloc based zeros in Julia
Julia is kind enough to expose basic C routines via the module Libc. Libc.calloc(num::Integer, size::Integer) takes two arguments. num is the number of elements, while size is the size of each element. The routine returns a Ptr{Nothing} the equivalent of a void pointer in C. This will allocate zeroed memory that is not managed by the garbage collector.
To incorporate this memory into a Julia array, we will use unsafe_wrap(Array, pointer::Ptr{T}, dims; own). This wraps an Array with specified dimensions around the pointer. The keyword argument own specifies whether Julia should take ownership of the memory and be responsible for freeing the memory when we are done with it.
Implementing zeros_via_calloc is a matter of calling Libc.calloc with the appropriate arguments. We can get the number of elements by taking the product of the dimensions. The size of each element is just the size of the the type T. For unsafe_wrap the resulting Ptr{Nothing} needs to be converted a Ptr{T}. We will then let Julia own the memory so that we do not have free the memory ourselves.
function zeros_via_calloc(::Type{T}, dims::Integer...) where T
ptr = Ptr{T}(Libc.calloc(prod(dims), sizeof(T)))
return unsafe_wrap(Array{T}, ptr, dims; own=true)
end
The performance is about is faster as expected. There are some differences in performance on Windows versus Windows Subsystem for Linux 2 on the same hardware though.
# Windows
julia> @benchmark zeros_via_calloc(Float64, 1024, 1024)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
Range (min ⊠max): 12.300 ÎŒs ⊠80.400 ÎŒs â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 13.700 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 15.137 ÎŒs ± 5.399 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
âââââââââââââ â
âââââââââââââââââââââââââ
â
â
â
â
ââ
â
âââ
ââââââ
ââ
â
ââ
â
â
â
â
ââ
â
âââ
â
ââ â
12.3 ÎŒs Histogram: log(frequency) by time 41.5 ÎŒs <
Memory estimate: 8.00 MiB, allocs estimate: 2.
julia> @benchmark zeros(Float64, 1024, 1024)
BenchmarkTools.Trial: 2142 samples with 1 evaluation.
Range (min ⊠max): 1.639 ms ⊠9.415 ms â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 1.843 ms â GC (median): 0.00%
Time (mean ± Ï): 2.330 ms ± 1.121 ms â GC (mean ± Ï): 20.28% ± 22.35%
ââââââââ ââââââ âââ â â
âââââââââââ
ââââ
â
â
âââââ
ââââââââââââââââ
âââââââââââââââââââ â
1.64 ms Histogram: log(frequency) by time 5.5 ms <
Memory estimate: 8.00 MiB, allocs estimate: 2.
# Linux
julia> @benchmark zeros_via_calloc(Float64, 1024, 1024)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
Range (min ⊠max): 22.100 ÎŒs ⊠1.364 ms â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 273.400 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 292.431 ÎŒs ± 62.129 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
ââââââ
âââââââââââââââââââââââââââââââââââââ
âââââââââââââââââââââââ â
22.1 ÎŒs Histogram: frequency by time 493 ÎŒs <
Memory estimate: 8.00 MiB, allocs estimate: 2.
julia> @benchmark zeros(Float64, 1024, 1024)
BenchmarkTools.Trial: 7878 samples with 1 evaluation.
Range (min ⊠max): 458.300 ÎŒs ⊠2.069 ms â GC (min ⊠max): 0.00% ⊠31.44%
Time (median): 532.200 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 626.414 ÎŒs ± 191.989 ÎŒs â GC (mean ± Ï): 8.12% ± 12.52%
âââ
ââââââ
âââââââââââââââââââââââââââââââââââââââââââââââââââââââ â
458 ÎŒs Histogram: frequency by time 1.15 ms <
Memory estimate: 8.00 MiB, allocs estimate: 2.
Incorporating this into Base Julia is a bit more complicated since Julia usually uses aligned memory when allocating arrays of this size. The most recent attempt at this was four years ago.
Is zeros_via_calloc actually faster in practice?
In discussing this @Sukera on Zulip and @tim.holy on Github, the contention was that zeros_via_calloc would not be faster in practice. The idea is that via calloc the operating system is just being lazy and deferring the zero initialization operating until later. Thus when we actually try to iterate or otherwise use the array that performance would suffer as the operating system actually does the work. However, as noted in the introduction, it is also possible that the operating system has done the work ahead of time and may be offering memory that already has been initialized with zeros.
Summation
Letâs begin by just accessing the memory by summing it together. The tests below include array creation time.
# Windows
julia> @benchmark sum(zeros_via_calloc(Float64, 1024, 1024))
BenchmarkTools.Trial: 2134 samples with 1 evaluation.
Range (min ⊠max): 1.680 ms ⊠5.428 ms â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 1.847 ms â GC (median): 0.00%
Time (mean ± Ï): 1.885 ms ± 204.224 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
ââââ
âââ
âââ
âââ
â
ââââââââââââââââ
ââââââââââââââââââââââââââââââââââââââââââ â
1.68 ms Histogram: frequency by time 2.82 ms <
Memory estimate: 8.00 MiB, allocs estimate: 2.
julia> @benchmark sum(zeros(Float64, 1024, 1024))
BenchmarkTools.Trial: 1563 samples with 1 evaluation.
Range (min ⊠max): 2.131 ms ⊠10.005 ms â GC (min ⊠max): 0.00% ⊠59.89%
Time (median): 2.419 ms â GC (median): 0.00%
Time (mean ± Ï): 3.189 ms ± 1.589 ms â GC (mean ± Ï): 20.99% ± 23.03%
ââââââââââ âââââ
ââââââââââââââââââ
âââ
ââââ
âââââââââââââââââ
ââââ
ââ
â
â
ââ
â
âââââ
â
2.13 ms Histogram: log(frequency) by time 8.86 ms <
Memory estimate: 8.00 MiB, allocs estimate: 2.
julia> sum(zeros_via_calloc(Float64, 1024, 1024))
0.0
julia> versioninfo()
Julia Version 1.6.3
Commit ae8452a9e0 (2021-09-23 17:34 UTC)
Platform Info:
OS: Windows (x86_64-w64-mingw32)
CPU: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
# Windows Subsystem for Linux 2
julia> @benchmark sum(zeros_via_calloc(Float64, 1024, 1024))
BenchmarkTools.Trial: 8838 samples with 1 evaluation.
Range (min ⊠max): 418.500 ÎŒs ⊠2.682 ms â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 471.400 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 496.652 ÎŒs ± 80.999 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
âââââââââ
ââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââ â
418 ÎŒs Histogram: frequency by time 774 ÎŒs <
Memory estimate: 8.00 MiB, allocs estimate: 2.
julia> @benchmark sum(zeros(Float64, 1024, 1024))
BenchmarkTools.Trial: 4866 samples with 1 evaluation.
Range (min ⊠max): 821.900 ÎŒs ⊠3.744 ms â GC (min ⊠max): 0.00% ⊠8.10%
Time (median): 934.100 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 1.018 ms ± 202.350 ÎŒs â GC (mean ± Ï): 6.28% ± 10.47%
âââââââ
â
âââââââââââââââ
âââââ
âââââââââââââââââââââââââââââââââââââââââ â
822 ÎŒs Histogram: frequency by time 1.53 ms <
Memory estimate: 8.00 MiB, allocs estimate: 2.
julia> versioninfo()
Julia Version 1.6.3
Commit ae8452a9e0 (2021-09-23 17:34 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
On both Windows and WSL2, we see benefits when looking at the combined time of creating the array and summation. We can also isolate the summation step in the benchmarks.
# Windows
julia> @benchmark sum(C) setup = ( C = zeros_via_calloc(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 2131 samples with 1 evaluation.
Range (min ⊠max): 1.669 ms ⊠3.298 ms â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 1.834 ms â GC (median): 0.00%
Time (mean ± Ï): 1.863 ms ± 163.536 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
ââ âââ
âââ
âââ
ââââ
ââââââââââââââââââââââ
âââââââââââââââââââââââââââââââââââââ â
1.67 ms Histogram: frequency by time 2.54 ms <
Memory estimate: 0 bytes, allocs estimate: 0.
julia> @benchmark sum(A) setup = ( A = zeros(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 1686 samples with 1 evaluation.
Range (min ⊠max): 319.700 ÎŒs ⊠1.030 ms â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 394.600 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 417.203 ÎŒs ± 64.969 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
ââââ
âââââââââââââââ
âââââââ
ââââââââââââââââââââââââââââââââââââââ â
320 ÎŒs Histogram: frequency by time 682 ÎŒs <
Memory estimate: 0 bytes, allocs estimate: 0.
# Windows Subsystem for Linux 2
julia> @benchmark sum(C) setup = ( C = zeros_via_calloc(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 8958 samples with 1 evaluation.
Range (min ⊠max): 171.600 ÎŒs ⊠687.400 ÎŒs â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 192.350 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 203.257 ÎŒs ± 34.846 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
ââ
ââââââââââ
â
â
â
âââââââââ ââ â â
âââââââââââââââââââââââââââââââââââââââââââââââââââââââââââ
ââ
â
172 ÎŒs Histogram: log(frequency) by time 350 ÎŒs <
Memory estimate: 0 bytes, allocs estimate: 0.
julia> @benchmark sum(A) setup = ( A = zeros(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 4855 samples with 1 evaluation.
Range (min ⊠max): 184.900 ÎŒs ⊠2.484 ms â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 399.500 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 387.149 ÎŒs ± 91.006 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
âââââââ
ââââââââ
ââââââââââââââââââââââââââââââ
âââ
âââââââââââââââââââ â
185 ÎŒs Histogram: frequency by time 567 ÎŒs <
Memory estimate: 0 bytes, allocs estimate: 0.
On Windows, we see the summation in isolation is slower using zeros_with_calloc than with zeros. On WSL2, the summation in isolation actually appears faster using zeros_with_calloc than with zeros.
Writing
Next we will try writing to the array. The tests below do not include array creation times.
julia> inds = CartesianIndices(1:5:1024*1024);
# Windows
julia> @benchmark C[$inds] .= $inds setup = ( C = zeros_via_calloc(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 8756 samples with 1 evaluation.
Range (min ⊠max): 365.000 ÎŒs ⊠2.712 ms â GC (min ⊠max): 0.00% ⊠73.24%
Time (median): 388.700 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 551.171 ÎŒs ± 349.209 ÎŒs â GC (mean ± Ï): 27.37% ± 25.49%
âââââââ ââââââââ â
ââââââââââââ
â
â
âââ
â
â
ââââââââââââââââââââââââââââââââ
ââââââââââ â
365 ÎŒs Histogram: log(frequency) by time 1.42 ms <
Memory estimate: 80 bytes, allocs estimate: 2.
julia> @benchmark A[$inds] .= $inds setup = ( A = zeros(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 2016 samples with 1 evaluation.
Range (min ⊠max): 143.800 ÎŒs ⊠365.700 ÎŒs â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 149.200 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 156.769 ÎŒs ± 24.008 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
â
ââââ
â â
âââââââââ
ââââââ
âââââ
ââââââââââââââ
ââ
ââââ
ââââââââ
âââââââââââ
ââ â
144 ÎŒs Histogram: log(frequency) by time 254 ÎŒs <
Memory estimate: 80 bytes, allocs estimate: 2.
# Windows Subsystem for Linux 2
julia> inds = CartesianIndices(1:5:1024*1024);
julia> @benchmark C[$inds] .= $inds setup = ( C = zeros_via_calloc(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 9029 samples with 1 evaluation.
Range (min ⊠max): 142.000 ÎŒs ⊠3.562 ms â GC (min ⊠max): 0.00% ⊠59.63%
Time (median): 148.100 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 269.166 ÎŒs ± 215.394 ÎŒs â GC (mean ± Ï): 26.06% ± 23.50%
ââ
ââââââ âââ âââ âââ â
âââââââââââââââ
âââ
ââââââââââ
âââââ
âââââââââââââââââââââââââââ
â â
142 ÎŒs Histogram: log(frequency) by time 838 ÎŒs <
Memory estimate: 80 bytes, allocs estimate: 2.
julia> @benchmark A[$inds] .= $inds setup = ( A = zeros(Float64, 1024, 1024) ) evals=1
BenchmarkTools.Trial: 6052 samples with 1 evaluation.
Range (min ⊠max): 140.400 ÎŒs ⊠417.000 ÎŒs â GC (min ⊠max): 0.00% ⊠0.00%
Time (median): 149.100 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 159.025 ÎŒs ± 27.826 ÎŒs â GC (mean ± Ï): 0.00% ± 0.00%
ââ
âââââ
ââââ â
ââââââââââââââââââââââââââââââââââââââââââââââââââââ
â
â
â
ââ
ââ
â
â
â
140 ÎŒs Histogram: log(frequency) by time 280 ÎŒs <
Memory estimate: 80 bytes, allocs estimate: 2.
Here writing does appear be slower.
Combined create, write, sum
In the last benchmarks of this initial post, I will benchmark the combined creation, writing, and summation of the resulting arrays.
julia> function c_func()
A = zeros_with_calloc(Float64, 1024, 1024)
A[1:5:length(A)] .= 2.0
sum(A)
end
c_func (generic function with 1 method)
julia> function a_func()
A = zeros(Float64, 1024, 1024)
A[1:5:length(A)] .= 2.0
sum(A)
end
a_func (generic function with 1 method)
# Windows
julia> @benchmark c_func()
BenchmarkTools.Trial: 1825 samples with 1 evaluation.
Range (min ⊠max): 2.066 ms ⊠9.072 ms â GC (min ⊠max): 0.00% ⊠52.24%
Time (median): 2.233 ms â GC (median): 0.00%
Time (mean ± Ï): 2.734 ms ± 1.126 ms â GC (mean ± Ï): 17.22% ± 20.25%
ââââ
âââââââââââââââââââââââââââââââââââââââââââââââââââââââââ â
2.07 ms Histogram: frequency by time 5.62 ms <
Memory estimate: 8.00 MiB, allocs estimate: 4.
julia> @benchmark a_func()
BenchmarkTools.Trial: 1500 samples with 1 evaluation.
Range (min ⊠max): 2.375 ms ⊠11.108 ms â GC (min ⊠max): 0.00% ⊠48.42%
Time (median): 2.686 ms â GC (median): 0.00%
Time (mean ± Ï): 3.325 ms ± 1.433 ms â GC (mean ± Ï): 19.19% ± 22.26%
ââââââââ ââââââ â
ââââââââââââ
âââââ
âââ
ââââââââââ
ââââââââââââââââââââââââââââ
â
2.38 ms Histogram: log(frequency) by time 7.08 ms <
Memory estimate: 8.00 MiB, allocs estimate: 4.
# Windows Subsystem for Linux 2
julia> @benchmark c_func()
BenchmarkTools.Trial: 6228 samples with 1 evaluation.
Range (min ⊠max): 618.600 ÎŒs ⊠2.404 ms â GC (min ⊠max): 0.00% ⊠27.01%
Time (median): 710.000 ÎŒs â GC (median): 0.00%
Time (mean ± Ï): 787.481 ÎŒs ± 173.925 ÎŒs â GC (mean ± Ï): 7.60% ± 11.97%
âââââââ
ââââââââââââ
â
â
â
â
âââââââââââââââââââââââââââââââââââââââââââââ â
619 ÎŒs Histogram: frequency by time 1.28 ms <
Memory estimate: 8.00 MiB, allocs estimate: 4.
julia> @benchmark a_func()
BenchmarkTools.Trial: 3429 samples with 1 evaluation.
Range (min ⊠max): 1.157 ms ⊠3.570 ms â GC (min ⊠max): 0.00% ⊠25.64%
Time (median): 1.366 ms â GC (median): 0.00%
Time (mean ± Ï): 1.446 ms ± 229.285 ÎŒs â GC (mean ± Ï): 5.05% ± 9.18%
âââââ
â
ââââ
âââââââââââââââââ
â
âââââââââââââââââââââââââââââââââââââââââ â
1.16 ms Histogram: frequency by time 2.22 ms <
Memory estimate: 8.00 MiB, allocs estimate: 4.
In the combined tests, we see benefits for both Windows and WSL 2.
Conclusions and Discussion
zeros_via_calloc offers some performance benefits over the current implementation of zeros on both Windows and Windows Subsystem for Linux 2.
Array creation with zeros_via_calloc on Windows is faster, almost on par with uninitialized array creation, but array access and write is slower. The combined operation on Windows is still overall faster taking 82% of the time compared to when the array is created with zeros.
On Windows Subsystem for Linux 2, array creation with zeros_via_calloc is also faster but not as dramatic as on Windows. Array access and write is slower, but the overall combined operation on WSL2 only takes 54% of the time compared to when the array is created with zeros.
Overall, for the conditions tested here, zeros_via_calloc does appear to have performance benefits over the current implementation of zeros on Windows and Windows Subsystem for Linux 2. Prior testing suggests that the benefit is reduced for smaller arrays.
Is zeros_via_calloc faster for your applications?