Immer patches for Array are correct, yet inefficient. Suggesting a new algorithm for optimized patches

Aberta
  • Algo errado?
#1,052 1 comentário 2 reações 0 responsáveis Ver no GitHub

Mantenedores costumam responder em até 4 dias

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
5/5
Tempo estimado
Mais de uma semana
Facilidade para iniciantes
25/100
Tipo de issue
Funcionalidade
Clareza
Razoavelmente clara
Status de atividade
Estagnada
Stack de tecnologia
javascript, typescript
Domínio
performance

Direção de pesquisa

Comece com o teste de patch de arrays em tests/patch.js, especialmente o caso "arrays - multiple prepend" nas linhas referenciadas. Compare os patches esperados atuais com o resultado proposto e, em seguida, avalie o algoritmo de matching limitado sugerido para prepend, splice e outras alterações em arrays. Considera-se concluído quando o comportamento otimizado continua correto e reduz patches desnecessários para pequenas edições em arrays.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

proposal

I am thinking as offering it as a pull request - let me know what you think

🚀 Feature Proposal

Today when computing a patch on arrays, immer compares objects by index, which results in all array change in case of unshift or splice usage. An example is the following test taken from immer testing -

https://github.com/immerjs/immer/blob/main/__tests__/patch.js#L543-L559

describe("arrays - multiple prepend", () => {
	runPatchTest(
		{x: [1, 2, 3]},
		d => {
			d.x.unshift(4)
			d.x.unshift(5)
			// 4,5,1,2,3
		},
		[
			{op: "replace", path: ["x", 0], value: 5},
			{op: "replace", path: ["x", 1], value: 4},
			{op: "replace", path: ["x", 2], value: 1},
			{op: "add", path: ["x", 3], value: 2},
			{op: "add", path: ["x", 4], value: 3}
		]
	)
})

the expected result should be instead

		[
			{op: "add", path: ["x", 0], value: 5},
			{op: "add", path: ["x", 1], value: 4}
		]

Motivation

I am working on a new framework that also serializes patches, and the above is a performance issue.

Consider the above case - for an array of object, lets say an array of 100 objects with 10 attributes each, the current algorithm will generate 1000 patches, while my suggestion is to produce only 1 per added / removed object

Can this be solved in user-land code?

no

Example

See the example above.

Usage: immer -> serialize -> deserialize -> patched object

suggested algorithm

(pseudo code)

the problem with json diff is that given two arrays, without any additional knowledge, to figure out if an item was
pushed to the front, we have to do a === comparison between the array items, which is O(n^2) complexity.

for (let a = 0; a < A.length; a++) {
    for (let b = 0; b < A.length; b++) {
        if (A[a] === B[b])
            // compute the diff    
    }    
}

However, we can create an algorithm focused on small changes that has complexity O(n) with a cutoff.
The algorithm makes the assumption that small changes can be found fast and require small number of mutations to describe.
The cutoff is set at let limit = log(min(A.length, B.length)) and the algorithm has complexity O(limit^2) ~ O(n)

The algorithm -

let limit = log(min(A.length, B.length));
let a=0, b=0;
mainLoop: while (a < A.length && b < B.length) {
    if (A(a) === B(b)) {
        a += 1;
        b += 1
    }
    continue;
    for (let seekSize = 1; seekSize < limit; seekSize++) {
        for (let index = 1; index <= seekSize; index++) {
            if (A[a+index] === B[b+seekSize-index])
                // we have a match, the elements from A between (a..a+index) and replace them with the items from B between (b..b+seekSize-index)
            continue mainLoop;    
        }
    }
    // revert to direct comparison of attributes json diff model (the standard model used by all other algorithms)
}
Linguagem predominante
JavaScript
Estrelas
29k
Forks
905
Merge médio
3d 16h
PRs com merge (30d)
22

Preparar o ambiente

Este projeto não oferece contêiner de desenvolvimento, Dockerfile nem guia de contribuição, então a configuração fica por sua conta: comece pelo README e veja nosso guia da primeira contribuição para os passos gerais.

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de immerjs/immer

Todas as issues de immerjs/immer

Issues semelhantes

Mais issues de JavaScript

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.