The use of right data types from the viewpoint of 64-bit technologies

The use of base data types corresponding to the hardware platform in C/C++ languages is an important point of creating quality and high-performance program solutions. With the appearance of 64-bit systems new data models have been used - LLP64, LP64, ILP64 (see table 1) and this changes the rules and recommendations concerning the use of base data types. To such types int, unsigned, long, unsigned long, ptrdiff_t, size_t and pointers can be referred. Unfortunately, there are practically no popular literature and articles which touch upon the problems of choosing types. And those sources which do, for example "Software Optimization Guide for AMD64 Processors" [12], are seldom read by application programmers.

The urgency of right choice of base types for processing data is determined by two important causes: the correct code’s work and its efficiency.

Due to the historical development the base and the most often used integer type in C and C++ languages is int or unsigned int. It is accepted to consider int type the most optimal as its size coincides with the length of the processor’s computer word.

The computer word is a group of RAM memory bits taken by the processor at one call (or processed by it as a single group) and usually contains 16, 32 or 64 bits.

The tradition to make int type size equal to the computer word has been seldom broken until recently. On 16-bit processors int consisted of 16 bits. On 32-bit processors it is 32 bits. Of course, there existed other correlations between int-size and the computer word’s size but they were used seldom and are not of interest for us now.

We are interested in that fact that with the appearance of 64-bit processors the size of int type remained 32-bits in most systems. Int type has 32-bit size in data models LLP64 and LP64 which are used in 64-bit Windows operating system and most Unix systems (Linux, Solaris, SGI Irix, HP UX 11).

It is a bad decision to leave int type size of 32-bit due to many reasons, but it is really a reasonable way to choose the lesser of two evils. First of all, it is related to the problems of providing backward compatibility. To learn more about the reasons of this choice you may read the blog "Why did the Win64 team choose the LLP64 model?" [13] and the article "64-Bit Programming Models: Why LP64?" [14].

For developers of 64-bit applications all said above is the reason to follow two new recommendations in the process of developing software.

Recommendation 1. Use ptrdiff_t and size_t types for the loop counter and address arithmetic’s counter instead of int and unsigned.

Recommendation 2. Use ptrdiff_t and size_t types for indexing in arrays instead of int and unsigned.

In other words you should use whenever possible data types whose size is 64 bits in a 64-bit system. Consequently you shouldn’t use constructions like:

for (int i = 0; i != n; i++)
  array[i] = 0.0;	

for (size_t i = 0; i != n; i++)
  array[i] = 0.0;

1) long type’s size remained 32-bit in 64-bit Windows operating system (see table 1). Consequently it cannot be used instead of ptrdiff_t and size_t types.

2) The use of long and unsigned long types causes a lot of troubles for developers of cross-platform applications for Windows and Linux systems. Long type has different sizes in these systems and only complicates the situation. It’s better to stick to types which have the same size in 32-bit and 64-bit Windows and Linux systems.

Now let’s explain by examples why we are so insistent asking you to use ptrdiff_t/size_t type instead of usual int/unsigned type.

We’ll begin with an example illustrating the typical error of using unsigned type for the loop counter in 64-bit code. We have already described a similar example before but let’s see it once again as this error is widespread:

size_t Count = BigValue;
for (unsigned Index = 0; Index != Count; ++Index)
{ ... }  	

The next example shows the error of using int type for indexing large arrays:

double *BigArray;
int Index = 0;
while (...)
  BigArray[Index++] = 3.14f;

As the last example we’d like to demonstrate the potential danger of mixed use of 32-bit and 64-bit types, which you should avoid whenever possible. Unfortunately, few developers think about the consequences of inaccurate mixed arithmetic and the next example is absolutely unexpected for many (the results are received with the use of Microsoft Visual C++ 2005 at 64-bit compilation mode):

int x = 100000;
int y = 100000;
int z = 100000;
intptr_t size = 1;                  // Result:
intptr_t v1 = x * y * z;            // -1530494976
intptr_t v2 = intptr_t(x) * y * z;  // 1000000000000000

intptr_t v3 = x * y * intptr_t(z);  // 141006540800000
intptr_t v4 = size * x * y * z;     // 1000000000000000
intptr_t v5 = x * y * z * size;     // -1530494976
intptr_t v6 = size * (x * y * z);   // -1530494976
intptr_t v7 = size * (x * y) * z;   // 141006540800000
intptr_t v8 = ((size * x) * y) * z; // 1000000000000000

intptr_t v9 = size * (x * (y * z)); // -1530494976

Now let’s look at the example demonstrating the advantages of using ptrdiff_t and size_t types from the viewpoint of productivity. For demonstration we’ll take a simple algorithm of calculating the minimal length of the path in the labyrinth. You may see the whole code of the program through this link: http://www.Viva64.com/articles/testspeedexp.zip.

In this article we place only the text of functions FindMinPath32 and FindMinPath64. Both these functions calculate the length of the minimal path between two points in a labyrinth. The rest of the code is not of interest for us now.

typedef char FieldCell;
#define FREE_CELL 1
#define BARRIER_CELL 2
#define TRAVERSED_PATH_CELL 3
unsigned FindMinPath32(FieldCell (*field)[ArrayHeight_32], unsigned x,
								unsigned y, unsigned bestPathLen,
								unsigned currentPathLen) {
  ++currentPathLen;
  if (currentPathLen >= bestPathLen)
    return UINT_MAX;
  if (x == FinishX_32 && y == FinishY_32)
    return currentPathLen;
  FieldCell oldState = field[x][y];
  field[x][y] = TRAVERSED_PATH_CELL;
  unsigned len = UINT_MAX;
  if (x > 0 && field[x - 1][y] == FREE_CELL) {
    unsigned reslen =
      FindMinPath32(field, x - 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (x < ArrayWidth_32 - 1 && field[x + 1][y] == FREE_CELL) {
    unsigned reslen =
      FindMinPath32(field, x + 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y > 0 && field[x][y - 1] == FREE_CELL) {
    unsigned reslen =
      FindMinPath32(field, x, y - 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y < ArrayHeight_32 - 1 && field[x][y + 1] == FREE_CELL) {
    unsigned reslen =
      FindMinPath32(field, x, y + 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  field[x][y] = oldState;
  
  if (len >= bestPathLen)
    return UINT_MAX;
  return len;
}
size_t FindMinPath64(FieldCell (*field)[ArrayHeight_64], size_t x,
								size_t y, size_t bestPathLen,
								size_t currentPathLen) {
  ++currentPathLen;
  if (currentPathLen >= bestPathLen)
    return SIZE_MAX;
  if (x == FinishX_64 && y == FinishY_64)
    return currentPathLen;
  FieldCell oldState = field[x][y];
  field[x][y] = TRAVERSED_PATH_CELL;
  size_t len = SIZE_MAX;
  if (x > 0 && field[x - 1][y] == FREE_CELL) {
    size_t reslen =
      FindMinPath64(field, x - 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (x < ArrayWidth_64 - 1 && field[x + 1][y] == FREE_CELL) {
    size_t reslen =
      FindMinPath64(field, x + 1, y, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y > 0 && field[x][y - 1] == FREE_CELL) {
    size_t reslen =
      FindMinPath64(field, x, y - 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  if (y < ArrayHeight_64 - 1 && field[x][y + 1] == FREE_CELL) {
    size_t reslen =
      FindMinPath64(field, x, y + 1, bestPathLen, currentPathLen);
    len = min(reslen, len);
  }
  field[x][y] = oldState;
  
  if (len >= bestPathLen)
    return SIZE_MAX;
  return len;
}

Table 2. Execution time of FindMinPath32 and FindMinPath64 functions.

Table 2 shows the time relative to the FindMinPath32 function’s execution speed in a 32-bit system. This is made for more clearness.

In the first line the work time of FindMinPath32 function in a 32-bit system is 1. It is because we take its work time for a unit of measure.

In the second line we see that FindMinPath64 function’s work time in a 32-bit system is 1 too. This is not surprising because unsigned type coincides with size_t type in a 32-bit system and there is no difference between FindMinPath32 and FindMinPath64 functions. Some deviation (1.002) means only a little time calculation error.

In the third line we see 7% productivity increase. This is an expected result of the code recompilation for a 64-bit system.

The fourth line is the most interesting. Productivity increase is 15% here. This means that the simple use of size_t type instead of unsigned allows the compiler to construct more efficient code working 8% faster!

It is a simple and clear example of how the use of data not equal to the computer word’s size decreases the algorithms productivity. Simple replacement of int and unsigned types with ptrdiff_t and size_t may give great productivity increase. First of all this refers to the use of these data types for indexing arrays, address arithmetic and organization of loops.

We hope that having read all said above you will think if you should continue to write:

for (int i = 0; i !=n; i++)
  array[i] = 0.0;

To learn more about the problems of developing quality and efficient 64-bit code you may read the following articles: "Problems of testing 64-bit applications" [17], "24 Considerations for Moving Your Application to a 64-bit Platform" [18], "Porting and Optimizing Multimedia Codecs for AMD64 architecture on Microsoft Windows" [19], "Porting and Optimizing Applications on 64-bit Windows for AMD64 Architecture" [20].

Page 5