Tornar a substituição de parâmetros em strings separadas por novas linhas mais eficiente

Uma resposta curta para minha pergunta inicial poderia ser: "evite isso" .

Quanto a um PARAMETER SUBSTITUTIONfiltro sobre uma string separada por novas linhas como em:

_IFS="$IFS"; IFS=$'\n'
tmpArr=(${tmpVar//[? ][MTARDC?]+([^$'\n'])?($'\n')})
IFS="$_IFS"

Não consegui encontrar uma alternativa viável para o problema, mas infelizmente precisei de extensão PATTERN MATCHERS .

E agora?

Um exame detalhado e comparativo de como diferentes abordagens de filtragem funcionariam sob condições variadas — poucos ou muitos loops, com poucos ou muitos itens, em strings ou matrizes inteiras — produziu alguns resultados interessantes.

Ao usar uma máquina de alta especificação (aqui: 8 núcleos), ou não houver necessidade de se preocupar com eficiência, provavelmente não importará qual método for escolhido, ao permanecer abaixo de uma carga de 1000 elementos e 100 loops - talvez você queira parar de ler aqui.

No entanto, se você realmente (precisa) se importar com eficiência , seja devido às baixas especificações da máquina (4 núcleos/notebook/embarcado), ao consumo de energia ou aos tempos gerais de execução somados - ou em cenários de carga mais pesada, talvez você queira continuar lendo.

Os esforços para buscar uma alternativa melhor - ou até mesmo a melhor - se transformaram em uma lição valiosa sobre quando e por que evitar completamente a abordagem mencionada acima e retornaram informações sobre o que usar melhor em qual situação.

Geralmente, os desempenhos do método estão caindo linearmente ao número crescente de elementos a serem processados, ou ao número de loops iterados. Mas alguns já começam com uma penalidade, que aumenta junto com um número maior de elementos e iterações.

Alguns métodos terão um desempenho excepcionalmente bom em um conjunto limitado de casos de uso, enquanto se tornarão praticamente inutilizáveis ​​para outros cenários - especialmente, onde um grande número de conjuntos (à 10 elementos) foi envolvido. Outros tiveram um desempenho excelente, se repetidos muitas vezes com um número baixo de elementos.

Alerta de spoiler:

PARAMETER SUBSTITUTIONsobre array , com native array fetchingresultados foi a única abordagem que escalou e funcionou melhor para todos os tipos de casos de uso.

Resultados em detalhes:

1. Para 10 ou menos elementos, os resultados entre duas máquinas completamente diferentes com sistemas operacionais diferentes não seriam muito diferentes ou seriam quase exatamente iguais.

2. PARAMETER SUBSTITUTION(PSUB) não é recomendável para filtragem de elementos de substring VAR ( ${var//[? ]*}) e tem desempenho excepcionalmente ruim , especialmente com strings muito grandes.

Portanto, evite filtrar um grande número de elementos delimitados por nova linha em uma única VAR STRINGvia PSUB. Filtrar pequenos conjuntos <~50 uma vez pode ser OK, mas não faça algo assim com strings grandes e/ou loops internos:

_IFS="$IFS"; IFS=$'\n'
tmpArr=(${tmpVar//[? ][MTARDC?]+([^$'\n'])?($'\n')})
IFS="$_IFS"

Nota: EXTENDED PATTERN MATCHING like <@*+?!>(...)pode tornar um script significativamente mais lento (isso também vale para [[ $var =~ ... ]], em comparação com [[ $var == *...* ]]).

É necessário escanear toda a sequência de caracteres EXTENDED PATTERN MATCHINGaqui para corresponder e remover elementos individuais da sequência, o que torna esse tipo de filtro muito mais lento.

Então, para grandes sequências de elementos, provavelmente é melhor dividir em novas linhas primeiro e processar a matriz resultante, conforme indicado abaixo, ou fazer tudo isso dentro de um AWKscript, ou usar GREP(quando não for repetido com muita frequência), que mostrou os melhores resultados para esse tipo de caso de uso, superando todos os outros métodos, quando as cargas estão ficando muito altas (~1 milhão de sequências de elementos).

3. Quando aplicado a matrizes , por outro lado, PARAMETER SUBSTITUTIONpode ser uma das melhores opções disponíveis para quase qualquer cenário.

   Ele demonstrou eficiência superior, superando outros métodos/ferramentas dedicadas como SED, GREPe AWK, especialmente para conjuntos de elementos de pequeno a médio porte (<100.000), com até 1.000 iterações e, ainda mais obviamente, com um número ainda maior de iterações.

   Começando com 100.000 elementos e para um determinado número de 1.000 iterações, AWK e SED começaram a ganhar terreno e, especialmente, SED se tornou significativamente mais rápido com matrizes , enquanto GREP ficou para trás.

   Penalidades de invocação para ferramentas dedicadas como AWK, SED e especialmente GREP:

   Eles sofrem uma queda significativa de desempenho para conjuntos <=1000 em muitas iterações, começando em ~50-100 loops e crescendo exponencialmente a partir daí, deixando máquinas lentas em séria desvantagem.

   Portanto, use matrizes em vez de strings delimitadas por (novas linhas) sempre que possível e aplique a atribuição de matriz nativa do Bash , especialmente ao criar e trabalhar com grandes conjuntos de elementos, e considere usá-laPARAMETER SUBSTITUTION ao filtrá-los.

   Criar e filtrar uma matriz por meio de - se for usada uma CORRESPONDÊNCIA DE PADRÕES simples ePSUB/PMATCH cuidadosamente elaborada - e então armazenar o resultado novamente por meio da atribuição de matriz /native, pode ter um impacto tremendamente positivo no desempenho, em comparação a outras abordagens!IFS=$'\n'

Converter de strings delimitadas por nova linha com restrito IFS:

_IFS="$IFS"; IFS=$'\n'
array=("$elements")
IFS="$_IFS"

Ou, para coletar/excluir-filtrar de uma matriz, basta fazer (e filtrar os vazios depois):

array=("${tmpArr[@]/#[? ]*}")

Isso terá um desempenho muito melhor do que um loop de coleção dedicado e significativamente melhor do que readarray- particularmente, quando a criação do array em si é feita em loop. E pode converter de forma muito eficiente strings de elementos delimitados por nova linha existentes em arrays muito mais processáveis.

Ele deve ter um desempenho muito bom para até 1.000.000 de elementos , em comparação com qualquer outra ferramenta dedicada como AWK, SED ou GREP, ou pode até mesmo superá- los drasticamente, principalmente para um número de elementos abaixo de 10.000 , e cada vez mais, com mais iterações .

O esforço de criar novas matrizes via nativo array+=(...)é mínimo; coletar matrizes de resultados filtrados novamente e depois processá-las definitivamente supera o processamento de grandes strings concatenadas em todos os casos de uso possíveis, exceto nos menores e mais simples.

Por outro lado , criar grandes conjuntos de strings de concatenação separadas por novas linhas em um loop dedicado tem um desempenho muito ruim e pode até mesmo travar para strings muito grandes >1.000.000 de elementos , então a vantagem de desempenho que GREP ou SED podem oferecer aqui para processamento, em comparação ao uso de matrizes, é frustrada desde o início, devido aos custos de concatenação da criação de strings em geral.

4. Para pequenos conjuntos de elementos <=1000 , um loop dedicado FOR/WHILE read -r, com (simples) PATTERN MATCHING(PMATCH) por elemento também pode ser uma boa opção, que ainda deve superar as ferramentas dedicadas usuais, como AWK, SED e GREP.

Desde que a Here Documenttécnica de expansão direta de matriz/PMATCH seja usada:

_IFS="$IFS"; IFS=$'\n'
while read -r; do ...; done <<<"${tmp[@]/#[ ?]*}" 
IFS="$_IFS"

for e in ""${tmp[@]/#[ ?]*}"; do ... done

Não o streaming muito mais caro via Pipe, Sub Process' or Process Substitution` como:

for e in "$(printf '%s\n' "${tmp[@]}")"; do ... done

while read -r; do ...; done < <(printf '%s\n' "${tmp[@]}")

Mas cuidado , em máquinas lentas o desempenho pode cair muito , começando mesmo com ~50 elementos em >10 iterações. Para hardware rápido, pode ser ~1000 elementos em bem mais de 100 iterações, até que as coisas fiquem notavelmente lentas.

Porém, se o número de elementos permanecer abaixo dessas margens críticas, LOOP/PMATCHo comportamento de dimensionamento do loop externo será muito melhor do que as chamadas de programas externos, como GREP, superado apenas pela abordagem PSUB.

5. Das ferramentas dedicadas, AWKdeve apresentar o melhor desempenho, sendo significativamente mais lento, enquanto é melhor e GREPfica um pouco atrás.RegEXSED/replaceSED/delete

   Abaixo de ~50 elementos , os custos de invocação de AWK, SED e GREP aumentarão significativamente o tempo de execução consumido, em comparação aos for/whileloops, ~4x ou mais.

   Aqui, os loops de filtro dedicados, ou PSUBgeralmente apresentam melhor desempenho.

   Acima de ~100 elementos , ferramentas dedicadas superarão rapidamente a filtragem com loops explícitos, se a vantagem não for anulada novamente por muitas invocações em um loop.

   Para um número muito maior de loops de encapsulamento, os loops de filtragem explícitos devem vencer a corrida, desde que PATTERN MATCHINGsejam restritos a padrões simples .

   Caso contrário, para ~1000 elementos ou mais , AWK, SED e GREP devem mostrar desempenho superior (~10x ou melhor), em relação a for/whileloops explícitos com PATTERN MATCHING.

   Porém, somente para matrizes muito grandes (>~1.000.000) eles conseguiram superar a enorme vantagem inicial de desempenho PSUB.

6. Para muitas iterações/requisitos de alto desempenho, não se atenha dogmaticamente ao DRYprincípio: no script Bash, cada comando simples iterado como ifpode ter um impacto significativo nos tempos de execução.

   Se o desempenho for insuficiente, agrupar caminhos de comutação dedicados no loop de código semelhante em loops separados e comutados externamente e EVITAR TODO O CÓDIGO NÃO NECESSÁRIO DENTRO dos loops pode fazer a diferença:

Comparando tempos de execução de ramificação de loop/condição 1.000.000 para iterações:

# EXTERNALLY SWITCHED LOOPS (~13% faster)
if [[ $RESTRICT ]]; then
    while [[ $((++i)) -le $loops ]]; do
        # BLOCK1
    done
elif [[ $CASE1 ]]; then
    while [[ $((++i)) -le $loops ]]; do
        # BLOCK2
    done
elif [[ $CASE2 ]]; then
    while [[ $((++i)) -le $loops ]]; do
        # BLOCK3
    done
else
    while [[ $((++i)) -le $loops ]]; do
        # BLOCK1
        # BLOCK2
        # BLOCK3
    done
fi

-> 48,4s

# IN-LOOP SWITCHING (much more compact code, but ~13% slower)
while [[ $((++i)) -le $loops ]]; do
    if [[ -z $CASE1 ]]; then
        # BLOCK1
        # [[ $RESTRICT ]] && continue
        # BLOCK2
    fi
    if [[ -z $CASE2 ]]; then
        # BLOCK3
    fi
done

-> 61,8s

Cerca de 13% do tempo de execução poderia ser economizado , embora ao custo de alta redundância de código.

7. Os tempos de criação para conjuntos de teste array vs. concat string var diferem imensamente: quanto mais elementos, mais extremo.

   Enquanto uma string concat é gerada muito rapidamente a partir de uma matriz existente, o tempo para construir grandes strings concatenadas e separadas por novas linhas em um loop dedicado cresce desproporcionalmente muito rápido em máquinas lentas (aqui: 4-Core).

   Uma matriz de 1.000.000 de elementos ainda era construída em ~4s, e convertê-la em uma string de concat levaria apenas 0,8s, mas construir diretamente uma string do mesmo tamanho de elementos em um loop consumiria ~127s :

EM GERAL:

Ao filtrar matrizes em um loop grande, usar uma FILTERING ARRAYSexpressão apropriada deve ser de longe a solução mais eficiente e rápida.

Com as ferramentas usuais, deveria ser o contrário; devido às suas penalidades de invocação, elas ficarão muito para trás com muitas iterações e poucos itens, mas podem chegar ao topo, com grandes quantidades de elementos em apenas algumas iterações.

Aqui estão alguns números dos resultados dos testes:

Intel W10 notebook 4-Core   | AMD Linux workstation 8-Core

1x à 10 elements in 
PSUB        0,000083s       | 0,000082s     best
FOR/PMATCH  0,00015s        | 0,00013s      next best 
SED | GREP  0,039s          | 0,0014s       next best

10x à 10 elements in 
PSUB        0,00063s        | 0,00066s      best
FOR/PMATCH  0,0015s         | 0,0012s       next best
SED | GREP  0,38s           | 0,013s        next best

100x à 10 elements in 
PSUB        0,006s          | 0,0052s       best
FOR/PMATCH  0,016s          | 0,01s         next best
SED | GREP  4,03s           | 0,1s          next best

1.000x à 10 elements in 
PSUB        0,06s           | 0,049s        best
FOR/PMATCH  0,152s          | 0,1s          next best
SED | GREP  39,85s          | 1,1s          next best

10.000x à 10 elements in 
PSUB        1,1s            | 0,5s          best
FOR/PMATCH  1,059s          | 1,0s          next best
SED | GREP  7m8,4s          | 21,4s         next best


1.000x à 10 elements in 
PSUB        0,062s          | 0,049s        best
FOR/PMATCH  0,15s           | 0,10s         next best 
SED | GREP  40,62s          | 1,10s         next best

1.000x à 100 elements in 
PSUB        0,16s           | 0,14s         best
FOR/PMATCH  0,79s           | 0,62s         next best
SED | GREP  40,20s          | 1,13s         next best

1.000x à 1.000 elements in 
PSUB        2,06s           | 0,64s         best
FOR/PMATCH  9,85s           | 3,84s         next best
AWK | GREP  47,03s          | 1,78s         next best

1.000x à 10.000 elements in 
PSUB        16,6s           | 7,12s         best
FOR/PMATCH  74,75s          | 36,47s        next best
AWK | GREP  64,39s          | 7,35s         next best

1.000x à 100.000 elements in 
PSUB        188,89s         | 78,02s        best
FOR/PMATCH  780,61s         | 387,8s        next best
AWK | GREP  146,04s         | 51,04s        next best


1x à 2000 elements in 
PSUB        0,11s           | ?             best
FOR/PMATCH  0,19s           | ?             next best
GREP        84,19s          | ?             next best

1x à 5000 elements in 
PSUB        0,28s           | ?             best
FOR/PMATCH  0,46s           | ?             next best
SED         213,75s         | ?             next best

1x à 10000 elements in 
PSUB        0,63s           | ?             best
FOR/PMATCH  0,91s           | ?             next best
SED         440,62s         | ?             next best

Para matrizes muito grandes (acima de 1.00.000), pode valer a pena usar uma ferramenta dedicada, principalmente GREP e AWK:

1x 1.000.000 em ~0,9s pelo GREP, comparado ao próximo melhor ~1,7s pelo AWK e PSUB.

Para filtrar um único conjunto apenas uma vez, SED(em 8 núcleos)/GREP(em 4 núcleos) apresentam o melhor desempenho, seguidos por AWK e PSUB.

Para grandes sequências de VAR - dependendo da complexidade do RegExuso - GREP mostra o melhor desempenho geral, seguido por AWK e depois SED.

O PSUB não foi considerado para este caso de uso, o que seria um exagero.

O desempenho das ferramentas dedicadas cai em ~1/2, ao processar ARRAYS, para aproximadamente o mesmo rendimento, conforme observado com o PSUB, que está tendo desempenho igual ou melhor.

Alguns diagramas para ilustrar:

CONFIGURAÇÃO DO TESTE:

Um filtro mais próximo possível/de melhor desempenho RegEx( ^[ ?].*), substituição ( ${var/#[? ]*}) ou padrão de comparação ( != [\ \?]*) foi aplicado para cada uma das seguintes abordagens de filtragem:

AWK REGEX from ARRAY
AWK REGEX from VAR
SED REGEX from ARRAY
SED REGEX DELETE from VAR
GREP REGEX from ARRAY
GREP REGEX from VAR
PARAMETER SUBSTITUTION from ARRAY 
FOR LOOPED PATTERN MATCH over ARRAY 
WHILE LOOPED PATTERN MATCH over VAR 
FOR LOOPED PATTERN MATCH over VAR 

[ PSUB from VAR] -> ignorado, desempenho muito baixo para qualquer requisito, exceto os mais baixos!

The test scenario was to filter out all git status -s changes beginning with [ ?] (untracked + unstaged), from a given set of 10 changes elements, which would then be multiplied tenfold for (100x1 -> 1000 elements), per each of the test cases with higher requirements, and/or again looped 10x more often each time, beginning at 1 iteration, then 10, 100, 1k, 10k, 100k, up to 1M loops (were still feasible).

In order to get the best possible test runtime measurement precision, start and stop test times were stored and summed up separately for each approach.

The tests were performed on 2 different test machines, an Intel 4-Core notebook (Cygwin/MinGW) and an AMD 8-Core workstation (Linux/Bash).

'AND THE WINNER IS':

By far the best performing variant over the charts is the native PARAMETER SUBSTITUTION in ARRAY deletion method, provided, only simple Pattern Matching expressions are used. On the other hand, extended Pattern Matching expressions like [+*@?!](...) can quickly spoil the performance advantage.

One drawback is, that this method (with native array collecting) will create aresult set containing empty entries. If empties are no problem, these can easily be filtered out later, while processing the result array.

The performance rewards can be tremendous, though.

For many iterations of small sets, it outperformed dedicated tools by ~10-20x; with numerous wrapping loops, applying this technique would clearly win over external program calls anyway, too.

CAVEAT:

The tests should be extended to more complex filters, comparing these results, too.