Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Implementation of Large Lists and its Use in Radix Sort

IP.com Disclosure Number: IPCOM000111221D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 53K

Publishing Venue

IBM

Related People

Case, DR: AUTHOR [+4]

Abstract

Sequential processing of a list is common in a variety of applications. The conventional realizations of a list are array and linked list. An array enjoys a good locality of reference, but suffers from a waste of memory when the number of items in the list is unknown. A linked list handles the unknown length better, but suffers from a poor locality of reference. Use of data structure with good locality of reference is desirable since large number of expensive memory accesses is saved because in most cases the data is found in the cache. Hence performance improves significantly.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 57% of the total text.

Implementation of Large Lists and its Use in Radix Sort

      Sequential processing of a list is common in a variety of
applications.  The conventional realizations of a list are array and
linked list.  An array enjoys a good locality of reference, but
suffers from a waste of memory when the number of items in the list
is unknown.  A linked list handles the unknown length better, but
suffers from a poor locality of reference.  Use of data structure
with good locality of reference is desirable since large number of
expensive memory accesses is saved because in most cases the data is
found in the cache.  Hence performance improves significantly.

      The problem addressed is how to implement a list of unknown
length while preserving the benefit of good cache exploitation.
Demonstrated is the effectiveness of the solution in the context of
Radix Sort.  The proposed technique suggests a design which enjoys
the advantages of both arrays and linked lists.  The idea is to use a
linked list of blocks.  A block is actually an array, i.e., a
contiguous segment of memory.  The rear of one block is linked to the
front of its successor.  This realization has the following
properties:

1.  Copes well with unknown size - grows with the requirement.

2.  Has a locality of reference close to optimal - every cache miss
    will bring many successor items into cache.

3.  Minimizes storage waste - waste is bound by the block size.

      Radix sort is a well known t...