Decompression of block-sorted data

A computer-implemented method of decoding data, comprising:

• performing N computations, where N is an integer greater than 1, so as to independently decode N distinct portions of a set of encoded data, each of the N computations comprising performing, a plurality of times, a set of operations including:
• invoking a lookup operation to access information in an array at a lookup location;
• performing a respective decoding operation using a result of the lookup operation;
• appending a result of the decoding operation to an output set;
• and
• identifying a new lookup location based on the result of the decoding operation;
• wherein the N computations are interleaved such that when a plurality of the lookup operations of the N computations result in cache misses, main memory accesses for completing the plurality of lookup operations are performed during overlapping time periods.

A computer-program product for decoding data for use in conjunction with a computer system, the computer-program product comprising a computer-readable storage medium and a computer-program mechanism embedded therein, the computer-program mechanism comprising:

• instructions for accessing information in an array to decode a set of encoded data and produce a set of decoded data, including instructions for performing a sequence of operations a plurality of times, the instructions for the sequence of operations including:
• instructions for invoking a plurality of lookup operations to access information in the array, wherein the plurality of lookup operations are mutually independent operations and a plurality of main memory accesses required to perform the plurality of lookup operations are performed during overlapping time periods when the computer system performing the instructions is capable of performing main memory access operations during overlapping time periods;
• instructions for performing a respective plurality of decoding operations using results of the plurality of lookup operations;
• and
• instructions for identifying a new plurality of lookup operations based on results of the plurality of decoding operations.

A computer system for decoding data, comprising:

• a main memory;
• a processor with a cache memory;
• and
• at least one program, stored in the main memory and executed by the processor, the at least one program including instructions for accessing information in an array to decode a set of encoded data and produce a set of decoded data, including instructions for performing a sequence of operations a plurality of times, the instructions for the sequence of operations including:
• instructions for invoking a plurality of lookup operations to access information in the array, wherein the plurality of lookup operations are mutually independent operations, and wherein the invoking instructions perform a plurality of main memory accesses during overlapping time periods when at least two of the lookup operations result in cache misses;
• instructions for performing a respective plurality of decoding operations using results of the plurality of lookup operations;
• and
• instructions for identifying a new plurality of lookup operations based on results of the plurality of decoding operations.

A computer system for decoding data, comprising:

• a means for accessing information in an array to decode a set of encoded data and produce a set of decoded data, including a means for performing a sequence of operations in a program stored in a main memory a plurality of times, the means for performing the sequence of operations including:
• means for selecting N starting points within the array, where N is an integer greater than 1;
• means for invoking N lookup operations to access information in the array, wherein the N lookup operations are mutually independent operations, and wherein the means for invoking N lookup operations includes means for performing at least two main memory accesses from the main memory during overlapping time periods when at least two of the N lookup operations result in cache misses;
• means for performing N decoding operations using results of the N lookup operations;
• and
• means for identifying a new set of N lookup operations based on results of the N decoding operations.