Proposal: Implement == and < for tuples where possible, up to some high arity


(Lily Ballard) #1

I'd really like to see tuples support comparison operators when
possible. Eventually they should even conform to the
Equatable/Comparable protocols, but that requires tuples being able to
conform to protocols at all to begin with.

In the absence of some sort of variadic type parameters, we'd only be
able to support the comparison operators on tuples up to some predefined
arity. There's precedent in Rust and Haskell for this. Rust defines
these operations up to arity 12, Haskell defines them up to arity 15.

Behavior of == should be obvious. Behavior of the ordered comparison
operators would work like comparison of strings, where the first element
is compared, and if equal, the second element is compared, etc.

This would be implemented using some .gyb code that generates
declarations that look something like

func == <A: Equatable, B: Equatable, C: Equatable>(lhs: (A, B, C), rhs:
(A, B, C)) -> Bool { return lhs.0 == rhs.0 && lhs.1 == rhs.1 && lhs.2
== rhs.2 }

func < <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C),
rhs: (A, B, C)) -> Bool { if lhs.0 != rhs.0 { return lhs.0 < rhs.0 }
if lhs.1 != rhs.1 { return lhs.1 < rhs.1 } return lhs.2 < rhs.2 }

func > <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C),
rhs: (A, B, C)) -> Bool { if lhs.0 != rhs.0 { return lhs.0 > rhs.0 }
if lhs.1 != rhs.1 { return lhs.1 > rhs.1 } return lhs.2 > rhs.2 }

If tuples ever gain the ability to conform to protocols (which I think
they should), and when types gain the ability to conditionally conform
to protocols, these declarations would be adjusted to declare the tuples
as conforming to Equatable and Comparable. This would be a backwards-
compatible change.

Similarly if Swift ever gains some form of variadic type parameters,
thus allowing for declaring behavior of arbitrary-sized tuples, then
this can be adjusted to use that feature and it should still be backwards-
compatible.

-Kevin Ballard


(Dmitri Gribenko) #2

Looks like a good idea to me! Also the <= and >= operators, right?

What concerns we with massive code generation is the code size of the core
swift library. It would be definitely important to see how much code this
adds, depending on the number of tuple elements.

I personally don't see a point in going as high as 12 tuple elements.
About 4 or 5 makes sense to me. Given that Swift does not have variadic
generics right now, these long tuples have to be defined by someone
manually. If one is defining a tuple that is that long, I'd argue that
they should be using a custom struct instead.

Dmitri

···

On Mon, Dec 7, 2015 at 11:48 AM, Kevin Ballard via swift-evolution < swift-evolution@swift.org> wrote:

I'd really like to see tuples support comparison operators when possible.
Eventually they should even conform to the Equatable/Comparable protocols,
but that requires tuples being able to conform to protocols at all to begin
with.

In the absence of some sort of variadic type parameters, we'd only be able
to support the comparison operators on tuples up to some predefined arity.
There's precedent in Rust and Haskell for this. Rust defines these
operations up to arity 12, Haskell defines them up to arity 15.

Behavior of == should be obvious. Behavior of the ordered comparison
operators would work like comparison of strings, where the first element is
compared, and if equal, the second element is compared, etc.

This would be implemented using some .gyb code that generates declarations
that look something like

func == <A: Equatable, B: Equatable, C: Equatable>(lhs: (A, B, C), rhs:
(A, B, C)) -> Bool {
    return lhs.0 == rhs.0 && lhs.1 == rhs.1 && lhs.2 == rhs.2
}

func < <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C), rhs:
(A, B, C)) -> Bool {
    if lhs.0 != rhs.0 { return lhs.0 < rhs.0 }
    if lhs.1 != rhs.1 { return lhs.1 < rhs.1 }
    return lhs.2 < rhs.2
}

func > <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C), rhs:
(A, B, C)) -> Bool {
    if lhs.0 != rhs.0 { return lhs.0 > rhs.0 }
    if lhs.1 != rhs.1 { return lhs.1 > rhs.1 }
    return lhs.2 > rhs.2
}

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Lily Ballard) #3

__
I'd really like to see tuples support comparison operators when
possible. Eventually they should even conform to the
Equatable/Comparable protocols, but that requires tuples being able
to conform to protocols at all to begin with.

In the absence of some sort of variadic type parameters, we'd only be
able to support the comparison operators on tuples up to some
predefined arity. There's precedent in Rust and Haskell for this.
Rust defines these operations up to arity 12, Haskell defines them up
to arity 15.

Behavior of == should be obvious. Behavior of the ordered
comparison operators would work like comparison of strings, where
the first element is compared, and if equal, the second element is
compared, etc.

This would be implemented using some .gyb code that generates
declarations that look something like

func == <A: Equatable, B: Equatable, C: Equatable>(lhs: (A, B, C),
rhs: (A, B, C)) -> Bool { return lhs.0 == rhs.0 && lhs.1 == rhs.1
&& lhs.2 == rhs.2 }

func < <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C),
rhs: (A, B, C)) -> Bool { if lhs.0 != rhs.0 { return lhs.0 < rhs.0
} if lhs.1 != rhs.1 { return lhs.1 < rhs.1 } return lhs.2 <
rhs.2 }

func > <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C),
rhs: (A, B, C)) -> Bool { if lhs.0 != rhs.0 { return lhs.0 > rhs.0
} if lhs.1 != rhs.1 { return lhs.1 > rhs.1 } return lhs.2 >
rhs.2 }

Looks like a good idea to me! Also the <= and >= operators, right?

Yeah, and != too. I just skipped them for brevity.

What concerns we with massive code generation is the code size of the
core swift library. It would be definitely important to see how much
code this adds, depending on the number of tuple elements.

Good question. What's the best way to measure this? File size of build/$target/swift-macosx-
x86_64/lib/swift/macosx/libswiftCore.dylib (does that even include
generic functions)? Or the x86_64/libswiftCore.dylib from the same
folder (what's the difference)? Or x86_64/Swift.swiftmodule?
Something else?

I personally don't see a point in going as high as 12 tuple elements.
About 4 or 5 makes sense to me. Given that Swift does not have
variadic generics right now, these long tuples have to be defined by
someone manually. If one is defining a tuple that is that long, I'd
argue that they should be using a custom struct instead.

Depends on how much code size it is. I'd rather err on the side of
defining it for a higher arity tuple than we expect people to actually
use in practice. Just because it's probably a good idea to not point
more than a handful of elements in a tuple doesn't mean people will
actually stick to that, and it's surprising behavior to have ==
suddenly break because you added one more (Equatable) value to the
tuple. As an example, my coworker recently wrote some code that uses a
tuple of 7 elements (as a typedef). It probably should have been a
struct, but I think it was originally defined with just 3 or 4 elements
and sprouted the others as he worked on it. Granted, this particular
tuple wouldn't actually support ==, but I'm sure others have written
similarly long tuples.

I'll probably prototype this some time today, and I can produce some
measurements of code size at different arities (if I can figure out the
best way to measure that).

-Kevin Ballard

···

On Mon, Dec 7, 2015, at 12:01 PM, Dmitri Gribenko wrote:

On Mon, Dec 7, 2015 at 11:48 AM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:


(Chris Lattner) #4

func > <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C), rhs: (A, B, C)) -> Bool {
    if lhs.0 != rhs.0 { return lhs.0 > rhs.0 }
    if lhs.1 != rhs.1 { return lhs.1 > rhs.1 }
    return lhs.2 > rhs.2
}

Looks like a good idea to me! Also the <= and >= operators, right?

+1 from me too.

I personally don't see a point in going as high as 12 tuple elements. About 4 or 5 makes sense to me. Given that Swift does not have variadic generics right now, these long tuples have to be defined by someone manually. If one is defining a tuple that is that long, I'd argue that they should be using a custom struct instead.

I tend to agree with Dmitri here. Independent of the code size concern, what is the expected use-case for > 4 element tuples?

-Chris

···

On Dec 7, 2015, at 12:01 PM, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:


(Dmitri Gribenko) #5

Good question. What's the best way to measure this? File size of
build/$target/swift-macosx-x86_64/lib/swift/macosx/libswiftCore.dylib (does
that even include generic functions)? Or the x86_64/libswiftCore.dylib from
the same folder (what's the difference)? Or x86_64/Swift.swiftmodule?
Something else?

Use utils/cmpcodesize.

The swift-macosx-x86_64/lib/swift/<target>/libswiftCore.dylib dylibs
are fat ones, the dylib nested inside the architecture directory is a
regular one. Please also measure for iOS (to build those, run
build-script with -i).

I personally don't see a point in going as high as 12 tuple elements. About
4 or 5 makes sense to me. Given that Swift does not have variadic generics
right now, these long tuples have to be defined by someone manually. If one
is defining a tuple that is that long, I'd argue that they should be using a
custom struct instead.

Depends on how much code size it is. I'd rather err on the side of defining
it for a higher arity tuple than we expect people to actually use in
practice. Just because it's probably a good idea to not point more than a
handful of elements in a tuple doesn't mean people will actually stick to
that, and it's surprising behavior to have == suddenly break because you
added one more (Equatable) value to the tuple. As an example, my coworker
recently wrote some code that uses a tuple of 7 elements (as a typedef). It
probably should have been a struct, but I think it was originally defined
with just 3 or 4 elements and sprouted the others as he worked on it.
Granted, this particular tuple wouldn't actually support ==, but I'm sure
others have written similarly long tuples.

I'll probably prototype this some time today, and I can produce some
measurements of code size at different arities (if I can figure out the best
way to measure that).

I can see that. Definitely depends on the code size, though!

Dmitri

···

On Mon, Dec 7, 2015 at 12:22 PM, Kevin Ballard <kevin@sb.org> wrote:

On Mon, Dec 7, 2015, at 12:01 PM, Dmitri Gribenko wrote:
On Mon, Dec 7, 2015 at 11:48 AM, Kevin Ballard via swift-evolution > <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Jacob Bandes-Storch) #6

On the contrary, I think >4-element-tuples are useful exactly *for* the
case of custom structs. You wouldn't want the tuples themselves to be part
of your API, but if you have a custom struct with 4+ Comparable fields, you
can implement its < operator as simply "return (a1,b1,c1,d1,e1) <
(a2,b2,c2,d2,e2)".

Jacob

···

On Mon, Dec 7, 2015 at 3:01 PM, Chris Lattner via swift-evolution < swift-evolution@swift.org> wrote:

On Dec 7, 2015, at 12:01 PM, Dmitri Gribenko via swift-evolution < > swift-evolution@swift.org> wrote:

I personally don't see a point in going as high as 12 tuple elements.
About 4 or 5 makes sense to me. Given that Swift does not have variadic
generics right now, these long tuples have to be defined by someone
manually. If one is defining a tuple that is that long, I'd argue that
they should be using a custom struct instead.

I tend to agree with Dmitri here. Independent of the code size concern,
what is the expected use-case for > 4 element tuples?

-Chris


(plx) #7

FWIW, the possibility of tuple-punning (tuple -> function arguments) provides a lot of practical uses for larger tuples, but these aren’t actually uses that would really benefit from having `==`, etc., defined.

What *would* be useful for those uses is some standard way to flatten “nested" tuples -> “flat" tuples — `((a,b),(c,d),(e,f,g)) -> (a,b,c,d,e,f,g)` and so on — if it doesn’t already exist (does it?).

···

On Dec 7, 2015, at 5:01 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 7, 2015, at 12:01 PM, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

func > <A: Comparable, B: Comparable, C: Comparable>(lhs: (A, B, C), rhs: (A, B, C)) -> Bool {
    if lhs.0 != rhs.0 { return lhs.0 > rhs.0 }
    if lhs.1 != rhs.1 { return lhs.1 > rhs.1 }
    return lhs.2 > rhs.2
}

Looks like a good idea to me! Also the <= and >= operators, right?

+1 from me too.

I personally don't see a point in going as high as 12 tuple elements. About 4 or 5 makes sense to me. Given that Swift does not have variadic generics right now, these long tuples have to be defined by someone manually. If one is defining a tuple that is that long, I'd argue that they should be using a custom struct instead.

I tend to agree with Dmitri here. Independent of the code size concern, what is the expected use-case for > 4 element tuples?

-Chris

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Charles Srstka) #8

When importing structs from C, all char arrays are converted into Int8 tuples. So, it’s pretty easy to end up with a tuple with quite a lot of elements.

For example:

struct Foo {
    char bar[256];
};

becomes:

public struct Foo {
    public var bar: (Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8)
    public init()
    public init(bar: (Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8))
}

These tuples are currently rather difficult to work with.

Charles

···

On Dec 7, 2015, at 5:01 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

I tend to agree with Dmitri here. Independent of the code size concern, what is the expected use-case for > 4 element tuples?


(Chris Lattner) #9

Sure, or:
   return (a1,b1,(c1,d1,e1)) < (a2,b2,(c2,d2,e2))

:-)

-Chris

···

On Dec 7, 2015, at 3:04 PM, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

On Mon, Dec 7, 2015 at 3:01 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
On Dec 7, 2015, at 12:01 PM, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I personally don't see a point in going as high as 12 tuple elements. About 4 or 5 makes sense to me. Given that Swift does not have variadic generics right now, these long tuples have to be defined by someone manually. If one is defining a tuple that is that long, I'd argue that they should be using a custom struct instead.

I tend to agree with Dmitri here. Independent of the code size concern, what is the expected use-case for > 4 element tuples?

-Chris

On the contrary, I think >4-element-tuples are useful exactly *for* the case of custom structs. You wouldn't want the tuples themselves to be part of your API, but if you have a custom struct with 4+ Comparable fields, you can implement its < operator as simply "return (a1,b1,c1,d1,e1) < (a2,b2,c2,d2,e2)”.


(Brent Royal-Gordon) #10

you can implement its < operator as simply "return (a1,b1,c1,d1,e1) < (a2,b2,c2,d2,e2)”.

  return zip([a1,b1,c1,d1,e1], [a2,b2,c2,d2,e2]).lazy.filter(==).first.flatMap(<) ?? false

Okay, so that wasn’t quite as easy as I thought when I started writing the email.

···

--
Brent Royal-Gordon
Architechies


(Lily Ballard) #11

Code size turns out to be much higher than expected.

When implementing ==, !=, <, <=, >, and >= for tuples of arities 2–6, I
end up with a 1.4% increase in libswiftCore.dylib code size:

                                   Section Old New Percent
libswiftCore.dylib __text: 3198165 3242853 -1.4%
libswiftCore.dylib __text: 2939740 2980844 -1.4%

(or about 43.6KiB)

After increasing it to go up to arity 12, it reaches a 5.3–5.5%
increase:

                                   Section Old New Percent
libswiftCore.dylib __text: 3198165 3373349 -5.5%
libswiftCore.dylib __text: 2939740 3096140 -5.3%

(171KiB for macosx, 152.7KiB for iphoneos)

I'm surprised at how large this is. 43.6KiB for arities 2–6 alone seems
bad enough, but up to 171KiB for arities 2–12? Where did all that code
size come from!

Note: this is compiling as Ninja-ReleaseAssert.

Based on this, I'm inclined to submit the change with arities 2–6, but
if anyone has any idea why this results in so much code size I'd love to
hear it.

-Kevin Ballard

···

On Mon, Dec 7, 2015, at 12:32 PM, Dmitri Gribenko wrote:

On Mon, Dec 7, 2015 at 12:22 PM, Kevin Ballard <kevin@sb.org> wrote:
> On Mon, Dec 7, 2015, at 12:01 PM, Dmitri Gribenko wrote:
>
> On Mon, Dec 7, 2015 at 11:48 AM, Kevin Ballard via swift-evolution > > <swift-evolution@swift.org> wrote:
> Good question. What's the best way to measure this? File size of
> build/$target/swift-macosx-x86_64/lib/swift/macosx/libswiftCore.dylib (does
> that even include generic functions)? Or the x86_64/libswiftCore.dylib from
> the same folder (what's the difference)? Or x86_64/Swift.swiftmodule?
> Something else?

Use utils/cmpcodesize.

The swift-macosx-x86_64/lib/swift/<target>/libswiftCore.dylib dylibs
are fat ones, the dylib nested inside the architecture directory is a
regular one. Please also measure for iOS (to build those, run
build-script with -i).

> I personally don't see a point in going as high as 12 tuple elements. About
> 4 or 5 makes sense to me. Given that Swift does not have variadic generics
> right now, these long tuples have to be defined by someone manually. If one
> is defining a tuple that is that long, I'd argue that they should be using a
> custom struct instead.
>
>
> Depends on how much code size it is. I'd rather err on the side of defining
> it for a higher arity tuple than we expect people to actually use in
> practice. Just because it's probably a good idea to not point more than a
> handful of elements in a tuple doesn't mean people will actually stick to
> that, and it's surprising behavior to have == suddenly break because you
> added one more (Equatable) value to the tuple. As an example, my coworker
> recently wrote some code that uses a tuple of 7 elements (as a typedef). It
> probably should have been a struct, but I think it was originally defined
> with just 3 or 4 elements and sprouted the others as he worked on it.
> Granted, this particular tuple wouldn't actually support ==, but I'm sure
> others have written similarly long tuples.
>
> I'll probably prototype this some time today, and I can produce some
> measurements of code size at different arities (if I can figure out the best
> way to measure that).

I can see that. Definitely depends on the code size, though!

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Chris Lattner) #12

Indeed. However, this doesn’t mean that this is a good thing and that making 256-element tuples comparable is a requirement. This means that we should (someday) investigate in-place fixed-size array types, so that we can import the C constructs better.

-Chris

···

On Dec 8, 2015, at 12:10 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 7, 2015, at 5:01 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

I tend to agree with Dmitri here. Independent of the code size concern, what is the expected use-case for > 4 element tuples?

When importing structs from C, all char arrays are converted into Int8 tuples. So, it’s pretty easy to end up with a tuple with quite a lot of elements.

For example:

struct Foo {
   char bar[256];
};

becomes:

public struct Foo {
   public var bar: (Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8)
   public init()
   public init(bar: (Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8, Int8))
}

These tuples are currently rather difficult to work with.


(Dmitri Gribenko) #13

That won't work, since tuples don't conform to Comparable.

Dmitri

···

On Mon, Dec 7, 2015 at 4:06 PM, Chris Lattner <clattner@apple.com> wrote:

On Dec 7, 2015, at 3:04 PM, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

On Mon, Dec 7, 2015 at 3:01 PM, Chris Lattner via swift-evolution > <swift-evolution@swift.org> wrote:

On Dec 7, 2015, at 12:01 PM, Dmitri Gribenko via swift-evolution >> <swift-evolution@swift.org> wrote:

I personally don't see a point in going as high as 12 tuple elements.
About 4 or 5 makes sense to me. Given that Swift does not have variadic
generics right now, these long tuples have to be defined by someone
manually. If one is defining a tuple that is that long, I'd argue that they
should be using a custom struct instead.

I tend to agree with Dmitri here. Independent of the code size concern,
what is the expected use-case for > 4 element tuples?

-Chris

On the contrary, I think >4-element-tuples are useful exactly *for* the case
of custom structs. You wouldn't want the tuples themselves to be part of
your API, but if you have a custom struct with 4+ Comparable fields, you can
implement its < operator as simply "return (a1,b1,c1,d1,e1) <
(a2,b2,c2,d2,e2)”.

Sure, or:
   return (a1,b1,(c1,d1,e1)) < (a2,b2,(c2,d2,e2))

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Lily Ballard) #14

That also allocates two intermediate arrays (the inputs to zip()).

-Kevin

···

On Mon, Dec 7, 2015, at 04:11 PM, Brent Royal-Gordon via swift-evolution wrote:

> you can implement its < operator as simply "return (a1,b1,c1,d1,e1) < (a2,b2,c2,d2,e2)”.

  return zip([a1,b1,c1,d1,e1], [a2,b2,c2,d2,e2]).lazy.filter(==).first.flatMap(<) ?? false

Okay, so that wasn’t quite as easy as I thought when I started writing
the email.


(Lily Ballard) #15

I've pushed my code (no tests) as
https://github.com/kballard/swift/commit/3b61da42986689d0f26323f88a49bf7d1175c717
if anyone wants to see it.

-Kevin Ballard

···

On Mon, Dec 7, 2015, at 10:04 PM, Kevin Ballard wrote:

Code size turns out to be much higher than expected.

When implementing ==, !=, <, <=, >, and >= for tuples of arities 2–6, I
end up with a 1.4% increase in libswiftCore.dylib code size:

                                   Section Old New Percent
libswiftCore.dylib __text: 3198165 3242853 -1.4%
libswiftCore.dylib __text: 2939740 2980844 -1.4%

(or about 43.6KiB)

After increasing it to go up to arity 12, it reaches a 5.3–5.5%
increase:

                                   Section Old New Percent
libswiftCore.dylib __text: 3198165 3373349 -5.5%
libswiftCore.dylib __text: 2939740 3096140 -5.3%

(171KiB for macosx, 152.7KiB for iphoneos)

I'm surprised at how large this is. 43.6KiB for arities 2–6 alone seems
bad enough, but up to 171KiB for arities 2–12? Where did all that code
size come from!

Note: this is compiling as Ninja-ReleaseAssert.

Based on this, I'm inclined to submit the change with arities 2–6, but
if anyone has any idea why this results in so much code size I'd love to
hear it.

-Kevin Ballard

On Mon, Dec 7, 2015, at 12:32 PM, Dmitri Gribenko wrote:
> On Mon, Dec 7, 2015 at 12:22 PM, Kevin Ballard <kevin@sb.org> wrote:
> > On Mon, Dec 7, 2015, at 12:01 PM, Dmitri Gribenko wrote:
> >
> > On Mon, Dec 7, 2015 at 11:48 AM, Kevin Ballard via swift-evolution > > > <swift-evolution@swift.org> wrote:
> > Good question. What's the best way to measure this? File size of
> > build/$target/swift-macosx-x86_64/lib/swift/macosx/libswiftCore.dylib (does
> > that even include generic functions)? Or the x86_64/libswiftCore.dylib from
> > the same folder (what's the difference)? Or x86_64/Swift.swiftmodule?
> > Something else?
>
> Use utils/cmpcodesize.
>
> The swift-macosx-x86_64/lib/swift/<target>/libswiftCore.dylib dylibs
> are fat ones, the dylib nested inside the architecture directory is a
> regular one. Please also measure for iOS (to build those, run
> build-script with -i).
>
> > I personally don't see a point in going as high as 12 tuple elements. About
> > 4 or 5 makes sense to me. Given that Swift does not have variadic generics
> > right now, these long tuples have to be defined by someone manually. If one
> > is defining a tuple that is that long, I'd argue that they should be using a
> > custom struct instead.
> >
> >
> > Depends on how much code size it is. I'd rather err on the side of defining
> > it for a higher arity tuple than we expect people to actually use in
> > practice. Just because it's probably a good idea to not point more than a
> > handful of elements in a tuple doesn't mean people will actually stick to
> > that, and it's surprising behavior to have == suddenly break because you
> > added one more (Equatable) value to the tuple. As an example, my coworker
> > recently wrote some code that uses a tuple of 7 elements (as a typedef). It
> > probably should have been a struct, but I think it was originally defined
> > with just 3 or 4 elements and sprouted the others as he worked on it.
> > Granted, this particular tuple wouldn't actually support ==, but I'm sure
> > others have written similarly long tuples.
> >
> > I'll probably prototype this some time today, and I can produce some
> > measurements of code size at different arities (if I can figure out the best
> > way to measure that).
>
> I can see that. Definitely depends on the code size, though!
>
> Dmitri
>
> --
> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(plx) #16

FWIW — and without trying to address why the absolute size is what it is — at least in my experience, "generic families” like “== for tuples of length 2 , … n“ seem to require size that reliably grows as O(n^2).

On the one hand, this growth pattern doesn't actually seem *surprising* (think about it); but, on the other hand, I’d also be curious to know if the ABI changes for Swift 3 will have any significant impact on the *absolute* size of such constructs (or if other features will provide other solutions).

···

On Dec 8, 2015, at 12:04 AM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

Code size turns out to be much higher than expected.

When implementing ==, !=, <, <=, >, and >= for tuples of arities 2–6, I
end up with a 1.4% increase in libswiftCore.dylib code size:

                                  Section Old New Percent
libswiftCore.dylib __text: 3198165 3242853 -1.4%
libswiftCore.dylib __text: 2939740 2980844 -1.4%

(or about 43.6KiB)

After increasing it to go up to arity 12, it reaches a 5.3–5.5%
increase:

                                  Section Old New Percent
libswiftCore.dylib __text: 3198165 3373349 -5.5%
libswiftCore.dylib __text: 2939740 3096140 -5.3%

(171KiB for macosx, 152.7KiB for iphoneos)

I'm surprised at how large this is. 43.6KiB for arities 2–6 alone seems
bad enough, but up to 171KiB for arities 2–12? Where did all that code
size come from!

Note: this is compiling as Ninja-ReleaseAssert.

Based on this, I'm inclined to submit the change with arities 2–6, but
if anyone has any idea why this results in so much code size I'd love to
hear it.

-Kevin Ballard

On Mon, Dec 7, 2015, at 12:32 PM, Dmitri Gribenko wrote:

On Mon, Dec 7, 2015 at 12:22 PM, Kevin Ballard <kevin@sb.org> wrote:

On Mon, Dec 7, 2015, at 12:01 PM, Dmitri Gribenko wrote:

On Mon, Dec 7, 2015 at 11:48 AM, Kevin Ballard via swift-evolution >>> <swift-evolution@swift.org> wrote:
Good question. What's the best way to measure this? File size of
build/$target/swift-macosx-x86_64/lib/swift/macosx/libswiftCore.dylib (does
that even include generic functions)? Or the x86_64/libswiftCore.dylib from
the same folder (what's the difference)? Or x86_64/Swift.swiftmodule?
Something else?

Use utils/cmpcodesize.

The swift-macosx-x86_64/lib/swift/<target>/libswiftCore.dylib dylibs
are fat ones, the dylib nested inside the architecture directory is a
regular one. Please also measure for iOS (to build those, run
build-script with -i).

I personally don't see a point in going as high as 12 tuple elements. About
4 or 5 makes sense to me. Given that Swift does not have variadic generics
right now, these long tuples have to be defined by someone manually. If one
is defining a tuple that is that long, I'd argue that they should be using a
custom struct instead.

Depends on how much code size it is. I'd rather err on the side of defining
it for a higher arity tuple than we expect people to actually use in
practice. Just because it's probably a good idea to not point more than a
handful of elements in a tuple doesn't mean people will actually stick to
that, and it's surprising behavior to have == suddenly break because you
added one more (Equatable) value to the tuple. As an example, my coworker
recently wrote some code that uses a tuple of 7 elements (as a typedef). It
probably should have been a struct, but I think it was originally defined
with just 3 or 4 elements and sprouted the others as he worked on it.
Granted, this particular tuple wouldn't actually support ==, but I'm sure
others have written similarly long tuples.

I'll probably prototype this some time today, and I can produce some
measurements of code size at different arities (if I can figure out the best
way to measure that).

I can see that. Definitely depends on the code size, though!

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #17

I've submitted this proposal as https://github.com/apple/swift-evolution/pull/45

-Kevin Ballard


(Chris Lattner) #18

Ah right, someone should really fix that :-) :-)

-Chris

···

On Dec 7, 2015, at 4:08 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On the contrary, I think >4-element-tuples are useful exactly *for* the case
of custom structs. You wouldn't want the tuples themselves to be part of
your API, but if you have a custom struct with 4+ Comparable fields, you can
implement its < operator as simply "return (a1,b1,c1,d1,e1) <
(a2,b2,c2,d2,e2)”.

Sure, or:
  return (a1,b1,(c1,d1,e1)) < (a2,b2,(c2,d2,e2))

That won't work, since tuples don't conform to Comparable.


(Dmitri Gribenko) #19

And relies on all variables having the same type.

Dmitri

···

On Mon, Dec 7, 2015 at 4:12 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

On Mon, Dec 7, 2015, at 04:11 PM, Brent Royal-Gordon via swift-evolution > wrote:

> you can implement its < operator as simply "return (a1,b1,c1,d1,e1) < (a2,b2,c2,d2,e2)”.

      return zip([a1,b1,c1,d1,e1], [a2,b2,c2,d2,e2]).lazy.filter(==).first.flatMap(<) ?? false

Okay, so that wasn’t quite as easy as I thought when I started writing
the email.

That also allocates two intermediate arrays (the inputs to zip()).

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(plx) #20

If these are to be added to the standard library it seems prudent to put them in under their own names — e.g. `#<`, and then `#==` for consistency — reserving `<` for any user-defined logic.

The reason I suggest this is that at least at present, the existing method-dispatch logic seems likely to lead to unintended consequences if e.g. `<` is defined so broadly; if you can paste the below into a playground you can see the kind of non-intuitive behavior that can crop up here:

// proposed function, arity-2
func == <A:Equatable,B:Equatable> (lhs: (A,B), rhs: (A,B)) -> Bool {
  return lhs.0 == rhs.0 && lhs.1 == rhs.1
}

// proposed function, arity-2
func < <A:Comparable,B:Comparable> (lhs: (A,B), rhs: (A,B)) -> Bool {
  if lhs.0 != rhs.0 { return lhs.0 < rhs.0 }
  return lhs.1 < rhs.1
}

// concrete `<` implementation:
func < (lhs: (String,String), rhs: (String,String)) -> Bool {
  switch customComparison(lhs.0, rhs.0) {
  case .OrderedAscending: return true
  case .OrderedDescending: return false
  case .OrderedSame:
    return customComparison(lhs.1, rhs.1) == .OrderedAscending
  }
}

// helper for `<`
private func customComparison(lhs: String, _ rhs: String) -> NSComparisonResult {
  return (lhs as NSString).compare(rhs, options: [.CaseInsensitiveSearch, .NumericSearch])
}

// trouble begins here:
extension SequenceType {
  
  func extractOrderedPairs<K:Comparable,Q:Comparable>(extractor: (Self.Generator.Element) -> (K,Q)) -> [(K,Q)] {
    return self.map(extractor).sort() {
      (l:(K,Q),r:(K,Q)) -> Bool
      in
      return l < r
    }
  }
  
  func extractOrderedPairs<K,Q>(
    isOrderedBefore: ((K,Q),(K,Q)) -> Bool,
    _ extractor: (Self.Generator.Element) -> (K,Q)) -> [(K,Q)] {
      return self.map(extractor).sort(isOrderedBefore)
  }
  
}

// helper for below:
extension String {
  
  var fileNamePieces: (String,String) {
    get {
      let lastComponent = (self as NSString).lastPathComponent
      return (
        (lastComponent as NSString).stringByDeletingPathExtension,
        (lastComponent as NSString).pathExtension
      )
    }
  }
  
}

let someFileNames = ["Image.png", "Image.jpeg", "Image.bmp", "Essay1.txt", "Essay11.txt", "Essay2.txt"]

let pairsV1 = someFileNames.extractOrderedPairs() { $0.fileNamePieces }
let pairsV2 = someFileNames.extractOrderedPairs(<) { $0.fileNamePieces }
// ^ note the `<` that gets passed-in

var pairV1Mismatches = 0
for index in 0..<(pairsV1.count-1) {
  if !(pairsV1[index] < pairsV1[index + 1]) {
    print("found mismatch: \(pairsV1[index]) !< \(pairsV1[index + 1])!")
    pairV1Mismatches += 1
  }
}
pairV1Mismatches // 1

var pairV2Mismatches = 0
for index in 0..<(pairsV2.count-1) {
  if !(pairsV2[index] < pairsV2[index + 1]) {
    print("found mismatch: \(pairsV2[index]) !< \(pairsV2[index + 1])!")
    pairV2Mismatches += 1
  }
}
pairV2Mismatches // 0

// END SNIPPET

Yes this is very contrived — and hopefully not something someone would write intentionally! — and yes if you understand the various scopes and dispatch rules involved you can work out why this happens, but I don’t think it’s intuitive (and thus it’s easy to stumble upon accidentally). I also think that with additional layers of generics / protocol extensions / customized implementations / etc. involved there’ll be a few more flavors of non-intuitive outcomes one can possibly stumble into.

Whence the suggestion that if these are to go into the standard library, put them in under distinct names, rather than as e.g. `==` and `<`. (FWIW `==` is by itself less problematic, but the comparisons likely customization targets, hence my concerns).

···

On Dec 10, 2015, at 1:14 AM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

I've submitted this proposal as https://github.com/apple/swift-evolution/pull/45

-Kevin Ballard
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution