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

[Heap] Express heap operations on UnsafeMutableBufferPointer #75

Closed
lorentey opened this issue Aug 7, 2021 · 1 comment · Fixed by #78
Closed

[Heap] Express heap operations on UnsafeMutableBufferPointer #75

lorentey opened this issue Aug 7, 2021 · 1 comment · Fixed by #78
Assignees
Labels
enhancement New feature or request Heap Min-max heap module

Comments

@lorentey
Copy link
Member

lorentey commented Aug 7, 2021

Heap currently uses regular array subscripting to access the contents of its storage. Array access is pretty fast, but it includes index validation that is (hopefully) unnecessary in Heap's case. I expect the optimizer is able to get rid of these index validations in some (but not all) cases; but it probably makes sense to not have them in the first place.

Rework the low-level heap implementation to operate on UnsafeMutableBuffer storage instead, turning index checks into debug-mode assertions rather than unconditional preconditions.

To do this, it would make sense to introduce a Heap._UnsafeHandle or _UnsafeHeap struct that consists of an UnsafeMutableBufferPointer value, and move most heap operation to that. We'll need to have closure-based read and update helpers that expose a read-only (or read-write) view of the Array storage. (Similar to how Deque and OrderedSet's hash tables work.)

@lorentey lorentey added enhancement New feature or request Heap Min-max heap module labels Aug 7, 2021
@lorentey lorentey self-assigned this Aug 7, 2021
@lorentey
Copy link
Member Author

The withUnsafeMutableBufferPointer implementations in Array and friends included ancient protection against concurrent mutations that actually made this slower than the original code for insert (but not for removals). This was fixed in the stdlib in swiftlang/swift#38867 & swiftlang/swift#38898. The insert code assumes these changes are in place, or else it will work a bit slower than expected. (These fixes ship in the stdlib SDK, so they're backdeployable. All we need to pick them up is to recompile the code with a future Swift release that contains them.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request Heap Min-max heap module
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant