The Art of Concurrency

Errata for The Art of Concurrency

Submit your own errata for this product.


The errata list is a list of errors and their corrections that were found after the product was released. If the error was corrected in a later version or reprint the date of the correction will be displayed in the column titled "Date Corrected".

The following errata were submitted by our customers and approved as valid errors by the author or editor.

Color Key: Serious Technical Mistake Minor Technical Mistake Language or formatting error Typo Question Note Update



Version Location Description Submitted By Date Submitted Date Corrected
Printed
Page 44
Example 2-6

To work with zero-based indexing, the left hand side of the assignment should be "B[k+3]".

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 62
example 3-5 Dekkers Algorithm

int favored; int Thread0WantsToEnter, Thread1WantsToEnter; These variables are not initialized. When ThreadZero() starts executing and evaluates

Note from the Author or Editor:
The global declarations in Example 3-5 (the three variables favored, Thread0WantsToEnter, and Thread1WantsToEnter) should all be initialized to zero as was done in previous attempts (Examples 3-1 to 3-4). You cannot rely on either thread initializing its desire flag before the other thread tests the value of that flag.

Anonymous  Jul 21, 2009 
Printed
Page 72
Fourth paragraph, first sentence

"Execution" should be "Extension". Thus, the sentence should start with... Streaming SIMD Extension (SSE) technology adds...

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 89
middle of the page

The functions listed as "pthread_lock()" and "pthread_unlock()" should be "pthread_mutex_lock()" and "pthread_mutex_unlock()", respectively.

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 90
Example 5-3

The example code in example 5-3 does not compile, as the function threadFunction is defined as returning a void *, which it then fails to do.

Note from the Author or Editor:
I'd swear that it compiled as is when I last tried it before publication. Now, I get the problem noted. To fix, simply add "pthread_exit(NULL);" where the return statement would be.

John Hardman  Jul 01, 2009 
Printed
Page 99
Example 6-3

Example 6-3 contains a call to InitializeArry instead of InitializeArray (as described in the text and as per other examples).

Note from the Author or Editor:
The code in Example 6-3 should call "InitializeArray(X, &N);"

John Hardman  Jul 01, 2009 
Printed
Page 99
Example 6-3 and Example 6-4 (on page 100)

The text says

Note from the Author or Editor:
If using a function to allocate memory for the data array within "InitializeArray()", the real array parameter must be "&X". Since the data may come from a different source (read from file, already available, subset of some larger data set, etc.), those details were glossed over by using the function "InitializeArray()". When testing examples, I had declared explicit arrays to be used in the algorithms. I forgot the details of passing arrays to be allocated within a function.

John Hardman  Jul 01, 2009 
Printed
Page 100
Example 6-4

Use of the combination of new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to code in Example 6-4 using the latter fix would be... void *Summation (void *pArg) { int tNum = *((int *) pArg); int lSum = 0; int start, end; start = (N/NUM_THREADS) * tNum; end = (N/NUM_THREADS) * (tNum+1); if (tNum == (NUM_THREADS-1)) end = N; for (int i = start; i < end; i++) lSum += X[i]; gSum[tNum] = lSum; delete (int *)pArg; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 105
Figure 6-4

Last box in second row (from top) says "5-7". This should be "6-7".

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 21, 2009 
Printed
Page 108
Example 6-8

The "HANDLE" declaration in the main() function has the wrong variable name. This line should be... HANDLE tHandles[NUM_THREADS];

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 108
Example 6-8, prefixScan() function

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to the top of the prefixScan() function code in Example 6-8 using the latter fix would be... unsigned __stdcall prefixSum(LPVOID pArg) { int tNum = *((int *) pArg); int start, end, i; int lPrefixTotal; delete (int *)pArg; start = (N / NUM_THREADS) * tNum; end = (N / NUM_THREADS) * (tNum + 1); if (tNum == (NUM_THREADS-1)) end = N;

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 113
Example 6-10

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to code in Example 6-10 using the latter fix would be... int SequentialSelect(int *S, int num, int k) { if (num <= Q) return SortLessThanQ(S, num, k); int cNum = num/Q + 1; int *Medians = new int[cNum]; int i = 0; for (int j = 0; j < num/Q; j++) { Medians[j] = SortSelect5(&S[i], 3); // find medians of subsequences i += Q; } int lastNum = num - (Q * (num / Q)); if (lastNum) { int lastQ = Q * (num / Q); Medians[cNum-1] = SortLessThanQ(&S[lastQ], lastNum, (lastNum+1)/2); } else cNum--; int M = SequentialSelect(Medians, cNum, (cNum+1)/2); delete Medians; int leg[3] = {0,0,0}; int *markS = new int[num]; CountAndMark(S, markS, num, M, leg); if (leg[0] >= k) { int *sPack = new int[leg[0]]; ArrayPack(S, sPack, num, markS, 0); delete markS; M = SequentialSelect(sPack, leg[0], k); delete sPack; return M; } else if ((leg[0] + leg[1]) >= k) { delete markS; return M; } else { int *sPack = new int[leg[2]]; ArrayPack(S, sPack, num, markS, 2); delete markS; M = SequentialSelect(sPack, leg[2], k-(leg[0]+leg[1])); delete sPack; return M; } }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 116
Example 6-12

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to code in Example 6-12 using the latter fix would be... int ParallelSelect(int *S, int num, int k) { if (num <= Q) return SortLessThanQ(S, num, k); int cNum = num/Q + 1; int *Medians = new int[cNum]; parallel_for(blocked_range<int>(0, num/Q), FindMedians(S, Medians), auto_partitioner()); int lastNum = num - (Q * (num / Q)); if (lastNum) { int lastQ = Q * (num / Q); Medians[cNum-1] = SortLessThanQ(&S[lastQ], lastNum, (lastNum+1)/2); } else cNum--; int M = ParallelSelect(Medians, cNum, (cNum+1)/2); delete Medians; int *markS = new int[num]; CountAndMark camBody(S, markS, M); parallel_reduce(blocked_range<size_t>(0,num), camBody, auto_partitioner()); int numLessEqual = camBody.leg.less + camBody.leg.equal; if (camBody.leg.less >= k) { int *sPack = new int[camBody.leg.less]; ArrayPack(S, sPack, num, markS, 0); delete markS; M = ParallelSelect(sPack, camBody.leg.less, k); delete sPack; return M; } else if ((numLessEqual) >= k) { delete markS; return M; } else { int *sPack = new int[camBody.leg.greater]; ArrayPack(S, sPack, num, markS, 2); delete markS; M = ParallelSelect(sPack, camBody.leg.greater, k-(numLessEqual)); delete sPack; return M; } }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 119
Example 6-15

There will be a memory leak in Example 6-15 without a delete of the new memory allocation. The better ArrayPack() function code would be... void ArrayPack(int S[], int sPack[], int num, int Marks[], int scanSym) { int *scanIdx = new int[num]; PackingScan body(scanIdx, Marks, scanSym); parallel_scan(blocked_range<int>(0,num), body, auto_partitioner()); if (scanIdx[0]) sPack[0] = S[0]; // move if first element is marked parallel_for(blocked_range<int>(1,num), PackingMove(scanIdx,sPack,S), auto_partitioner()); delete[] scanIdx; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 130
6th line from bottom

und so veiter should be und so weiter

Note from the Author or Editor:
That is correct. (My apologies to Herr Weir, my high school German teacher.)

Anonymous  Aug 06, 2010 
Printed
Page 131
Example 7-2

The function SumByReduction is defined as returning a void *, which it fails to do. A strict compiler will not allow this to build.

Note from the Author or Editor:
Add "pthread_exit(NULL);" where a 'return' statement would be.

John Hardman  Jul 01, 2009 
Printed
Page 131
Example 7-2, fourth line from bottom of page

The ampershand (&) used in the pthread_join() call should be removed. The pthread_t object itself, not a pointer to the object must be used. This source line should be... pthread_join(tHandles[0], NULL):

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 131
Example 7-2

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to the last executable line of code in the SumByReduction() function in Example 7-2 using the latter fix would be... delete (int *)pArg;

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 135
Code for pth_barrier() function at bottom of page

The broadcast in the "else" clause is better executed after the update of the barrier fields. The mutex unlock after the if-then-else will ensure that no threads that have been awakened have access to the barrier object before these values are set. The code for this clause should be... else { // last thread b->count = b->numThreads; b->color = !b->color; pthread_cond_broadcast(&b->c); }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 135
Code segment at the top of the page

The colon (:) at the end of the first code segment should be a semi-colon (;). Thus, the code segement should be... typedef struct { pthread_mutex_t m; pthread_cond_t c; int count, color, numThreads; } pth_barrier_t;

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 135
Second source code segment

The first underscore character (_) has been dropped from the pthread_cond_init() function call. The correct line should be... pthread_cond_init(&b->c, NULL);

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 140
Example 7-3

There will be a memory leak in Example 7-3 without a delete of the new memory allocations. The last two lines at the end of the code segment (end of the FriendlyNumbers() function) should be expanded to be... } // end parallel region delete[] the_num; delete[] num; delete[] den; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 156
Example 8-5

The bounds of the for-loop are incorrect. The termination condition should be "N-1" not "N", as it is given in the first algorithm attempt in Example 8-4. Thus, the correct line should be... for (i = start; i < N-1; i += 2) {

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 157
Example 8-6

"#pargma omp parallel" should be "#pragma omp parallel"

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 158
Example 8-6

The bounds of the for-loop are incorrect. The termination condition should be "N-1" not "N", as it is given in the serial algorithm (Example 8-3). Thus, the correct line should be...<p> for (i = start; i < N-1; i += 2) {

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 158
Example 8-6, second critical region

The correct function name to call is omp_get_num_threads(). The correct line in the OpenMP critical (within the for-loop) should be... exch = omp_get_num_threads(); // Assign with the number of threads

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 166
examples 8-10 and 8-11

The code as is will cause a segfault. In order to fix this, this line: while(A[j-h] > v) should be changed to: while(j >= h && A[j-h] > v) Look at the first iteration, for example. k=0, i=k (so i=0), and j=i (so j=0). h is guaranteed to be non-zero, so A[j-h] will attempt to index into A using a negative index which causes a segfault.

Note from the Author or Editor:
Good catch. (I blame soft compilers that don't automatically do bounds checking and myself for trusting them.) This change also eliminates the if test to break at the end of the loop. Thus, the while-loop in Examples 8-10 and 8-11 should be... while (j >= h && A[j-h] > v) { A[j] = A[j-h]; j -= h; }

Geoffrey Fairchild  Sep 29, 2010 
Printed
Page 172
Example 8-13

The third parameter of WaitForMultipleObjects() was left out. The correct third parameter should be "TRUE". The correct line should be... WaitForMultipleObjects(2, tH, TRUE, INFINTE);

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 173
Example 8-14

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The first few lines of the while-loop code in Example 8-14 using the latter fix would be... while (notEmpty(Q)) { dequeue(Q, d); //pull out next index pair p = d->lo; r = d->hi; delete d;

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 179
Example 8-17

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The first few lines of the while-loop code in Example 8-17 using the latter fix would be... while (1) { WaitForSingleObject(hSem, INFINITE); if (Done) break; // external signal to terminate threads dequeue(Q, d); p = d->lo; r = d->hi; delete d;

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 184
Example 8-19

The while loop line in RadixExchangeSort() should be: while (notEmpty(Q)) {

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 21, 2009 
Printed
Page 184
Example 8-19

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The first few lines of the while-loop code in the RadixExchangeSort() function in Example 8-19 using the latter fix would be...< while (notEmpty(Q)) { dequeue(Q, d); //pull out next index pair, unless queue is empty p = d->lo; r = d->hi; bPos = d->bitPosition-1; delete d;

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 187
Example 8-20

Use of pointers will not work if an odd number of iterations within the given function are executed. Better, more general code for the example would be: #define mbits 4 #define M 16 void StraightRadixSort(int **A, int N, int b) { int i, j, pass, tBits; int count[M]; int *tA = new int[N]; int *tempPtr; for (pass = 0; pass < (b / mbits); pass++) { for (j = 0; j < M; j++) count[j] = 0; for (i = 0; i < N; i++) { count[bits((*A)[i], pass*mbits, mbits)]++; } count[0]--; for (j = 1; j < M; j++) count[j] += count[j-1]; // prefix sum on counts for (i = N-1; i >= 0; i--) { tBits = bits((*A)[i], pass*mbits, mbits); tA[count[tBits]] = (*A)[i]; count[tBits]--; } // swap pointers to swap arrays to sort in next pass tempPtr = tA; tA = *A; *A = tempPtr; } delete[] tA; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 21, 2009 
Printed
Page 189
within "Note"

The last sentence of the note begins "This scheme is only scalable to the number of different bit patterns used (mbits squared) and requires all ...." The number of distinct bit patterns for mbits is 2 to the mbits.

Note from the Author or Editor:
D'oh! You're right, I had my "2" in the wrong place. The proper phrase in the parenthesis of that sentence should be "2 raised to the power of mbits".

Robert H. Stine, Jr.  Feb 28, 2011 
Printed
Page 191
Example 8-21

Use of pointers will not work if an odd number of iterations within the given function are executed. Better, more general code for the example would be: #define mbits 4 #define M 16 void SerialStraightRadixSort(int **A, int N, int b) { int i, j, pass; int offset, rank; int count; int *tA = new int[N]; int *tempPtr; for (pass = 0; pass < (b / mbits); pass++) { offset = -1; //for 0-base index for (j = 0; j < M; j++) { count = 0; for (i = 0; i < N; i++) { if (bits((*A)[i], pass*mbits, mbits) == j) count++; } rank = offset + count; for (i = N-1; i >= 0; i--) { if (bits((*A)[i], pass*mbits, mbits) == j) tA[rank--] = (*A)[i]; } offset += count; } // swap pointers to swap arrays to sort in next pass tempPtr = tA; tA = *A; *A = tempPtr; } delete[] tA; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 21, 2009 
Printed
Page 194
Figure 8-11

gcount[1] holds "1". This value should be "2". There are two elelments (both '61') with a '1' in the least significant digit of the original data.

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 21, 2009 
Printed
Page 195
Example 8-22

The variable "offset" is not used in the function; the declaration can be removed. The final declaration line should be... int start, end;

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 196
Example 8-22

The function ParallelStraightRadixSort is defined as returning a void *, which it fails to do. A strict compiler will not allow this to build.

Note from the Author or Editor:
Add "pthread_exit(NULL);" where a 'return' statement would be.

John Hardman  Jul 01, 2009 
Printed
Page 206
Example 9-4

The function pSearch is defined as returning a function, but it does not do so. A strict compiler will not allow this code to build. ExitThread is used in this example, which is acceptable in C code, but not recommended in C++ code. It would work in this particular piece of code even if built as C++, but is not a good habit to pick up, as if the code were modified to construct any objects, their destructors would not get called when ExitThread was called.

Note from the Author or Editor:
All codes are written in C -- with a dash of C++ when needed (classes for TBB) or convenient ('new' for allocation). This is mentioned in the Preface at the top of page ix. If you are using C++ (or Java or C# or something else) there may be required changes to the example codes.

John Hardman  Jul 01, 2009 
Printed
Page 206
Example 9-4

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to to the last few lines of code in the pSearch() function in Example 9-4 using the latter fix would be... LinearPSearch(A, start, end, key, &pos); delete (sParam *)pArg; ExitThread(pos); }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 214
Example 9-7

There will be a memory leak in Example 9-7 without a delete of the new memory allocations. The last few lines of the NarySearch() function code would be... if (locate[Ntrvl] != locate[Ntrvl+1]) lo = mid[Ntrvl] + 1; } delete[] locate; delete[] mid; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 217
Example 9-8

There will be a memory leak in Example 9-8 without a delete of the new memory allocations. The last few lines of the NarySearch() function code would be... if (locate[Ntrvl] != locate[Ntrvl+1]) lo = mid[Ntrvl] + 1; } // end single } } // end parallel region delete[] locate; delete[] mid; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 222
Third paragraph, first sentence

The phrase "edge pairs" makes no sense. The first line should read... A graph is directed if all node pairs (representing edges) are ordered.

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 22, 2009 
Printed
Page 233
Example 10-5

The original code is not wrong. As it is, the call to ReleaseSemaphore() is done each time the "if" condition is true. The idea was to keep a count and then call this function once. This can be done by the following change to the relevant conditional code given in Example 10-5: if (iWillVisit) { /* Do something to VISIT node k */ long semCount = 0; for (i = V-1; i >= 0; i--) if (adj[k][i]) { push(S, i); semCount++; } if (semCount) ReleaseSemaphore(hSem, semCount, NULL); iWillVisit = 0; if (gCount == V) SetEvent(tSignal); } Since the count declaration is now in the (WillVisit) test, the extra braces (from the for-loop) aren't needed.

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 21, 2009 
Printed
Page 244
Second sentence of second full paragraph

The correct sentence should be: We can compute each term by finding the smallest sum, d^k/2[i][l] + d^k/2[l][j], for all possible nodes l. The first "j" and second "i" should be "l" (12th letter of alphabet)and the addition of the "l" index value at the end of the sentence and in italics.

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 21, 2009 
Printed
Page 249
Example 10-9

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The last few lines of the Prims() function code in Example 10-9 using the latter fix would be... } // for i delete[] nearNode; delete[] minDist; return; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009 
Printed
Page 253
Example 10-11

There will be a memory leak in Example 10-11 without a delete of the new memory allocations. To fix this, the last few lines of the cPrims() function code in Example 10-11 should be... } // for i delete[] nearNode; delete[] minDist; return; }

Clay Breshears
Clay Breshears
O'Reilly Author 
Dec 23, 2009