This queue is for tickets about the Algorithm-Diff CPAN distribution.

Report information
The Basics
Id:
50169
Status:
open
Priority:
Low/Low

People
Owner:
Nobody in particular
Requestors:
frequency [...] cpan.org
Cc:
AdminCc:

BugTracker
Severity:
Wishlist
Broken in:
1.1902
Fixed in:
(no value)



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
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
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
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
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



This service runs on Request Tracker, is sponsored by The Perl Foundation, and maintained by Best Practical Solutions.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.