Microsoft Technology Licensing, LLC

Douglas S Boa

Barry M Nolte

Simon M Meacham

Michael Andrew Brian Parkes

A method, apparatus, software and data structure is disclosed for more efficient access times for linear operations in a hash table, including finding the nearest logical record. A plurality of actual data records and a plurality of marker data records are inserted in a hash table using a hash function. The actual data records and marker data records have a logical ordering specified by a key and are threaded into the hash table to allow linear access by walking the hash table. The logical ordering of the actual data records and marker records is lost upon entry into the hash table, and the keys of the marker data records are distributed at known positions throughout the range of the keys of the actual data records. If when hashing a given key no record exists in the database for the given key, one of the keys for the marker data records are hashed to locate the associated marker data record in the hash table. A nearest logical record may thus be retrieved entering the hash table through the marker data record.

Method and apparatus for finding nearest logical record in a hash table

A method, apparatus, software and data structure is disclosed for more efficient access times for linear operations in a hash table. A plurality of actual data records and a plurality of marker data records are inserted in a hash table using a hash function. The actual data records and marker data records have a logical ordering specified by a key and are threaded into the hash table to allow linear access by walking the hash table. The logical ordering of the actual data records and marker records is lost upon entry into the hash table, and the keys of the marker data records are distributed at known positions throughout the range of the keys of the actual data records. If when hashing a given key no record exists in the database for the given key, one of the keys for the marker data records are hashed to locate the associated marker data record in the hash table. Distribution of data records according to the hash function is also determined by locating a marker data record in the database and examining the position of adjacent records. The distribution of records provides a measure of performance of the hash table and for tuning of the hash table.

Method and apparatus for marking a hash table and using the marking for determining the distribution of records and for tuning

An invention for reassigning data elements of an application to cache lines to decrease the occurrence of cache line faults is described. First, an application is executed and used in a typically manner. While the application is running, data is collected concerning the loading and storing of data elements. This collection process creates a massive volume of data that is then processed to determine correlations between the loading and storing pairs of elements within each of the application's data structures. These correlations provide a mechanism for weighing the probability of pairs of intra-structure data elements being accessed in sequence, which is best accomplished when the data elements are within a single cache line. A set of simultaneous equations describe the probabilities using the data recording the correlations. These equations are then solved using commonly known linear programming techniques to derive a suggested ordering of data structures. An interactive editor is then used to reorder these data elements in the derived preferred order as authorized by the programmer.

Optimized allocation of data elements among cache lines

An invention for optimizing the logging of data elements to a hardware device is described. Using this invention, a large stream of data can be written to a hardware device at a rate that approaches the limits of the physical characteristics of the hardware device. To achieve this efficiency, the performance of a logging operation is divided between a data source and a data logging software processes which operate in different threads or processes. The data source collects pieces of data to be written to the hardware device into a larger buffer retrieved from a pool of empty buffers. When a buffer becomes full, the buffer is placed at the end of a full buffer queue. The data logger, operating asynchronously, retrieves a full buffer from the queue and then writes the data to the hardware. In this fashion, the hardware data logging device is able to perform optimally while creating or expanding the file.

Growing community of inventors

Redmond, WA, United States of America

Douglas S Boa