Re: [swift-evolution] [swift-users] How does "Sequence.joined" work?

[Taylor Swift via swift-evolution]

On Wed, Aug 9, 2017 at 5:54 AM, Daniel Vollmer via swift-evolution <
swift-evolution@swift.org> wrote:

>
> > On 9. Aug 2017, at 06:51, Taylor Swift via swift-users <
> swift-us...@swift.org> wrote:
> >
> > It’s possible to implement a classic red-black tree in Swift that
> performs better than a sorted Array, down to about n = 1,500 items, not n =
> 100,000 items as it claims. (Actually, heap allocators these days are good
> enough that performance is on par with Array all the way down to n = 1.)
>
> I’m not sure how that can be because you lose locality (but that probably
> depends on what operations “perform” includes). And IMO, heap allocations
> remain (and will remain) a bottleneck for small allocations.
>
> Daniel.
> ___
>
>
If the number of nodes is small, Swift’s heap allocator will actually place
then contiguously in memory, just like an Array, as long as you don’t wait
too long between calls to insert(_:). You can also write your own simple
memory allocator in Swift that’s backed by an Array which guarantees the
nodes will live near each other in memory. But that’s getting off topic lol
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [swift-users] How does "Sequence.joined" work?

[Daniel Vollmer via swift-evolution]

> On 9. Aug 2017, at 06:51, Taylor Swift via swift-users 
>  wrote:
> 
> It’s possible to implement a classic red-black tree in Swift that performs 
> better than a sorted Array, down to about n = 1,500 items, not n = 100,000 
> items as it claims. (Actually, heap allocators these days are good enough 
> that performance is on par with Array all the way down to n = 1.)

I’m not sure how that can be because you lose locality (but that probably 
depends on what operations “perform” includes). And IMO, heap allocations 
remain (and will remain) a bottleneck for small allocations.

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

Re: [swift-evolution] [swift-users] How does "Sequence.joined" work?

[Félix Cloutier via swift-evolution]

The benefit that standard library containers have over containers from other 
modules is that they're optimized as if they were part of your own module, so 
you can get the same thing by including the collection classes in your own 
executable instead of linking with the module. It's my understanding that the 
@_transparent attribute could surface to the public side with module format 
stability.

Either way, the issue of cross-module optimizations is separate from COW 
mechanics, and it was certainly not my goal to distract anyone from the main 
topic by including an after-thought reference to an algorithmically impressive 
package. The important takeaway is that COW semantics don't rely on special 
features, joined() doesn't have to go out of its way to ensure that new storage 
isn't allocated, and the one important library feature behind these containers, 
isKnownUniquelyReferenced, lives in broad daylight.

> Le 8 août 2017 à 22:56, Taylor Swift  a écrit :
> 
> 
> 
> On Wed, Aug 9, 2017 at 1:50 AM, Rob Mayoff  > wrote:
> On Tue, Aug 8, 2017 at 11:51 PM, Taylor Swift via swift-users 
> mailto:swift-us...@swift.org>> wrote:
> 
> 
> On Wed, Aug 9, 2017 at 12:29 AM, Félix Cloutier via swift-evolution 
> mailto:swift-evolution@swift.org>> wrote:
> Yes, exactly. An Array is a struct wrapper for a reference type 
> representing storage. Mutating functions first check if they own the only 
> reference to the storage using isKnownUniquelyReferenced 
> .
>  If not, they make a fresh copy before applying the mutating operation.
> 
> There's no difference for `let` arrays. Access control is enforced at 
> compile-time through Array's design: the compiler will prevent you from 
> calling `mutating` functions on `let` structs, and Array is careful to not 
> expose functionality that could modify its storage outside of `mutating` 
> functions.
> 
> There is no secret. Anyone could implement the same thing only using publicly 
> available and documented compiler features. In fact, it's been done already 
> for some very powerful collections .
> 
> This isn’t entirely true. That BTree module readme seems to contain a lot of 
> unsubstantiated hyperbole. It’s possible to implement a classic red-black 
> tree in Swift that performs better than a sorted Array, down to about n = 
> 1,500 items, not n = 100,000 items as it claims. (Actually, heap allocators 
> these days are good enough that performance is on par with Array all the way 
> down to n = 1.) Red-Black trees are slow when distributed as packages because 
> of the crossmodule optimization boundary. (This also means the BTree module 
> is much slower than Array for most reasonable n.) It’s possible to write 
> modules using compiler attributes that mitigate this slowdown (reclaiming 
> over 50% of lost performance) but it’s hacky and forces you to design your 
> libraries like the standard library (meaning: ugly underscored properties 
> everywhere and everything is public). And these features aren’t “publicly 
> available” or documented at all. 
> 
> This seems harsh. I didn't notice Félix making any claims about BTree's 
> performance. The necessary API for implementing COW is indisputably public 
> and documented:
> 
> https://developer.apple.com/documentation/swift/2429905-isknownuniquelyreferenced
>  
> 
> 
> 
> I really didn’t mean it to be harsh (sorry if it sounded that way 🙁), it’s 
> just that people tend to be overly optimistic about the performance that can 
> be achieved with custom Collection packages. It’s true that you can imitate 
> the functionality of stdlib Collection types with public and documented Swift 
> features, but such custom Collections (when distributed as packages) are 
> almost never effective at improving an application’s performance due to the 
> huge constant factor of cross module calls, unless the library author was 
> willing to make use of undocumented compiler features.
> 

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

Re: [swift-evolution] [swift-users] How does "Sequence.joined" work?

[Taylor Swift via swift-evolution]

On Wed, Aug 9, 2017 at 1:50 AM, Rob Mayoff  wrote:

> On Tue, Aug 8, 2017 at 11:51 PM, Taylor Swift via swift-users <
> swift-us...@swift.org> wrote:
>
>>
>>
>> On Wed, Aug 9, 2017 at 12:29 AM, Félix Cloutier via swift-evolution <
>> swift-evolution@swift.org> wrote:
>>
>>> Yes, exactly. An Array is a struct wrapper for a reference type
>>> representing storage. Mutating functions first check if they own the only
>>> reference to the storage using isKnownUniquelyReferenced
>>> .
>>> If not, they make a fresh copy before applying the mutating operation.
>>>
>>> There's no difference for `let` arrays. Access control is enforced at
>>> compile-time through Array's design: the compiler will prevent you from
>>> calling `mutating` functions on `let` structs, and Array is careful to not
>>> expose functionality that could modify its storage outside of `mutating`
>>> functions.
>>>
>>> There is no secret. Anyone could implement the same thing only using
>>> publicly available and documented compiler features. In fact, it's been
>>> done already for some very powerful collections
>>> .
>>>
>>
>> This isn’t entirely true. That BTree module readme seems to contain a lot
>> of unsubstantiated hyperbole. It’s possible to implement a classic
>> red-black tree in Swift that performs better than a sorted Array, down
>> to about *n* = 1,500 items, not *n* = *100,000* items as it claims.
>> (Actually, heap allocators these days are good enough that performance is
>> on par with Array all the way down to *n* = 1.) Red-Black trees are slow
>> when *distributed* as packages because of the crossmodule optimization
>> boundary. (This also means the BTree module is much slower than Array
>> for most reasonable *n*.) It’s possible to write modules using compiler
>> attributes that mitigate this slowdown (reclaiming over 50% of lost
>> performance) but it’s hacky and forces you to design your libraries like
>> the standard library (meaning: ugly underscored properties everywhere and
>> everything is public). And these features aren’t “publicly available” or
>> documented at all.
>>
>
> This seems harsh. I didn't notice Félix making any claims about BTree's
> performance. The necessary API for implementing COW is indisputably public
> and documented:
>
> https://developer.apple.com/documentation/swift/2429905-
> isknownuniquelyreferenced
>
>
I really didn’t mean it to be harsh (sorry if it sounded that way 🙁), it’s
just that people tend to be overly optimistic about the performance that
can be achieved with custom Collection packages. It’s true that you can
imitate the *functionality* of stdlib Collection types with public and
documented Swift features, but such custom Collections (when distributed as
packages) are almost never effective at improving an application’s
performance due to the huge constant factor of cross module calls, unless
the library author was willing to make use of undocumented compiler
features.
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [swift-users] How does "Sequence.joined" work?

[Rob Mayoff via swift-evolution]

On Tue, Aug 8, 2017 at 11:51 PM, Taylor Swift via swift-users <
swift-us...@swift.org> wrote:

>
>
> On Wed, Aug 9, 2017 at 12:29 AM, Félix Cloutier via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>> Yes, exactly. An Array is a struct wrapper for a reference type
>> representing storage. Mutating functions first check if they own the only
>> reference to the storage using isKnownUniquelyReferenced
>> .
>> If not, they make a fresh copy before applying the mutating operation.
>>
>> There's no difference for `let` arrays. Access control is enforced at
>> compile-time through Array's design: the compiler will prevent you from
>> calling `mutating` functions on `let` structs, and Array is careful to not
>> expose functionality that could modify its storage outside of `mutating`
>> functions.
>>
>> There is no secret. Anyone could implement the same thing only using
>> publicly available and documented compiler features. In fact, it's been
>> done already for some very powerful collections
>> .
>>
>
> This isn’t entirely true. That BTree module readme seems to contain a lot
> of unsubstantiated hyperbole. It’s possible to implement a classic
> red-black tree in Swift that performs better than a sorted Array, down to
> about *n* = 1,500 items, not *n* = *100,000* items as it claims.
> (Actually, heap allocators these days are good enough that performance is
> on par with Array all the way down to *n* = 1.) Red-Black trees are slow
> when *distributed* as packages because of the crossmodule optimization
> boundary. (This also means the BTree module is much slower than Array for
> most reasonable *n*.) It’s possible to write modules using compiler
> attributes that mitigate this slowdown (reclaiming over 50% of lost
> performance) but it’s hacky and forces you to design your libraries like
> the standard library (meaning: ugly underscored properties everywhere and
> everything is public). And these features aren’t “publicly available” or
> documented at all.
>

This seems harsh. I didn't notice Félix making any claims about BTree's
performance. The necessary API for implementing COW is indisputably public
and documented:

https://developer.apple.com/documentation/swift/2429905-isknownuniquelyreferenced
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution