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

[SR-14654] Array and ArraySlice use different implementations of replaceSubrange #57006

Open
karwa opened this issue May 24, 2021 · 2 comments
Open

Comments

@karwa
Copy link
Contributor

@karwa karwa commented May 24, 2021

Previous ID SR-14654
Radar None
Original Reporter @karwa
Type Bug
Environment

Swift 5.4, N/A

Additional Detail from JIRA
Votes 0
Component/s Standard Library
Labels Bug
Assignee None
Priority Medium

md5: b5433a00ab59e1890d7cbd65c67200b5

Issue Description:

The implementation of ArraySlice.replaceSubrange uses the following pattern:

if _buffer.beginCOWMutation() && _buffer.capacity >= oldCount + growth {
      _buffer.replaceSubrange(
        subrange, with: insertCount, elementsOf: newElements)
    } else {
      _buffer._arrayOutOfPlaceReplace(subrange, with: newElements, count: insertCount)
    }

This checks to see if the buffer is uniquely-referenced and has sufficient capacity for the result: if it does, the implementation calls ArrayBufferProtocol.replaceSubrange, which performs the replacement in-place using moves. Otherwise, it calls ArrayBufferProtocol._arrayOutOfPlaceReplace, which allocates a new buffer with the required capacity (the destination), and passes it in a call to ArrayBufferProtocol._arrayOutOfPlaceUpdate . This function then checks to see if it (the source) is uniquely-referenced (note: it calls 'requestUniqueMutableBackingBuffer(minimumCapacity🙂', but passes its own count as the desired capacity, so this is basically just a uniquely-referenced check).

If the source buffer is uniquely-referenced, the source contents will be moved to the destination, except for the replaced region, which will be initialised directly. If the source is not uniquely-referenced, the source contents will be copied rather than moved to the destination (again, excepting the replaced region). So when allocating new storage, that storage is initialised to the correct post-replacement sequence of elements.

Phew! Okay - and with that, we're done. With ArraySlice, that is.

Now, the interesting thing is that plain-old Array, itself, skips a couple of these steps. The implementation for Array.replaceSubrange just looks like this:

    _reserveCapacityImpl(minimumCapacity: self.count + growth,
                         growForAppend: true)
    _buffer.replaceSubrange(subrange, with: insertCount, elementsOf: newElements)
    _endMutation()

This just reserves the required capacity up-front, then calls in to our old friend ArrayBufferProtocol.replaceSubrange, which performs the replacement in-place using moves. It doesn't do any extra work to initialise the newly-allocated buffer with the correct post-replacement elements from the start - if the source is, say, non-uniquely-referenced, it will first copy everything and then deinitialise the objects it doesn't need any more; potentially incurring more refcounting operations than is strictly necessary.

So my question is: why?

I've tracked it down to this PR: #29068 which was intended to reduce code-size; but this isn't mentioned as an intended functional change and the same change was not made to ArraySlice.

@karwa
Copy link
Contributor Author

@karwa karwa commented May 24, 2021

@eeckstein this was introduced by the PR linked at the end of the description. Can you confirm whether this was an intentional change?

@eeckstein
Copy link
Member

@eeckstein eeckstein commented May 25, 2021

I can't remember the details, but I think the reason was the ArraySlice buffer works differently than the Array buffer. So I'm not sure if this change would have saved some code size for ArraySlice as well.
But both implementations should be functional equivalent.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 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

2 participants