5 ms·

I've seen the claim that Julia has offest-arrays at essentially no additional cost a few times now, and I'm just not buying it. As in, I don't see how its poss

I've seen the claim that Julia has offest-arrays at essentially no additional cost a few times now, and I'm just not buying it. As in, I don't see how its possible without stretching the meaning of "no additional cost". I'm familiar with displaced arrays and the like in Common Lisp, so i get that you can do offsets and things without using much additional memory, and i feel its a small jump from that to arbitrary indexing. I mean, sure, if you're programming with constants or common patterns or things like that, a compiler could theoretically figure out and adjust the references itself. Or you can use macrology (I presume, since julia is so close to being lisp in matlab clothing, there's no issues with this in theory). Or you can come up with some kind of functional wrapper to adjust offset indexes back to the base case... But if you're actually using run-time calculations using returned numbers from a calculation to index N-quadrillion times into various arrays and you're swapping between a standard and arbitrary/offset index measure, which is about the only time I can see you'd actually care about the relative efficiency of repeated arbitrary indexing, then it can't be a pre-compiled thing. The offsets between the actual numbers you're getting back and the actual index into the arrays have to be calculated in an additional step at run time. Now its true that's likely to be only an addition or multiplication operation for each one, (and if it isn't, the run time application of another transformation just cements my point) but perhaps my notion of "essentially no additional cost" is more strict...

3JPLW 9y ago
This is easily testable: julia> using BenchmarkTools using OffsetArrays A = rand(1000) O = OffsetArray(A, 0:999) function naive_sum(A) s = zero(eltype(A)) @unsafe for i in eachindex(A) # @unsafe will eventually be folded into @inbounds s += A[i] end return s end naive_sum (generic function with 1 method) julia> @btime naive_sum($A) 1.025 μs (0 allocations: 0 bytes) 514.0960505118594 julia> @btime naive_sum($O) 1.023 μs (0 allocations: 0 bytes) 514.0960505118594 Yes, there's an extra operation or two in there, but it's effectively free on modern CPUs due to caching/op latencies/pipelining/etc.
- StefanKarpinski 9y ago
  The performance is the same because the core loop in both cases is identical: loop: vaddsd (%rcx), %xmm0, %xmm0 addq $8, %rcx addq $-1, %rax jne loop There's more setup required for offset arrays, but otherwise there's no difference. I'm not sure why arrays having an offset would be any more work: array indexing in general involves adding an index to a base pointer; having an offset effectively just changes what the base pointer value is.

3JPLW 9y ago

This is easily testable: julia> using BenchmarkTools using OffsetArrays A = rand(1000) O = OffsetArray(A, 0:999) function naive_sum(A) s = zero(eltype(A)) @unsafe for i in eachindex(A) # @unsafe will eventually be folded into @inbounds s += A[i] end return s end naive_sum (generic function with 1 method) julia> @btime naive_sum($A) 1.025 μs (0 allocations: 0 bytes) 514.0960505118594 julia> @btime naive_sum($O) 1.023 μs (0 allocations: 0 bytes) 514.0960505118594 Yes, there's an extra operation or two in there, but it's effectively free on modern CPUs due to caching/op latencies/pipelining/etc.

StefanKarpinski 9y ago
The performance is the same because the core loop in both cases is identical: loop: vaddsd (%rcx), %xmm0, %xmm0 addq $8, %rcx addq $-1, %rax jne loop There's more setup required for offset arrays, but otherwise there's no difference. I'm not sure why arrays having an offset would be any more work: array indexing in general involves adding an index to a base pointer; having an offset effectively just changes what the base pointer value is.