Безопасен ли поток qsort?

Question

У меня есть какой-то старый код, который использует 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, но мне стало интересно, действительно ли вышесказанное небезопасно?

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

EDIT2: функция SortProc была изменена для соответствия реальному коду.

Answer 1

Ваша проблема не обязательно связана с безопасностью потоков.

Функция обратного вызова sort принимает указатели на каждый элемент, а не на сам элемент. Поскольку вы сортируете 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;
}

Answer 2

Ваш 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;
}

Answer 3

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

Answer 4

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

Answer 5

На странице руководства pthreads перечислены стандартные функции, которые не обязательно должны быть поточно-ориентированными. qsort не входит в их число, поэтому он должен быть потокобезопасным в POSIX .

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

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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