O thread qsort é seguro?

Question

Eu tenho um código antigo que usa qsort para classificar um MFC CArray de estruturas, mas estou vendo a queda ocasional que poderia estar com vários threads chamando qsort ao mesmo tempo.O código que estou usando é mais ou menos assim:

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

Estou prestes a refatorar esse código horrível para usar std::sort em vez disso, mas imaginou se o que foi dito acima é realmente inseguro?

EDITAR: Sorter::DoSort é na verdade uma função estática, mas não usa variáveis ​​estáticas.

EDITAR2:A função SortProc foi alterada para corresponder ao código real.

Answer 1

Seu problema não tem necessariamente nada a ver com segurança de thread.

A função de retorno de chamada de classificação recebe ponteiros para cada item, não para o item em si.Já que você está classificando Foo* o que você realmente quer fazer é acessar os parâmetros como Foo**, assim:

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

Seu SortProc não está retornando resultados corretos, e isso provavelmente leva à corrupção da memória, assumindo que os dados estão, bem, classificados depois que você terminar de classificá-los.Você pode até estar levando o qsort à corrupção enquanto tenta classificá-lo, mas isso varia de acordo com a implementação.

A função de comparação para qsort deve retornar negativo se o primeiro objeto for menor que o segundo, zero se forem iguais e positivo caso contrário.Seu código atual retorna apenas 0 ou 1 e retorna 1 quando você deveria retornar 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 não oferece nenhuma garantia sobre a segurança do thread.O máximo que você pode dizer é que vários leitores OU um único gravador em uma estrutura de dados serão adequados.Qualquer combinação de leitores e escritores, e você precisa serializar o acesso de alguma forma.

Answer 4

Já que você marcou sua pergunta com MFC tag Suponho que você deva selecionar Biblioteca de tempo de execução multithread nas configurações do projeto.

Answer 5

No momento, seu código é thread-safe, mas inútil, já que o método DoSort usa apenas variáveis ​​locais e nem retorna nada.Se os dados que você está classificando forem membros do Sorter, não será seguro chamar a função de vários threads.Em geral, leia em reentrada, isso pode lhe dar uma ideia do que você precisa observar.

Answer 6

o que o torna thread-safe é se o seu objeto é thread-safe, por exemplo, para tornar o qsort thread-safe, você deve garantir que qualquer coisa que grave ou leia de ou para o objeto seja thread-safe.

Answer 7

A página man pthreads lista as funções padrão que não são necessárias para serem thread-safe.qsort não está entre eles, então é necessário ser seguro para threads em POSIX.

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

Não consigo encontrar a lista equivalente para Windows, portanto, esta não é realmente uma resposta à sua pergunta.Eu ficaria um pouco surpreso se fosse diferente.

Esteja ciente do que "thread-safe" significa neste contexto.Isso significa que você pode chamar a mesma função simultaneamente em arrays diferentes - isso não significa que o acesso simultâneo aos mesmos dados via qsort seja seguro (não é).

Answer 8

Como uma palavra de advertência, você pode encontrar std::sort não é tão rápido quanto qsort.Se você achar isso, tente std::stable_sort.

Certa vez, escrevi um compressor BWT baseado no código apresentado por Mark Nelson no Dr. Dobbs e quando o transformei em aulas descobri que regular sort foi muito mais lento. stable_sort corrigiu os problemas de velocidade.