Geek Answers Handbook

Why is there a longer process than merging into two sorted std :: list?

I am very amazed at the result that it takes more time to go through than merging into two sorted ones by std::listabout 12%. Since merging can be viewed and implemented as continuous comparisons of elements, list the splices and iterators through two separate sorted linked lists. Therefore, moving should not be slower than merging between them, especially when the two lists are large enough, because the ratio of repeating elements increases.

However, the result does not seem to 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 , 2. sum += num; sum.

perf: ( perf)

1:

       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

2:

       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

- . , CPU . , 2 , 1, . ?

+6
1

, , .

, .

:

, , , . , . , , , .

, .

, , . , - .

/ . , .

, , , , .

, ,

24,254,303,068      cycle-activity.stalls-ldm-pending

- :

25,141,751,107      cycle-activity.stalls-ldm-pending

, , 10% - , .

+3

More articles:


All Articles