diff --git a/tests/other/cs-benchmark.cpp b/tests/other/cs-benchmark.cpp
index fcd9d20..3e7a5a2 100644
--- a/tests/other/cs-benchmark.cpp
+++ b/tests/other/cs-benchmark.cpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
- * Copyright (c) 2014-2015,  Regents of the University of California,
+ * Copyright (c) 2014-2016,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
@@ -24,10 +24,13 @@
  */
 
 #include "table/cs.hpp"
-#include <ndn-cxx/security/key-chain.hpp>
 
 #include "tests/test-common.hpp"
 
+#ifdef HAVE_VALGRIND
+#include <valgrind/callgrind.h>
+#endif
+
 namespace nfd {
 namespace tests {
 
@@ -39,17 +42,26 @@
 #ifdef _DEBUG
     BOOST_TEST_MESSAGE("Benchmark compiled in debug mode is unreliable, "
                        "please compile in release mode.");
-#endif // _DEBUG
+#endif
 
     cs.setLimit(CS_CAPACITY);
   }
 
-  time::microseconds
-  timedRun(std::function<void()> f)
+  static time::microseconds
+  timedRun(const std::function<void()>& f)
   {
-    time::steady_clock::TimePoint t1 = time::steady_clock::now();
+#ifdef HAVE_VALGRIND
+    CALLGRIND_START_INSTRUMENTATION;
+#endif
+
+    auto t1 = time::steady_clock::now();
     f();
-    time::steady_clock::TimePoint t2 = time::steady_clock::now();
+    auto t2 = time::steady_clock::now();
+
+#ifdef HAVE_VALGRIND
+    CALLGRIND_STOP_INSTRUMENTATION;
+#endif
+
     return time::duration_cast<time::microseconds>(t2 - t1);
   }
 
@@ -84,7 +96,7 @@
     Name m_prefix;
   };
 
-  std::vector<shared_ptr<Interest>>
+  static std::vector<shared_ptr<Interest>>
   makeInterestWorkload(size_t count, const NameGenerator& genName = SimpleNameGenerator())
   {
     std::vector<shared_ptr<Interest>> workload(count);
@@ -95,7 +107,7 @@
     return workload;
   }
 
-  std::vector<shared_ptr<Data>>
+  static std::vector<shared_ptr<Data>>
   makeDataWorkload(size_t count, const NameGenerator& genName = SimpleNameGenerator())
   {
     std::vector<shared_ptr<Data>> workload(count);
@@ -108,7 +120,7 @@
 
 protected:
   Cs cs;
-  static const size_t CS_CAPACITY = 50000;
+  static constexpr size_t CS_CAPACITY = 50000;
 };
 
 BOOST_FIXTURE_TEST_SUITE(TableCsBenchmark, CsBenchmarkFixture)
@@ -116,8 +128,8 @@
 // find miss, then insert
 BOOST_AUTO_TEST_CASE(FindMissInsert)
 {
-  const size_t N_WORKLOAD = CS_CAPACITY * 2;
-  const size_t REPEAT = 4;
+  constexpr size_t N_WORKLOAD = CS_CAPACITY * 2;
+  constexpr size_t REPEAT = 4;
 
   std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_WORKLOAD);
   std::vector<shared_ptr<Data>> dataWorkload[REPEAT];
@@ -139,8 +151,8 @@
 // insert, then find hit
 BOOST_AUTO_TEST_CASE(InsertFindHit)
 {
-  const size_t N_WORKLOAD = CS_CAPACITY * 2;
-  const size_t REPEAT = 4;
+  constexpr size_t N_WORKLOAD = CS_CAPACITY * 2;
+  constexpr size_t REPEAT = 4;
 
   std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_WORKLOAD);
   std::vector<shared_ptr<Data>> dataWorkload[REPEAT];
@@ -162,8 +174,10 @@
 // find(leftmost) hit
 BOOST_AUTO_TEST_CASE(Leftmost)
 {
-  const size_t N_CHILDREN = 10;
-  const size_t N_INTERESTS = CS_CAPACITY / N_CHILDREN;
+  constexpr size_t N_CHILDREN = 10;
+  constexpr size_t N_INTERESTS = CS_CAPACITY / N_CHILDREN;
+  constexpr size_t REPEAT = 4;
+
   std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_INTERESTS);
   for (auto&& interest : interestWorkload) {
     interest->setChildSelector(0);
@@ -176,8 +190,6 @@
   }
   BOOST_REQUIRE(cs.size() == N_INTERESTS * N_CHILDREN);
 
-  const size_t REPEAT = 4;
-
   time::microseconds d = timedRun([&] {
     for (size_t j = 0; j < REPEAT; ++j) {
       for (const auto& interest : interestWorkload) {
@@ -191,8 +203,10 @@
 // find(rightmost) hit
 BOOST_AUTO_TEST_CASE(Rightmost)
 {
-  const size_t N_CHILDREN = 10;
-  const size_t N_INTERESTS = CS_CAPACITY / N_CHILDREN;
+  constexpr size_t N_CHILDREN = 10;
+  constexpr size_t N_INTERESTS = CS_CAPACITY / N_CHILDREN;
+  constexpr size_t REPEAT = 4;
+
   std::vector<shared_ptr<Interest>> interestWorkload = makeInterestWorkload(N_INTERESTS);
   for (auto&& interest : interestWorkload) {
     interest->setChildSelector(1);
@@ -205,8 +219,6 @@
   }
   BOOST_REQUIRE(cs.size() == N_INTERESTS * N_CHILDREN);
 
-  const size_t REPEAT = 4;
-
   time::microseconds d = timedRun([&] {
     for (size_t j = 0; j < REPEAT; ++j) {
       for (const auto& interest : interestWorkload) {