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

General Usage Performance
1

Hello! I’ve been taking a stab at porting the YASS sokoban solver 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:
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:
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.
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:

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?

2

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.

3

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

1 Like
4

Gotcha. In that case, I wonder whether this might be helpful.

1 Like
5

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
1 Like
6

As for your first question, I guess you can use usual thing, that one can do, when he is implementing trees in 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

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.

1 Like
7

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)

8

The {T} templating is a nice trick!

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

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))))
1 Like
9

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.

3 Likes
10

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.

6 Likes
11

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

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.
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
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:
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!

1 Like
12

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

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).

1 Like