¿Es seguro QSORT el hilo?

Question

Tengo un código antiguo que usa qsort Para ordenar un MFC CArray de estructuras pero estoy viendo el choque ocasional que mayo Reduzca a múltiples hilos llamando qsort al mismo tiempo. El código que estoy usando se parece a esto:

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

Estoy a punto de refactorizar este horrible código para usar std::sort En cambio, pero se preguntó si lo anterior es realmente inseguro.

EDITAR: Sorter::DoSort es en realidad una función estática pero no usa variables estáticas en sí.

Edit2: la función Sortproc se ha cambiado para que coincida con el código real.

Answer 1

Su problema no necesariamente tiene nada que ver con Thread Saftey.

La función de devolución de llamada de clasificación toma punteros a cada elemento, no al elemento en sí. Dado que estas clasificando Foo* Lo que realmente quieres hacer es acceder a los parámetros como Foo**, como esto:

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

Su sortproc no está devolviendo los resultados correctos, y esto probablemente conduce a la corrupción de la memoria por algo que supone que los datos están, bueno, ordenados después de que termine de clasificarlo. Incluso podría estar llevando a Qsort a la corrupción, ya que intenta clasificar, pero eso, por supuesto, varía según la implementación.

La función de comparación para QSORT debe devolver negativo si el primer objeto es menor que el segundo, cero si son iguales y positivos de lo contrario. Su código actual solo devuelve 0 o 1, y devuelve 1 cuando debe devolver negativo.

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 ++ realmente no hace ninguna garantía sobre la seguridad de los hilos. Lo máximo que puede decir es que varios lectores o un solo escritor en una estructura de datos estarán bien. Cualquier combinación de lectores y escritores, y necesitas serializar el acceso de alguna manera.

Answer 4

Desde que etiquetaste tu pregunta con MFC Etiqueta Supongo que debe seleccionar la biblioteca de tiempo de ejecución múltiple en la configuración del proyecto.

Answer 5

En este momento, su código es seguro de hilo, pero inútil, ya que el método de dosort solo usa variables locales, y ni siquiera devuelve nada. Si los datos que está clasificando son un miembro del clasificador, entonces no es seguro llamar a la función desde múltiples subprocesos. En Gerenal, lea sobre reentrado, esto puede darle una idea de lo que necesita tener en cuenta.

Answer 6

Lo que hace que el subproceso sea seguro es, ya sea que su objeto sea seguro, por ejemplo, para hacer que QSORT sea seguro de hilo, debe asegurarse de que cualquier cosa que escriba o lea hacia o desde y hacia el objeto sea seguro de los subprocesos.

Answer 7

La página del hombre PTHREADS enumera las funciones estándar que no se requiere que sean seguras de hilo. Qsort no está entre ellos, por lo que se requiere que sea seguro en Posix.

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

Sin embargo, no puedo encontrar la lista equivalente para Windows, por lo que esta no es realmente una respuesta a su pregunta. Me sorprendería un poco si fuera diferente.

Sin embargo, tenga en cuenta lo que significa "seguro de hilo" en este contexto. Significa que puede llamar a la misma función simultáneamente en diferentes matrices: no significa que el acceso concurrente a los mismos datos a través de QSORT sea seguro (no lo es).

Answer 8

Como una advertencia, puede encontrar std::sort no es tan rápido como qsort. Si lo encuentras, intente std::stable_sort.

Una vez escribí un compresor BWT basado en el código que presenta mi Mark Nelson en el Dr. Dobbs y cuando lo convertí en clases encontré que Regular sort fue mucho más lento. stable_sort Se solucionó los problemas de velocidad.