This question might be a stupid question. If it is, I haven’t realized why.
Does Julia have efficient move semantics?
Consider the following example, which is a stupid example, but it’s also a simple example.
v::Vector{String} = [some stuff]
function does_a_move_operation(v::Vector{T})::Vector{T} where T
t::Vector{T} = []
while length(v) > 0
element = pop!(v)
push!(t, element)
end
return t
end
This function is O(N). But it could have been O(1), if there were some efficient way to move the memory referenced by v to t. Actually, it would probably have to swap the references t and v otherwise v wouldn’t reference anything anymore.
Consider the point of view of the client.
v = ...
v2 = does_a_move_operation(v)
# v still needs to be "valid", unless it
# becomes "uninitialized" (?)
Note the following doesn’t have the same semantics.
function does_not_do_a_move(v)
t = v
return t
end
# because
v = [1, 2, 3]
v2 = does_not_do_a_move(v)
println(v) # [1, 2, 3] !
v2[3] = 4
println(v) # [1, 2, 4] !
I think your question is meaningless and confused due to C++ -brain.
Let me propose a definition of “move semantics”; with that the question almost answers itself. If that is not what you meant with “move semantics”, then please clarify.
Heap memory management. This is the issue of determining lifetimes of heap-allocated memory. This is opposed to arena-allocated memory (most important example of arena allocation is stack allocation). The difference between heap and arena allocation is that lifetimes of arena allocated memory have an additional invariant: Lifetimes of two chunks of memory in the same arena never overlap nontrivially, i.e. they are either subsets of each other or they are distinct.
Unique ownership. A useful technique is to tie the lifetimes of two allocations to each other: There is a parent allocation and a child allocation, and the property that the child allocation will not outlive the parent allocation (yeah, CS terminology uses quite broken metaphors). This allows a convenient form of semi-automatic memory management: When the parent gets free’d / finalized / destroyed, then some system automatically does the same for the child. This technique is notably used a lot in the C++ and rust languages.
This technique is only sound, i.e. avoids use-after-free, if nobody takes a reference/pointer to the child and keeps it around until after the parent’s death. There are various language / API approaches to discourage / disincentivize people from writing such code and compilers from compiling such broken code.
When using a system that uses unique ownership for semi-automatic memory management, then APIs to create a parent object are in a conundrum. An issue is that if you have the prospective child in hand, already allocated, and now want to create the parent, then you want to establish unique ownership of the parent over the prospective child, but the compiler / language might not have been aware of whether you already had unique ownership of the child. Typically there are two paths:
4.1. A copy is taken, because the invariant cannot be established.
(trying to figure out whether other references/pointers to the prospective child have already escaped and may outlive the parent is too hard)
4.2. No copy is taken, the invariant can be established, either by the language or by programmer fiat (on pain of UAF vuln). C++ has its own language-lawyered giant tower of abstractions, and calls this “move semantics” / “move constructor”. It is important to note that no move nor construction actually happens, the “moving” / “construction” is only happening in the C++ -brain.
In terms of automatic memory management, julia uses garbage collection, not unique ownership for all julia objects, i.e. most allocations.
In other words, your question is meaningless except for the tiny amount of ownership-based memory management!
The main examples of ownership-based memory management are the backing allocations of 1. built-in Array/Memory and 2. custom code like BigInt.
Either way, since there is no language-level concept of unique ownership, move semantics works the same as in C – your library has conventions / requirements on which pointers are unique wrt lifetimes, and then you simply set pointers where you need them, adhering to the required invariants without any compiler help.
Focus on the example code I provide, to put it into a descriptive form:
In the first example, I used pop! to transfer elements from one data structure to another. Note the exact choice of data structure is not that important. It could have been a boxed type, or a Vector or something more complex than a Dict. The performance of this is O(N).
In the second example, I show some pseduocode for an O(1) operation, which I do not believe exists in Julia - but I am hoping that I am mistaken.
I could have written the second example like this:
function does_do_a_move_as_desired(a)
tmp = move(v) # or tmp = nothing; swap(v, tmp)
return tmp
end
v = [1, 2, 3]
v2 = does_do_a_move_as_desired(v)
println(v) # nothing (ok)
v2[3] = 4
println(v) # nothing (ok)
I hope it’s clear?
The important point here is the semantics. A function takes a data structure (here, a Dict) as an argument. Is there an optimized way to move the data to another variable.
In Python, there is no way to do this. (As far as I am aware.) Since Julia variables have the same semantics as Python, so possibly the situation is the same?
To put it another way, there’s no way to do this:
function example(d::Dict)
tmp = d
delete_all_elements_of(d)
return tmp # no elements in tmp !
end
… and this would also be pointless because from the point of view of the caller
d = Dict(...) ...
d2 = example(d) # d is a reference,
# the reference is copied
# no change to d (the reference) here, the only thing
# which changes is the object referenced by `d`
Let me know if it still isn’t clear? I suspect the answer here is “Julia doesn’t have this”.
Since @world-peace specified that v / d should be ‘valid’, I think
d2 = d
d = empty(d2)
would be ‘better’. But if I’m reading the thread correctly, I think the goal is to do this in a function: d2 = move_function(d) which would output a ‘copy’ of d and empty! d inplace, but without actually explicitly copying or emptying (so basically swapping pointers). I’m not sure if this is possible without actually using RefValues. But clearly, the workaround is not very complicated.
function example(d::Dict)::Dict
d2 = d
d = nothing
return d2
end
my_d = Dict(1=>2)
my_d_2 = example(my_d)
println(my_d) # prints contents of: Dict(1=>2), NOT `nothing`
Can you do even do this in any language, say C++? I.e. write a (void) function
that takes in (a pointer/reference of) some Object object, such that afterwards &object points somewhere different. This does not seem to make sense to me.
You cannot make &object point somewhere different, but you can replace all data within object, such that the value of object changes after exiting the function. See std::swap, std::move, operator=.
Others have already said that relabeling in the form x, y = empty(x), x effectively moves x to y. It might be inefficient in Python due to interpretation rules, in Julia it’s optimized by the compiler.
But directly, no, Julia is strictly pass-by-value language, so you cannot swap “contents” of a variable such that it’s visible outside, in that respect Julia is exactly like Python.
As @eldee has mentioned, you can move the contents of a Ref (or any other mutable struct), but not contents of a variable.
Example:
function move_ref(x::Ref{T})::Base.RefValue{T} where {T}
# Ref unifies references to a single value and to an array element
# in context of this function, they should behave the same
tmp = Ref(x[]) # must be RefValue
x[] = default(T) # default(T) is some function that returns the default value for the corresponding type
return tmp
end
Oh interesting, perhaps Ref{x} provides the semantics I’m looking for here. Let me have a think about it and see if I can integrate this into my existing code.
For your curiosity, here’s some info about some languages which allow this:
Rust:
Everything is move by default rather than copy by default. This is not just for speed, but also because it makes more sense with the single owner rules of the borrow checker logic, which is there to protect against undefined behavior which exists in a language like C++. This means you effectively always “move” data rather than copy it. You can get explicit copying behavior with .clone(). Some types like POD types actually copy instead of move, but they look like they move. Rust also has references, and box types which behave like pointers.
C++/C
Since you have the classical raw pointers, you can always take the address of a value, and using that modify the value itself. This is how you can use arguments of functions to get data back out rather than just relying on return values. It doesn’t move by default, but modern C++ has move semantics for objects, so you can construct an object by moving data, or make an assignment to and object by moving data, rather than copying data.
These are very hand-wavey overviews. You can get a much more concrete view of how it works, if you get stuck into learning either language. That isn’t something you can do in 10 minutes, or even a couple of hours. There’s a lot to learn, in both cases.
Please state an example of what you consider “move” in C.
Then we can tell you whether something like that can be done in julia.
This is nonsense. Almost everything you can do in C++ you can also do in C, with potentially less syntactic sugar and less compiler help / enforced invariants. So you can desugar whatever you understand under “move” to plain C (or to assembly!), and then use that to tell us what the hell you want.
You will probably discover that the “move” is not a real thing, in the sense of instructions that your CPU executes. You will see that the “move” happens only with respect to an abstraction that exists in C++ (and Rust). Julia and C and java and python and javascript and bare metal / CPUs do not have the underlying abstraction on a language level (which I labeled “unique ownership”), and the question is therefore meaningless on a language level.
There’s definitely a core misunderstanding about Julia’s (and Python’s) concept of variables, and it seems to be rooted in assuming characteristics of variables in languages like C, C++, and Rust.
Brass tacks, what is move semantics? You have one variable owning its data, and after the move, you have a 2nd variable owning said data while the first variable owns nothing. This contrasts with copy semantics where the 2 variables end up owning their own separate copies of data. Rust’s description of the Copy trait gives a good example of this behavior. Those are the language-level characteristics that don’t really explain why things are the way they are. When we discuss the implementation, then it becomes clearer: copying data around is expensive, and if we really just need the 2nd variable, we can just make the existing data belong to the 2nd variable and flag the 1st variable as inaccessible. Just to emphasize, it’s the motivating implementation details of move or copy semantics that concern performance, not the language-level details.
None of that matters in Julia and Python where variables do not own data, instances do. Variables are only references that an instance may have. Now, that may immediately sound like pointers are involved, but note that there are no pointers on the language level. Instance identity and the im/mutability of instances are language-level details, and they do have implications for implementation.
To clarify what is happening here, you are asserting that the variable v will be assigned to a Vector{String} instance, and any assignment to an instance will attempt a conversion of said instance to said type. Prior to this assignment, you instantiate Vector{Any}; incidentally, you don’t need and likely don’t want to, you might prefer String[#=some stuff=#] to make the “conversion” do nothing.
Vector happens to be a mutable type, which in Julia and Python means that the instance can be changed; the important implication is that all its references observe that change afterward, no assignments involved. That indeed implements its references with pointers, so the “O(1)” action is simply assigning another variable to that instance. You can use v to help: t = v. When you pass the instance as an argument into a method, you do that as well; the v in does_a_move_operation is different from the global v. No move, no copy, just assignment on the language level.
If you’d like global v to no longer be assigned to the instance after you assign another variable, you’ll have to reassign it in the global scope. The usual “move” is to assign it to nothing, but your type annotation would force a conversion that errors. You could have done v::Union{Vector{String}, Nothing} if you want that capability. Of course, this is completely unnecessary for any other variable being assigned to the Vector{String} instance in “O(1)”, just a mimicry of move semantics.
Instead of explaining more about immutables and how they’re implemented, I’ll end by pointing out how “indirect” this is compared to C/C++/Rust etc; our compiler decides on the instructions that map more cleanly to the traditional copies, moves, pointers, etc. The intention of such a design is to simplify how we write and think; it works on some level, but obviously when we are concerned with performance, we have to worry about implementation to some degree. The advantage of lower level languages (in the secondary relative sense, these are strictly high-level languages) is the direct control, and Rust in particular could only implement its GC-less memory management because of the semantics given to the user.
The answers to both of your questions can be found by reading the example with the description of the semantics which I provided. Both replies suggest that you have not understood it.
with swapref(a,b) = begin tmp = a[]; a[] = b[]; b[] = tmp; end.
This looks slightly more verbose on surface, but is much cleaner: The very first thing the compiler does for a local variable that has its address taken is to turn it into two local variables: A pointer and a stack-slot.
In C++ one has the even less transparent syntax where you can write swap(v1, v2) and this can be declared as by-ref and becomes syntactic sugar for the C version. This really is mere syntactic sugar – you can compile your C++ thing with a header that declares by-ref arguments, and then link against a version that takes pointer arguments.
I think you are confused about references and bindings?
Really, please try to state an example of what you want in C, python, javascript, java or some kind of assembly code. If you come to the conclusion that these languages do not support whatever you understand as “move”, then julia probably doesn’t support it either.
I still do not understand what you mean by “move”. Just type down the assembly code and ask “how do I get julia to emit this code”?
On the other hand, there are interesting move/swap like constructs that julia lacks sometimes. These constructs would be easy to implement in C (using julia.h), but they are not supported because they would break invariants in julia (e.g. garbage collection or const-ness).
An example would be: convertInPlace(x::Vector[Float64])::Nothing that takes a vector of Float64 and turns it into a Vector[Int64], in place, such that you can write
a = [1.0]
convertInPlace(a)
a isa Vector[Int64] #true
You could implement that by mutating the object header, via pointer arithmetic / C. If you run the above snippet in the interpreter, it may work. If you run it in compiled code, it won’t work: The compiler assumes that this part of the object header stays constant. This is equivalent to changing the vtable of a C++ object via pointer arithmetic: You can certainly do it, but it’s UB and will almost surely break something.
I honestly cannot tell whether you are hopelessly confused and ask for something that is meaningless, or whether you are asking for something well-defined that is actually supported, or whether you are asking for something well-defined that is not supported due to language limitations / invariants (like the above example of in-place mutation of the type of an object).
I think one fundamental difference between this and your example involving Dict above is that swap here fundamentally takes a pointer to something, not the thing itself. This is generally not done/needed in Julia, because passing a large object (such as a Dict) around, or assigning it to a new variable, does not copy the object around by default. Neither does it move anything; it shares access to the variable.
Generally, the way I think about variables in Julia is that they’re a label for some object. An object can have many labels, and assigning something to one of those labels merely takes that label and puts it on something else - the other labels referring to the same object are unaffected. Of course, if you write something into the object (e.g. by setting something at an index), that will be visible through all variables that have access to the object.
Coming back around to swap/move semantics, this means that if you want to affect other variables and what they refer to, all of your variables would need to be assigned the sameRef{Dict} from the beginning. Then you can change the Dict the other variables are “pointing” to by swapping out the specific Dict the sole Ref holds onto.
Note that this doesn’t imply that assigning has to copy either - in fact, the vast majority of cases (barring some cases of implicit convert) won’t copy. For example, in this function:
function foo(n)
a1 = Vector{Int}(undef, n)
a2 = a1
a3 = a2
a4 = a3
return a4
end
all the various a* refer to the sameVector{Int} object; there is no copy constructor, there is no move constructor (you can’t overload assignment!). The variables are only labels, stuck onto the object like post-it notes. Of course, the same applies to objects passed into functions as well - the argument name is simply another label referring to the incoming object. That’s why you can’t “unassign” the variable outside of your example function by reassigning the variable passed in through an argument; they’re two separate labels.