[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [creduce-dev] halfempty algorithm for creduce?

Hi Nico, it would be great if you could give us any speedup numbers your big machine. It could easily be time to increase the default number of cores that we use. Limiting C-Reduce to 4 cores by default was based on a few observations we made on some quite old hardware. Also, the actual speedup depends a lot on how slow the interestingness test is.
There's an obvious and possibly-important improvement left for parallel C-Reduce, which is that currently it produces variants in the main process and only runs interestingness tests in parallel. This kept things nice and simple. The alternative, of course, is to also produce the variants in parallel. I'm not sure how much of a difference this will make, and I'm not sure how hard it is to implement-- I haven't thought hard about this part of C-Reduce for a few years.
The only other changes I can think of that would help is to reconsider the first few passes that C-Reduce runs. These are always the most important: if the initial passes can kill a lot of text, then the reduction goes quickly, if not then C-Reduce gets stuck trying out little stuff for a long time. 

John




On 6/14/19 5:55 AM, Nico Weber wrote:

Thanks for sharing the data and the test scripts!
The inputs we usually use with creduce are 2-4MB (basically what clang writes when it hits an assert -- it's a single cpp file with all .h files inlined via -frewrite-includes -E), so orders of magnitude larger. I'd expect the speedup to be much larger. If so, I suppose I could run halfempty first and then creduce second.
Thanks to your reply and went and looked at the default value for --n, and apparently it's 4 (https://github.com/csmith-project/creduce/blob/a1aa2a3601addc4d8d22c203c1ddecdbdde3df6e/creduce/creduce_utils.pm#L151), which means I'm using only 10% of my cores when running creduce. I wasn't aware of that, so thanks for making me look it up. Maybe just passing --n 48 will make things much faster already. 

I'll do a comparison of my last bisect and will report numbers.
On Fri, Jun 14, 2019 at 2:38 AM Vegard Nossum <vegard.nossum@gmail.com <mailto:vegard.nossum@gmail.com>> wrote: 

    I did a creduce vs. halfempty benchmark at some point. These were my
    results:

    """
    Same input (739 bytes C++), ~same test script, 1 vs 32 threads (on
    32 cores).

    Halfempty speedup = ~2.7 (-63%),
    creduce speedup = ~8.7 (-89%).

    at 32 cores the two programs were within 8 seconds of each other (!),
    whereas on 1 core, halfempty took 7m27 and creduce took 22m57

    The final file sizes were:

    460 bytes for halfempty,
    317 for c-reduce
    """

    File dump from back then at:
    https://gist.github.com/vegard/e79b96cefffbfb753da17c4646132fab


    Vegard

    On Thu, 13 Jun 2019 at 22:57, Nico Weber <thakis@chromium.org
    <mailto:thakis@chromium.org>> wrote:
     >
     > Hi,
     >
     > creduce often takes more than an hour to run, with most cores
    being idle. https://github.com/googleprojectzero/halfempty is an
    approach to doing delta debugging in parallel. Could that approach
    be implemented in creduce as well?
     >
     > Thanks,
     > Nico