bytestring-trie icon indicating copy to clipboard operation
bytestring-trie copied to clipboard

Asymptotic complexity of functions deleting values

Open wrengr opened this issue 3 years ago • 1 comments
trafficstars

When using the internal functions arc, arc_, arcNN, or prepend to rebuild the spine after deleting values, under certain circumstances we can end up chaining those together and thus encounter an asymptotic slowdown similar to #25 (albeit greatly reduced in scope and severity). However, unlike #25, the bug here is not intrinsic to the data structure. We should be able to adjust those functions to behave more like a zipper, and only do the bytestring concatenation once an arc is "complete" (akin to the use of RevLazyByteString in the priority-queue functions).

wrengr avatar Dec 15 '21 05:12 wrengr

Fwiw, this can only (potentially) affect functions that delete several values (and not in a delete-a-whole-subtrie way). If only a single value is deleted, then while there may be iterated calls to those functions, at most one of them can actually result in a bytestring append (thanks to our invariants). In order to trigger the bug, you'd need to delete several values whose keys are all prefixes of one another (but leaving a value whose key all the deleted keys are prefixes of), and/or deleting entire side branches off of such a prefix chain— because every value and branch point serves as a terminator for iterated bytestring appends.

Since it requires such specific conditions to trigger, I'm removing the "Bug" label for now.

wrengr avatar Dec 15 '21 06:12 wrengr