Why is traversing more time-consuming than merging on two sorted std::list?

Viewed 215

I am pretty amazed on the result that traversing takes more time than merging on two sorted std::list by around 12%. Since merging can be considered and implemented as continuous element comparisons, list splice and iterators traversal through two separated sorted linked lists. Hence, traversing should not be slower than merging through them especially when two lists are large enough because the ratio of iterated elements is getting increased.

However, the result seems to not match what I thought, and this is how I test my ideas above:

std::list<int> list1, list2;

for (int cnt = 0; cnt < 1 << 22; cnt++)
    list1.push_back(rand());
for (int cnt = 0; cnt < 1 << 23; cnt++)
    list2.push_back(rand());

list1.sort();
list2.sort();

auto start = std::chrono::system_clock::now();  // C++ wall clock

// Choose either one option below
list1.merge(list2);         // Option 1
for (auto num : list1);     // Option 2
for (auto num : list2);     // Option 2

std::chrono::duration<double> diff = std::chrono::system_clock::now() - start;
std::cout << std::setprecision(9) << "\n       "
          << diff.count() << " seconds (measured)" << std::endl;  // show elapsed time

PS. icc is smart enough to eliminate Option 2. Try sum += num; and print out sum.

This is the output from perf: (the measured time remains the same without using perf)

Option 1: Merge

       0.904575206 seconds (measured)

 Performance counter stats for './option-1-merge':

    33,395,981,671      cpu-cycles
       149,371,004      cache-misses              #   49.807 % of all cacherefs
       299,898,436      cache-references
    24,254,303,068      cycle-activity.stalls-ldm-pending    

       7.678166480 seconds time elapsed

Option 2: Traverse

       1.01401903 seconds (measured)

 Performance counter stats for './option-2-traverse':

    33,844,645,296      cpu-cycles
       138,723,898      cache-misses             #   48.714 % of all cacherefs
       284,770,796      cache-references
    25,141,751,107      cycle-activity.stalls-ldm-pending

       7.806018949 seconds time elapsed

Due to the property of horrible spatial locality on these linked lists. The cache miss is the major reason that make CPU stalls, and occupies most of the CPU resources. The strange point is that option 2 has fewer cache misses than option 1, but it has a higher amount of CPU stalls and CPU cycles to accomplish its task. What makes this abnormality happen?

1 Answers
Related