[swift-users] Help! Slicing an array is very expensive

Tue May 9 23:27:00 CDT 2017

Try:

struct SegmentedArray {
    private static let segmentCapacityPowerOf2 = 13
    private static let segmentCapacity = 1 <<
SegmentedArray.segmentCapacityPowerOf2
    private var offset: Int
    private var firstSegments: [[UInt8]]
    private var lastSegment: [UInt8]
    var count: Int {
        return (firstSegments.count <<
SegmentedArray.segmentCapacityPowerOf2) + lastSegment.count - offset
    }
    var capacity: Int {
        return (firstSegments.count + 1) <<
SegmentedArray.segmentCapacityPowerOf2
    }
    private init(offset: Int, firstSegments: [[UInt8]], lastSegment:
[UInt8]) {
        (self.offset, self.firstSegments, self.lastSegment) = (offset,
firstSegments, lastSegment)
    }
    private init(offset: Int) {
        self.init(offset: offset, firstSegments: [[UInt8]](), lastSegment:
[UInt8]())
        lastSegment.reserveCapacity(SegmentedArray.segmentCapacity)
    }
    init() { self.init(offset: 0) }
    init(sA: SegmentedArray) {
        (offset, firstSegments, lastSegment) = (sA.offset,
sA.firstSegments, sA.lastSegment)
    }
    mutating func append(_ x: UInt8) {
        if lastSegment.count == SegmentedArray.segmentCapacity {
            firstSegments.append(lastSegment)
            lastSegment = [UInt8]()
            lastSegment.reserveCapacity(SegmentedArray.segmentCapacity)
        }
        lastSegment.append(x)
    }
    subscript(r: Range<Int>) -> SegmentedArray {
        let l = r.lowerBound + offset
        let lI = l >> SegmentedArray.segmentCapacityPowerOf2
        let o = l - (lI << SegmentedArray.segmentCapacityPowerOf2)
        let u = r.upperBound + offset
        let uI = u >> SegmentedArray.segmentCapacityPowerOf2
        let fS = Array(firstSegments[lI ..< uI])
        let r = 0 ..< (u - (uI << SegmentedArray.segmentCapacityPowerOf2))
        let lS = Array(uI >= firstSegments.count ? lastSegment[r] :
firstSegments[uI][r])
        return SegmentedArray(offset: o, firstSegments: fS, lastSegment: lS)
    }
}

It has fast slicing and the slice returned is a `SegmentedArray` and hence
doesn't require wrapping. The append method is a little slower though.

  -- Howard.

On 10 May 2017 at 04:32, Michael Gottesman <mgottesman at apple.com> wrote:

> Could you file a bug report? bugs.swift.org?
>
> Michael
>
> On May 9, 2017, at 12:59 AM, Howard Lovatt via swift-users <
> swift-users at swift.org> wrote:
>
> My mistake. If I create a new array I get the problem. EG:
>
> import Foundation
>
> func elapsed(s: DispatchTime, e: DispatchTime) -> Double {
>     return Double(e.uptimeNanoseconds - s.uptimeNanoseconds) /
> 1_000_000_000
> }
>
> let s = 250_000_000
> var a = [UInt8]()
> a.reserveCapacity(s)
>
> let sa = DispatchTime.now()
> for i in 1 ... s {
>     a.append(0)
> }
> let ea = DispatchTime.now()
> print("Append time: \(elapsed(s: sa, e: ea)) s")
>
> let st = DispatchTime.now()
> a = Array(a[0 ..< (s >> 1)])
> let et = DispatchTime.now()
> print("Trim time: \(elapsed(s: st, e: et)) s")
> print("a count: \(a.count), capacity: \(a.capacity)")
>
>
> Prints:
>
> Append time: 2.65726525 s
> Trim time: 36.954417356 s
> a count: 125000000, capacity: 125001696
>
>
>   -- Howard.
>
> On 9 May 2017 at 17:53, Howard Lovatt <howard.lovatt at gmail.com> wrote:
>
>> I find trimming relative to appending OK on my 6 year old MacBook Pro. EG:
>>
>> import Foundation
>>
>> func elapsed(s: DispatchTime, e: DispatchTime) -> Double {
>>     return Double(e.uptimeNanoseconds - s.uptimeNanoseconds) /
>> 1_000_000_000
>> }
>>
>> let s = 250_000_000
>> var a = [UInt8]()
>> a.reserveCapacity(s)
>>
>> let sa = DispatchTime.now()
>> for i in 1 ... s {
>>     a.append(0)
>> }
>> let ea = DispatchTime.now()
>> print("Append time: \(elapsed(s: sa, e: ea)) s")
>>
>> let st = DispatchTime.now()
>> let ha = a[0 ..< (s >> 1)]
>> let et = DispatchTime.now()
>> print("Trim time: \(elapsed(s: st, e: et)) s")
>>
>> print("ha count: \(ha.count), capacity: \(ha.capacity)")
>>
>>
>> Prints:
>>
>> Append time: 2.612397389 s
>> Trim time: 0.000444132 s
>> ha count: 125000000, capacity: 125000000
>>
>>
>>   -- Howard.
>>
>> On 9 May 2017 at 12:56, Kelvin Ma via swift-users <swift-users at swift.org>
>> wrote:
>>
>>> Depending on what you’re trying to do with the data, you might be better
>>> off using an UnsafeBufferPointer and allocating and reallocating that,
>>> C-style.
>>>
>>> On Mon, May 8, 2017 at 7:01 PM, Philippe Hausler via swift-users <
>>> swift-users at swift.org> wrote:
>>>
>>>> I wonder if Data might be a better tool for the job here since it is
>>>> it’s own slice type and would avoid copying large amounts of data into
>>>> temporary buffers.
>>>>
>>>> > On May 8, 2017, at 16:47, Rick Mann via swift-users <
>>>> swift-users at swift.org> wrote:
>>>> >
>>>> > I have this C library that interacts with some hardware over the
>>>> network that produces a ton of data. It tells me up front the maximum size
>>>> the data might be so I can allocate a buffer for it, then does a bunch of
>>>> network requests downloading that data into the buffer, then tells me when
>>>> it's done and what the final, smaller size is.
>>>> >
>>>> > Thanks to previous discussions on the list, I settled on using a
>>>> [UInt8] as the buffer, because it let me avoid various .withUnsafePointer{}
>>>> calls (I need the unsafe buffer pointer to live outside the scope of the
>>>> closures). Unfortunately, When I go to shrink the buffer to its final size
>>>> with:
>>>> >
>>>> >    self.dataBuffer = Array(self.dataBuffer![0 ..< finalBufferSize])
>>>> >
>>>> > This ends up taking over 2 minutes to complete (on an iPad Pro).
>>>> finalBufferSize is very large, 240 MB, but I think it's doing a very naive
>>>> copy.
>>>> >
>>>> > I've since worked around this problem, but is there any way to
>>>> improve on this?
>>>> >
>>>> > Thanks,
>>>> >
>>>> > --
>>>> > Rick Mann
>>>> > rmann at latencyzero.com
>>>> >
>>>> >
>>>> > _______________________________________________
>>>> > swift-users mailing list
>>>> > swift-users at swift.org
>>>> > https://lists.swift.org/mailman/listinfo/swift-users
>>>>
>>>> _______________________________________________
>>>> swift-users mailing list
>>>> swift-users at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-users
>>>>
>>>
>>>
>>> _______________________________________________
>>> swift-users mailing list
>>> swift-users at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-users
>>>
>>>
>>
> _______________________________________________
> swift-users mailing list
> swift-users at swift.org
> https://lists.swift.org/mailman/listinfo/swift-users
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20170510/edffb578/attachment.html>