Skip to content

Only calculate size of a dynamic table entry once#129

Closed
sethmlarson wants to merge 3 commits intomasterfrom
SethMichaelLarson-patch-1
Closed

Only calculate size of a dynamic table entry once#129
sethmlarson wants to merge 3 commits intomasterfrom
SethMichaelLarson-patch-1

Conversation

@sethmlarson
Copy link
Member

@sethmlarson sethmlarson commented Jul 5, 2017

Optimization to reduce the number of calls to table_entry_size by half when adding and evicting entries to the dynamic table so the size of an entry is only calculated on add().

@sethmlarson
Copy link
Member Author

sethmlarson commented Jul 5, 2017

This seems like it would be a breaking change, perhaps this should be bundled up into work to improve the dynamic table lookup speed. Potentially can use a helper object to preserve outward API.

@sethmlarson
Copy link
Member Author

Might write a subclass to deque that handles all shrinking/growing along with preserving public API.

Copy link
Member

@Lukasa Lukasa left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah, so I think this isn't a breaking change: we don't expect people to be messing about with this data structure. Changelog entry would be good though!

@sethmlarson
Copy link
Member Author

sethmlarson commented Jul 5, 2017

Sure thing, I was about to ask you whether we expect people to mess around with dynamic_entries. I've also got an idea that could bring down our name, value -> index look-up time from O(N) to O(1) while keeping memory usage linear relative to current usage.

I'll have to change a lot of tests that seem to be touching dynamic_entries to make them pass.

@sethmlarson sethmlarson force-pushed the SethMichaelLarson-patch-1 branch from f30c334 to 0d85f75 Compare July 5, 2017 21:28
@sethmlarson
Copy link
Member Author

My idea to reduce lookup time has too much of a memory usage trade-off. Will take the simple route here, just need to fix some tests.

if v == value:
return i + 1, n, v
elif partial is None:
partial = (i + 1, n, None)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks like you accidentally included a reversion to the old lookup style.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this is from where I mucked up a rebase from 119. I'm probably going to just restart with master since the change is so minor.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants