Comment by ssivark | Hacker News Reader

Comment by ssivark | Hacker News Reader

Parent Full thread

Any time 1-based indexing is mentioned as a shortcoming of Julia reminds me of PG's 'Blub paradox' [1].

> As long as our hypothetical Blub programmer is looking down the power continuum, he knows he's looking down. Languages less powerful than Blub are obviously less powerful, because they're missing some feature he's used to. But when our hypothetical Blub programmer looks in the other direction, up the power continuum, he doesn't realize he's looking up. What he sees are merely weird languages. He probably considers them about equivalent in power to Blub, but with all this other hairy stuff thrown in as well. Blub is good enough for him, because he thinks in Blub.

Julia has offset array indexing (for essentially no additional cost) which is an amazingly useful feature! See eg. [2] Think of this feature as blurring the distinction between data (accessing an array) and computation (calling a function). The fact is that arrays as they are used (contiguous memory location collection) often carry more information than being just a dumb list of arbitrary data, and it's very convenient to expose that in their interface.

[1]: http://www.paulgraham.com/avg.html [2]: https://julialang.org/blog/2017/04/offset-arrays

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...

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.

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.

I didn't mean to seem petty, it's just that going back and forth between zero-based and one-based languages just added extra mental overhead (admittedly this was with Fortran, so there may have been other issues).

The way I think of it is that different indexing schemes suit different problems. I want to think carefully about the problem domain and use the most convenient convention. For example, when my array stores a time series, I would like the index to correspond to timestamps (and still be performant, so long as my timestamps can be efficiently mapped to memory locations, which is true for affine transformations, for example). When another array stores the Fourier transform of that time series, I would like to access elements by the frequency they correspond to. That stops me from making annoying indexing errors (eg: off-by-1), because the data structure's interface maps nicely to the problem domain. I find that much easier than the cognitive cost that comes with trying to shoehorn a single convention on every situation. But it's difficult to appreciate that when thinking of language constructs divorced from specific problem domains, as one tends to do when typically studying data structures and/or algorithms.

Fourier transforms are a great example: when I started with Julia, this was the only time I missed 0-based indexing.

Now there is the awesome FFTViews.jl package which goes one better with wrap-around indexing: https://github.com/JuliaArrays/FFTViews.jl

Sounds like https://github.com/JuliaArrays/AxisArrays.jl/ ;)

I am so sold I want to learn right now.

I think it crucial to offer at this point the important Julia package TwoBasedIndexing.jl :-)

https://github.com/simonster/TwoBasedIndexing.jl

Honestly, given how much work I do in R, and how much the assumption of 1-based indexing is in my field, this is a massive Julia selling point for the exact same mental overhead reasons you mention.

Wait a minute. Having an arbitrary offset is one thing. Settling on 1 as a standard is another one!

Reply on news.ycombinator.com