Ist der Qsort-Thread sicher?

Question

Ich habe einen alten Code, der verwendet qsort um einen MFC zu sortieren CArray von Strukturen, aber ich sehe gelegentlich Abstürze Mai liegt an mehreren Thread-Aufrufen qsort gleichzeitig.Der Code, den ich verwende, sieht ungefähr so ​​aus:

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();

Ich bin dabei, diesen schrecklichen Code für die Verwendung umzugestalten std::sort Stattdessen habe ich mich gefragt, ob das oben Genannte tatsächlich unsicher ist?

BEARBEITEN: Sorter::DoSort ist eigentlich eine statische Funktion, verwendet aber selbst keine statischen Variablen.

EDIT2:Die SortProc-Funktion wurde geändert, um sie an den echten Code anzupassen.

Answer 1

Ihr Problem hat nicht unbedingt etwas mit der Thread-Sicherheit zu tun.

Die Sortierrückruffunktion nimmt Zeiger auf jedes Element entgegen, nicht auf das Element selbst.Da Sie sortieren Foo* Was Sie eigentlich tun möchten, ist auf die Parameter zuzugreifen Foo**, so was:

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

Ihr SortProc gibt keine korrekten Ergebnisse zurück, und dies führt wahrscheinlich zu einer Speicherbeschädigung, da davon ausgegangen wird, dass die Daten, nun ja, sortiert sind, nachdem Sie mit dem Sortieren fertig sind.Es könnte sogar sein, dass qsort beim Sortieren beschädigt wird, aber das variiert natürlich je nach Implementierung.

Die Vergleichsfunktion für qsort muss negativ zurückgeben, wenn das erste Objekt kleiner als das zweite ist, null, wenn sie gleich sind, und andernfalls positiv.Ihr aktueller Code gibt immer nur 0 oder 1 zurück und gibt 1 zurück, wenn Sie negativ zurückgeben sollten.

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

C++ gibt keine wirklichen Garantien für die Thread-Sicherheit.Man kann höchstens sagen, dass entweder mehrere Leser ODER ein einzelner Schreiber für eine Datenstruktur in Ordnung sind.Jede Kombination aus Lesern und Autoren, und Sie müssen den Zugriff irgendwie serialisieren.

Answer 4

Da Sie Ihre Frage mit markiert haben MFC Tag Ich nehme an, Sie sollten in den Projekteinstellungen die Option „Multithreaded Runtime Library“ auswählen.

Answer 5

Im Moment ist Ihr Code threadsicher, aber nutzlos, da die DoSort-Methode nur lokale Variablen verwendet und nicht einmal etwas zurückgibt.Wenn die von Ihnen sortierten Daten ein Mitglied von Sorter sind, ist es nicht sicher, die Funktion von mehreren Threads aus aufzurufen.Lesen Sie im Allgemeinen weiter Wiedereintritt, das gibt Ihnen vielleicht eine Vorstellung davon, worauf Sie achten müssen.

Answer 6

Was es threadsicher macht, ist, ob Ihr Objekt threadsicher ist. Um beispielsweise qsort threadsicher zu machen, müssen Sie sicherstellen, dass alles, was in das Objekt schreibt oder liest oder von diesem Objekt liest, threadsicher ist.

Answer 7

Die pthreads-Manpage listet die Standardfunktionen auf, die nicht Thread-sicher sein müssen.qsort gehört nicht dazu und muss daher threadsicher sein in POSIX.

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

Ich kann die entsprechende Liste für Windows jedoch nicht finden, daher ist dies keine wirkliche Antwort auf Ihre Frage.Es würde mich ein wenig wundern, wenn es anders wäre.

Beachten Sie jedoch, was „threadsicher“ in diesem Zusammenhang bedeutet.Dies bedeutet, dass Sie dieselbe Funktion gleichzeitig auf verschiedenen Arrays aufrufen können. Dies bedeutet jedoch nicht, dass der gleichzeitige Zugriff auf dieselben Daten über qsort sicher ist (das ist nicht der Fall).

Answer 8

Als Warnung finden Sie vielleicht std::sort ist nicht so schnell wie qsort.Wenn Sie das finden, versuchen Sie es std::stable_sort.

Ich habe einmal einen BWT-Kompressor geschrieben, der auf dem von Mark Nelson in Dr. Dobbs vorgestellten Code basierte, und als ich ihn in Klassen umwandelte, fand ich ihn normal sort war viel langsamer. stable_sort die Geschwindigkeitsprobleme behoben.