Что замедляет эту функцию сортировки сегментов?

Функция определяется как

void bucketsort(Array& A){
  size_t numBuckets=A.size();
  iarray<List> buckets(numBuckets);

  //put in buckets
  for(size_t i=0;i!=A.size();i++){
    buckets[int(numBuckets*A[i])].push_back(A[i]);
  }

  ////get back from buckets
  //for(size_t i=0,head=0;i!=numBuckets;i++){
  //size_t bucket_size=buckets[i].size();
  //for(size_t j=0;j!=bucket_size;j++){
  //  A[head+j] = buckets[i].front();
  //  buckets[i].pop_front();
  //}
  //head += bucket_size;
  //}
 for(size_t i=0,head=0;i!=numBuckets;i++){
   while(!buckets[i].empty()){
     A[head]          = buckets[i].back();
     buckets[i].pop_back();
     head++;
   }
 }

  //inseration sort
  insertionsort(A);
}

, где List - это просто list в STL.

Содержимое массива генерируется случайным образом в [0 , 1) . Теоретически сегментная сортировка должна быть быстрее быстрой сортировки для большого размера для O (n), но это не удается, как показано на следующем графике.

Я использую google-perftools , чтобы профилировать его на массиве 10000000 double. Он сообщает следующее

Кажется, мне не следует использовать список STL, но мне интересно, почему? Что делает std_List_node_base_M_hook ? Должен ли я писать класс списков сам?

PS: Эксперимент и улучшение
, которое я пробовал, просто оставили коды для размещения в сегментах, и это объясняет, что большая часть времени уходит на создание сегментов.

Содержимое массива генерируется случайным образом в [0,1) . Теоретически сегментная сортировка должна быть быстрее быстрой сортировки для большого размера для O (n), но это не удается, как показано на следующем графике.

Я использую google-perftools , чтобы профилировать его на массиве 10000000 double. Он сообщает следующее

Кажется, мне не следует использовать список STL, но мне интересно, почему? Что делает std_List_node_base_M_hook ? Должен ли я писать класс списков сам?

PS: Эксперимент и улучшение
, которое я пробовал, просто оставили коды для размещения в сегментах, и это объясняет, что большая часть времени уходит на создание сегментов.

Содержимое массива генерируется случайным образом в [0,1) . Теоретически сегментная сортировка должна быть быстрее быстрой сортировки для большого размера для O (n), но это не удается, как показано на следующем графике.

Я использую google-perftools , чтобы профилировать его на массиве 10000000 double. Он сообщает следующее

Кажется, мне не следует использовать список STL, но мне интересно, почему? Что делает std_List_node_base_M_hook ? Должен ли я писать класс списков сам?

PS: Эксперимент и улучшение
, которое я пробовал, просто оставили коды для размещения в сегментах, и это объясняет, что большая часть времени уходит на создание сегментов.

Я использую google-perftools , чтобы профилировать его в двойном массиве 10000000. Он сообщает следующее

Кажется, мне не следует использовать список STL, но мне интересно, почему? Что делает std_List_node_base_M_hook ? Должен ли я писать класс списков сам?

PS: Эксперимент и улучшение
, которое я пробовал, просто оставили коды для размещения в сегментах, и это объясняет, что большая часть времени уходит на создание сегментов.

Я использую google-perftools , чтобы профилировать его в двойном массиве 10000000. Он сообщает следующее

Кажется, мне не следует использовать список STL, но мне интересно, почему? Что делает std_List_node_base_M_hook ? Должен ли я писать класс списков сам?

PS: Эксперимент и улучшение
, которое я пробовал, просто оставили коды для размещения в сегментах, и это объясняет, что большая часть времени уходит на создание сегментов.
Сделано следующее улучшение: - Используйте вектор STL как сегменты и зарезервируйте разумное пространство для сегментов - Используйте два вспомогательных массива для хранения информации, используемой при построении сегментов, что позволяет избежать использования связанного списка, как в следующем коде

void bucketsort2(Array& A){
  size_t    numBuckets = ceil(A.size()/1000);
  Array B(A.size());
  IndexArray    head(numBuckets+1,0),offset(numBuckets,0);//extra end of head is used to avoid checking of i == A.size()-1

  for(size_t i=0;i!=A.size();i++){
    head[int(numBuckets*A[i])+1]++;//Note the +1
  }
  for(size_t i=2;i<numBuckets;i++){//head[1] is right already
    head[i] += head[i-1];
  }

  for(size_t i=0;i<A.size();i++){
    size_t  bucket_num         = int(numBuckets*A[i]);
    B[head[bucket_num]+offset[bucket_num]] = A[i];
    offset[bucket_num]++;
  }
  A.swap(B);

  //insertionsort(A);
  for(size_t i=0;i<numBuckets;i++)
    quicksort_range(A,head[i],head[i]+offset[i]);
}

Результат на следующем графике где строка начинается со списка с использованием списка в качестве сегментов, начинается с вектора с использованием вектора в качестве сегментов, начинается с 2 с использованием вспомогательных массивов. По умолчанию используется сортировка вставкой по умолчанию, а некоторые используют быструю сортировку, поскольку размер сегмента большой.
Обратите внимание: «список» и «список, только вставка», «вектор, резерв 8» и «вектор, резерв 2» почти перекрываются.
Я попробую небольшой размер с достаточным объемом зарезервированной памяти.