-
Notifications
You must be signed in to change notification settings - Fork 3
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Potential performance issue with 2D-array randomization #2
Comments
I noticed that I had set
|
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 exampleThe 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: vsc results
constrainedrandom results
Making constrainedrandom fasterBy removing the constrainedrandom but faster code
constrainedrandom but faster results
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 solutionTo 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: Procedural solution
Procedural results
This is orders of magnitude faster than using a constrained random approach for this problem. A different two-dimensional array problemI 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: vsc code
constrainedrandom code
vsc results
constrainedrandom results
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 badlyConstrainedrandom 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. vsc code
constrainedrandom code
If we provide the concrete value to constrainedrandom's 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. SummaryThere 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 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. |
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
constrainedrandom
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
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?
The text was updated successfully, but these errors were encountered: