Slow reduction using delta debugging

Open
#8,712 18 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
35/100
Issue type
Bug
Clarity
Needs clarification
Activity status
Quiet
Tech stack
wasm

Research direction

Start by reproducing the delta-debugging reduction described in the issue and inspect the repeated partition attempts in the reduction process. Compare the time spent on function removal with the intervening passes and destructive reduction; done means reducing unnecessary repeated work while preserving effective reduction progress.

Written by the indexing model from the issue text.

Description

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.

Dominant language
WebAssembly
Stars
8.6k
Forks
885
Avg merge
1d 20h
Merged PRs (30d)
64

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from WebAssembly/binaryen

All issues in WebAssembly/binaryen

Similar issues

More Compilers issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.