The \emph{Order-Maintenance} (OM) data structure maintains a total order list
of items for insertions, deletions, and comparisons. As a basic data structure,
OM has many applications, such as maintaining the topological order, core
numbers, and truss in graphs, and maintaining ordered sets in Unified Modeling
Language (UML) Specification. The prevalence of multicore machines suggests
parallelizing such a basic data structure. This paper proposes a new parallel
OM data structure that supports insertions, deletions, and comparisons in
parallel. Specifically, parallel insertions and deletions are synchronized by
using locks efficiently, which achieve up to $7$x and $5.6$x speedups with $64$
workers. One big advantage is that the comparisons are lock-free so that they
can execute highly in parallel with other insertions and deletions, which
achieve up to $34.4$x speedups with $64$ workers. Typical real applications
maintain order lists that always have a much larger portion of comparisons than
insertions and deletions. For example, in core maintenance, the number of
comparisons is up to 297 times larger compared with insertions and deletions in
certain graphs. This is why the lock-free order comparison is a breakthrough in
practice.