What is the best type for a Matrix to be used in Multiplication to give good performance?

suavesito · May 16, 2022, 3:07pm

(post deleted by author)

suavesito · May 16, 2022, 3:44pm

Ok, so there is a difference between name, binding, memory and value. If I miss something, I hope people correct me.

Name

Name is the symbol that you read as the variable. In a = 0, a is the name.

Value

Value is the data that defines a variable that is hold in memory. In a = 0, 0 is the value. Here comes a distinction of mutability in Julia, for immutable types, the data held define the whole value

a = 10
b = 10

a === b # test for "strict" equality, the values are the same

struct MyStruct # immutable
    a::Int
end

a = MyStruct(10)
b = MyStruct(10)

a === b # true, the content on both MyStruct define the value

But for mutable types, the value is not defined by the content, but by some internal reference that the compiler holds, to give an example we can do

a = [1, 2, 3]
b = [1, 2, 3]

a === b # false, those two arrays are _not_ the same because they are not pointing to the same memory

But if we do

a = [1, 2, 3]
a = b

a === b # true, they are pointing to the same memory

mutable MyMutStruct
    a::Int
end

a = MyMutStruct(10)
b = MyMutStruct(10)

a === b # false, they are not pointed by the same reference in the compiler

Binding

Binding is the relation between a name and a value. In the case a = 0, a is bound to the value 0.

In the case of an Array, that is mutable, the value is the underlying structure hold by the compiler.

Here comes const. const says to the compiler that the binding is constant. This will always mean that the type will not change. For immutable types, the binding being constant implies that the value will not change. But for mutable types, it doesn’t say anything about the content.

Memory

You might be tempted to say that then the value of an Array is defined by the pointer to the data, but that is also not true. The pointer to the data in an Array is part of the content of the array, so this code execute without problem

julia> const x = [1, 2, 3]
3-element Vector{Int64}:
 1
 2
 3

julia> y = x;

julia> y === x
true

julia> pointer(x)
Ptr{Int64} @0x00007f4291ef21b0

julia> push!(x, 4)
4-element Vector{Int64}:
 1
 2
 3
 4

julia> pointer(x) # it changed
Ptr{Int64} @0x00007f42920cb8f0

julia> x === y # but not the binding
true

So in the case of ik, the memory pointer and the content can be changed, but the binding, and importantly the type, also doesn’t change.

ufechner7 · May 16, 2022, 5:14pm

Summary for the users who are not computer scientists:

If you want high performance, anything on global level must be declared as const . You cannot change scalars, defined as const, but you CAN change the values and sizes of arrays and dicts and the values of mutable structs.

The keyword const mainly tells the compiler that the type won’t change.

Amro · May 16, 2022, 6:28pm

Thank you very much for your explanations! I have a few concerns about the difference between the binding and the pointer.

suavesito:

But for mutable types, the value is not defined by the content, but by some internal reference that the compiler holds, to give an example we can do
a = [1, 2, 3]
b = [1, 2, 3]

a === b # false, those two arrays are _not_ the same because they are not pointing to the same memory

1- Sine the value here is the reference pointer, what do we call the values 1,2,3?
2- Is there any function in Julia to know the value of this internal reference?

suavesito:

julia> const x = [1, 2, 3]
3-element Vector{Int64}:
 1
 2
 3
So in the case of ik , the memory pointer and the content can be changed, but the binding, and importantly the type , also doesn’t change.

1- The type is the one that can be known by typeof(), right? for example it is Vector{Int64} for x?
2- What is the benefit (in terms of performance) of making the binding not changing?

Amro · May 16, 2022, 6:29pm

Thank you very much for your helpful note!

suavesito · May 16, 2022, 7:04pm

I would call it the content of the array.

I was worried that my lexical would not be enough, as English is not my first language.

I don’t know, but if there is one, it must be internal to the compiler. I don’t think Julia should expose it, as it is an implementation detail.

Exactly, this is the type that the variable will have.

As said by @ufechner7, it allows the compiler to know the type of the variable, which in turn allows the compiler to specialize methods that use the variable on the type of it. This specialization on type information is what allows Julia to compile to fast native code.

Amro · May 16, 2022, 7:26pm

Thank you very much!
I got the whole picture except the exact meaning of the binding as I just understood it as the type for the object. If it is not the exactly the type, could you please give me example for two objects that they have the same value and type (pointer?) but different binding?

suavesito · May 16, 2022, 8:28pm

I think I could have explained it better. I think maybe a better name for a value is to call it object. A binding is a relation between an object and a name. So for example

mutable struct Thing
    a::Int
end

a = Thing(1) # `a` is the name, `Thing#1` is the "object", `a` is bound to the object `Thing#1`, which has type `Thing` and content `1`

b = Thing(1) # this is a different object _because_ the type `Thing` is mutable (you can change `b.a` to be different), we will call this object `Thing#2`

a === b # false, diferent objects

c = a # `c` is bound  to the object `Thing#1`. This is a _new_ bound, which means we can change the content of `Thing#1` through `c` and it will be reflected on `a` (the other name bound to `Thing#1`)

println(a) # prints `Thing(1)`
c.a = 2
println(a) # this changed to `Thing(2)`

Some things can be said about bindings,

Binding is a relation between an object in memory and a name
A binding does not have type, the object in memory is what have type.
The same name can be bound to a different object, i.e., first you do a = 1, then a = [1], the name is the same (a), but the object bound to it is different (1, later [1])
When you say a bond is constant, it means that the object associated with the name will not change, which in turn implies that the type associated with the name (through the object) will not change.

I hope this makes it more clear. But in any case, I would not worry too much about the exact meaning of binding, as you can program without thinking much about it.

The really important part is that you follow the advices given above by ufechner7.

Amro · May 16, 2022, 8:39pm

Elrod:

@inline function AmulB!(C, A, B)
    @turbo for n ∈ indices((B,C), 2), m ∈ indices((A,C), 1)
         Cmn = zero(eltype(C))
         for k ∈ indices((A,B), (2,1))
            Cmn += A[m,k] * B[k,n]
        end
        C[m,n] = Cmn
     end
end

Does the ! after the function refer to something special?

Elrod · May 16, 2022, 8:47pm

In Julia, the ! is a convention to let you know that the function is mutating one or more of its arguments.
By convention, the arguments being mutated are the first non-callable arguments.
I.e., AmulB!(C::AbstractMatrix, A::AbstractMatrix, B::AbstractMatrix) is mutating at least C, but maybe also A, or even all three.
In this case, it is only mutating C.

The ! is useful, so that you won’t be surprised if calling AmulB! suddenly changes an input.
Mutating inputs isn’t always what people want. If it isn’t, you may need to first make a copy to mutate the copy instead.

As a second example, map!(f, dest, src) mutates dest. Callables, like functions, tend to be placed in front of everything else – including mutated arguments, because of the do syntax in Julia.

map!(dest, src) do x
    # do something to x
end

The do syntax creates an anonymous function, and places that as the first argument of map!.

TLDR: the ! is a way of letting people using a function know that this function mutates input arguments (and those arguments are generally those at the front of the argument list).
Knowing the convention makes it easier to understand what code like AmulB!(C,A,B) is doing; otherwise, it’d be a bit mysterious what’s happening to the variables in the program. Even with the convention, it is still less clear than C = A*B, but the convention helps.

Amro · May 17, 2022, 4:25pm

Thank you very much for your explanation. Does when we say a bond is constant mean that there should be only one name referring to the object?

Amro · May 17, 2022, 4:35pm

Thank you very much for your explanations! I got it.
One thing regarding view. Does it help also for SparceMatrix?

suavesito · May 17, 2022, 5:18pm

Nope, the binding being constant means that you cannot change the object associated with the name. But you can bind the same object to another name. For example

const a = [1, 2, 3] # the array is bound to `a`, as this is constant you cannot change the object bound to `a`

a = 1 # this error, because you try to change the object bound to a

b = a # his create a new binding of the array object, but this time the new binding is to `b`

a === b # true, they are bound to the same object

Amro · May 17, 2022, 6:15pm

Thank you very much! I got it.

Amro · May 20, 2022, 2:01pm

One thing regarding view . Does it help also for SparceMatrix? Because when I tried it in my case, it did lead to a better performance. So, I am wondering if it is because of my improper usage or something belongs to its implementation.