[swift-evolution] [Pitch] Swift needs fixed-size array

[Jens Persson]

I've used code like the following example in similar situations and I've
always (after a lot of profiling, trial and error) managed to get the
(ugly) Swift code as fast as the C/C++ code.

struct UnsafeStatic19x19<E> {
    var storage: (
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E,
    E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E, E
    )
    subscript(x: Int, y: Int) -> E {
        get {
            // No index out of bounds check
            var m = self // <-- This workaround will be optimized away.
            return withUnsafeBytes(of: &m) {
                let byteOffset = MemoryLayout<E>.stride * (x + y*19)
                return $0.load(fromByteOffset: byteOffset, as: E.self)
            }
        }
        set {
            withUnsafeMutableBytes(of: &self) {
                let byteOffset = MemoryLayout<E>.stride * (x + y*19)
                $0.storeBytes(of: newValue, toByteOffset: byteOffset, as:
E.self)
            }
        }
    }
}

It isn't pretty but it works (haven't tried this code example though, but
you get the idea).


I wish it was possible to write something like
struct StaticArray<Element, Count> {
    ...
}
instead (a statically allocated array with type-level Count as well as
Element).

/Jens


On Mon, Apr 17, 2017 at 7:52 PM, Anders Kierulf via swift-evolution <
swift-evolution at swift.org> wrote:

> Swift needs a datatype that contains a fixed number of a given type;
> basically a simple fixed-size array.
>
> Motivation: I’ve been porting code for Monte Carlo Tree Search in my
> Go-playing program from C++ to Swift. Performance is crucial for this code,
> as more simulations lead to better play. After the initial port, the Swift
> code was more than 10x slower than my C++ code. After several weeks of
> optimizing, profiling, and digging through disassembly, I’ve gotten to
> within a factor of 2. Most of that gain came from using the ugly workaround
> of importing fixed-size arrays from C.
>
> My app is designed for a 19x19 (or smaller) Go board, not an arbitrary N x
> N board, so I don’t want to pay the high cost of variable-size data
> structures in the lowest levels of my app. Most apps are not like this, and
> most of my app is not, but this kernel of my app needs to be fast. Heap
> allocations, reference counting, and indirections all slow down the code. I
> just need a fixed size of memory that I can access like an array, and Swift
> doesn’t let me do that.
>
> Workaround: By importing an array from C, I can allocate a blob of memory
> on the stack or include it in a struct. I can then use UnsafeRawPointer to
> access that blob like an array (see details in SR-4548). This is ugly, but
> it works, and it is much faster than using a Swift array. However, I’m
> stymied by SR-4542, which causes mutability to spread like a plague through
> client code.
>
> (SR-4542: Calling a function taking an UnsafeRawPointer forces the
> parameter to be passed as inout, which means the method must be mutating.
> UnsafeMutableRawPointer should require inout, UnsafeRawPointer should not.)
>
> Proposal: UnsafeMutablePointer almost provides what I need. However, it
> can only allocate memory on the heap, or it can take a given blob of memory
> and interpret it as something else. What’s missing is a way to allocate
> typed memory of a certain size on the stack or in a struct. For example,
> something like this, with support for subscripts, limited to value types:
>
>     var foo = UnsafeMemory<Int64>(count: 6)
> or
>     var bar = FixedSizeArray<UInt32>(repeating: 0, count: 380)
>
> Alternatives:
> (1) C arrays are currently imported as tuples, so extending tuples with
> subscripts and adding a way to create tuples with a specific count of the
> same type could address this need. However, I don’t think this fits well
> with the concept of tuples.
> (2) Changing the Array type to allow a fixed size could be considered in
> the future. ‘count’ and ‘capacity’ would be fixed and only known to the
> compiler, not stored with the data. However, I suspect the consequences
> would be far-reaching, and thus I don’t see this happening soon.
>
> An UnsafeMemory type would be a limited addition that fits in well with
> the existing low-level Pointer module, and fills a gap in the capabilities
> of Swift. The Pointer module helps implement low-level,
> performance-critical code, and not being able to create data on the stack
> is a serious omission. Jumping through C hoops is not a solution.
>
> Anders Kierulf
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170417/ee388525/attachment.html>