[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.
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
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 <email@example.com
I did a creduce vs. halfempty benchmark at some point. These were my
Same input (739 bytes C++), ~same test script, 1 vs 32 threads (on
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:
On Thu, 13 Jun 2019 at 22:57, Nico Weber <firstname.lastname@example.org
> 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?