Pointers in Julia documentation

General Usage
,
1

Hi, I was trying to implement some algorithms and data structures such as linked list, for which I need pointers. I wanted to know why is the use of pointers so obscured. I have not really found any formal explanation of use and limits of them in the documentation. Some spread answers here and there in forums, but I really want to know, can I make a fully working code for linked lists, graphs etc dealing with pointers.

To make it explicit:
In C++ I can have an object Node that stores it’s element and the pointer to the next node:

template <typename T>
class Node{
    Node* next:
    T elem
    //constructor...
}

But in Julia, without pointers, I would have to make

mutable struct Node{T}
    el::T
    prev::Union{Node{T},Nothing}
    next::Union{Node{T},Nothing}
end

But that, to my understanding, would be less efficient in memory than a pointer, because it would need for the node object to contain the whole two related node objects (one object if is a single linked list), instead of just having a pointer like field.

2

You don’t want pointers. You need to understand pass by sharing. For an example linked list implimentation, see DataStructures.jl/src/list.jl at master · JuliaCollections/DataStructures.jl · GitHub

3 Likes
3

I edited my question to be clearer. I would need pointers beyond the passing by reference aspect of them

1 Like
4

one option is

mutable struct Node{T}
    el::T
    prev::Node{T}
    next::Node{T}
end

and make prev/next be circular if there is no next/prev element.

1 Like
5

But my point is that by having the field prev as type Node{T} I am not being efficient in memory. Every Node will have itself another object Node as its field. In the c++ code it just has a reference, if the type T is memory consuming, the longer the list, the more I will be “duplicating” memory and being inefficient, am I wrong?

1 Like
6

these Node{T}s are just references.

mutable struct Node{T}
    el::T
    prev::Node{T}
    next::Node{T}
    function Node(el::T) where T
        N = new{T}(el)
        N.prev = N
        N.next = N
    end
end
julia> dump(Node(5))
Node{Int64}
  el: Int64 5
  prev: Node{Int64}#= circular reference @-1 =#
  next: Node{Int64}#= circular reference @-1 =#
2 Likes
7

Yes. Consider

struct Foo  # or mutable struct, doesn't matter
    x::Bar
end

If Bar is a mutable type, an instance of Foo will only contain a reference, not an inlined value. This is necessary to preserve the semantics of mutable memory: If I stick the same instance of Bar into several different instances of Foo and mutate it via one of them, the change should be observed in all of them. This is only possible if all the Foos contain a reference to the same Bar, rather than separate copies of the Bar value.

Since your Node is mutable, it will always be passed around by reference and never duplicated, whether inside other Nodes or anywhere else in your program.

Thus you can often get around without explicitly worrying about pointers in Julia. For the few occasions where you do, there’s a dedicated wrapper called Ref.

2 Likes
8

Thank you. One doubt: if Bar is just a struct, not mutable, then would it also contain just the reference? Where in the documentation can I see that

9

If Bar isn’t mutable then the compiler is allowed to make either choice (but usually will store it inline). The fundamental difference between mutables and immutables is that mutables have reference identity while immutables have value identity. Since you can’t change the value of an immutable, your program can’t find a difference between different “copies” of an immutable with the same value.

5 Likes
10

I find myself only very rarely reaching for Ref (the julia-level equivalent to a pointer) and even more rarely for an actual Ptr (actual, C-like pointers). The latter is basically only relevant for FFI interop.

If you’re worried about memory consumption of your Node struct, try one using Ref to refer to its neighbors and compare its sizeof with the version of the struct where you place the neighbors “directly inside” the struct. They should be the same in the mutable case, due to the above mentioned pass-by-sharing.

3 Likes