DBX4 – Resultados Parciais de Otimização com Paralelismo

Hoje em dia é super comum e barato comprar computadores com dois/quatro núcleos. Cada dia que passa estão mais acessíveis. Mas as aplicações desenvolvidas para estes processadores continuam sendo feitas sequencialmente (“mono-thread”).

Já olhou o Gerenciador de Tarefas e viu sua aplicação patinando nos 50% em uma máquina com dois núcleos? Isso só muda quando duas aplicações estão usando processador ao mesmo tempo, ou ainda, quando uma aplicação possui várias threads simultâneas para resolver um algoritmo.

Pensando nisso, a um bom tempo venho trabalhando em algumas idéias de otimização no driver DBX4. Apesar de o Delphi 2010 agora já vir com driver para Firebird, pretendo colocar esta otimização também nos demais drivers que fiz e disponibilizar para meus clientes de Postgres e Oracle.

A primeira idéia consiste em ter um buffer circular, mais ou menos uma espécie de pipelining. Uma thread busca os dados do banco e a outra repassa estes dados para o framework DBX. Desta forma, enquanto o framework DBX aloca memória e copia os valores dos campos, o driver vai requisitando a frente os dados do banco de dados.

A segunda idéia é um cache de statements. O Firebird ainda não tem um cache de statements preparados como os demais bancos (Oracle por exemplo). E o framework DBX não aproveita os statements criados. A cada registro de inserção/update, um novo statement é preparado e executado.

Os resultados parciais desta segunda idéia são animadores. Veja só o gráfico que compara o driver para Firebird e o TBODBXFB. No eixo y está o tempo em milisegundos e no eixo x a quantidade de registros inseridos em cada teste.

Gráfico Comparativo driver FIREBIRD X TBODBXFB

O teste consiste em inserir 1000, 5000, 10000, 50000 e 100000 registros numa tabela do banco. Para isolar qualquer interferência entre um e outro driver, o banco é criado no momento do início de cada teste. Também é utilizado o servidor classic do Firebird, para evitar qualquer tipo de cache entre as conexões. Os testes foram executados em uma máquina local. Firebird e Aplicação juntos.

Os tempos em milisegundos estão na tabela abaixo:

Registros inseridos TBODBXFB FIREBIRD D2010
1000 1279 2028
5000 6586 11158
10000 12212 20068
50000 64095 102144
100000 127065 202174

Caso deseje fazer um teste, o instalador do driver está no link abaixo. Por enquanto só pode ser instalado no Delphi 2010:

Driver TboDbxFb para Delphi 2010

Em breve darei mais detalhes e o código do teste. Também efetuarei testes com o banco em outro computador, já que este é o ambiente mais comum de utilização. Também exibirei outros testes a respeito do pipeline de registros em um artigo. Aguarde!

Hadoop, Núvens, Banco de Dados distribuído, Delphi é útil neste ambiente?

Serviços nas nuvens estão na moda. Todo dia chega alguma mensagem na minha caixa a respeito. Talvez porque o tema de minha dissertação esbarra no assunto, mas acredito que não.

Então veio a pergunta hoje, depois de receber um anúncio a respeito do HadoopDb. Alguma pessoa que programa em Delphi trabalha com um projeto que precisa escalar ao ponto de rodar a aplicação em um cluster de 50, 100 nós?

Ou estes “monstros” são pilotados sempre com Java/C++?

Seria por conta de não ter como acessar diretamente no Delphi, já que não fazem binding para Delphi? Mas e aí, serviços na nuvem vieram para ficar, na minha opnião. Se houvesse um driver DBX, por exemplo, que mapeasse a API para chamar este tipo de serviço, alguém em Delphi usaria?

Enfim, muitas questões. Será que Delphi cabe neste mundo?

FieldByName é O(n), que tal melhorá-lo para O(Lg n)?

Há muitas formas de acessar os campos dos DataSets no Delphi, conforme a relação a seguir (observe a relação linha x item enumerado):

DataSet.Fields[0].AsString
cdsClienteNOMECLIENTE.AsString
DataSet.FieldByName(''NOMECLIENTE'').AsString
DataSet[''NOMECLIENTE'']
  1. Pelo índice do campo: É uma causa frequente de erros, afinal, mudando a ordem dos campos (na SQL ou no DataSet) altera totalmente o comportamento do código.
  2. Diretamente pelo objeto que representa o campo: Evita os erros da primeira e ainda garante que você acesse somente campos que existem no dataset, avisando durante a compilação caso contrário. Só pode ser usada quando os campos são adicionados em tempo de projeto. Quando se trabalha com multi-bancos existem problemas de mapeamento de tipos de campos e classes de representação.
  3. Por FieldByName: Evita os problemas da primeira abordagem. Mas não há aviso a respeito de campos não existentes no dataset em tempo de compilação.
  4. Pegando o valor diretamente: Usa FieldByName internamente.
  5. Alguma outra?

Para o objetivo deste artigo, irei considerar o uso de FieldByName (3).

Não uso FieldByName, portanto vou parar de ler o artigo!

Calma! Há um detalhe que passa despercebido. Mesmo você não usando, a própria VCL e componentes de terceiros estão cheios de chamadas a este método! Por exemplo, um simples TDBEdit chama este método. O DBGrid, o seu gerador de relatórios e muitos outros.

Hummm, mesmo atribuindo o DataField em tempo de projeto ao TDBEdit?

Sim! A propriedade DataField é uma string. Para fazer o primeiro vínculo é chamado o método FieldByName. Observe este trecho de código, retirado da unit DBCtrls.pas:

procedure TFieldDataLink.UpdateField;
begin
  if Active and (FFieldName <> '''') then
  begin
    FField := nil;
    if Assigned(FControl) then
      SetField(GetFieldProperty(DataSource.DataSet, FControl, FFieldName)) else
      SetField(DataSource.DataSet.FieldByName(FFieldName));
  end else
    SetField(nil);
end;

Abra a unit DBGrids.pas e procure por FieldByName. Você irá encontrar referência em muitas linhas.

Chegamos então a questão do título. O algoritmo que procura um campo no dataset é linear em relação a quantidade de campos, ou seja, sua complexidade é:

  • Ω(1). No melhor caso, o campo procurado é o primeiro da lista.
  • Θ(n/2). No caso médio, você encontra o campo mais ou menos na metade e para.
  • O(n). No pior caso, o campo procurado é o último. O nome do campo foi comparado com todos os outros.

Veja o algorítmo, retirado da unit DB.pas. Note que o TDataSet.FieldByName chama TFields.FindField:

function TFields.FindField(const FieldName: string): TField;
var
  I: Integer;
begin
  for I := 0 to FList.Count - 1 do
  begin
    Result := FList.Items[I];
    if WideCompareText(Result.FFieldName, FieldName) = 0 then Exit;
  end;
  Result := nil;
end;

Repare a simplicidade. Na linha 5 é realizado um for na lista de campos (FList). Atribui o i-ésimo item à variável de retorno Result na linha 7. Na linha 8, caso o FFieldName seja igual ao campo procurado o algoritmo é interrompido. Se o campo procurado for o último da lista, o for será executado completamente.

Isso é conhecido como o algoritmo do pintor burro. Suponha que você contrate um pintor para pintar aquelas linhas do meio da rodovia. Mas o pintor não move a lata de tinta. Então todas as vezes ele molha o pincel, pinta a rodovia e volta para molhar o pincel novamente. No começo é rápido, mas quanto mais ele se distancia da lata de tinta, mais demorado fica. (Veja mais sobre isso neste ótimo post no Blog do Joel)

Puxa, isso é muito ruim. Como melhorar isso?

De fato existem alguns algoritmos melhores para fazer isso. Pode-se implementar um hash que distribua os nomes dos campos de acordo com os índices. Mas isso parece um pouco complicado. Além do mais, não existe este tipo de estrutura pronta no Delphi, e então seria necessário incluir uma outra dependência no DB.pas.

Outra forma de melhorar é usar uma lista ordenada. Sabe-se que procurar um item numa lista ordenada é O(lg n). Inclusive, este algoritmo é implementado no tão conhecido TStringList. Só é necessário ordenar ele, com a propriedade sorted := true.

Ótimo então, vamos alterar o arquivo DB.pas e incluir uma lista ordenada!

Realizar uma alteração em um arquivo da VCL é mais complicado que só alterar o código. O ideal seria:

  1. Adicionar uma variável privada na classe TFields do tipo TStringList.
  2. Ao adicionar os Fields no dataset, adicioná-lo também nesta outra lista ordenada.
  3. Ao procurar por um campo, utilizar a lista ordenada.

Porém, alterar a definição de um objeto implica em recompilar todas as units dependentes. Isso inclui tudo que usa TDataSet, inclusive partes da própria VCL. Já recebeu à famosa mensagem Unit x was compiled with a different version of y?

Como é melhor causar o menor impacto possível, a saída é declarar uma variável global na unit DB.pas. Porém, sendo global, não temos uma instância própria para cada instância de dataset. Isso implica em termos uma lista de datasets antes. Cada item desta lista tem uma outra lista com os campos, ou seja, uma lista de listas. (Uma lista de datasets onde cada item é uma outra lista de campos)

Desta forma, realizar a alteração é feito na seguinte ordem:

  1. Declarar uma variável global do tipo TStringList. Iniciar na seção initialization e destruir na finalization;
  2. Alterar o método FindField da classe TDataSet. (O melhor seria FindField de TFields, mas o código não ficaria tão simples, já que precisaria preocupar com a leitura de campos do dfm)
  3. Na primeira chamada de FieldByName, construir a lista ordenada de campos
  4. Destruir a lista ao fechar o dataset

“Há, mas qual é o overhead introduzido com estas alterações?”

Bom, não tem como não ter nenhum. Então o overhead introduzido com esta alteração é o seguinte:

  • Uma lista é instanciada no início da aplicação. Esta lista será preenchida com dataset”s que invocaram o método FieldByName pelo menos uma vez. O dataset é removido da lista quando for fechado. Isso só é preocupante quando se tem muitos dataset”s ativos na aplicação. Deixá-los abertos também é uma má prática, ok?
  • Uma outra lista é instanciada para cada dataset, e contém os campos do mesmo, de forma ordenada. É executado o algoritmo quicksort Θ(lg n) para ordenar a lista. Isto é feito uma vez a cada abertura do dataset.
  • O quicksort tem pior caso O(n²), quando os itens já estão ordenados. Mas em geral isso raramente irá acontecer, certo?

Não seria melhor remover o dataset da lista somente no evento Destroy do TDataSet?

Seria. Mas há o caso de dataset”s temporários, onde os campos são criados em tempo de execução. E se o desenvolvedor fechar o dataset e modificar os campos?

Para ser mais breve, vou anexar um diff do arquivo DB.pas no final. Por hora, uma análise da alteração no método TDataSet.FindField:

function TDataSet.FindField(const FieldName: string): TField;
var
  List: TStringList;
  i, di: Integer;
begin
  di := DataSetsListOrderFields.IndexOf(GetObjectUniqueName(Self));
  if di < 0 then
  begin
    List := TStringList.Create;
    List.Capacity := FFields.Count;
    for i := 0 to FFields.Count - 1 do
      List.AddObject(FFields[i].FieldName, Fields[i]);
    List.Sorted := True;
    DataSetsListOrderFields.AddObject(GetObjectUniqueName(Self), List);
  end
  else
    List := TStringList(DataSetsListOrderFields.Objects[di]);

  Result := nil;
  if List.Find(FieldName, i) then
    Result := TField(List.Objects[i]);
  if (Result = nil) and ObjectView then
    Result := FieldList.Find(FieldName);
  if Result = nil then
    Result := FAggFields.FindField(FieldName);
end;

Seja m a quantidade de dataset”s abertos e n a quantidade de campos:

  • Ao iniciar o método (linha 6), procuramos pelo dataset na lista. Essa operação leva O(lg m), já que esta lista também é ordenada.
  • Se ele não é encontrado (primeira chamada a FieldByName), o dataset é então adicionado a lista (linhas 9 a 14). Esta operação leva O(n + lg m). O lg m é para buscar a posição onde inserir o dataset.
  • Na linha 20 o campo é então procurado, isso leva O(lg n).

Resumindo, a complexidade total na primeira chamada seria O(2 lg m + lg n) e nas demais O(lg m + lg n). Poderia remover o O(lg m) se fosse declarado uma nova variável a classe TDataSet. Mas esta complexidade já garantirá um bom desempenho. Vamos aos testes?

Os testes executados consistem em criar um ClientDataset com cem (100) campos inteiros, preenchê-lo com 10, 20 e 30 mil registros usando FieldByName e consultar os valores do melhor caso (1º campo), caso médio (50º campo) e pior caso (último campo). Veja a figura com os resultados:

Comparação de FieldByName O(n) e O(lg n)
Tempos da comparação de FieldByName O(n) e O(lg n)

Os testes foram executados em uma máquina virtual VMWare com Windows XP e Delphi 2009. O aplicativo foi executado fora do Delphi, para não haver interferência do debugger. Talvez os tempos mudem em uma máquina real, mas acredito que a proporção entre eles se mantenha. Segue uma breve discussão dos resultados:

  • Append: Na adição de registros todos os campos são chamados uma vez para cada registro. O novo método FieldByName mostra-se até 73% mais rápido que o antigo (de 9,78 para 2,59 segundos).
  • No melhor caso: Como era esperado, o novo método é alguns centésimos de segundos (0,14 para 0,17) pior. Isso ocorre porque o novo algoritmo é Ω (lg n), ao contrário do antigo, que é Ω (1).
  • No caso médio: O novo FieldByName chega a ser 63% mais rápido que o antigo.
  • No pior caso: O novo FieldByName é até 80% mais rápido.
  • Constante: Observe também que tempo entre o melhor, médio e pior caso se mantém constante entre os registros, mostrando que sua complexidade é sempre lg n (na tabela, destacado em laranja).

Aqui está o arquivo diff com as modificações no arquivo DB.pas e o código dos testes. Elas foram feitas para o Delphi 2009. Aplicarei elas ao Delphi 2006 e 2007. Caso haja alguma diferença, postarei as outras versões.

Para você que resistiu firme até aqui, se tiver algum comentário ou observação, sinta-se a vontade!