Changeset 6eed619

Timestamp:

Apr 24, 2019, 11:06:30 AM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

71a12390

Parents:

70eaa80b

Message:

thesis: add reference to concurrent hash tries

Location:

doc

Files:

• bibliography/pl.bib (modified) (2 diffs)
• theses/aaron_moss_PhD/phd/type-environment.tex (modified) (1 diff)

doc/bibliography/pl.bib

@@ -1091 +1091 @@
     year        = 2006,
     edition     = {4th},
+}
+
+@techreport{Prokopec11,
+  keywords = {ctrie, concurrent map},
+  contributer = {a3moss@uwaterloo.ca}, 
+  title={Cache-aware lock-free concurrent hash tries},
+  author={Prokopec, Aleksandar and Bagwell, Phil and Odersky, Martin},
+  institution={EPFL},
+  year={2011}
 }
 
@@ -1667 +1676 @@
     address     = {Redwood City},
     year        = 1991,
+}
+
+@inproceedings{Prokopec12,
+  keywords={ctrie, hash trie, concurrent map},
+  contributer={a3moss@uwaterloo.ca},
+  title={Concurrent tries with efficient non-blocking snapshots},
+  author={Prokopec, Aleksandar and Bronson, Nathan Grasso and Bagwell, Phil and Odersky, Martin},
+  booktitle={ACM SIGPLAN Notices},
+  volume={47},
+  number={8},
+  pages={151--160},
+  year={2012},
+  organization={ACM}
 }
 

doc/theses/aaron_moss_PhD/phd/type-environment.tex

@@ -299 +299 @@
 This persistent union-find data structure is efficient, but not thread-safe; as suggested in Section~\ref{resn-conclusion-sec}, it may be valuable to parallelize the \CFA{} expression resolver. 
 However, allowing multiple threads concurrent access to the persistent data structure is likely to result in ``reroot thrashing'', as different threads reroot the data structure to their own versions of interest. 
-This contention could be mitigated by partitioning the data structure into separate subtrees for each thread, with each subtree having its own root node, and the boundaries among them implemented with a lock-equipped !ThreadBoundary! edit node.
+This contention could be mitigated by partitioning the data structure into separate subtrees for each thread, with each subtree having its own root node, and the boundaries among them implemented with a lock-equipped !ThreadBoundary! edit node. 
+\cbstartx
+Alternatively, the concurrent hash trie of Prokopec \etal{} \cite{Prokopec11,Prokopec12} may be a useful hash-table replacement.
+\cbendx