Slow reduction using delta debugging
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
- Domain
- compilers, performance
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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from WebAssembly/binaryen
-
Difficulty 2/5 Half a day Newbie friendliness 76/100
WebAssembly/binaryen#9018 · 3 comments ·
-
Difficulty 4/5 3-5 days Newbie friendliness 52/100
WebAssembly/binaryen#9123 ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
WebAssembly/binaryen#9122 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 48/100
WebAssembly/binaryen#9086 · 2 comments ·
-
Difficulty 4/5 3-5 days Newbie friendliness 48/100
WebAssembly/binaryen#9038 · 5 comments ·
All issues in WebAssembly/binaryen
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
objectionary/eo#8869 · 1 comment ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
EricSpencer00/Resilient#4824 · 1 comment ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
objectionary/jeo-maven-plugin#1758 ·
-
generics
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
-
mlir
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
llvm/llvm-project#224908 · 1 comment ·