[llvm-dev] Delta reduction of front-end bugs: New tool

[Elias Pipping via llvm-dev]

Dear list,

under

  http://llvm.org/docs/HowToSubmitABug.html

it continues to be recommended that input which leads to crashes or assertion failures in clang be reduced using e.g. the delta tool[1]. Even though there are by now far more elaborate tools for such tasks, I’m still using delta and I assume so are many (I should probably be able to justify this better but I think it’s mostly down to my inability to get C-Reduce to work in the first place). Now, delta hasn’t been updated since 2006 as far as I can see. That’s probably in part because it does a pretty decent job (it’s never crashed on me or produced incorrect results in any way). It could be improved upon in rather straightforward ways, though. E.g. by allowing multicore machines to utilise more than one core. The potential for time savings is rather large here and since delta reductions can take up quite a lot of time, that’s true both in relative and absolute terms.

For no good reason, I’ve reimplemented delta (which is implemented in perl) in common lisp a few years ago. The other day then, I cleaned it up a bit (I’m quite happy with it now), added asynchronous IO, and all of a sudden the tool became actually useful — it now does something the original delta didn’t do, after all. So I’d like to advertise here a bit (the tool is open source/free software(*) so I hope this isn’t frowned upon): It’s up at

  https://github.com/pipping/delta-lisp

It has at the time of this writing almost surely exactly one user (me). So maybe it’s broken on a platform that I don’t have access to. Or maybe I made some obvious common lisp packaging mistakes (probably, judging by the warnings about redefinitions). And maybe the entire interface is a disaster and highly unintuitive. So I’m hoping for bug reports and pull requests. While no guarantee that looking into this will be worth your time, an indication that it might be is e.g. these runtimes that I got for a simple test case on macOS: perl (1 process): 76.24s, lisp (1 process): 57.57s, lisp (4 processes): 29.90s(**). On linux, I even saw a speedup of 2.6 when going from one process to four for this test (since it’s rather contrived and silly it lives in the subdirectory test-silly; the README has the details on how to run it).


Thanks for reading.

Elias Pipping

(*) I haven’t spent a lot of thought on the particular license so if you wish it were a different one, let me know.
(**) The fact that the single-process lisp implementation is fast than perl is down to a different order in which options are checked, I assume. The perl implementation calls the test script 570 times, the lisp implementation just 485 times for this test case. I haven’t looked into this in detail so this might also swing the other way. The speedup from asynchronous IO is the more interesting number here, I think.