COIN-OR::LEMON - Graph Library

Opened 5 years ago

Last modified 5 years ago

#618 new enhancement

Constrained time measure

Reported by: Balazs Dezso Owned by: Alpar Juttner
Priority: minor Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:


It is not simple to implement benchmarking tool in C++. One of the difficulties is that some algorithms can run for unacceptable long time on some inputs, so the benchmark running time can be impractical.

There are workarounds for this problem. For example, we can blacklist some test cases for some algorithms, but this can be a tedious work, and it requires updates on algorithm changes. Other solution is to use a controller script which starts the benchmarking tool with different parameters, but this requires the separation of the controller tool and the benchmark tool.

Instead of the previous solutions, I propose a time measure tool, which executes a function with a time constraint. Technically, this can be implemented with a forked subprocess in unix systems (WIN32 doesn't have proper tool for it). This solution is similar to using a controller script, but we don't need to split out the test cases to the script.

My implementation is [7a1a282efbb4].

Attachments (1)

7a1a282efbb4.patch (8.2 KB) - added by Balazs Dezso 5 years ago.

Download all attachments as: .zip

Change History (4)

Changed 5 years ago by Balazs Dezso

Attachment: 7a1a282efbb4.patch added

comment:1 Changed 5 years ago by Peter Kovacs

I like this proposal and would have been used this tool if it had been developed before. :)

Let's add it to the main branch!

Minor comments:

  • The method name: it is a bit strange for me, but I don't have a better suggestion. Maybe using "limited" or "timeout" in the name?
  • The possible exceptions thrown by the method in different cases should be mentioned in its API doc.
  • What about combining this new method with the currently existing runningTimeTest()? That method accepts a min_time parameter and calls the measured function several times in order to achieve more reliable measurement. Using both min_time and max_time seems to be reasonable in several cases.
  • In write_full(pipefd[1], &success, sizeof(bool)), I would use sizeof(success) for the sake of consistency.

comment:2 Changed 5 years ago by Alpar Juttner

What about runningTimeTestWithTimeOut()? I understand it is stupidly long, but it is not something we have to write million times.

comment:3 in reply to:  2 Changed 5 years ago by Peter Kovacs

Replying to Alpar Juttner:

What about runningTimeTestWithTimeOut()? I understand it is stupidly long, but it is not something we have to write million times.

I think it's better than the original name constrainedRunningTimeTest(), as it clearly expresses the meaning of the function.

However, I would prefer the spelling runningTimeTestWithTimeout(), ie. considering "timeout" instead of "time out". Both versions are used, but the single word seems to be more common in US English and computer science:

Note: See TracTickets for help on using tickets.