Skip to content

Potential performance issue with 2D-array randomization #2

Open
@KasperHesse

Description

@KasperHesse

I've been trying to compare PyVSC and constrainedrandom's performance when it comes to randomization of 2D-arrays. The test case is a "checkerboard randomization", where each field can be 0 or 1, but cannot have the same value as its neighbours.

Consider the following implementations

PyVSC
import vsc
import timeit

@vsc.randobj
class Checkers():
  def __init__(self, N):
    self.N = N
    self.board = [vsc.rand_list_t(vsc.rand_uint8_t(), self.N) for _ in range(self.N)]

  @vsc.constraint
  def con_values(self):
    for row in self.board:
      with vsc.foreach(row) as c:
        0 <= c and c <= 1

  @vsc.constraint
  def constraints(self):
    for i in range(1, self.N):
      with vsc.foreach(self.board[i], idx=True) as j:
        if j == 0:
          pass
        (self.board[i][j] != self.board[i-1][j]) and (self.board[i][j] != self.board[i][j-1])

def benchmark():
  numRounds = 10
  for N in (4, 8, 16, 32, 64, 128, 256):
    t = timeit.timeit(stmt='c.randomize()', setup=f'c = Checkers({N})', number=numRounds, globals=globals())
    print(f"N={N:4d}: Runtime: {t/numRounds}")

benchmark()
constrainedrandom
from constrainedrandom import RandObj
import timeit

class Checkers(RandObj):
  def __init__(self, N):
    super().__init__(max_iterations=1000)
    self.N = N
    for i in range(self.N):
      self.add_rand_var(f"list{i}", domain=range(2), length=self.N, disable_naive_list_solver=True)

    for i in range(1, self.N):
      for j in range(1, self.N):
        self.add_constraint((lambda row1, row2: row1[j] != row2[j]), (f"list{i-1}", f"list{i}"))
        self.add_constraint((lambda row: row[j-1] != row[j]), (f"list{i}", ))

def benchmark():
  numRounds = 10
  for N in (4, 8, 16, 32, 64, 128, 256):
    t = timeit.timeit(stmt='c.randomize()', setup=f'c = Checkers({N})', number=numRounds, globals=globals())
    print(f"N={N:4d}: Runtime: {t/numRounds}")

benchmark()

The average runtimes reported for the two on my machine are as follows. The fields labeled "DNF" took so long that I didn't bother waiting for them to complete

N PyVSC constrainedrandom
4 0.008 0.001
8 0.029 1.265
16 0.112 45.786
32 0.305 DNF
64 1.208 DNF
128 5.371 DNF
256 22.421 DNF

As you can see, the performance of PyVSC seems vastly superior to the performance of constrainedrandom. However, I am unsure whether my implementation with constrainedrandom is optimal, but I haven't found a better way of implementing 2D-arrays and randomization thereof.

Is there a better way of constraining this problem that would lead to better performance with constrainedrandom?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions