COST Metric

COST — the Configuration that Outperforms a Single Thread — is a benchmarking metric proposed by Frank McSherry, Michael Isard, and Derek G. Murray at HotOS in 2015. Their definition: “The COST of a given platform for a given problem is the hardware configuration required before the platform outperforms a competent single-threaded implementation.” A system with a COST of sixteen cores needs sixteen cores before it is faster than one good thread; a system with unbounded COST has no reported configuration that gets there.

The problem it was invented for

Scaling curves look impressive and prove less than they appear to. The paper’s opening question is the useful one: “To what degree are these systems truly improving performance, as opposed to parallelizing overheads that they themselves introduce?” Its blunt corollary is that “any system can scale arbitrarily well with a sufficient lack of care in its implementation” — inefficiency parallelizes beautifully, so doubling the machines and halving the time can mean the system was doing twice the necessary work.

COST closes that gap by anchoring the comparison to an absolute baseline rather than to the system’s own smallest configuration. The authors describe it as weighing scalability against the overheads a system introduces, “without rewarding systems that bring substantial but parallelizable overheads.”

What they found, and its scope

Surveying data-parallel systems reported at major systems conferences and comparing them with single-threaded implementations on a 2014 laptop, the authors found many systems with “a surprisingly large COST, often hundreds of cores,” and several for which no reported configuration got past the single thread. For PageRank on one graph they report a COST of 16 cores for one system, 512 for another, and unbounded for a third; in some cases the single-threaded implementation was more than an order of magnitude faster than published results from hundreds of cores.

The scope matters. This is a 2015 paper about graph processing systems, and the authors themselves note that the comparisons are “neither perfect nor always fair.” It is not evidence that clusters are unnecessary, that any particular product is slow today, or that single-node tools always win. What survives is a method.

Using it on your own systems

• Establish the single-thread baseline first. Take the real problem and write, or run, a competent single-threaded implementation of the same task on the same input, producing the same results. Without that number, “it scales” has nothing to scale against. A multi-threaded run on one node is a different comparison: it can be reported, but it is not the single-thread baseline that COST uses.
• Read scaling curves as shape, not as merit. A curve shows what happens when resources are added. Absolute performance is a separate question, and it is the one users experience.
• Distinguish the reasons for distributing. Isolation, availability, and elastic cost are legitimate reasons to run a cluster even when the COST is high. Speed on a single job is the claim COST tests.

The paper’s epigraph, quoting Paul Barham, is the compact version: “You can have a second computer once you’ve shown you know how to use the first one.” How that judgment applies to choosing between one node and a cluster is worked through in Do You Actually Need a Cluster?

References

• Frank McSherry, Michael Isard, and Derek G. Murray, Scalability! But at what COST?, HotOS XV, 2015