A while back I wrote TableSalt - a constraint satisfaction framework written in [currently pure] lua. Every now and again I'll revisit it and try to make it run faster and get rid of any bugs found along the way. For benchmarking I use my SudokuSolver on a test of 95 sudoku puzzles.

My goal is a 100ms average. Back in May 2014 I was chilling at 337ms. Before these layout changes, I was at 253ms. Now I'm at 222ms and am only inching ever closer!

Original Code Layout

Initially I had a cell object, this is best thought of as an empty "cell" in sudoku or a variable in constraint satisfaction problems. Each cell has a domain, value, and a reference to each of the constraints it is associated with.

As such the code was pretty straigtforward:

function cell:initialize(domain)  
     self.domain = domain
     self.value = nil
     self.constraints = {}
 end

I needed a table of cells to keep track of all the cells:

self.cells = {}  
for i = 1, self.size do  
    self.cells[i] = cell:new({unpack(domain)})
end  

The {unpack()} created a deepcopy for each cell's domain. unpack is a built-in lua function that explodes a table, the curly brackets around it create a new version and a deep copy is born!

The Backup

While writing TableSalt, I wrote a ForwardCheck (or look-ahead) function that needed to backup and restore the current state of the cells. Easy enough:

function TableSalt:backupCells()  
    local serial = {{}, {}}
    for i = 1, self.size do
        serial[1][i] = {unpack(self.cells[i].domain)}
        serial[2][i] = self.cells[i].value
    end
    return serial
end

function TableSalt:restoreCells(serial)  
    for i=1, self.size do
        self.cells[i].domain = serial[1][i]
        self.cells[i].value = serial[2][i]
    end
end  

The Problem.

This was slow. When I ran the code against a profiler, the code backup and AllDiff constraint were usually the prime culprits of wasting time. On my [unrealistic?] goal towards 100ms, wasting time on backups and restores was not an option. I read up on optimizing lua code and posted on stackoverflow looking for help.

SPEEDING IT ALL UP!

I got rid of the cell class. Arguably, it's bad code design, but I did it in the name of speed. Here's what the initializer code became:

self.cellValue = {}  
self.cellDomain = {}  
self.cellConstraint = {}  
for i = 1, self.size do  
    self.cellConstraint[i] = {}
    self.cellDomain[i] = {unpack(domain)}
end  

and as some of you lua aficionados might notice - I could've used a self.cells = {} and made each of those tables into self.cells.value, self.cells.domain, and self.cells.constrains, but I would gain ~4ms if I did so. If I ever get sub-100ms, I may consider adding it back in for the sake of better code design.

Anyway, this allowed me to do was create clones quickly and avoid the need to "restore" the values to their initial state. Now the backup function (which looks VERY similar to before) is:

local function backupCells(cellDomain, cellValue)  
    local cellDomain, cellValue = cellDomain, cellValue
    local serial = {{}, {}}
    for i = 1, #cellDomain do
        serial[1][i] = {unpack(cellDomain[i])}
        serial[2][i] = cellValue[i]
    end
    return serial
end  

and restore has become a quick two-liner:

self.cellDomain = cellCopy[1]  
self.cellValue = cellCopy[2]  

This provided a fairly significant speedup! On the sudoku benchmark, I now average ~222ms/puzzle - a whopping 31ms speedup from the 253ms before it.

The Future

I'm starting to think I'm reaching the end of pure-lua optimizations. I want to convert the cell backup and parts of the AllDiff function to C and see if that offers any significant speedup. If anyone has any other suggestions for speed (the code can be found on GitHub) - please let me know I'd love to hear it!