KihongHeo
commented
4 years ago Hi. Amazing. You are like making an optimizing compiler. I should definitely run a competition for this from next year's lecture.
Because implementing all such pruning techniques is also a part of this homework, here I will just give very low-level or very high-level. If needed we can discuss more in this thread.
- normalization: There are many different syntactic forms of a certain (partial) program.
(S + y) + zis equivalent toy + (S + z). You can only take care of one. - memoization: Once you have normalization, you may need memoization to discard further duplicated explorations. You can use
Setin the OCaml standard library to do that.
In general, bottom-up and top-down are incomparable (no one completely outperforms the other). But in our homework, bottom-up may be much faster, because 1) program size is very small, and 2) currently we don't consider very powerful pruning/searching techniques for the top-down much, such as
- constraint solving: E.g, complicated conditional expressions that is always true or false,
- divide-and-conquer: E.g., partition the whole set of input-output examples into two parts, one for true branch and the other for false branch, then recursively solve subproblems
- probabilistic approaches as in the lecture
- etc
If you are interested in, you can visit the Sygus competition (https://sygus.org), an annual program synthesis competition.
hyunsikjeong
KunJeong
Medowhill
tomtomjhj
hyunsukimsokcho
Hi. My current top-down algorithm finds a solution at 6 mins 30 secs for example3, which doesn't feel like a "safe" time, since we should terminate in 10 mins for all test cases. This feels especially long compared to bottom-up, which takes under three seconds for every case.
I've tried various pruning/optimization techniques, such as 1) restricting the grammar in the unrolling stage, 2) creating a "simplifying" algorithm to simplify the program before checking equivalence / adding to the queue, 3) depth comparisons to "balance" unrolling, 4) changing most of the code and API calls to be tail-recursive as well as 5) the basic equivalence checking for various mathematically equivalent structures. However, more sophisticated algorithms don't help the execution time very much, they often increase the time instead because of the added complexity.
Could you give some tips on how to shorten the execution time (which optimizations to focus on, which to ignore, etc.)? Would it be better to focus on improving the equivalence checking instead of trying these new approaches, like the original algorithm from the slides? Or are there other pruning techniques that I should explore?
Also, I'm curious about the bottom-up algorithm being so much faster, and whether it is possible to achieve such an execution time with the top-down algorithm.
Thank you.