Approaches for fixed-size arrays

... if that code cannot be written in generic fashion, nor can it be written against a wrapping type.

I'm fairly certain this isn't true btw. _SmallString works by using a tuple for its storage and getting a pointer to it to modify it, and it stays on the stack.

6 Likes

Right. The optimizer has to be able to prove that the pointer does not escape the stack frame, but if it can, then this optimization ought to be reliable.

2 Likes

Just wanted to throw some thoughts in here since this is something I've been hoping for since like Swift 2:

From what I recall, the stickiest point from previous proposals was that since fixed-size arrays are value types, the natural way to pass them around is a copy. This would have hilarious codegen, so I think it's safe to say that serious people will usually work very hard to avoid having to pass fixed-size array copies.

Inout will be an option sometimes, but I think this points to a necessary indirection over the storage to manipulate the collection, and an interesting outcome of that is that the storage doesn't need to conform to Collection if we expect that people will always use a view. To me, this tilts the balance pretty strongly towards the "views over fixed-size storage" strategy. I'm not a big fan of the proposed syntax, but I have nothing better to offer.

I think that there should be a way to very tersely present a fixed-size array as a [T] without causing a copy. Array(fixedSizeArray) is already be too much textual overhead, IMO. We shouldn't ask people to make their code generic just to be able to accept either one of [T] or FixedSizeArray (at least for immutable bindings).

Lastly, I think that at the same time fixed-size arrays with inline storage are introduced, there should also be a fixed-size array type with out-of-line storage which should be slightly easier to reach for. Without an out-of-line-storage alternative, I predict that we'll see a lot of people have gigantic fixed-size arrays of gigantic types in their structs without realizing how much overhead they incur.

1 Like

in C array is a pointer.
Are fixed-size arrays kind of smart pointer in swift?
Where memory is allocated for fixed-size array: on stack or heap or CPU registers?

@asdf As far as I understand it, the contents would be inline with the containing entity.

  • If it’s a property of a struct, class or actor, or an associated value of an enumeration case, then it would be inline in those instances

  • If it’s a static variable, it’s be in the static data segment of the program

  • If it a local variable, then it would be allocated onto the stack. The contents could be promoted to registers if worthwhil, but only if the optimiser can prove that you never take a pointer to it (which would require the contents be in memory, and contiguous)

This is basically the same as how struct and tuples are stored today (ignoring the padding and type metadata differences Joe mentioned in the OP)

(Someone please correct me if I’m wrong)

2 Likes

Value type arguments are typically passed by borrow, and if they're large, then the compiler can (though doesn't always currently) be passed as a pointer to the same in-memory representation used by the caller when we know nobody can modify it during the call. The codegen problems with large value types aren't specific to fixed-size arrays, and we ought to fix them independently of whether we have fixed-size value type arrays.

16 Likes

So this might well seem a little bit over the top...

I always considered the generic argument section of the Type signature to be the init method of the meta type.

If we get compile time expressions (as issues as a future enhancement of Build-Time Constant Values) then these really could be considered as the init signature of the MetaType where the meta type constructor is evaluated at compile time.

The reason I think having these exressabel as in compile time expressions is once we start to add the complexity of value type instances to the generic signature we need to be able to provide constraints on what is legal at compile time.

let a = Tensor<4, 2, Float>(filled: 1)
let b = Tensor<square: 4, Float>(filled: 0)

struct Tensor {
   meta {
        let shape: [UInt]
        let columns: Uint
        let Scalar: any Type
        
        // is impliclty @const so all values must be const values
        init(_ rows: Uint, columns: Uint, scalar: any type) {
            precondition(rows > 0, "Can not create matrix with 0 rows")
            precondition(columns > 0, "Can not create matrix with 0 columns")
            self.shape = [rows, columns]
            self.scalar = scalar
        }

        init(square: Uint, columns: Uint, scalar: any type) {
            precondition(square > 0, "Can not create square matrix 0 rows and 0 columns")
            self.shape = [square, square]
            self.scalar = scalar
        }
    }

   // For storing values
   let values: Tuple<size: Self.shape.reduce(*, 1), of: Self.Scalar>()
}

It would be important that all meta types conform to Equatable (possibly hashable) so that the compiler can coalesce all of the meta types that are the same even if they signature used to create them is different (eg Tensor<4, 4, Float> == Tensor<square: 4, Float> so should be one Meta Type for the compile).

instance properties and methods of the MetaType would then be all implicitly @costs so could be used in compile time evaluated where constraints.

where 
    A.shape.count == 2,
    B.shape.count == 2, 
    A.shape[0] == B.shape[1],
    A.shape[1] == B.shape[0],
    A.Scalar == B.Scalar

Meta types would need to be considered value types a thus be immutable like structs.

3 Likes

Some miscellaneous thoughts:

  • I'm glad something is being done about this, because as everyone else has pointed out, working with imported C arrays is a pain.

  • I think the tail padding issue is important enough that "just use tuples" is a bad idea; it will come back to bite someone. (You probably could have guessed this is my opinion.)

  • I don't actually think the type metadata backwards deployment thing would be a huge issue in practice. There are a variety of options, from making these a special kind of struct to carefully tiptoeing around any operations where older runtimes would switch on the metadata type at all. The main thing that makes this okay in my mind is that conformances aren't attached to type metadata except for dynamic lookup. Even if, say, the backwards-deployed Collection conformance can't be written in Swift (or at least not normal Swift) it can absolutely be contrived/handcoded to do something reasonable.

  • If I think about where I've been using fixed-sized arrays in Rust that aren't C interop or interpreting binary data, it's things like the backing for UUIDs ([u8; 16]), or Curve25519 keys ([u8; 32]), or SHA-256 hashes (also [u8; 32]). But of course you'd want strong types for most of these whenever possible, and they're not (usually) interchangeable, so most of the benefit is when you're using these types with C interop, or interpreting binary data, or checking that your compile-time constants aren't missing a digit.

  • EDIT: I'm not convinced that there's enough of a use case for Erik's "great fixed-size array", and I wouldn't want to see Collectiony semantics left out of the "imported from C fixed-size array".

8 Likes

To this point, I think it's worth calling out that the backing fixed size array makes implementing these strong types nicer. Just a note. Can't imagine where I got the motivation for it from.

1 Like

Right, but if the main use is backing strong concrete types, then Joe’s magic property attributes fit the bill. It’s only if you pass them around as bare values or genericize over them that they need to be in the type system.

5 Likes

Having to do this now working with BLE and transports.

I've gone down the route of the following, it's work in progress, but works basically as follows :

protocol FixedSizeArray: ExpressibleByArrayLiteral {
    associatedtype Element
    static var size: UInt32 { get }
    var array: Array<Element> { get set }
}

extension FixedSizeArray {
    public init(arrayLiteral elements: ArrayLiteralElement...) {
        self.init()

        let trimmedElements = elements.prefix(Int(Self.size))
        let bufferCapacity = Int(Self.size) * MemoryLayout<Element>.size
        self.array = Array(
            unsafeUninitializedCapacity: bufferCapacity,
            initializingWith: { destinationBuffer, initializedCount in
                let destPointer = destinationBuffer.baseAddress
                
                trimmedElements.withUnsafeBytes { sourceBuffer in
                    let srcPointer = sourceBuffer.baseAddress

                    memset(destPointer, 0, bufferCapacity)
                    memcpy(destPointer, srcPointer, trimmedElements.count * MemoryLayout<Element>.size)
                }
            }
        )
    }
}

public struct Array8<Element>: FixedSizeArray {
    public typealias ArrayLiteralElement = Element

    //typealias Element = Element
    static var size: UInt32 { 8 }
    var array: Array<Element>
}

Usage is something like this.

var fixedSizeArray: Array16<UInt32> = another array (Array will be trimmed and initialised to a certain size.

1 Like

My full working implementation below, don't mind the weird initialisers, it was the only way I could fix an infinite loop recursion when using the ExpressibleByArrayLiteral method :

import Foundation

protocol FixedSizeArray: ExpressibleByArrayLiteral {
    static var size: UInt32 { get }
    var array: Array<ArrayLiteralElement> { get set }
    var asData: Data { get }
    init()
}

extension FixedSizeArray {
    public init(arrayLiteral elements: ArrayLiteralElement...) {
        self.init()

        // We need to set this here because otherwise the type complains we haven't set everything before our call.
        self.array = elements
        updateArrayFrom(elements: array)
    }

    mutating func updateArrayFrom(elements: Array<ArrayLiteralElement>) {
        let trimmedElements = elements.prefix(Int(Self.size))
        let bufferCapacity = Int(Self.size) * MemoryLayout<ArrayLiteralElement>.size
        self.array = Array<ArrayLiteralElement>(
            unsafeUninitializedCapacity: bufferCapacity,
            initializingWith: { destinationBuffer, initializedCount in
                let destPointer = destinationBuffer.baseAddress

                trimmedElements.withUnsafeBytes { sourceBuffer in
                    let srcPointer = sourceBuffer.baseAddress

                    memset(destPointer, 0, bufferCapacity)
                    memcpy(destPointer, srcPointer, trimmedElements.count * MemoryLayout<ArrayLiteralElement>.size)
                }

                initializedCount = Int(Self.size)
            }
        )
    }

    public var asData: Data {
        let data = array.withUnsafeBytes { bufferPointer in
            Data(bufferPointer)
        }

        return data
    }
}

public struct Array8<Element>: FixedSizeArray {
    public typealias ArrayLiteralElement = Element
    static var size: UInt32 { 8 }
    var array: Array<Element>

    init() {
        self.array = []

        // Need to set this here so that we generate the correct sized internal array on initialisation
        updateArrayFrom(elements: [])
    }
}

public struct Array16<Element>: FixedSizeArray {
    public typealias ArrayLiteralElement = Element
    static var size: UInt32 { 16 }
    var array: Array<Element>

    init() {
        self.array = []

        // Need to set this here so that we generate the correct sized internal array on initialisation
        updateArrayFrom(elements: [])
    }
}

does the swift calling convention eagarly destructure tuples that are inside frozen types?

@frozen public
struct RGBA32
{
    public
    let byte:(UInt8, UInt8, UInt8, UInt8)
}

can a type that passes along an RGBA32 as a value pass 4 UInt8 arguments at the machine code level?

Regardless of what we do at the end of the day for the fixed-sized arrays, can we have a subscript on homogeneous tuples please?

subscript(_ index: Int) -> Element { get set }

let i = 1
tuple.1   ←→  tuple[i]

Although I admit, I primarily want this to implement fixed-sized arrays! :wink:

1 Like

I remember one time trying to create an equivalent to C#’s Guid.Empty. Because this is (currently) bridged as a tuple, I couldn’t use Array(repeating: 0, count: 16) and instead had to manually write out (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0). Some shorthand for things like that would be nice. Being a collection means we could also invoke operations like FixedSizeArray(1...16) to fill it with consecutive numbers, etc.


How would using the number as a generic interact with variadic generics? C++ allows …this:

template<class T, size_t... dims>
class multidim_array;

template<class T, size_t dim>
class multidim_array<T, dim> {
    T m_array[dim];
};

template<class T, size_t dim0, size_t... dims>
class multidim_array<T, dim0, dims...> {
    multidim_array<T, dims...> m_array[dim0];
};

Do we want to enable structures like this?

Since years I am looking for Swift to support native fixed size array.
Here we have a lot of C interop where struct elements are fixed array and a pain to deal in Swift using tuple. Its a shame because otherwise in my opinion Swift has the best C interop compared to other languages like C#, Python, Java...

For example dealing with a simple C stuct like this:

// C Side 

typedef struct Sensor_t {
  char name[256];
  int valuesCount;  
  double values[8192];      
} Sensor_t;

void readSensor(Sensor_t* sensor);
void writeSensor(Sensor_t* sensor);

The struct Is now exported in Swift like this:

// Swift side actual

struct Sensor_t {
  var name: (CChar, CChar, CChar, CChar.. 256 times...)
  var valuesCount: Int
  var values : (Double, Double, Double.. 8192 times... ?) // No, Boom !! Simply not possible !! Swift Tuple size limit is 4096 elements    
}

Not only turning these tuples into usable string (the name element) and large array (the values element) need ugly glue code but the tuple limit of 4K elements is a deal breaker.

What I would like is a very simple way to deal with C fixes size array like this:

// Swift Side I would like:

// The C struct imported in Swift like this
struct Sensor_t {
  var name: FixedArray<CChar>
  var valuesCount: Int
  var values: FixedArray<Double>   
}

// I can use the struct like this to read the sensor
var sensor = Sensor_t()
readSensor(&sensor)

let sensorName: String = String(cstring: sensor.name)
print(“The sensor name is: \(sensorName)”)

for index in 0..<sensor.valuesCount {
	sensorValue = sensor.values[index]
	print(sensorValue)
}

// or better

for sensorValue in sensor.values {
	print(sensorValue)
}

// I can use the struct like this to write to the sensor

var sensor = Sensor_t()
sensor.name = FixedArray<CChar>(fromString: "Temperature Sensor")

sensor.valuesCount = 6000
var simulatedTemperature = 20.0
for index in 0..< sensor.valuesCount {
    sensor.values[index] = simulatedTemperature
    simulatedTemperature += 1.5
}

writeSensor(&sensor)

I have no idea how the required changes can be implemented in Swift. This is just a point of vue from a Swift user dealing daily with C interop,

Can I hope this kind of fixed array support be implemented in the upcoming 5.8 ? Please !!!, even if the implementation cause source breaking the old tuple solution.

Thanks !

4 Likes

Perhaps with the size, pseudocode:

struct Sensor_t {
    var name: FixedArray<256, CChar>
    var valuesCount: Int
    var values: FixedArray<8192, Double>   
}

C-like syntax would also be reasonable:

struct Sensor_t {
    var name: Char[256]
    var valuesCount: Int
    var values: Double[8192]
}

and the current array syntax may get these equivalents:

struct Sensor_t {
    var name: Char[]        // same as [Char], same as Array<Char>
    var valuesCount: Int
    var values: Double[]    // same as [Double], same as Array<Double>
}

Worth to mention whether:

  1. count is not stored inside FixedArrays (like in tuples). count is always == capacity.
  2. count is optionally stored inside FixedArrays (opt-in / opt-out). Array can "grow" up to a fixed capacity.
  3. count is aways stored inside FixedArray. Array can "grow" up to a fixed capacity.

(3) is not good for C compatibility, but whether we should land at 1 or 2 I'm not sure, leaning towards (1) for simplicity.

IMHO the lack of fixed sized arrays is a hole in the language, worth filling.

2 Likes

Is there a proposal for this kind of thing? I feel it's far more important than many of the other proposals going around, which are far more niche than such a basic function of fixed size array types.

Thoughts?

2 Likes

Could we use a similar approach to A large fixed-width integer Swift package to construct the large sizes necessary. It would probably look a bit ugly but might get the job done - macros would make constructing them quite easy too.