search

intelie / immutable-js-diff

MIT License
261 stars 32 forks source link

lcs only performed on small sequences, resulting in large diffs for larger sequences #21

Open orph opened 7 years ago

orph commented 7 years ago

this line: https://github.com/intelie/immutable-js-diff/blob/master/src/diff.js#L67 performs a mapdiff if the input sequences are >99 long, which results in a large element-by-element diff. this is very unexpected and was hard to track down.

pedroteixeira commented 7 years ago

The rationale was that patches would be equivalent, and the actual implementation wanted to avoid high cpu usage for large sequences, so the tradeoffs was between diff size and computational complexity.

but you're right, it's pretty arbitrary :/

not sure if we should remove this behaviour and make it configurable somehow. Any suggestions? for your case for eg., a higher number would be better?

orph commented 7 years ago

the problem is that the patches are not equivalent - inserting an element causes many more operations with mapDiff. It's stepping through each pair following the inserted index, finding them different, and diffing all the individual fields. Versus with sequenceDiff it would be a single 'add' operation.