I definitely underestimated what it would take mentally to implement Overview creation. It would have been better had I kept matching printers and drivers as a discrete step. Either way it’s done and hopefully I will not have to touch it for a while. Now to build some Ikea furniture.
Compared to parsing printers and drivers generating, the Overview is definitely more complex. For Printers, Drivers, and Options XMLs (the “primary” XMLs) only occasional processing was necessary. This leaves Overview to simply process the data into the overview structure. By lines of code about half of Overview is spent removing excess keys, a simple matter.
The complexity arises from the need to combine printers with drivers that support them. We get this compatibility information from two places, the printers which contain a list of drivers, and the drivers which contain a list of printers. Only one XML needs to claim compatibility to establish a relationship. Thus this relationship need not be mutual, a driver may claim to support a printer yet the printer could claim to be a brick. As well if a driver references a printer for which we have no XML we create a new in memory entry for this otherwise unknown printer.
The simplest approach would be to compute the relationships as a discrete step. This would leave you with an algo similar to this:
Build hash of Printers Build hash of Drivers Compute relationships Compile based on relationships
Your Compute relationships algo could be quite naive, with hashes we get unique entries quite easily. You might end up with a structure like this:
'printer' => {'driver'=>'', 'driver' =>'', 'driver'=>''};
Having Computer Relationships be a descrete step makes conceptualization easier but nothing says it has to be desecrate. Once we know of a relationship we can act on it. This does complicate the algo as we now need to avoid mutual relationships from causing a driver getting added twice. In my implementation we do this by removing the reference to a printer in the driver if it exists.
Upto this morning my implementation had a logic defect in that it assumed a reference to a driver in the printer was a mutual relationship. Thus once it was done processing the relationships it computed from printers it assumed that any references in drivers were ONLY to printers without XMLs. Essentially I had not considered that a driver may reference a printer while the same printer may not reference the driver. With hind-sight the deficiency is obvious, unfortunately the downside of not treating Relationship Computation as a discrete step is that your relationship algo gets spread over more code, and thus harder to conceptualize.
If I were to re-implement Overview I would have Compute Relationships as a discrete step.This would have saved me about two days of debugging with only slightly increased complexity in the Combine step. In the end I am only out the debugging time and I do have a computationally more effective function and have learned to keep steps discrete in the future, a fair trade.
Since the last blog post most of my work has been less milestone oriented.
I felt the the XML schema was important because my Perl module, the one replacing the C programs, is very forgiving. Robustness is of course a desirable trait in production software but Foomatic still needs something to enforce consistency. I knew we had XML XSDes but we were missing a simply script to run them. Once I had my new script in place two bugs in the printer schema came up. After I fixed that a rerun uncovered four XMLs that needed fixing.
When I started writing support for overviews (a massive data structure containing every printer and its drivers) I uncovered a bug, see if you can spot it:
# This variable holds the current time #
my $now = time;
my $Parser = xmlParse->new('en','0');
my @allPrinters
foreach my $xml (<../printer/*.xml>) {
my$perlData = $Parser->parsePrinter($xml);
print Dumper($perlData);
}
# Calculate runtime
$runtime = time - $now;
I hope you didn’t look too hard, the bug is way too easy to be obvious. This is from scaffolding.pl, a script I use to run xmlParse.pl through its paces. Its a throw away script that exists only for testing. Part of this testing is keeping an eye on runtime, and this is where the bug was.
Notice that our runtime calculation includes Dumper(A helper function that outputs Perl data structures in human readable form), when I wrote the script my assumption was that dumping the data structure was trivial. I was very wrong about this. We can read and parse an XML in one third the time it takes Dumper to print it. Every single printer XML can be read and parsed in under four seconds. Parsing every single Driver we get a runtime of 0:00, the one second resolution of the crude runtime calculator is insufficient! Fixing this bug also reduces the runtime of the C programs, but because the data structures are the same the cost of dumping is constant between the two parsing implementations. Thus the Perl implementation’s relative runtime advantage is even greater than I originally thought.
Definitely good news to report for the next OpenPrinting teleconn.
Since the Openprinting teleconn on Wednesday I’ve added support for the Driver XMLs and moved everything into a new non-prototype branch: https://launchpad.net/gsoc2011danieldressler/xmlparse
Progress is good and in the next few days I plan to get Option XML support done, and finally PPDs.
The first week of my project was scheduled as “April 25: Write a perl script capable of parsing a specific XML, extrapolate results to determine relativity to our performance requirements.”.
That week is over and the original goals of the prototype have been completed. In fact I sort of got carried away and the prototype is now nearly feature complete, for printer xml parsing. It turned out to be so fast that I simply have it parse ALL of the printer xmls when ever I want to test it. How fast? About twice as fast as the C program. Since this is a prototype the results are only preliminary, but I expect the final implementation to be at least on par with the C program. This speed was unexpected, my expectation was for the Perl to be linearly slower than the C, and hoped it wasn’t exponentially slower, yet it is actually faster! This bodes well for the other three fourths of this portion of the project; driver xml, options xml, and overview.
Thanks to this unexpected computational speed I will be focusing on simplicitly in the implementation, since maintainability was the primarly goal of this portion of the project. I will keep an eye out for improvements but now primarily for the opportunity to simplify the code base.