# Restructuring Performant Code (C, Pascal) with Type Unions and Pointers

**URL:** <https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374>\
**Category:** Performance\
**Created:** [April 1, 2021, 4:09pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374 "2021-04-01T16:09:14Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![tawheeler](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tawheeler/32/17657_2.png) [@tawheeler](https://discourse.julialang.org/u/tawheeler)\
**Post date:** [April 1, 2021, 4:09pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/1 "2021-04-01T16:09:15Z")

</div>

Hello! I’ve been taking a stab at porting the [YASS sokoban solver](https://github.com/joriswit/YASS/blob/master/app/src/main/jni-pascal/YASS.pas) into Julia as a programming exercise. It is a 20k line Pascal program that can solve some pretty hard sokoban problems (block pushing) in under a second.

I am struggling a bit converting the programming style that Pascal allows into something compatible with Julia. So far there are three main structural differences:

1. Pascal uses a lot of pointers. For example, the position type effectively has linked lists of board positions by storing edge pointers:

```julia
TPositionLinks = record
    Prev::PPosition;
    Next::PPosition;
end;

TPosition = packed record // Pascal's version of struct
   HashValue::THashValue;
   HashBucket::TPositionLinks;
   Parent::PPosition;
   ...
end;

```

where `PPosition` is a pointer to a `TPosition`. I’m not sure how to translate that into Julia. Is the best way forward to pre-allocate a vector of positions and store indices into that array instead? IE replace every `PPosition` with a `PositionIndex = Int`?

1. The Pascal types do a lot of careful memory layout. Structs are packed. Furthermore, I am pretty sure they assume memory is located inside the struct rather than farmed out via references to substructs:

```julia
TOptimizerPosition = record
   Position:TPosition;
   MoveCount:UInt16;
   BoxLines:UInt16;
   BoxChanges:UInt16;
   PushingSessions:UInt16;
end

```

In my Julia equivalent, I made TPosition a mutable struct. As a result, my Julia equivalent of TOptimizerPosition contains a reference to a Position rather than baking in the value. I am definitely not far enough into this process to really know, but I highly suspect that this is going to cause problems, if the solver uses memory manipulation tricks based on byte offsets to quickly access information. Is that something I have any hope of replicating in Julia, or does does such an approach have to be totally abandoned?

1. The solver makes use of C-style type unions, in which a struct has fields that overlap in memory.

```julia
TThingy = packed record
   case TThingy of
      subA:
        (a:Uint32;
         b:Integer);
     subB:
        (c:Float32;
         d:UInt16;
         e:Int16)
end

```

Without rearchitecting, all I came up with was defining structs for all possible union entries:

```julia
struct TThingySubA
    a::UInt32
    b::Int
end

struct TThingySubB
    c::Float64
    d::UInt16
    e::Int16
end

struct TThingy
   sub::SubA
end

```

and then reinterpret casting `sub` into the struct I want at any given point in time. Is that viable?

While the Pascal architecture is definitely more confusing, it has led to a super-efficient solver. Does this difference in programming represent an inherent tradeoff - IE Julia users cannot manage memory at this low level, and thus cannot quite get such solver speeds, but we get a lot of other benefits that make up for it in other areas?

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [April 1, 2021, 5:24pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/2 "2021-04-01T17:24:11Z")

</div>

I don’t know how to answer your question directly, but maybe one of these sources will contain some insights. In either case, I look forward to seeing what solution you settle on.

> **[JuMPing into Puzzle Solving with Linear Programming](https://towardsdatascience.com/jumping-into-puzzle-solving-with-linear-programming-57852609d516)**
>
> Linear programming (LP) is a powerful technique to solve optimization problems, and you will often see it applied to problems from airline…

> <https://github.com/jump-dev/JuMP.jl/blob/40abf8dd626b998becb733c054edee58f92757c3/docs/src/tutorials/Mixed-integer%20linear%20programs/sudoku.jl>

---

<div class="post-metadata">

**Author:** ![tawheeler](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tawheeler/32/17657_2.png) [@tawheeler](https://discourse.julialang.org/u/tawheeler)\
**Post date:** [April 1, 2021, 5:32pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/3 "2021-04-01T17:32:45Z")

</div>

Sorry, I messed up. Its sokoban, not sudoku. Block pushing puzzles.

---

<div class="post-metadata">

**Author:** ![Christopher\_Fisher](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/christopher_fisher/32/26132_2.png) [@Christopher\_Fisher](https://discourse.julialang.org/u/Christopher_Fisher)\
**Post date:** [April 1, 2021, 5:40pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/4 "2021-04-01T17:40:02Z")

</div>

Gotcha. In that case, I wonder whether [this](https://rosettacode.org/wiki/Sokoban#Julia) might be helpful.

---

<div class="post-metadata">

**Author:** ![tawheeler](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tawheeler/32/17657_2.png) [@tawheeler](https://discourse.julialang.org/u/tawheeler)\
**Post date:** [April 1, 2021, 5:48pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/5 "2021-04-01T17:48:07Z")

</div>

Thank you.  
More specifically I’m wondering:

1. What does one do in Julia when C or Pascal uses in-struct pointer-style linked lists
2. What does one do in Julia when C or Pascal relies on packed structs and bit offsets
3. What does one do in Julia when C or Pascal store different types in the same memory address

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [April 1, 2021, 5:54pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/6 "2021-04-01T17:54:37Z")

</div>

As for your first question, I guess you can use usual thing, that one can do, when he is implementing trees in Julia

```julia
mutable struct PositionLinks{T}
  prev::Union{T, Nothing}
  next::Union{T, Nothing}
end
PositionLinks{T}() = PositionLinks{T}(nothing, nothing)

struct Position
  hashvalue::HashValue
  hashbucket::PositionLinks{Position}
  parent::Position
  ...
end

Position(hashvalue, parent, ...) = Position(hashvalue, PositionLinks{Position}(), parent, ...)

```

This way you can create `Position` and update its links. Not sure whether it is the fastest possible solution, but premature optimization is one of the roots of all evils. This approach will give you close enough translation, which you can change later if necessary. It will be much easier when you have fully written Julia code.

You can use just

```julia
mutable struct PositionLinks{T}
  prev::T
  next::T
  PositionLInks{T}() = new{T}()
end

```

and check fields on `undef`, but in my experience it was slower than testing for `Nothing`.

---

<div class="post-metadata">

**Author:** ![tawheeler](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tawheeler/32/17657_2.png) [@tawheeler](https://discourse.julialang.org/u/tawheeler)\
**Post date:** [April 1, 2021, 6:02pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/7 "2021-04-01T18:02:27Z")

</div>

Looks like reinterpret is okay, and the general consensus is that C-style unions are not a thing Julia really does (which is okay). ([post here](https://discourse.julialang.org/t/port-c-union-to-julia/950/2))

---

<div class="post-metadata">

**Author:** ![tawheeler](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tawheeler/32/17657_2.png) [@tawheeler](https://discourse.julialang.org/u/tawheeler)\
**Post date:** [April 1, 2021, 6:11pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/8 "2021-04-01T18:11:44Z")

</div>

The {T} templating is a nice trick!

This appears to work (even if Position is mutable).

```julia
julia> mutable struct PositionLinks{T}
                 prev::Union{T,Nothing}
                 next::Union{T,Nothing}
              end
julia> PositionLinks{T}() where T = PositionLinks{T}(nothing, nothing)
julia> mutable struct Position
                 v::Float64
                 bucket::PositionLinks{Position}
              end
julia> p1 = Position(1.0, PositionLinks{Position}())
Position(1.0, PositionLinks{Position}(nothing, nothing))
julia> p2 = Position(2.0, PositionLinks{Position}())
Position(2.0, PositionLinks{Position}(nothing, nothing))
julia> p1.bucket.next = p2
Position(2.0, PositionLinks{Position}(nothing, nothing))
julia> p2.bucket.prev = p1
Position(1.0, PositionLinks{Position}(nothing, Position(2.0, PositionLinks{Position}(Position(#= circular reference @-4 =#), nothing))))
julia> p1.v = 999
999
julia> p2.bucket.prev
Position(999.0, PositionLinks{Position}(nothing, Position(2.0, PositionLinks{Position}(Position(#= circular reference @-4 =#), nothing))))

```

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [April 1, 2021, 6:14pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/9 "2021-04-01T18:14:44Z")

</div>

Not directly related to the question, just an advice: you may want to adjust `show` function, otherwise it is very hard to read output and it will slowdown debugging sessions.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 2, 2021, 2:39pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/10 "2021-04-02T14:39:51Z")

</div>

> [@tawheeler](#):
>
> Thank you.  
> More specifically I’m wondering:
> 
> 1. What does one do in Julia when C or Pascal uses in-struct pointer-style linked lists
> 2. What does one do in Julia when C or Pascal relies on packed structs and bit offsets
> 3. What does one do in Julia when C or Pascal store different types in the same memory address

Generally, I would approach this problem at a more abstract level and reimplement the _algorithm_, instead of translating an implementation from another language which implicitly has already made a lot of choices that may be idiomatic in that language, but are not necessarily essential to the algorithm.

Especially as the code you linked is a 1.7Mb / 27kLOC monstrosity _in a single file_. Translating that to Julia _as is_ is a monumental project which at the same time may not help you develop skills for writing idiomatic Julia.

---

<div class="post-metadata">

**Author:** ![tawheeler](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tawheeler/32/17657_2.png) [@tawheeler](https://discourse.julialang.org/u/tawheeler)\
**Post date:** [April 2, 2021, 5:01pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/11 "2021-04-02T17:01:49Z")

</div>

So the pascal architecture implements a transposition table by having in-struct pointers. It looks something like this:

```julia
mutable struct TranspositionTable
   positions::Vector{Positions} # All of the positions!
   best_position::*Position # pointer to best position in the list
   current_position::*Position # pointer to current position in the list
   ...
end

struct Position
   move::Move
   player_pos::UInt16
   parent::*Position # pointer to parent in TranspositionTable
   successor::*Position # pointer to successor in TranspositionTable
   ...
end

```

It makes sense that this representation is not Julian. As such, I see several options.

1. Use indices instead of pointers. This is what I listed originally.

```julia
PositionIndex = UInt
mutable struct TranspositionTable
   positions::Vector{Positions} # All of the positions!
   best_position::PositionIndex
   current_position::PositionIndex
   ...
end

struct Position
   move::Move
   player_pos::UInt16
   parent::PositionIndex
   successor::PositionIndex
   ...
end

```

This approach is pretty close to the original. Instead of following pointers, you follow indices into arrays.

1. Use the Union{T, Nothing} approach

```julia
mutable struct TranspositionTable
   positions::Vector{Positions} # All of the positions!
   best_position::Union{T, Nothing}
   current_position::Union{T, Nothing}
   ...
end

struct Position{T}
   move::Move
   player_pos::UInt16
   parent::Union{T, Nothing}
   successor::Union{T, Nothing}
   ...
end

```

This feels unjulian, and because of the order in which things are declared, its awkward that T cannot be forced to be of type Position. As mentioned above, it messes up @show and similar display methods, as one can end up with very long chains.

1. Move lists out of the position and into the transposition table:

```julia
PositionIndex = UInt
mutable struct TranspositionTable
   positions::Vector{Positions} # All of the positions!
   best_position::PositionIndex
   current_position::PositionIndex
   parent_positions::Vector{PositionIndex} # For each position, its parent index in positions (or 0)
   successor_positions::Vector{PositionIndex} # For each position, its successor index in positions (or 0)
   ...
end

struct Position
   move::Move
   player_pos::UInt16
   ...
end

```

This seems quite nice, since the Position type becomes only concerned with its own data and its easier to use a non-mutable type.

In all three cases we can preallocate a big transposition table and keep it up to date.

There are still technicalities to work out. For example, YASS uses a pointer partway inside of the positions vector to make double-use of the memory for “reserved areas like the hash buckets and the precalculated deadlock-sets”. It is really trying to pack a lot into as small a space as possible.

> Generally, I would approach this problem at a more abstract level and reimplement the _algorithm_ , instead of translating an implementation from another language which implicitly has already made a lot of choices that may be idiomatic in that language, but are not necessarily essential to the algorithm.

If the objective is to write an efficient solver that has a fixed amount of memory (ie, 1GB), it is hard to not want to re-use memory locations for multiple purposes. I was hoping that with a 1:1 translation my implementation would not diverge and thus get me horribly lost. That being said, it is almost certainly better to write a more easy to understand version first and worry about that sort of optimization later.

Thanks all for the discussion!

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [April 2, 2021, 5:39pm UTC](https://discourse.julialang.org/t/restructuring-performant-code-c-pascal-with-type-unions-and-pointers/58374/12 "2021-04-02T17:39:13Z")

</div>

> [@tawheeler](#):
>
> This feels unjulian, and because of the order in which things are declared, its awkward that T cannot be forced to be of type Position.

If you just want a self-referential struct, you can do that without any tricks:

```julia
julia> struct Position
         parent::Union{Position, Nothing}
       end

julia> p = Position(nothing)
Position(nothing)

julia> p2 = Position(p)
Position(Position(nothing))

```

The type parameter trick is only necessary when you have two different types which need to contain instances of each other. That doesn’t seem to be the case (at least in the example you posted above).