Issue802

Title M&S: add support for time limit and computing partial abstractions in general
Priority feature Status in-progress
Superseder Nosy List florian, malte, silvan
Assigned To silvan Keywords
Optional summary

Created on 2018-06-17.19:33:06 by silvan, last changed by silvan.

Messages
msg8393 (view) Author: silvan Date: 2018-12-18.16:34:32
I updated the pull-request, hope it works now.
msg8387 (view) Author: malte Date: 2018-12-18.15:20:01
I currently can't review this properly on bitbucket because of a merge conflict.
Can you address it (probably by merging from default)?
msg8371 (view) Author: silvan Date: 2018-12-17.11:04:02
This one is also close to being finished; any chance we can come to a conclusion
here in the next days? Otherwise, I'll put it back to the queue.

(I'm basically only missing an answer from you, Malte, regarding the discussion
on bitbucket on CountdownTimer. I addressed all of Florian's comments.)
msg8354 (view) Author: silvan Date: 2018-12-14.17:06:33
I addressed the comments and also got rid of the duplicate print_time function.
For printing progress with time, there now is a general log_progress function
for the M&S algorithm implementation file and a lambda function local to the
main loop.
msg8343 (view) Author: florian Date: 2018-12-14.15:13:54
I left two more minor comments. Apart from that, I think this is ready for merging.
msg8338 (view) Author: silvan Date: 2018-12-14.14:35:59
I'm done addressing your comments. Do you want to have a look at the commits?
msg8337 (view) Author: silvan Date: 2018-12-14.14:35:23
I prefer not to add custom exceptions, since all these checks happen in a single
method.
msg8329 (view) Author: florian Date: 2018-12-14.12:59:45
ran_out_of_time(timer) currently checks if the timer is expired, optionally
prints a log message and returns true or false. If it would throw an exception
instead of returning true, the checks in the main loop would just have to call
the function without having to check the return value and break if it is true.

Of course this is just a small change, I don't mind if it stays like it is.
msg8328 (view) Author: malte Date: 2018-12-14.12:53:38
What is the one line? I don't understand what you mean.
(Also, the example could of course easily be written in two lines.)
msg8327 (view) Author: florian Date: 2018-12-14.12:52:19
I had a few minor comments but overall the code looks good.

On the topic of throwing an exception vs. returning on a timeout that you
discussed a while ago: the patch introduces a lot of three-line blocks
    if (ran_out_of_time(timer)) {
        break;
    }
in a loop that is already very long. With exceptions you could reduce this to
one line per check. Not a big difference but maybe worth considering.
msg8322 (view) Author: silvan Date: 2018-12-14.11:53:40
I decided to only support computing the maximum heuristics over all remaining
factors if several remain when using a time limit, and not to choose a single
one according to some scoring functions. This greatly simplifies the diff.
Florian will make a review.
msg8296 (view) Author: silvan Date: 2018-12-13.18:42:21
In issue851, we realized that the reason for not being able to compute atomic
FTS for all tasks of our standard suite is memory, not time. Issue851 thus now
longer should be considered a blocker. 

I changed the time limit to only apply to the main loop of the algorithm, thus
simplifying the diff to some extent. This is ready for review:
https://bitbucket.org/SilvanS/fd-dev/pull-requests/36/issue802/diff
msg7833 (view) Author: silvan Date: 2018-10-02.18:58:05
We discussed this off the tracker and decided that we should a) first split off
the implementation of the algorithm from the heuristic and b) make the
computation of atomic FTS faster so that we don't need to add a time limit there.
msg7761 (view) Author: malte Date: 2018-09-21.19:45:30
This has moved to the top of the review queue, so I have started having a look.
However, I realize I cannot complete the review now, and it is perhaps more
efficient to discuss this together when we meet next week.

What do you think?
msg7351 (view) Author: malte Date: 2018-09-09.20:11:55
There is nothing wrong with using return values if it results in clean and
readable code. One possible advantage of using exceptions is that they make it
easy to abort the computation several levels deep into the call stack without
needing to change any of the methods called in between the throwing and catching
code. This is also a possible disadvantage if whoever is looking at the
"intermediate" code isn't aware that and where exceptions can thrown and hence
might leave the object in an unclean state.
msg7350 (view) Author: silvan Date: 2018-09-09.19:32:57
I noticed that the hillclimbing generator for pattern collections uses a custom
exception which is thrown when the time limit for hillclimbing is reached. In my
implementation of the time limit for the merge-and-shrink compoutation, I use an
"if out-of-time then return" logic. Is there any benefit of using exceptions? My
guess is that we use exceptions in the PDB code because there are many methods
that all have non-void return values already which would make it complicate to
pass on the flag that the time ran out. Anyway, the question I wanted to ask is
if I should also use exceptions here.
msg7272 (view) Author: silvan Date: 2018-06-22.16:36:22
I opened a pull-request:
https://bitbucket.org/SilvanS/fd-dev/pull-requests/36/issue802/diff

I also put it into the review queue.
msg7263 (view) Author: silvan Date: 2018-06-17.19:33:06
I would like to add support for computing partial abstractions, i.e., support
for terminating the merge-and-shrink algorithm early on, which requires to
compute the merge-and-shrink heuristic given a set of remaining abstractions
(each factor induces its own abstraction). Terminating the algorithm early on is
best achieved by imposing a time limit, as the experiments for the recent SoCS
paper (Sievers 2018) suggest. We could also add a limit on the number of
transitions, which I also already implemented but which isn't as beneficial as
limiting time.
History
Date User Action Args
2018-12-18 16:34:32silvansetmessages: + msg8393
2018-12-18 15:20:01maltesetmessages: + msg8387
2018-12-17 11:04:02silvansetmessages: + msg8371
2018-12-14 17:06:33silvansetmessages: + msg8354
2018-12-14 15:13:54floriansetmessages: + msg8343
2018-12-14 14:35:59silvansetmessages: + msg8338
2018-12-14 14:35:23silvansetmessages: + msg8337
2018-12-14 12:59:45floriansetmessages: + msg8329
2018-12-14 12:53:38maltesetmessages: + msg8328
2018-12-14 12:52:19floriansetmessages: + msg8327
2018-12-14 11:53:40silvansetnosy: + florian
messages: + msg8322
2018-12-13 18:42:21silvansetmessages: + msg8296
summary: Blocked by issue851. ->
2018-12-03 11:40:36silvansetstatus: reviewing -> in-progress
summary: Blocked by issue849. Also we should first make the computation of transitions of irrelevant operators smarter by directly computing them as an equivalence class. -> Blocked by issue851.
2018-10-02 18:58:05silvansetmessages: + msg7833
summary: Blocked by issue849. Also we should first make the computation of transitions of irrelevant operators smarter by directly computing them as an equivalence class.
2018-09-21 19:45:30maltesetmessages: + msg7761
2018-09-09 20:11:55maltesetmessages: + msg7351
2018-09-09 19:32:57silvansetmessages: + msg7350
2018-06-22 16:36:23silvansetstatus: unread -> reviewing
messages: + msg7272
2018-06-17 19:33:06silvancreate