Practically efficient array initialization. (2nd February 2015)

• Record Type: Journal Article
• Authors: Fredriksson, Kimmo; Kilpeläinen, Pekka
• Is Part Of: Software, practice & experience. Volume 46:Number 4(2016)
• Page Start: 435
• Page End: 467
• Publication Date: 2015-02-02
• Subjects: array -- constant‐time initialization -- performance -- word‐level parallelism -- cache‐efficiency -- experimentation; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2314
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Initialization of an array, out of which only a small initially unknown portion will eventually be used, is a frequent need in programming. A folklore solution for initializing an array of n entries in constant time uses 2 n ⌈log2 n ⌉ extra bits to realize a stack of back pointers to the actually used entries of the array. Navarro has given a succinct version of this technique, which requires only n + o ( n ) bits of auxiliary storage. We describe, analyze, and experimentally compare these solutions and their space‐efficient but theoretically suboptimal alternatives based on a simple bitmap for keeping track of the array entries which have been assigned a value. Experimental results suggest that each of the methods has its niche of excellence, which are roughly as follows: the theoretically optimal solutions based on a stack of back pointers perform in general best on sparse arrays, whose access frequency is less than 1% of the number of their entries. Brute‐force initialization of the entire array seems generally to give the best overall performance for dense arrays whose access frequency is over 10% of their size. For the remaining cases of arrays with 1–10% access frequency, the methods which use a simple bitmap appear to give the best performance. The experiments show that the choice of a suitable implementation may yield substantial, up to hundreds of times speed‐ups in the performance of initializable array operations. Copyright © 2015 John Wiley & Sons Ltd.