GeezerVison

ENIAC vacuum tube array 1 ENIAC vacuum tube array ¹

Computer memory from Wikipedia ↩︎

An Array is a linear data structure to collect data elements or entities by random access, which also includes sequential access. The address of each array element can be identified by one or more integer indices. Array structures are the computer analog of the mathematical concepts of vector and matrix.

Therefore, an one-dimensional array is often synonymously called vector, either in the context of a vector processors and SIMD instruction sets, operating on multiple data, or as vector container, for instance as class template in the C++ Standard Template Library, which works like a dynamic array.

Contents

One-Dimensional Array
Multidimensional Array
1. Homogeneous
2. Array of Arrays
Fixed Sized Arrays
Dynamic Arrays
1. On the Heap
2. On the Stack
Array Samples
1. Assembly
2. C / C++
3. Java
Arrays inside a Chess Program
1. Lookup Tables
2. Read/Write
  1. Square
  2. Two Squares
  3. Ply
  4. Pieces
  5. Hash key
See also
Publications
Forum Posts
External Links
1. Assembly
2. Basic
3. C
4. C++
5. D
6. Java
7. Lisp
8. Pascal
9. Perl
10. Python
11. Ruby
12. TCL
13. .NET
14. Math
15. Misc
References

One-Dimensional Array

A one-dimensional or linear Array contains n elements indexed by one integer. Each element has the same size. Arrays exploit the addressing machinery of computers, whose random-access memory is treated as one-dimensional array of bytes or words, and indices are their addresses. One-dimensional arrays are therefore very efficient, and used to implement many other data structures, such as multidimensional arrays, linked lists, queues, stacks, hash tables, trees and strings.

Array in memory ¹

Multidimensional Array

Homogeneous

A homogeneous two- or multidimensional array may be interpreted as array of commensurate, embedded arrays, typically associated with the array data structure. A one-dimensional address calculation from an index tuple is a simple, multiplicative formula.

int zobristKeys[12][64];
zobristKey[piece][square]

With following one-dimensional translation:

int zobristKeys[12*64];
zobristKey[piece*64 + square]

Often, those index translations are already done by the (chess) programmer, i.e. a classical 8x8 board is most often treated as one-dimensional array indexed by square rather than a two-dimensional array indexed by a tuple of file and rank. Multidimensional Array ²

Array of Arrays

If sub-arrays of a multidimensional array have different sizes, they are allocated elsewhere and referred by a pointer or reference. In Java, multidimensional arrays are treated that way implicitly as array data type, in C and C++ they need to be implemented explicitly. Due to the additional indirection(s), the access is slightly slower.

Arrays of different sized sub-arrays are f. i. used in Fancy Magic Bitboards to safe memory for "denser" squares. A triangular PV-table is often implemented as a one-dimensional array either with accordant index calculation, or wasting some space for commensurate, maximum sized sub-arrays for each PV.

Array of Arrays ³

Fixed Sized Arrays

An Array whose size is already determined at compile time is allocated statically if either declared as fixed sized global array, or in C equivalently as static array inside the scope of a subroutine or module, whose lifetime extends across the run of the program. Alternatively, fixed sized arrays may be allocated once from the dynamic heap, or created temporary as local array-variable on the stack of the processor, valid inside a scope of a routine.

These arrays work most efficiently, since one array access of a word or integer element directly translates into an appropriate machine instruction using a (scaled) index register in conjunction with an immediate address or base register for the base address of the array. The danger without any runtime bounds checking is that (a probably very rare) index-overflow will either cause the program to crash, or even harder to find, to make the program behave sporadically erroneous. Some programmers, often provide a debug assertion ⁴ to check array bounds at runtime in a debug version.

// assuming signed index
assert (index >= 0 && index < MAX_PLY);
alpha[index] = a;

While global and static arrays may be initialized at compile time as well, as often used for lookup tables, arrays located in the bss-segment or allocated from the heap or stack may require runtime initialization depending on the application.

Dynamic Arrays

Dynamic arrays can be created at runtime with a size or number of elements actually needed. Once created, they may be treated as static arrays without further bound checking, or they may be re-allcoated to dynamically shrink or grow their size. Abstract arrays support a random access interface, and may pre-check the index to perform a dynamic re-allocation policy if required.

On the Heap

Dynamic arrays are usually allocated from the heap, a dynamic data area supported by the operating system and underlying BIOS. In C, dynamic arrays can be created by malloc (sizeof(type)*size), in C++ by new type [size]. Memory areas should be explicitly freed if no longer needed, in C++ by delete[]. Various configurable sized hash tables like the transposition table are usually allocated from the heap by explicit runtime initialization.

On the Stack

Some operating systems provide C library calls which allow runtime dynamic allocation from the stack rather than the heap, e. g. in Unix with alloca ⁵ and malloca ⁶ for Windows. Further, C99 supports variable-length arrays (VLA). Like other automatic variables or fixed sized arrays on the stack, this memory is freed automatically after leaving the scope of the routine.

Array Samples

Definitions and usage in various programming languages:

Assembly

 board db 64 dup (?)
 square dd

 mov ebx, [square]
 mov al, [board+ebx]

C / C++

Note that in C and C++, pointer may be treated as array.

 static const int magicTable[64] = {
   0, 1,48, 2,57,49,28, 3,
  61,58,50,42,38,29,17, 4,
  62,55,59,36,53,51,43,22,
  45,39,33,30,24,18,12, 5,
  63,47,56,27,60,41,37,16,
  54,35,52,21,44,32,23,11,
  46,26,40,15,34,20,31,10,
  25,14,19, 9,13, 8, 7, 6,
 };

 int board[64];
 int distance[64][64];
 int zobristKeys[12][64];
 int* pBoard = malloc(sizeof(int) * 64);

 int* pboard = new int[64];
 for (int sq = 0; sq < 64; ++sq)
    pboard[sq] = board[sq]; // in C/C++ identical to *(pboard + sq) = board[sq];
 ...
 delete[] pboard;

Java

 static private final int[] magicTable = {
   0, 1,48, 2,57,49,28, 3,
  61,58,50,42,38,29,17, 4,
  62,55,59,36,53,51,43,22,
  45,39,33,30,24,18,12, 5,
  63,47,56,27,60,41,37,16,
  54,35,52,21,44,32,23,11,
  46,26,40,15,34,20,31,10,
  25,14,19, 9,13, 8, 7, 6,
 };
 
 int[] board = new int[64];