Bug #50169 for Algorithm-Diff: Load the XS Implementation if Available

Fri Oct 02 11:15:08 2009 frequency [...] cpan.org - Ticket created

Subject:

Load the XS Implementation if Available

Hi: Audrey Tang has written a module which re-implements the LCSidx command in XS/C. This means that compact_diff is accelerated in that package. I'm not personally sure if it always provides the same output, so this idea needs further investigation, but it would be nice if Algorithm::Diff either: 1. Accelerated itself using Algorithm::Diff::XS if installed (ie, have require Algorithm::Diff::XS in an eval, and remap internal LCSidx to the XS implementation) 2. Adopted this LCSidx implementation (assuming licensing is compatible) by copying the XS 3. Requesting a takeover of ::XS or comaintainership from Audrey Option 1 takes the XS implementation out of your control, which is bad in the case where there are bugs and Audrey doesn't (for whatever reason) fix them -- making Algorithm::Diff look bad -- but being outside of your control. Option 2 might cause some issues on systems where C/XS modules can't be built (ie those without compilers). It might be tricky to hack in detection and optional fallback where XS is unavailable (which is why I prefer to use ::XS modules myself) Option 3 seems the best option at this time. Of course there may be others. Thanks for reading and considering this. Audrey's benchmarks in Algorithm::Diff::XS look impressive, and it might be useful for various applications, particularly when using this algorithm as part of a web application, as it means you can serve more users at once. Cheers, Jonathan

Wed Oct 14 23:44:27 2009 tyemq [...] cpan.org - Correspondence added

I have a strong preference for Option 1. If Audrey cares to grant me co-maintainer status for A::Diff::XS, then I can more easily address compatibility issues. But I can also submit patches to Audrey, just like anybody else can. (Too bad CPAN doesn't allow and seems unlikely to ever allow any author to contribute to a module, almost as if modules were truly open-source.) Yes, I almost always implement XS-vs-Pure-Perl implementations by having the XS implementation be a separate distribution. I would probably advocate that A::Diff::XS be made so that it requires installation of A::Diff. This way, a user need only install A::Diff::XS to get the best of both (since installing A::Diff should not be a burden since it is Pure Perl) or a user can just install A::Diff if they know that an XS module would be hard to install in their environment. And I'm not too worried about the two implementations producing somewhat different results. In part, because in reviewing the original algorithm, I noticed that the Perl translation of it has at least one mistake (which probably means the Ruby implementation also is flawed since it looked to be a translation of the Perl version not a translation of the original). It appears to not matter in the majority of cases, however. It was also not immediately obvious how to easily fix it. I should look into whether Audrey's XS version is just a translation of the Perl or a translation of the original. Then there are some major improvements that I believe are possible as far as memory footprint... Thanks, Tye

Wed Oct 14 23:44:28 2009 The RT System itself - Status changed from 'new' to 'open'

Thu Oct 15 09:51:42 2009 ned [...] bike-nomad.com - Correspondence added

Subject:	Re: [rt.cpan.org #50169] Load the XS Implementation if Available
Date:	Thu, 15 Oct 2009 06:51:22 -0700
To:	bug-Algorithm-Diff [...] rt.cpan.org
From:	"Ned Konz" <ned [...] bike-nomad.com>

On Oct 14, 2009, at 8:44 PM, Tye McQueen via RT wrote: Show quoted text

> Queue: Algorithm-Diff > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=50169 > > > And I'm not too worried about the two implementations producing > somewhat > different results. In part, because in reviewing the original > algorithm, I noticed that the Perl translation of it has at least one > mistake

That is, of course, entirely possible; I did compare the results of A::D vs. the command-line diff after I re-wrote it (which I did while looking at Mario Wolczko's Smalltalk source), but could easily have made mistakes. The tricky part of the port, as I recall, was trying to maintain backwards compatibility for LCS. But it's been quite a while. Show quoted text

> (which probably means the Ruby implementation also is flawed > since it looked to be a translation of the Perl version not a > translation of the original).

The source of that says: The implementation is based on Mario I. Wolczko's[3] Smalltalk version (1.2, 1993)[4] and Ned Konz's[5] Perl version (Algorithm::Diff)[6]. Show quoted text

> Then there are some major improvements that I believe are possible > as far as memory > footprint...

Yes, it's a pig. Ned Konz

Sat Nov 07 16:37:18 2009 frequency [...] cpan.org - Correspondence added

From:

frequency [...] cpan.org

All: I have a proposal for a way we might be able to work around this without changing the current behaviour of things, but I thought it might be useful to get your opinion first. Basically, I propose adding a new package, Algorithm::Diff::Any, which would select either from Algorithm::Diff or Algorithm::Diff::XS. This way, compatibility errors are clearly Someone Else's Fault (not the Algorithm::Diff maintainer's problem). It also has the advantage of not breaking any existing code. It would be a simple (just a couple lines, really) module, but would get the job done. I could write it and upload the code soonish, pending a bit more discussion (to make sure I don't upset you guys, who have put quite a bit of work into it.. thanks!) Cheers, Jonathan

Sun Nov 08 22:25:25 2009 tyemq [...] cpan.org - Correspondence added

Subject:	Re: [rt.cpan.org #50169] Load the XS Implementation if Available
Date:	Sun, 8 Nov 2009 12:18:30 -0800
To:	bug-Algorithm-Diff [...] rt.cpan.org
From:	Tye McQueen <tyemq [...] cpan.org>

That'd be fine with me. Thanks, Tye On Sat, Nov 7, 2009 at 1:37 PM, Jonathan Yu via RT < bug-Algorithm-Diff@rt.cpan.org> wrote: Show quoted text

> Queue: Algorithm-Diff > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=50169 > > > All: > > I have a proposal for a way we might be able to work around this without > changing the current behaviour of things, but I thought it might be > useful to get your opinion first. > > Basically, I propose adding a new package, Algorithm::Diff::Any, which > would select either from Algorithm::Diff or Algorithm::Diff::XS. This > way, compatibility errors are clearly Someone Else's Fault (not the > Algorithm::Diff maintainer's problem). It also has the advantage of not > breaking any existing code. > > It would be a simple (just a couple lines, really) module, but would get > the job done. > > I could write it and upload the code soonish, pending a bit more > discussion (to make sure I don't upset you guys, who have put quite a > bit of work into it.. thanks!) > > Cheers, > > Jonathan >