Является ли qsort потокобезопасным?

StackOverflow https://stackoverflow.com/questions/2424505

  •  19-09-2019
  •  | 
  •  

Вопрос

У меня есть какой-то старый код, который использует qsort как отсортировать MFC CArray из конструкций, но я вижу случайные сбои, которые мочь сводиться к вызову нескольких потоков qsort в одно и то же время.Код, который я использую, выглядит примерно так:

struct Foo
{
  CString str;
  time_t t;

  Foo(LPCTSTR lpsz, time_t ti) : str(lpsz), t(ti)
  {
  }
};

class Sorter()
{
public:
    static void DoSort();
    static int __cdecl SortProc(const void* elem1, const void* elem2);
};

...

void Sorter::DoSort()
{
  CArray<Foo*, Foo*> data;
  for (int i = 0; i < 100; i++)
  {
    Foo* foo = new Foo("some string", 12345678);
    data.Add(foo);
  }

  qsort(data.GetData(), data.GetCount(), sizeof(Foo*), SortProc);
  ...
}

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = (Foo*)elem1;
  Foo* foo2 = (Foo*)elem2;
  // 0xC0000005: Access violation reading location blah here
  return (int)(foo1->t - foo2->t);
}

...

Sorter::DoSort();

Я собираюсь провести рефакторинг этого ужасного кода для использования std::sort вместо этого, но задался вопросом, действительно ли вышесказанное небезопасно?

Редактировать: Sorter::DoSort на самом деле это статическая функция, но сама по себе не использует статических переменных.

РЕДАКТИРОВАТЬ 2:Функция SortProc была изменена, чтобы соответствовать реальному коду.

Это было полезно?

Решение

Ваша проблема не обязательно имеет какое -либо отношение к потоке Saftey.

Функция обратного вызова сортировки принимает указатели на каждый элемент, а не на сам элемент. Поскольку вы сортируете Foo* Что вы на самом деле хотите сделать, так это получить доступ к параметрам как Foo**, как это:

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = *(Foo**)elem1;
  Foo* foo2 = *(Foo**)elem2;
  if(foo1->t < foo2->t) return -1;
  else if (foo1->t > foo2->t) return 1;
  else return 0;
}

Другие советы

Ваш SortProc не возвращает правильные результаты, и это, вероятно, приводит к повреждению памяти чем -то, предполагая, что данные, в общем, отсортированы после того, как вы ее сортируете. Вы можете даже привести QSORT в коррупцию, поскольку она пытается сортировать, но это, конечно, зависит от реализации.

Функция сравнения для QSORT должна вернуть отрицательный, если первый объект меньше, чем второй, нулевой, если они равны и положительны в противном случае. Ваш текущий код возвращает только 0 или 1, и возвращает 1, когда вам следует возвращать отрицательный.

int __cdecl Sorter::SortProc(const void* ap, const void* bp) {
  Foo const& a = *(Foo const*)ap;
  Foo const& b = *(Foo const*)bp;
  if (a.t == b.t) return 0;
  return (a.t < b.t) ? -1 : 1;
}

C ++ на самом деле не дает никаких гарантий о безопасности ниток. Больше всего вы можете сказать, что либо несколько читателей, либо единого автора в структуре данных будут в порядке. Любая комбинация читателей и писателей, и вам нужно как -то сериализировать доступ.

Поскольку вы отметили свой вопрос MFC Тег, я полагаю, вы должны выбрать многопоточную библиотеку времени выполнения в настройках проекта.

Прямо сейчас ваш код безопасен для потока, но бесполезен, так как Dosort-Method использует только локальные переменные и даже ничего не возвращает. Если данные, которые вы сортируете, являются членом сортировщика, то небезопасно вызывать функцию из нескольких потоков. В Геренале читать о Повторная достопримечательность, это может дать вам представление о том, на что вам нужно искать.

Что делает его безопасным потоком, так это то, является ли ваш объект безопасным потоком, например, для того, чтобы сделать QSORT-поток безопасным, вы должны убедиться, что все, что записывает или читается в или обратно, и к объекту безопасно.

На странице Pthreads Man перечислены стандартные функции, которые не обязаны быть безопасными. QSORT не среди них, поэтому он должен быть защитой. в Posix.

http://www.kernel.org/doc/man-pages/online/pages/man7/pthreads.7.html

Я не могу найти эквивалентный список для Windows, так что это не на самом деле ответ на ваш вопрос. Я был бы немного удивлен, если бы все было иначе.

Имейте в виду, что «безопасно-безопасное» означает в этом контексте. Это означает, что вы можете вызывать одну и ту же функцию одновременно на разных массивах - это не означает, что одновременный доступ к одним и тем же данным через QSORT безопасен (это не так).

В качестве предупреждения вы можете обнаружить std::sort это не так быстро, как qsort.Если вы все-таки найдете это, попробуйте std::stable_sort.

Однажды я написал компрессор BWT на основе кода, представленного моим Марком Нельсоном в книге " Доктор Доббс", и когда я превратил его в классы, я обнаружил, что это обычное дело. sort было намного медленнее. stable_sort исправлены проблемы со скоростью.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top