Compiler Optimization of Optional-returning Functions followed by '!'


(Jon Hull) #1

Hi all,

I would like to propose an optimization to the compiler where, when a call to an optional-returning function is immediately followed by a ‘!’, we allow the compiler to generate an alternate version of the function where a trap replaces 'return nil’ and the function returns a non-optional result. This would save the build-up and tear-down cost of the optional.

Is this possible?

The main reason I would want this is to be able to later propose moving our default array index handling to a safer optional-returning version. I know that a safe variant is on the horizon, but defaults really matter… especially with newcomers to the language. Array indexing should return an optional, forcing the programmer to deal with an out-of-bounds case appropriately. Where the current behavior is desired, the access is immediately followed by a ‘!’ indicating the potential crash-point explicitly in code. Migration would simply add a ‘!’ after every array subscript access. The above proposal is meant to mitigate any performance issues from the change, because the generated function for the cases followed by ‘!’ would be identical to the current version.

It should also have a good effect on runtime performance for any place in code where a function result is immediately force unwrapped...

Thanks,
Jon


(Joe Groff) #2

There are other reasons collection indexing doesn't return Optional besides performance; there have been a number of threads on this topic in the past already. I'd be surprised if building an optional were really all that expensive to begin with—the binary representation of '.some(x)' inside an Optional is always the same as 'x', with at most a zero byte tacked on the end. Checking an optional in turn only needs to check for an invalid representation of x (like a null pointer) or check that that extra bit is unset.

-Joe

···

On Jan 19, 2017, at 2:17 PM, Jonathan Hull via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

I would like to propose an optimization to the compiler where, when a call to an optional-returning function is immediately followed by a ‘!’, we allow the compiler to generate an alternate version of the function where a trap replaces 'return nil’ and the function returns a non-optional result. This would save the build-up and tear-down cost of the optional.

Is this possible?

The main reason I would want this is to be able to later propose moving our default array index handling to a safer optional-returning version. I know that a safe variant is on the horizon, but defaults really matter… especially with newcomers to the language. Array indexing should return an optional, forcing the programmer to deal with an out-of-bounds case appropriately. Where the current behavior is desired, the access is immediately followed by a ‘!’ indicating the potential crash-point explicitly in code. Migration would simply add a ‘!’ after every array subscript access. The above proposal is meant to mitigate any performance issues from the change, because the generated function for the cases followed by ‘!’ would be identical to the current version.

It should also have a good effect on runtime performance for any place in code where a function result is immediately force unwrapped...


(Tony Allevato) #3

Hi all,

I would like to propose an optimization to the compiler where, when a call
to an optional-returning function is immediately followed by a ‘!’, we
allow the compiler to generate an alternate version of the function where a
trap replaces 'return nil’ and the function returns a non-optional result.
This would save the build-up and tear-down cost of the optional.

Is this possible?

The main reason I would want this is to be able to later propose moving
our default array index handling to a safer optional-returning version. I
know that a safe variant is on the horizon, but defaults really matter…
especially with newcomers to the language. Array indexing should return an
optional, forcing the programmer to deal with an out-of-bounds case
appropriately.

I've heard it argued on this list before, and I agree, that in most cases
(i.e., those not involving user input, which should be sanity checked
separately anyway) an out-of-bounds array index is essentially a
precondition failure, not a legal program state that users need to
proactively test.

I personally adopt a style where I try to avoid the use of ! unwraps as
much as possible, so incurring those on every array access wouldn't improve
the quality of my code.

In a world where we have an abstract index model, iterators, and for-each
loops, is the problem of people accidentally accessing out-of-bounds
elements really as severe as it used to be, to the point that we shouldn't
simply require them to check the bounds before such operations where it
might occur?

That being said, I like the idea of the optimization you describe above *in
general*, but I would hope it wouldn't require a fully alternate version of
the function to be generated—maybe the optimizer could handle it more
generally. I haven't personally looked into it, but what's the overhead
incurred by the optional build-up/tear-down?

···

On Thu, Jan 19, 2017 at 2:17 PM Jonathan Hull via swift-evolution < swift-evolution@swift.org> wrote:

Where the current behavior is desired, the access is immediately followed
by a ‘!’ indicating the potential crash-point explicitly in code.
Migration would simply add a ‘!’ after every array subscript access. The
above proposal is meant to mitigate any performance issues from the change,
because the generated function for the cases followed by ‘!’ would be
identical to the current version.

It should also have a good effect on runtime performance for any place in
code where a function result is immediately force unwrapped...

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


(Xiaodi Wu) #4

>
> Hi all,
>
> I would like to propose an optimization to the compiler where, when a
call to an optional-returning function is immediately followed by a ‘!’, we
allow the compiler to generate an alternate version of the function where a
trap replaces 'return nil’ and the function returns a non-optional result.
This would save the build-up and tear-down cost of the optional.
>
> Is this possible?
>
>
> The main reason I would want this is to be able to later propose moving
our default array index handling to a safer optional-returning version. I
know that a safe variant is on the horizon, but defaults really matter…
especially with newcomers to the language. Array indexing should return an
optional, forcing the programmer to deal with an out-of-bounds case
appropriately. Where the current behavior is desired, the access is
immediately followed by a ‘!’ indicating the potential crash-point
explicitly in code. Migration would simply add a ‘!’ after every array
subscript access. The above proposal is meant to mitigate any performance
issues from the change, because the generated function for the cases
followed by ‘!’ would be identical to the current version.
>
> It should also have a good effect on runtime performance for any place
in code where a function result is immediately force unwrapped...

There are other reasons collection indexing doesn't return Optional
besides performance; there have been a number of threads on this topic in
the past already. I'd be surprised if building an optional were really all
that expensive to begin with—the binary representation of '.some(x)' inside
an Optional is always the same as 'x', with at most a zero byte tacked on
the end. Checking an optional in turn only needs to check for an invalid
representation of x (like a null pointer) or check that that extra bit is
unset.

All other things being equal, it's hard to come out _against_ making code
run faster.

But as Joe already touched on already, it's certainly not the case that
indexing traps _only_ because of performance. This was touched on in the
extensive discussions on "lenient" indexing. As here, some were calling
that proposed feature "safe" indexing, and it was pointed out to them (by
Dave A, I think?) that this use of the term "safe" misunderstands the kind
of safety that Swift has prioritized. When you write `array[10]`, it's not
saying "I don't know how many elements there are, try and find the
eleventh"; it's saying "I _know_ there are at least eleven elements, so get
me that one."

When you _know_ that there are 11 elements, but in fact there are only 10,
then something has gone badly wrong (because `array.count` doesn't
lie). Trapping on a logic error is safe: an undefined state cannot do any
more harm. Continuing on a logic error is unsafe. As Swift chooses safety
by default, the default must be the current behavior.

For those times when you _don't_ know how many elements there are, don't
care, and for some reason can't be bothered to get `array.count`, but you
need to explicitly access an element by its index *and* have a useful
fallback value, IMO it's reasonable to have an alternative subscript like
the proposed `array[lenient: 10]`. But with facilities like `for...in`,
`map`, etc., and others like `count` and `enumerated`, it's hard to argue
that it's nearly as common a scenario as those where you are given a
known-good index.

Alternatively, consider the effect of your proposed use case on a practical
level. You have two arrays of known equal length and wish to swap every
other element (this itself may be uncommon, but having two arrays and a
task that involves both is, I'm sure you'll agree, very common):

for i in stride(from: 0, to: a.count, by: 2) {
  swap(&a[i], &b[i])
}

Even with no performance penalty, it would look much uglier with:

for i in stride(from: 0, to: a.count, by: 2) {
  swap(&a[i]!, &b[i]!)
}

// Actually, would this even be possible? At first blush,
// it seems like it might not, since &a[i] once unwrapped
// would have to be a _copy_ of the original, and a
// compiler optimization must not change the _semantics_
// of `!`, only its performance.

Littering `!` everywhere is not conducive to readable code.

···

On Thu, Jan 19, 2017 at 4:35 PM, Joe Groff via swift-evolution < swift-evolution@swift.org> wrote:

> On Jan 19, 2017, at 2:17 PM, Jonathan Hull via swift-evolution < > swift-evolution@swift.org> wrote:

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


(Russ Bishop) #5

I’m not sure why people keep asking for this; the extension is trivial so anyone who wants it can have it:

extension Collection
{
    subscript(ifExists index: Index) -> Iterator.Element? {
        guard index < self.endIndex else { return nil }
        return self[index]
    }
}

// won't assert!
myArray[ifExists: 42]

Russ

···

On Jan 19, 2017, at 4:17 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

For those times when you _don't_ know how many elements there are, don't care, and for some reason can't be bothered to get `array.count`, but you need to explicitly access an element by its index *and* have a useful fallback value, IMO it's reasonable to have an alternative subscript like the proposed `array[lenient: 10]`. But with facilities like `for...in`, `map`, etc., and others like `count` and `enumerated`, it's hard to argue that it's nearly as common a scenario as those where you are given a known-good index.


(Pierre Monod-Broca) #6

It just occurs to me that you can't put none<T> in a [T], so on optional subscript would only be get and we would need the current subscript beside anyway.

I have no particular opinion on the main subject, I wonder what the order of magnitude would be that optimisation.

Pierre

···

Le 20 janv. 2017 à 07:41, Russ Bishop via swift-evolution <swift-evolution@swift.org> a écrit :

On Jan 19, 2017, at 4:17 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

For those times when you _don't_ know how many elements there are, don't care, and for some reason can't be bothered to get `array.count`, but you need to explicitly access an element by its index *and* have a useful fallback value, IMO it's reasonable to have an alternative subscript like the proposed `array[lenient: 10]`. But with facilities like `for...in`, `map`, etc., and others like `count` and `enumerated`, it's hard to argue that it's nearly as common a scenario as those where you are given a known-good index.

I’m not sure why people keep asking for this; the extension is trivial so anyone who wants it can have it:

extension Collection
{
    subscript(ifExists index: Index) -> Iterator.Element? {
        guard index < self.endIndex else { return nil }
        return self[index]
    }
}

// won't assert!
myArray[ifExists: 42]

Russ

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


(Karl) #7

Amen!

Although technically, you should do (startIndex..<endIndex).contains(index) — what about if somebody asked for something lower than startIndex? But yeah, it’s such a trivial extension.

Asking a Collection for an item at a specific index which does not exist is, let’s be clear, a nonsense operation.

let myArray = [] // empty array
// would all be valid
myArray[0]
myArray[-1]
myArray[Int64.max]

I think that’s ludicrous. It completely flies in the face of our current indexing/collection model, which is this: items are retrieved by an associated Index type, and the various types of collection define how you are able to actually get one of those indexes:

- Collection: Provides startIndex/endIndex anchors, can only get the Index after an existing Index
- BidirectionalCollection: Can also get the Index before an existing Index
- RandomAccessCollection: Can also get the Index at an arbitrary offset from an existing Index

So essentially what is being proposed is that you can subscript Collections by invalid Indexes (maybe an Index from another instance of that Collection, or one which in other ways violates the axioms of the indexing model). Not only that, but everything which uses an Index (e.g. suffix(from:)) would have to also return an Optional to account for a nonsense index being given.

Also, let’s not beat around the bush: this isn’t a general Collection feature, this is only for Array (because its Index is not an opaque type — if it was, invalid indexes would be even more obviously a result of your own bad logic).

So basically this is being driven by programmers who are **abusing** Array and its indexes. If Array.Index was an opaque type, none of this would be possible. For your convenience, the index was made an integer, but that doesn’t mean you can just pass in *any* integer. You still need to abide by the general Collection indexing model.

- Karl

···

On 20 Jan 2017, at 07:41, Russ Bishop via swift-evolution <swift-evolution@swift.org> wrote:

On Jan 19, 2017, at 4:17 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

For those times when you _don't_ know how many elements there are, don't care, and for some reason can't be bothered to get `array.count`, but you need to explicitly access an element by its index *and* have a useful fallback value, IMO it's reasonable to have an alternative subscript like the proposed `array[lenient: 10]`. But with facilities like `for...in`, `map`, etc., and others like `count` and `enumerated`, it's hard to argue that it's nearly as common a scenario as those where you are given a known-good index.

I’m not sure why people keep asking for this; the extension is trivial so anyone who wants it can have it:

extension Collection
{
    subscript(ifExists index: Index) -> Iterator.Element? {
        guard index < self.endIndex else { return nil }
        return self[index]
    }
}

// won't assert!
myArray[ifExists: 42]

Russ

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