The Fast Implementation Builds OABST for 2,000,000 nodes!

The goal of this chapter is to evaluate the performance of the different implementations of the Hu-Tucker algorithm. The break even point between the fast implementation, described in 3.1.1 using leftist tree for priority queue, and the implementation building the tree by combining local minimum compatible pairs will be experimentally established. The time complexities of the two implementations will be compared to their corresponding theoretical time complexities. The performance of all phases of the Hu-Tucker algorithm will be measured for potential practical usage. An OABST will be build for the electronic version of ``The Complete Works of William Shakespeare" and the results will be analyzed. The costs of the OABST, built using the Hu-Tucker algorithm, and the OBT, built using the Huffman algorithm, will be compared for variety of random input sequences.

The test environment for the experiments is: Sun Ultra 60, dual processor configuration with 4-way superscalar UltraSPARC-II, 300 MHz processor, MMU with 64 Instruction-TLB and 64 Data-TLB entries, 16 KB data and 16 KB instruction caches on chip, with 2 MB external secondary cache, and 512 MB RAM. The version of the instruction set is SPARC 9. The operating environment is Solaris 2.6. The source code is compiled using the GCC version 2.8.1 compiler. The getrusage system call is used to measure the total amount of time spent executing in user and system mode in seconds. The measurements in the following sections are performed as in the following fragment of code:

struct getrusage ruse;
$t_0= (getrusage(RUSAGE\_SELF, \&ruse),ruse.ru\_utime.tv\_sec + \\ \indent \ind... ...1e-6 * \\ \indent \indent (ruse.ru\_utime.tv\_usec + ruse.ru\_stime.tv_usec));$
callToFunction();
$t_1= (getrusage(RUSAGE_SELF, \&ruse),ruse.ru\_utime.tv\_sec + \\ \indent \inde... ...1e-6 * \\ \indent \indent (ruse.ru\_utime.tv\_usec + ruse.ru\_stime.tv_usec));$
$User\_and\_System\_Time_{spent\_by\_(\mathbf{callToFunction()})} = t_1 - t_0;$