BIND 10 #1603: replace name compression with more efficient one

[BIND 10 Development]

#1603: replace name compression with more efficient one
-------------------------------------+-------------------------------------
                   Reporter:         |                 Owner:  jinmei
  jinmei                             |                Status:  accepted
                       Type:  task   |             Milestone:
                   Priority:         |  Sprint-20120320
  medium                             |            Resolution:
                  Component:         |             Sensitive:  0
  libdns++                           |           Sub-Project:  DNS
                   Keywords:         |  Estimated Difficulty:  7
            Defect Severity:  N/A    |           Total Hours:  0
Feature Depending on Ticket:  auth   |
  performance                        |
        Add Hours to Ticket:  0      |
                  Internal?:  0      |
-------------------------------------+-------------------------------------

Comment (by jinmei):

 trac1603 is ready for review.

 I needed to update the `LabelSequence` class (for fixing small bugs
 and for some missing features), and the branch has become larger than
 I expected (once again...).

 The changes to the `LabelSequence` are independent, so if the branch
 looks too big, we can separate the review process for the updates to
 `LabelSequence` and the `MessageRenderer` changes.

 - first, I've copied the original `MessageRenderer` implementation to a
   separate file with changing the class name (dc0963a) so I can
   compare the performance.  My plan is to remove this file and the
   corresponding code in the benchmark once review is completed.

 - changes from bfb21ab to ba84010 are the necessary updates to
   `LabelSequence`.  I've fixed the reversal meaning issue of #1754
   within this branch (commit 681c927)

 - Commits f0b94ec and 1296fe2 are the main changes.  Basically, it
   updates the internal of `MessageRenderer`Impl and the writeName()
   method.  Other part was basically intact except for things changed
   in 1296fe2.

 - 7eda3c0 is a newly added microbenchmark test.  It's a standalone
   test (test data are hardocded) so anyone should be able to run it on
   their environment to compare the old and new versions.

 This is a result of this test on my laptop:
 {{{
 Benchmark for old MessageRenderer (positive response)
 Performed 4200000 iterations in 10.491190s (400335.90ips)
 Benchmark for dumb MessageRenderer (positive response)
 Performed 4200000 iterations in 0.168659s (24902317.69ips)
 Benchmark for new MessageRenderer (positive response)
 Performed 4200000 iterations in 1.353617s (3102797.91ips)
 Benchmark for old MessageRenderer (NXDOMAIN response)
 Performed 400000 iterations in 0.678503s (589533.13ips)
 Benchmark for dumb MessageRenderer (NXDOMAIN response)
 Performed 400000 iterations in 0.015943s (25089380.92ips)
 Benchmark for new MessageRenderer (NXDOMAIN response)
 Performed 400000 iterations in 0.217929s (1835460.17ips)
 Benchmark for old MessageRenderer (SERVFAIL response)
 Performed 100000 iterations in 0.068628s (1457131.20ips)
 Benchmark for dumb MessageRenderer (SERVFAIL response)
 Performed 100000 iterations in 0.004277s (23380874.44ips)
 Benchmark for new MessageRenderer (SERVFAIL response)
 Performed 100000 iterations in 0.081888s (1221180.15ips)
 }}}

 Note: in the case of "SERVFAL" scenario (where there's only one name),
 the new version is actually slower than the old version.  If we want
 to avoid that, we could have the auth server use the "dumb" renderer
 when it returns an error message.  The dumb implementation is mostly
 empty, so the additional implementation/maintenance overhead should be
 minimal, and it's faster than other versions in the order of
 magnitude.

 One more thing: to do more "fair" comparison with the old version, I
 made another branch on top of the main branch, trac1603bench (pushed
 to the public repo).  It includes the optimization made in #1568 (use
 assert instead of throw in the buffer class).  The microbenchmark
 shows the new version still 2 to 5 times faster (except for the
 "SERVFAIL" case).

 Finally, while I originally didn't think we need a changelog for this
 task, it turned out to include one minor backward-incompatible
 change, so I propose adding this one:
 {{{
 395.    [func]*         jinmei
         libdns++: updated the internal implementation of the
         MessageRenderer class.  This is mostly a transparent change, but
         the new version now doesn't allow changing compression mode in the
         middle of rendering (which shouldn't be an issue in practice).
         On the other hand, name compression performance was significantly
         improved: depending on the number of names, micro benchmark tests
         showed the new version is 3 to 7 times faster than the previous
         version .
         (Trac #1603, git TBD)
 }}}

-- 
Ticket URL: <http://bind10.isc.org/ticket/1603#comment:4>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development