# Internals of types and how they hash

**URL:** <https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998>\
**Category:** Internals & Design\
**Created:** [February 9, 2024, 5:19pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998 "2024-02-09T17:19:43Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [February 9, 2024, 5:19pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/1 "2024-02-09T17:19:43Z")

</div>

> [@Why do hash functions use xor to combine multiple values?](https://discourse.julialang.org/t/why-do-hash-functions-use-xor-to-combine-multiple-values/109967/10):
>
> The common idiom I see and like here is to also hash the type itself.

Yes, that makes a lot more sense, occurred to me that one could just do that after I posted. I presume that `Base.hash(T::DataType, h)` uses the immutable parts of the `DataType` struct? It would kind of have to. That would let the compiler perform the hash once at compile time, and nothing good could come of the hash of a type changing every time a subtype was added…

Edit: checked the layout of `DataType` out of curiosity, and it contains a precomputed `hash` field. So that answers that.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 9, 2024, 5:32pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/2 "2024-02-09T17:32:21Z")

</div>

> [@mnemnion](#):
>
> I presume that `Base.hash(T::DataType, h)` uses the immutable parts of the `DataType` struct?

Are there non-immutable parts of the type? (I don’t think a `<: Type` object is modified when a subtype is added?)

> [@mnemnion](#):
>
> That would let the compiler perform the hash once at compile time

~~I don’t think this currently happens, since~~ hashing a type [does a `ccall` to `jl_type_hash`](https://github.com/JuliaLang/julia/blob/95233619745ef84c96af82299b162aa008a7debd/base/hashing.jl#L34) (which [uses a cached value](https://github.com/JuliaLang/julia/blob/95233619745ef84c96af82299b162aa008a7debd/src/jltypes.c#L1575-L1577) for `DataType`).

It looks like this was finally fixed to be done at compile time just [two months ago](https://github.com/JuliaLang/julia/pull/52427), whereas in prior Julia versions I think type hashing was still doing a `ccall` at runtime.

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [February 9, 2024, 5:40pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/3 "2024-02-09T17:40:26Z")

</div>

> [@stevengj](#):
>
> Are there non-immutable parts of the type? (I don’t think a `<: Type` object is modified when a subtype is added?)

I have a helper function in the REPL for inspecting structs, this is what it returned:

```julia
julia> inform(DataType)
mutable struct DataType <: Type{T}
    0 name Core.TypeName
    8 super DataType
    16 parameters Core.SimpleVector
    24 types Core.SimpleVector
    32 instance Any
    40 layout Ptr{Nothing}
    48 hash Int32
    52 flags UInt16
end

```

So I think types get added to the `types` vector when they’re created, and it is a mutable struct.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 9, 2024, 5:42pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/4 "2024-02-09T17:42:24Z")

</div>

> [@mnemnion](#):
>
> So I think types get added to the `types` vector when they’re created

The `types` vector is not a vector of subtypes, it is a vector of the types of the fields of a `struct`. For example:

```julia
julia> Complex{Int}.types
svec(Int64, Int64)

julia> Complex{Float64}.types
svec(Float64, Float64)

```

Since abstract types don’t have fields, their `types` are empty:

```julia
julia> Real.types
svec()

```

(Of course, beware that these are all undocumented implementation internals.)

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [February 9, 2024, 5:45pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/5 "2024-02-09T17:45:37Z")

</div>

> [@stevengj](#):
>
> The `types` vector is not a vector of subtypes, it is a vector of the types of the fields of a `struct`.

Good to know, that’s what I get for guessing. I wonder why they’re mutable at all then?

In any case, they have a precomputed hash, so adding that to an instance hash function would be pretty cheap, and whatever mutation might happen presumably wouldn’t change it, I’m sure nothing good could come of the hash of a type changing.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 9, 2024, 5:52pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/6 "2024-02-09T17:52:08Z")

</div>

> [@mnemnion](#):
>
> I wonder why they’re mutable at all then?

Probably so that a `DataType` instances can live on the heap and be identified uniquely by a pointer/address.

Instances of an `immutable` type are identified only by their contents, e.g. if I have an array `[3,3,3,3]` then there are 4 copies of `3::Int` being stored, rather than 4 pointers to a single object. This makes a lot of sense for something like a number object, where there are lots of instances (often small), but it makes less sense for types where the number of instances is relatively small (and typically doesn’t grow much during program execution), while the amount of data in each instance is much larger than a pointer. If I have an array `[Int, Int, Int, Int]`, I don’t want to have 4 copies of the `Int::DataType` datastructure, I want to have 4 pointers to the same unique `Int` instance.

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [February 9, 2024, 6:36pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/7 "2024-02-09T18:36:31Z")

</div>

> [@stevengj](#):
>
> Probably so that a `DataType` instances can live on the heap and be identified uniquely by a pointer/address.

Ok, that makes sufficient sense.

Out of curiousity I tried defining a struct and changing the value of the `.hash` field, which threw an error. So clearly “mutable” is not synonymous with “can or should be mutated” here.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [February 9, 2024, 6:50pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/8 "2024-02-09T18:50:53Z")

</div>

> [@mnemnion](#):
>
> Out of curiousity I tried defining a struct and changing the value of the `.hash` field, which threw an error. So clearly “mutable” is not synonymous with “can or should be mutated” here.

You can also mark individual fields of a struct as `const` to ensure that they can’t be mutated after construction of the object anymore. E.g. in this struct:

```julia
mutable struct Foo
    const a::Int
    b::Int
end

```

only `b` can be reassigned once you have an instance of `Foo`:

```julia
julia> f = Foo(1,2)
Foo(1, 2)

julia> f.a = 3
ERROR: setfield!: const field .a of type Foo cannot be changed
Stacktrace:
 [1] setproperty!(x::Foo, f::Symbol, v::Int64)
   @ Base ./Base.jl:53
 [2] top-level scope
   @ REPL[3]:1

julia> f.b = 3
3

julia> f
Foo(1, 3)

```

For `Type`, I’d think the reason its cached `hash` is a constant is because changing that really breaks assumptions about the identity of a type.

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [February 9, 2024, 7:01pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/9 "2024-02-09T19:01:03Z")

</div>

> [@Sukera](#):
>
> You can also mark individual fields of a struct as `const` to ensure that they can’t be mutated after construction of the object anymore.

I’m glad that got added for sure. `DataType` is implemented in C, and has probably had a custom `setfield!` method which throws an error for much longer than `const` fields in mutable structs have been available (1.8 iirc). There may be some mechanism to inform the compiler about the const-ness of a struct field when the struct is defined in C, but no compelling reason to change `DataType` code to use that.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 9, 2024, 8:20pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/10 "2024-02-09T20:20:01Z")

</div>

> [@mnemnion](#):
>
> `DataType` is implemented in C, and has probably had a custom `setfield!` method which throws an error

Close — if you look at the stack trace, it is a [custom `setproperty!` method](https://github.com/JuliaLang/julia/blob/95233619745ef84c96af82299b162aa008a7debd/base/Base.jl#L44):

```julia
julia> Int.hash = 7
ERROR: setfield! fields of Types should not be changed
Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] setproperty!(x::Type, f::Symbol, v::Int64)
   @ Base ./Base.jl:33
 [3] top-level scope
   @ REPL[62]:1

```

The `setproperty!` function is overloadable, whereas `setfield!` is a low-level “builtin function” that cannot be overloaded. This overload was actually added [in Julia 1.7](https://github.com/JuliaLang/julia/pull/37847) … in very old versions of Julia you could silently overwrite internal fields of `DataType`, which presumably would cause bad things to happen. For example, in Julia 1.0, you could do:

```julia
julia> Int.types
svec()

julia> Int.types = Core.svec(Int)
svec(Int64)

julia> Int.types
svec(Int64)

```

Arguably, the custom `setproperty!` method can now be removed, since the fields of `DataType` are declared as `const`. If you now call `setfield!` directly, you still get an error:

```julia
julia> setfield!(Int, :hash, 0)
ERROR: setfield!: const field .hash of type DataType cannot be changed
Stacktrace:
 [1] top-level scope
   @ REPL[66]:1

```

(But if you try hard enough, you can always break Julia’s internals. Heck, you can write to a random pointer address if you insist.)

---

<div class="post-metadata">

**Author:** ![mnemnion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mnemnion/32/206596_2.png) [@mnemnion](https://discourse.julialang.org/u/mnemnion)\
**Post date:** [February 9, 2024, 8:30pm UTC](https://discourse.julialang.org/t/internals-of-types-and-how-they-hash/109998/11 "2024-02-09T20:30:05Z")

</div>

> [@stevengj](#):
>
> Close — if you look at the stack trace, it is a [custom `setproperty!` method](https://github.com/JuliaLang/julia/blob/95233619745ef84c96af82299b162aa008a7debd/base/Base.jl#L44):

Makes sense, the error message has `setfield!` in it and it didn’t occur to me to check the stacktrace. ¯\_(ツ)\_/¯

> [@stevengj](#):
>
> (But if you try hard enough, you can always break Julia’s internals. Heck, you can write to a random pointer address if you insist.)

Good, imho. The goal should be to prevent accidentally ruining the runtime, not to protect the user from their own hubris.