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

Automatic copying by keeping runtime statistics #10

Open
noughtmare opened this issue Jan 29, 2025 · 0 comments
Open

Automatic copying by keeping runtime statistics #10

noughtmare opened this issue Jan 29, 2025 · 0 comments
Labels

Comments

@noughtmare
Copy link
Owner

noughtmare commented Jan 29, 2025

If each pointer in the chain would keep track of how many times it has been dereferenced. Then during a dereference we could check if the sum of these ticks is greater than the size of the array (or some threshold constant times the size of the array). If that is the case then we can copy, knowing that it is paid for by all previous accesses.

When accessing an old version, we only have to update its count. While traversing a chain we can multiply that count by the remaining length of the chain. That way we don't have to mutate every link every time.

We can also add two different constructors: one with the count and one without. Then we only have to incur the extra memory (and time?) overhead if the old versions are actually used.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant