Threads Cannot Be Implemented as a Library
ACM SIGPLAN Notices, 2005 · paper · Computer science
Argues that adding threading to a language like C through a library alone, with a compiler designed without threads in mind, cannot guarantee correct code. It also gives simple cases where this approach seems unable to express an efficient parallel algorithm.
Checked: PDF from read.seas.harvard.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
4 findings
Reference or label Reference [9] (Collins et al., Speculative precomputation, 28th ISCA) prints "pages 14–15, 2001."; the range is probably 14–25.
- p. 7 Reference [9] (entry starts on page 7, page range printed there)
pages 14–15, 2001.
- p. 7 Reference [9]
pages 14–15,
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that the Collins et al. ISCA 2001 paper runs to pages 14–25. Viewed the crop of page 7: the entry does print "pages 14–15, 2001." A two-page range for a full ISCA paper looks like a digit slip, but nothing in the files gives the true range, so the authors should check it.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [19] (Lamport) gives the journal as "IEEE Transactions on Computing, C-28(9):690–691, 1979."; the journal is probably IEEE Transactions on Computers.
- p. 8 Reference [19]
IEEE Transactions on Computing, C-28(9):690–691, 1979.
- p. 8 Reference [19]
IEEE Transactions on Computing,
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that Lamport's 1979 paper appeared in IEEE Transactions on Computers, whose volumes carry the "C-" prefix. Viewed the crop of page 8: the entry prints "IEEE Transactions on Computing" in italics. The journal name cannot be checked from the files.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [30] (Sarkar, ACM SIGPLAN PLDI) is dated "Portland, Oregon, January 1989."; the conference was probably held in June 1989.
- p. 8 Reference [30]
Portland, Oregon, January 1989.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that PLDI 1989 in Portland, Oregon took place in June 1989, not January. Viewed the crop of page 8: the entry prints "Portland, Oregon, January 1989." The conference month cannot be checked from the files.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [12] prints "M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):123–149, 1991."; the first page is probably 124.
- p. 8
M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Syste
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that Herlihy's "Wait-free synchronization" in TOPLAS 13(1) starts on page 124 (range 124–149), as the Crossref record cited by the reviewer states. Viewed the crop of page 8: the entry prints "13(1):123–149, 1991." The first page cannot be checked from the files.
Second check: another model agreed, code check
Report a problem with this finding
13 minor (typos and the like; most checked by the judge only)
Wording Section 5.1: "since the number of threads is less than the number of hardware threads", but the machine is "2 processors with 2 threads each" and runs go up to 4 threads, so the count equals the hardware threads in the 4-thread case.
- p. 6 Section 5.1, last paragraph of right column
since the number of threads is less than the number of hardware threads
- p. 6 Section 5.1, description of the Pentium 4 machine
2 processors with 2 threads each
- p. 6 Section 5.1, description of the Pentium 4 machine
2GHz, 2 processors with 2 threads each
- p. 6 text on Figure 4
since the number of
Judge's note: Page 6 gives the Pentium 4 machine as 2 processors with 2 threads each, i.e. 4 hardware threads, and the experiments use 1, 2 and 4 threads (the next sentence says "even with 4 threads"). "No more than" would be accurate. I found no statement elsewhere in the paper that changes the hardware thread count. Loose wording only.
Second check: another model agreed
Report a problem with this finding
Typo Footnote 2 duplicates a word: "multiple concurrent threads communicate communicate primarily through message passing".
- p. 1 Footnote 2
threads communicate communicate primarily
- p. 1 footnote 2
communicate communicate primarily
- p. 1 Footnote 2
communicate communicate
- p. 1 footnote 2
concurrent threads communicate communicate primarily
Judge's note: Viewed the crop of footnote 2 on page 1. The word "communicate" is printed twice in a row on the same line, so this is not an extraction or line-break artefact.
Second check: code check
Report a problem with this finding
Typo Section 2: "each of which can lead, and at least two of which have lead, to subtly incorrect code"; the participle should be "led".
- p. 2 Section 2 Overview, first paragraph
at least two of which have lead, to subtly incorrect
Judge's note: Viewed the crop of Section 2 on page 2; "have lead" is printed. Section 4 on page 3 uses the correct form ("the first problem led to an actual failure").
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.1: "Resolving it essential requires a programming-language-defined" (should be "essentially"); Section 5.1: "fully synchronized versions in figures 3" (plural with a single figure).
- p. 3 Section 4.1, penultimate paragraph
Resolving it essential requires a programming-language-defined
- p. 6 section 5.1
fully synchronized versions in fig- ures 3
- p. 4 section 4.2
it is know to the compiler
- p. 3 section 4.1 end
Resolving it essential requires
Judge's note: Both slips are visible on the page 3 and page 6 images. The other items bundled into this cluster ("have lead", "it is know", "libary") are real but are judged under C002, C006 and C010; this cluster is confirmed for the two items unique to it.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.2 code example "struct { int a:17; int b:15 } x;" lacks the semicolon after the last member declaration ("int b:15;").
- p. 3 Section 4.2, bit-field example
struct { int a:17; int b:15 } x;
Judge's note: The page 3 image shows the declaration exactly as quoted. The second struct on page 4 terminates its last member ("char h; } x;"). The paper's "taking some liberties with the C notation" remark is attached to a different expression on page 4. Cosmetic syntax slip in an illustrative snippet.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.2: "where it is know to the compiler that x is 64-bit aligned"; should be "known".
- p. 4 Section 4.2, paragraph before the 8-char struct
where it is know to the compiler that x is 64-bit
- p. 4 Section 4.2
it is know to the compiler that x is 64-bit
Judge's note: Visible in the left column of the page 4 image.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.3: "introduce variable updates were there were none in the source code"; the first "were" should be "where".
- p. 4 Section 4.3, first sentence
updates were there were none in the source code
- p. 4 Section 4.3 first sentence
introduce variable updates were there were none in the source code
- p. 4 Section 4.3 first paragraph
updates were there were none
Judge's note: Visible in the first sentence of Section 4.3 on the page 4 image.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.2: "The resulting behavior is sanctioned by the Pthreads standards, since it prohibits a concurrent write"; plural "standards" with singular "it".
- p. 4 Section 4.2, left column
sanctioned by the Pthreads standards, since it prohibits
Judge's note: Visible on the page 4 image. Elsewhere the paper writes "the Pthreads standard" in the singular (pages 2 and 5), though footnote 10 does say "the Posix standards". A minor number-agreement slip; either form could have been intended.
Second check: none (judge only)
Report a problem with this finding
Typo Section 5: "such as compare-and-swap, per libary call"; "library" is misspelled.
- p. 5 Section 5, third paragraph
libary call
- p. 5 section 5, first paragraph
per libary call
Judge's note: Visible in the left column of the page 5 image.
Second check: none (judge only)
Report a problem with this finding
Typo Section 5: "The continued use of the“double-checked locking” idiom" has no space between "the" and the opening quotation mark.
- p. 5 Section 5, last paragraph of left column
The continued use of the“double-checked locking” idiom
Judge's note: On the page 5 image (bottom of the left column) "the" and the opening quotation mark are run together.
Second check: none (judge only)
Report a problem with this finding
Typo Section 5.1: "we will see speed-ups due the additional threads"; the word "to" is missing.
- p. 6 Section 5.1, paragraph beginning "Thus N copies"
we will see speed-ups due the additional threads
Judge's note: Visible in the left column of the page 6 image, just before footnote mark 15.
Second check: none (judge only)
Report a problem with this finding
Typo Missing space after the comma in "other synchronization,while the last uses ordinary array accesses." (Section 5.1, PDF page 6).
- p. 6 Section 5.1, paragraph describing Figure 1
other synchronization,while the last
Judge's note: Viewed the crop of page 6. The printed line reads "other synchronization,while the last" with no space after the comma; the text layer agrees (main.txt line 864). It is in the published page, not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Plural used for a single figure: "less promising results for the fully synchronized versions in fig-ures 3." (Section 5.1, PDF page 6); should read "figure 3".
- p. 6 Section 5.1, paragraph beginning "Repeating the byte-array experiment"
fully synchronized versions in fig- ures 3
- p. 6 Section 5.1, right column, paragraph on the hyper-threaded Pentium 4
less promising results for the fully synchronized versions in fig- ures 3
- p. 6 text before Figure 4 discussion
fully synchronized versions in fig-
Judge's note: Viewed the crop of page 6. The right column prints "in fig-/ures 3. Here the single-threaded version..." across a line break. Only one figure number follows, and the Figure 3 caption ("HT P4 execution time for byte array (secs)") matches the hyper-threaded Pentium 4 byte-array experiment being described. The pointer goes to the right figure, so this is a number-agreement slip only.
Second check: none (judge only)