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:
- 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;
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?
- 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?
- 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?