Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Asymptotic complexity of functions deleting values #26

Open
wrengr opened this issue Dec 15, 2021 · 1 comment
Open

Asymptotic complexity of functions deleting values #26

wrengr opened this issue Dec 15, 2021 · 1 comment

Comments

@wrengr
Copy link
Owner

wrengr commented Dec 15, 2021

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
Copy link
Owner Author

wrengr commented Dec 15, 2021

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 added a commit that referenced this issue Jan 1, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant