Slow reduction using delta debugging

[kripken]

I see

|input size: 248089                         
|starting reduction!                        
|    try to remove function bodies          
|     try partition 1 / 1 (size 0 / 1745)   
|     try partition 1 / 2 (size 873 / 1745) 
|     try partition 2 / 2 (size 872 / 1745) 
|     try partition 1 / 4 (size 437 / 1745) 
|     try partition 2 / 4 (size 436 / 1745) 
|     try partition 3 / 4 (size 436 / 1745) 
|     try partition 4 / 4 (size 436 / 1745)  
|     try partition 1 / 4 (size 1308 / 1745) 
|     try partition 2 / 4 (size 1309 / 1745) 
|     try partition 3 / 4 (size 1309 / 1745) 
|     try partition 4 / 4 (size 1309 / 1745) 
|     try partition 1 / 8 (size 219 / 1745) 
|     try partition 2 / 8 (size 218 / 1745) 
|     try partition 3 / 8 (size 218 / 1745) 
|     try partition 4 / 8 (size 218 / 1745) 
|     try partition 5 / 8 (size 218 / 1745) 
|     try partition 6 / 8 (size 218 / 1745) 
|     try partition 7 / 8 (size 218 / 1745) 
|     try partition 8 / 8 (size 218 / 1745) 
|     try partition 1 / 8 (size 1526 / 1745)
|     try partition 2 / 8 (size 1527 / 1745) 
|     try partition 3 / 8 (size 1527 / 1745) 
|     try partition 1 / 7 (size 219 / 1527)  
|     try partition 2 / 7 (size 218 / 1527)  
|     try partition 3 / 7 (size 218 / 1527)
|     try partition 4 / 7 (size 218 / 1527)
|     try partition 5 / 7 (size 218 / 1527)
|     try partition 6 / 7 (size 218 / 1527)
|     try partition 7 / 7 (size 218 / 1527)
|     try partition 1 / 7 (size 1308 / 1527)
|     try partition 2 / 7 (size 1309 / 1527)
|     try partition 3 / 7 (size 1309 / 1527)
|     try partition 4 / 7 (size 1309 / 1527)
|     try partition 5 / 7 (size 1309 / 1527)
|     try partition 1 / 6 (size 219 / 1309)
|     try partition 2 / 6 (size 218 / 1309)
|     try partition 3 / 6 (size 218 / 1309)
|     try partition 4 / 6 (size 218 / 1309)

And it just keeps trying more and more here. This has been doing on for several minutes, with each change taking 1-2 seconds. It is making progress, but trying the passes and destructive reduction etc. in between could be a lot faster, I think.

@tlively I think we do need something like taking the factor into account. The basic idea there is that no single method works to exhaustion, they each try a small amount and then cycle. No single method knows how well the others can do - e.g. possibly a single -O3 would immediately do all the work that function removal is doing manually.

[tlively]

Oh wow, it's getting pretty unlucky in how many partitions it searches before finding an improvement. That being said, cycling to a different reduction strategy earlier always runs the risk of giving up just before being able to make significant progress. I think it's important that the time given to each strategy be allowed to scale up with the size of the test case in a principled manner. The current bailout at sqrt(N) partitions ensures that the number of unsuccessful iterations in a row is bounded by O(n), but we could tweak that heuristic if we wanted to.

We've seen other examples where running passes first takes several minutes and does not make significant forward progress. The fact that this reduction is making forward progress (a quarter of the function bodies removed in just a matter of minutes!) makes me think that this is mostly working as intended. If we can avoid very large reductions taking on the order of days, it's ok if medium reductions take a few minutes longer, IMO.

[kripken]

We've seen other examples where running passes first takes several minutes and does not make significant forward progress.

Passes, though, have a finite number before we move on, I think? O(1) in other words

(if they can cycle infinitely, perhaps we should change that too)

Basically my point is that any strategy should either run O(1) or at least only keep running if it sees huge progress. Otherwise cycling is just better.

[kripken]

Some data from my current reduction:

• Starts at 110155 bytes
• Works for many minutes using delta debugging, reaches... 101811. 10%
• Passes work very quickly and reach 25223: 75%

[tlively]

What kind of bug is this reduction for? I'm curious about why it is so resistant to removing function bodies.

[kripken]

This is for a wasm-split issue.

[tlively]

Can we try to run a smaller than normal set of passes first? On very large test cases where the passes aren't useful, it can take a long time to run through the full list.