Why are tuple literals better for constant-propagation than array literals?

General Usage Performance
1

I need functions that check if a symbol references a specific type of struct field, and this is supposed to compile away through constant propagation.

Now, I also had this heuristic that I shouldn’t use huge Tuples because compilation time grows a lot with large Tuples, I’m not sure if that applies to homogenous ones, though. So I tested two definitions against each other, one with a Tuple and one with a Vector.

function test_vec(x)
    x in [:A,:B,:C,:D,:E,:F,:G,:H,:I,:J,:K,:L,:M,:N,:O,:P,:Q,:R,:S,:T,:U,:V,:W,:X,:Y,:Z,:a,:b,:c,:d,:e,:f,:g,:h,:i,:j,:k,:l,:m,:n,:o,:p,:q,:r,:s,:t,:u,:v,:w,:x,:y,:z]
end

function test_tuple(x)
    x in (:A,:B,:C,:D,:E,:F,:G,:H,:I,:J,:K,:L,:M,:N,:O,:P,:Q,:R,:S,:T,:U,:V,:W,:X,:Y,:Z,:a,:b,:c,:d,:e,:f,:g,:h,:i,:j,:k,:l,:m,:n,:o,:p,:q,:r,:s,:t,:u,:v,:w,:x,:y,:z)
end

The first look was at @time, just as a sanity check:

julia> @time test_tuple(:x)
  0.000000 seconds
true

julia> @time test_vec(:x)
  0.000003 seconds (1 allocation: 496 bytes)
true

So the vector version already allocates here, pointing to an “inefficient” use of the list of symbols.

Then I tested constant propagation:

function test_constprop_tuple()
    if test_tuple(:a)
        1
    else
        2
    end
end

julia> @code_native test_constprop_tuple()
        .section        __TEXT,__text,regular,pure_instructions
; ┌ @ Untitled-1:126 within `test_constprop_tuple'
        movl    $1, %eax
        retq
        nopw    %cs:(%rax,%rax)

The call is replaced by the constant 1.

Now the vector version:

function test_constprop_vec()
    if test_vec(:a)
        1
    else
        2
    end
end

julia> @code_native test_constprop_vec()
        .section        __TEXT,__text,regular,pure_instructions
; ┌ @ Untitled-1:136 within `test_constprop_vec'
        pushq   %rax
; │ @ Untitled-1:137 within `test_constprop_vec'
        movabsq $test_vec, %rax
        movabsq $4377851312, %rdi               ## imm = 0x104F0B5B0
        callq   *%rax
        andb    $1, %al
        movzbl  %al, %ecx
        movl    $2, %eax
        subq    %rcx, %rax
; │ @ Untitled-1:138 within `test_constprop_vec'
        popq    %rcx
        retq
        nopw    %cs:(%rax,%rax)

So my question is, why is an array literal not useable for constant propagation while a tuple literal is? Nothing can modify the array as it does not escape the function. Or is the compiler not sure that the only function applied to it, which is in, does not modify it?

2

Vectors are inherently mutable and Tuples are inherently immutable. This is built into Julia. So, even though you may never alter your Vector, the representation in memory is indirect (on the heap) and will support access that overwrites a current element. Tuple entries are not alterable, and this allows the representation in memory to be direct (faster access).

In short, tuple literals are constant and vector literals are not. That is the reason that tuples are better for constant propogation.

Very large Tuples are not generally used. As a guideline, once your tuple grows to ~32 elements some operations slow down, certainly beyond ~64 elements (depending upon the use) consider using a Vector. StaticArrays.jl, a widely used package, keeps its tuples < 100 elements.

1 Like
3

Yeah my only need is for looking up whether a field of a struct belongs to a special group or not. But the number of fields could be >100. And it needs to work with constant propagation so that the check compiles away when fields are accessed in other functions.

4

I am not sure I follow your intent here. The ability to associate a field with a special group and the ability to access a field should not need to be intertwined. Are you expecting more than 100 fields for some particular struct, or is it that you expect a total of more than 100 fields over a collection of structs? Also, what type[s] of fields are expected? Is there one special group or are there several/many special groups?

5

Makie plot objects have attributes that are Observables. I’m trying to convert these to fields in a new design and an attribute field access needs different semantics than an ordinary field access. And yes one object can have upwards of 100 attribute fields.

6

Again, not sure this is on target for you.
If you have n special groups where n is small, and for each of these groups you define a struct that contains the fields which belong to that special group, and you use an overarching struct which contains each of these substructs as immediate fields, and to keep the access uniform, define getproperty for each field so it can access subfields as defined. The getproperty variations can be defined in an small group of @eval loops.

7

Sorry for opening a parenthesis in this thread. Maybe the above could be written as:

Symbol.(union('a':'z','A':'Z'))
1 Like
8

No I wanted a literal specifically to be sure to do everything I can for it to constant-prop. The real code will be macro-generated anyway. And it won’t be a list of letters :wink:

1 Like
9

Sounds like something you could meta-program.

julia> macro make_test_fun(func, props)
           tests = Expr(:block)
           for prop in eval(props)
               push!(tests.args, :(x == $(Meta.quot(prop)) && return true))
           end
           return esc(quote
               function $func(x)
                   $tests
                   return false
               end
           end)
       end
@make_test_fun (macro with 1 method)

julia> @make_test_fun f [:x, :y, :z]
f (generic function with 1 method)

This gives you a function f equivalent to

function f(x)
    x == :x && return true
    x == :y && return true
    x == :z && return true
    return false
end

which should allow constant propagation.

10

This thread drifts a bit off target, I already have a way to program this in a constant-propagating way (the if block would also suffice, yes). I merely wanted to know why the compiler can’t/doesn’t constant-propagate with an array of literal values that is not modified. I know about the differences between tuples and arrays, too, but not how the compiler deals with specifically written out collections like in my case.

11

Someone who really knows should confirm but from what I’ve read elsewhere constant propagation could work in the vector case too if Julia’s compiler had a better escape analysis than it currently has. For the immutable case of a tuple there’s no need to do any escape analysis.

1 Like
12

I think currently Julia doesn’t perform any special optimization for Array at Julia IR level. It directly lower Array construction to a ccall to Julia’s runtime and none of the high level information is used, and LLVM knows nothing special about this function call. So it even fails to optimize this function to a non-op:

function f()
    x = [1,2,3]
    return nothing
end

Anyway, doing this kind of optimization (constant propagation for mutable) needs to perform alias analysis on Julia’s IR, which is expensive. C++ doesn’t suffer from this because std::vector is implemented in C++, so compiler can see every information in std::vector, and they can just focus on the optimization of a low level form IR (LLVM IR). If you check the LLVM IR of the following code:

function f()
    x = [1,2,3]
    return x[1]
end

You can see that LLVM can figure out the return value is 1. But it can’t remove the call to array allocation (since it doesn’t know this is an allocation).

I guess we just need to teach LLVM some information of Julia’s Array and we can get the optimization for free…

13

This is what is currently been looked at https://github.com/JuliaLang/julia/pull/41777