[SP-pm] ordenando arquivos.

[Eden Cardim]

>>>>> "Thiago" == Thiago Yukio Kikuchi Oliveira <stratust em gmail.com> writes:

    Thiago> Então qual a vantagem de usar o módulo ao invés do gnu sort
    Thiago> padrão do linux para uma simples ordenação de arquivo texto?
    Thiago> Em teoria, ambos são implementados em C.

A diferença é que sendo uma biblioteca você pode passar os dados por
referência, que é muito mais rápido do que fazer IPC.

    Thiago> Se ele for multi-thread ai pode ser que seja
    Thiago> interessante. Vou dar uma olhada.

Para tudo, esse problema em particular não envolve processamento, o
problema aqui vai ser de I/O já que não tem memória suficiente pra
carregar tudo e processar. Não adianta nada ser multi-thread se você não
pode carregar o conjunto inteiro de dados na memória, pode ser em C,
assembly, o diabo que for, a depender de quanta memória tiver, o gargalo
vai ser na hora de ler e escrever os dados do disco. Por exemplo, numa
análise rápida (e sonolenta) e supondo barramento SATA2, você consegue
throughputs de cerca de 2.4 Gbit/s. Como precisa ler e escrever cada
bloco de dados que você está ordenando, se estiver usando o mesmo
dispositivo, esse throughput cai pra 1.2 Gbit/s por bloco. Uma cpu como
o i5, que tem 64 bits e clock de 2.3 Ghz, consegue, a grosso modo,
processar no máximo 64 * 2.3 bit/s [1][2][3], que é equivalente a um
throughput máximo de 147.2 Gbit/s. Como os melhores algoritmos de
ordenação são de complexidade O(n logn), isso vai dar um throughput
efetivo de 147.2n/n logn, que pro caso de n = 1.2 Gbit (o máximo de
dados que chegam na cpu em 1 segundo) dá, a grosso modo, 4.9 Gbit/s, que
é muito mais throughput de processamento do que de I/O, então não
adianta nada otimizar o algoritmo em si a não ser que você consiga
melhorar o custo de cada comparação de bit por um fator de 4.9/1.2 = 4x,
que eu duvido que alguém consiga numa mera re-escrita de merge sort em C
[4]. Se você, por exemplo, acrescentar um outro dispositivo SATA2 e
escrever o algoritmo de modo a ler de um e escrever no outro, aí precisa
refazer a análise com o valor de throughput de I/O atualizado pra 2.4
Gbit/s, etc. pra ver no que vai dar. Dá pra montar uma fórmula pra
preencher os valores certinhos, desenhar os gráficos etc. pra saber o
ponto ótimo de alocação entre throughput de I/O e throughput de CPU, mas
não vou fazer isso agora porque to morrendo de sono. É possível até que
a análise esteja um pouco equivocada, mas é só pra ilustrar que o
paralelismo e a linguagem de implementação são apenas alguns poucos
fatores dentre vários pra se considerar.

--
1 - É um pouco menos por conta do overhead de carregar o próximo bloco
de dados nos registradores.

2 - A penalidade de processamento depende da implementação da cpu,
algumas tem operadores que conseguem carregar a próxima sequência de 64
bits num registrador e processar os 64 bits que já estão carregados ao
mesmo tempo. Outros levam 2 ciclos pra fazer isso, etc.

3 - Isso também depende da capacidade do compilador de gerar opcodes de
cpu capazes de minimizar a quantidade de ciclos consumida.

4 - já que o sort/cmp do Perl são opcodes implementados internamente em
C

-- 
   Eden Cardim       Need help with your Catalyst or DBIx::Class project?
  Code Monkey                    http://www.shadowcat.co.uk/catalyst/
 Shadowcat Systems Ltd.  Want a managed development or deployment platform?
http://blog.edencardim.com/            http://www.shadowcat.co.uk/servers/
http://twitter.com/#!/edenc