So, I just had an interesting idea for a 2.0 redesign that could kill the problems with Dictionaries, array labeling, and OffsetArrays with one stone. Someone recently put out a very nice package which distinguishes between: Ordinal indices (the 1st index is always the same as first(x), and so on)…

Computing the map has a noticable runtime cost. Also, dictionaries have much worse locality since they scatter elements randomly which is a major hit since it breaks vectorization.

[image] ParadaCarleton: Aren’t there a bunch of libraries that implement array labels with roughly 0 runtime cost? “0 runtime cost” for which operations? Looking at AxisKeys.jl as an example: Iterating over such an array - zero overhead. Regular numeric indexing - zero overhead. “Indexing”…

Just to give an example of how runtime costs may be more complicated than you think, here is a simple comparison of a matrix * vector computation for a Matrix{Float64} vs. a Dict{CartesianIndex{2}, Float64}, with the latter multiplication implemented in the obvious way (two nested loops). julia> us…

[image] stevengj: It’s “only” 50× slower than Matrix–vector multiplication: To be fair, this is specifically due to Dict inefficiencies. The same code with Dictionaries.jl is about 5x faster, totalling to 10x overhead over Matrix-Vector.

Wait, we have a 5x overhead in our Dict? where?

This is because of how Dict works right now, not because of any problems with labels being slow. To prove it, here’s matrix-vector multiplication with DimensionalData.jl: julia> @btime $da * $dv 254.719 ns (1 allocation: 272 bytes) julia> @btime $a * $v 253.645 ns (1 allocation: 272 bytes) Al…

[image] ParadaCarleton: To prove it, here’s matrix-vector multiplication with DimensionalData.jl: DimensionalData only names the axes (and furthermore the axes labels are static, part of the type, which indeed has zero runtime overhead), which is a totally different problem from representing …

DimensionalData.jl does have runtime labels. But these are in addition to the indices of the data array. The slow thing is looking up elements by label, which has to first find an index. Operations like * won’t use that at all, and just act on the data array. Dictionaries.jl is somewhere half way b…

I don’t think I’ll join the debate about whether dictionaries should be unordered and have ordered counterparts, as in Base, or whether dictionaries should be ordered and have unordered counterparts, as in Dictionaries.jl. FWIW, Python used to do the former, but has been moving to the latter . I gue…

Thinking about this some more though, I don’t think my idea works. Specifically, a type like OrdinalLastOffset might be useful if it’s fed directly into getindex, but for things like generators and comprehensions: what is supposed to determine the ending index? Example: g(a) = sum(a[i,j]+b[i,j] f…

Ordinal Indexing as a Language Feature

Internals & Design

stevengj Split this topic December 24, 2022, 2:01am 13

3 posts were split to a new topic: Performance of Dictionaries.jl vs Base.Dict

Topic		Replies	Views
Does `AbstractArray` itself need to support indexing beyond 1-based? Internals & Design indexing	15	1599	July 5, 2022
Is OffsetArrays.jl a poison pill? Internals & Design	63	5594	December 5, 2022
OffsetArrays, inbounds, and confusion Internals & Design indexing , arrays	53	4201	July 10, 2022
How can i make Julia array index to start from zero 0 and not from one 1? New to Julia offsetarrays	31	1897	May 25, 2025
StringIndex idea (Julia 2.0) Internals & Design strings , indexing	72	3820	March 27, 2024

Ordinal Indexing as a Language Feature

Related topics