Potential performance issue with 2D-array randomization about constrainedrandom HOT 2 OPEN

I noticed that I had set max_iterations=1000 due to some issues with a previous constraint attempt. Removing that parameter seems to speed up the constraint solver, probably because it more quickly stops using the naive solver, but is still markedly slower than PyVSC.

N=   4: Runtime: 0.004006109999863838
N=   8: Runtime: 0.8024601899998742
N=  16: Runtime: 1.7624544599999354
N=  32: Runtime: 7.645777930000077
N=  64: Runtime: 73.60141107

from constrainedrandom.

Hi Kasper,

Thanks very much for raising this. 2D arrays (or lists of lists in python terms) aren't a use case we've yet required when using constrainedrandom internally in Imagination, so it's helpful to get your feedback.

You've raised a valid concern about performance here. In general, constrainedrandom isn't very good at cases where a small number of choices determine the only correct result for a large number of other variables. vsc does do better in these sorts of cases, because it considers the problem in a more interconnected way than constrainedrandom does (which is exactly the thing that slows it down in other cases).

I've tried to investigate this particular case and have written up what I found. Hopefully it's helpful, please let me know your thoughts.

Your checkerboard example

The example you've given is a bit of a corner-case in that the first choice you make for any cell in the checkerboard determines the result of all the other cells. If I choose a 1 or 0 to go anywhere, it effectively determines the results for every other cell immediately. vsc therefore performs better - constrainedrandom always really struggles with this kind of case due to its reliance on randomizing and checking.

I was able to reproduce the behaviour you showed in your original example with the code you provided.

My results from directly running your code:

N=   4: Runtime: 0.003800742000021273
N=   8: Runtime: 0.01277666030000546
N=  16: Runtime: 0.04529272580039105
N=  32: Runtime: 0.18716902040032438
N=  64: Runtime: 1.0156315014006396
N= 128: Runtime: 4.4076643840002365
N= 256: Runtime: 24.720914476300095

N=   4: Runtime: 0.00049386870014132
N=   8: Runtime: 1.050551228599943
N=  16: Runtime: 7.706638661499892
N=  32: Runtime: 47.63703318400003

(DNF for N=64, 128, 256)

Making constrainedrandom faster

By removing the max_iterations=1000 and the disable_naive_list_solver=True, I got better results:

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

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

N=   4: Runtime: 0.0007822489002137445
N=   8: Runtime: 0.2898493679000239
N=  16: Runtime: 0.1423995040000591
N=  32: Runtime: 0.4734258158998273
N=  64: Runtime: 2.1201752419001423
N= 128: Runtime: 9.272784179399604
N= 256: Runtime: 44.2909998391995

This is still about 2x slower than vsc for N >= 64, but I think you'd agree it's quite a bit better than the "did not finish" behaviour in the original example.

Please can you let me know whether you get comparable results running this on your machine? I'm just running it locally on my laptop.

Personally I'd just put this down as a case where vsc wins in terms of performance. Based on current user experience I would trade off slowness in this kind of case for speed in other cases.

There are ways to make this go much faster by manually optimizing the problem, e.g. by constraining the input space for each row, but at that point you might as well just write it procedurally...

Procedural solution

To be 100% honest with you, the original problem you stated doesn't really sound like a problem well-suited to either vsc or constrainedrandom - there's really only one element to randomize, and it's quite sub-optimal to treat the whole thing as a randomization problem.

If I had that problem in a real software project, I would write something procedural, like this:

import random
import timeit

class Checkers():
    def __init__(self, N):
        self.N = N
        self.board = []

    def randomize(self):
        self.board = []
        top_left = random.getrandbits(1)
        for i in range(self.N):
            self.board.append([None for _ in range(self.N)])
            for j in range(self.N):
                if i == 0 and j == 0:
                    self.board[i][j] = top_left
                else:
                    if j == 0:
                        self.board[i][j] = 0 if self.board[i-1][j] else 1
                    else:
                        self.board[i][j] = 0 if self.board[i][j-1] else 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()

N=   4: Runtime: 3.370100603206083e-06
N=   8: Runtime: 8.603600144851953e-06
N=  16: Runtime: 2.861399989342317e-05
N=  32: Runtime: 9.815220037125982e-05
N=  64: Runtime: 0.00036479769987636247
N= 128: Runtime: 0.0014662143003079109
N= 256: Runtime: 0.005748119200143264

This is orders of magnitude faster than using a constrained random approach for this problem.

A different two-dimensional array problem

I want to engage with the original point about two-dimensional array performance, so let me propose a slightly different case, where I think a constrained randomization problem is a much more user-friendly experience to write.

Let's take the checkerboard example, but let's say each element can have the value 0 to 4, and the sum of each element and all its neighbours must be less than or equal to 4.

I coded this in vsc and in constrainedrandom and got similar results:

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 <= 4

    @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] < 5) and (self.board[i][j] + self.board[i][j-1] < 5)


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

from constrainedrandom import RandObj
import timeit


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

        for i in range(1, self.N):
            for j in range(1, self.N):
                self.add_constraint((lambda row1, row2: row1[j] + row2[j] < 5), (f"list{i-1}", f"list{i}"))
                self.add_constraint((lambda row: row[j-1] + row[j] < 5), (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()

N=   4: Runtime: 0.005554529099754291
N=   8: Runtime: 0.022379124100552872
N=  16: Runtime: 0.06850886350002838
N=  32: Runtime: 0.30377212050007074
N=  64: Runtime: 1.354998340599559
N= 128: Runtime: 5.976018746299815
N= 256: Runtime: 31.340037856700654

N=   4: Runtime: 0.005820018600206822
N=   8: Runtime: 0.000641144199471455
N=  16: Runtime: 0.006594730899814749
N=  32: Runtime: 0.16832221820004634
N=  64: Runtime: 1.5169856319000246
N= 128: Runtime: 6.13921610949983
N= 256: Runtime: 27.28949799520051

As you can see, the results are pretty similar between the two, it's a narrow victory for constrainedrandom but not by a lot, so could be in the noise.

The reason to include this is to show that the class of problem matters a lot, not just the list dimensionality.

Other cases where constrainedrandom performs badly

Constrainedrandom performs badly when a constraint attempts to set a single legal value.

Consider a 32-bit integer, which we want to have the value 5. If we write this as a constrained randomization problem, vsc will beat constrainedrandom every time. In fact, constrainedrandom will fail to produce a result.

import vsc

@vsc.randobj
class RandInt:

    def __init__(self):
        self.x = vsc.rand_int32_t()

    @vsc.constraint
    def val_c(self):
        self.x == 5

r = RandInt()
r.randomize()

from constrainedrandom import RandObj

class RandInt(RandObj):

    def __init__(self):
        super().__init__()
        self.add_rand_var('x', bits=32)
        self.add_constraint(lambda a : a == 5, ('x'))

r = RandInt()
r.randomize()

If we provide the concrete value to constrainedrandom's randomize() method using randomize(with_values={'x': 5}) instead of adding a constraint, then it will just assign the variable and be done.

But you might also think, why not just create a variable and assign it the value 5? Why do I bring up this case which you wouldn't code as a randomization problem? I guess the point is just to say that constrainedrandom often loses to vsc in these kinds of cases where a variable is effectively assigned a value in a constraint.

I haven't looked to fix this behaviour, mainly because I'd just advise someone not to use randomization in this case.

You might say this is vsc being better at "constraint-based programming", which it is, but isn't really what constrainedrandom intends to be good at.

Summary

There are definitely cases where vsc will always beat constrainedrandom, and if you want a tool that performs "constraint-based programming", then vsc is definitely more complete than constrainedrandom. It's worth noting that vsc is much more user-friendly in handling lists of lists, too. Imagine if you had to do another dimension of lists in constrainedrandom - it would be very painful to define all the variable names!

However, I have optimized it for the cases that we generally use it for internally, which are problems where we want a randomized result. In benchmarking, it's always performed very favourably compared to vsc in the sorts of cases we use it for (e.g. see the instruction generation case in the benchmarks/ directory). (This does remind me I need to overhaul how those benchmarks are defined, as it's very clunky at the moment.)

Maybe it does need to support lists of lists better, though we haven't required this yet. Let me know if you have suggestions for this. For what it's worth, this is only deployed in one area internally and certainly doesn't replace doing constrained random stuff in SystemVerilog.

I hope that helps - please let me know any further thoughts you have, or any other performance cases you find where constrainedrandom is not adequate.

from constrainedrandom.