BIND 10 #539: Hash-based name compression

[BIND 10 Development]

#539: Hash-based name compression
-------------------------------------+-------------------------------------
           Reporter:  vorner         |                      Owner:
               Type:  task           |                     Status:  new
           Priority:  minor          |                  Milestone:  A-Team-
          Component:  Unclassified   |  Sprint-20110209
          Sensitive:  0              |                   Keywords:
Add Hours to Ticket:  0              |  Estimated Number of Hours:  0
        Total Hours:  0              |                  Billable?:  1
                                     |                  Internal?:  0
-------------------------------------+-------------------------------------
 Name compression is expensive operation
 (isc::dns::MessageRenderer::writeName with it's inlined functions takes
 16% of our runtime (this includes NameCompare::operator() and
 NameCompare::nextPosition). The isc::dns::OutputBuffer::operator[] is used
 a lot inside these functions, which increases the cost of it even more).

 There's idea to store positions of all already written names and suffixes
 of them to a hash table. When a new name is to be written, the hash table
 is queried first to see if it is already there. If yes, the address is
 taken and written. If not, the first label is written and noted into the
 hash table, then it is repeated with next label.

 It would be nice to get the hashes precomputed form the names. They can be
 provided by the datasource for example, or whenever the hash is needed, it
 is cached in the Name and if two names are compared and one does not have
 the cached hashes, while the other does, the ones for common parts are
 copied.

 This is a largish task, maybe we can put it off after we try the simpler
 ones.

-- 
Ticket URL: <https://bind10.isc.org/ticket/539>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development