Not true at all. Seriously not true. I don't think you know how hash tables work. Try your experiment with 1000 strings. But this is getting too off-topic already.
I love Set, but I don't think a special literal syntax for them is justified. If Swift had no type inference, I might see that differently.
6 Likes
Of course we can increase number of elements up to infinity, at some point it won't be true (probably). I don't know based on what you assume my understanding.
I'd argue that adding more syntax to promote sets is relatable to how actually useful sets are at larger scale. So just out of curiosity I did test from 10 to 1 million strings (randomly generated 128 symbols each). Then try inserting existing and new values to them in non-duplicating way:
Test functions
func test(array: inout [String], existingValue: String) {
if !array.contains(existingValue) {
array.append(existingValue)
}
let newValue = "" // omitted actual string
if !array.contains(newValue) {
array.append(newValue)
}
}
func test(set: inout Set<String>, existingValue: String) {
set.insert(existingValue)
let newValue = "" // omitted actual string
set.insert(newValue)
}
At the 1 million values array is still faster by huge amount on simple non-duplicating insertion:
Array: 0.024993896484375s, Set: 0.16235995292663574s
I wasn't aware that this is actually possible. Especially the type inference is nice. This for me is good enough.
1 Like
I didn’t as well until looked at previous topic, so thanks to @crontab for digging it up
That does not sound right. Please check that your code is measuring what you think it is measuring.
A million random lookups(+appends) into an unsorted Array<String> are nowhere near the performance of a Set<String>'s insert method -- it's not even close.
Benchmark code
import CollectionsBenchmark
var benchmark = Benchmark(title: "Collection Benchmarks")
let someLatinSymbols: [UnicodeScalar] = [
0x20 ..< 0x7f,
0xa1 ..< 0xad,
0xae ..< 0x2af,
0x300 ..< 0x370,
0x1e00 ..< 0x1eff,
].flatMap {
$0.map { UnicodeScalar($0)! }
}
extension UnicodeScalar {
static func randomLatin(using rng: inout some RandomNumberGenerator) -> Self {
someLatinSymbols.randomElement(using: &rng)!
}
}
extension String.UnicodeScalarView {
static func randomLatin(count: Int, using rng: inout some RandomNumberGenerator) -> Self {
var result = String.UnicodeScalarView()
for _ in 0 ..< count {
result.append(UnicodeScalar.randomLatin(using: &rng))
}
return result
}
}
extension [String] {
static func randomLatin(
count: Int,
using rng: inout some RandomNumberGenerator
) -> Self {
var result: [String] = []
result.reserveCapacity(count)
for _ in 0 ..< count {
result.append(String(String.UnicodeScalarView.randomLatin(count: 128, using: &rng)))
}
return result
}
}
benchmark.registerInputGenerator(for: [String].self) { count in
var rng = SystemRandomNumberGenerator()
return [String].randomLatin(count: count, using: &rng)
}
benchmark.addSimple(
title: "Input generation",
input: Int.self
) { count in
var rng = SystemRandomNumberGenerator()
blackHole([String].randomLatin(count: count, using: &rng))
}
benchmark.addSimple(
title: "Array<String>",
input: [String].self
) { input in
var result: [String] = []
for string in input {
if !result.contains(string) {
result.append(string)
}
}
blackHole(result)
}
benchmark.addSimple(
title: "Set<String>",
input: [String].self
) { input in
var result: Set<String> = []
for string in input {
result.insert(string)
}
blackHole(result)
}
benchmark.main()
Results:
Note that the Array results cut off at 32k input strings; this is because I lost patience waiting for its calculations to finish. Set managed to work through 1 million items before I grew tired of waiting.
The chart above shows overall execution time for the entire loop, on a linear scale. For reference, here is a chart with the same data, but displaying average per-element processing time on a log-log scale:
The linear chart is overemphasizing data at the high end. This log-log chart gives a far better picture of how these algorithms behave at every order of magnitude.
(I'm generating my strings by selecting 128 random latin(ish) Unicode scalars, which gives a big advantage to Array -- for this data, String.== is typically able to give a false result up to a few hundred times faster than what it takes to hash them. In both cases, execution time is very much dominated by String operations. (Hashing a String costs about half as much time as the worst case of comparing two String instances that happen to be equal -- most of the time is spent on Unicode normalization.)
Note how Set's behavior remains nice and flat no matter how large it gets -- for this hashing/==-dominated input, inserting into an empty set takes about the same time as inserting into one that holds a million items. Array.contains costs time proportional to the size of the entire array; while it starts with a huge initial advantage, it has no chance against Set.
23 Likes
Thanks for such detailed test, to be honest I was suspicious that on 1 million array performs better, maybe my test too synthetic, of just was for a bit different case as I simply checked how long it will take to insert new and existing elements into them, not build from the scratch.
Still, it holds for initial statement that on a small data sizes arrays are winning in performance.
I’m not advertising to replace sets with array at this level, just that it is still specific data structure to solve certain tasks, that doesn’t need specific literal syntax to make it use more often
You could say the same about dictionaries. Why use dictionaries when there are arrays and linear search? I bet small dictionaries are slower than arrays and yet everybody uses them whenever they think in terms of mapping A to B. Dictionaries are chosen over arrays by default in any such case, I argue, because they are first class citizens in the language.
1 Like
one day i hope OrderedDictionary will finally graduate. i keep running into bugs (or more common, non-deterministic serialization output) in libraries because the author thought they could get away with using a standard Dictionary, and it’s not hard for me to understand why. swift-collections is an old and decorated repo with a long history that takes far too long for SwiftPM to clone from anywhere that’s not a Bay Area corporate network, and that pushes people to avoid depending on it if possible, with all the predictable consequences. the incentives feel all wrong here.
6 Likes
Without getting into the merits of arrays vs sets, I think with the proposed syntax it would be very easy to miss the colon when reading the code and accidentally mistake a set for an array:
let daysOfWeek = :[“Monday”, “Tuesday”, “Wednesday”]
let daysOfWeek = [“Monday”, “Tuesday”, “Wednesday”]
In isolation, the difference is more obvious, but in the context of a property in a type declaration or a local variable in a function, I think it can easily be misread as an array.
As another poster had mentioned, using element type inference with the existing literal notation is fairly concise already, but it's very clear that a Set is being created:
let daysOfWeek : Set = [“Monday”, “Tuesday”, “Wednesday”]
Yes, I think the argument could be made that ‘array literal’ is a bit of a misnomer. Its general case is a ‘list literal’ notation that any type can adopt when initializing with a list of elements makes sense. If no type information is present, it defaults to array, but it is intended for use by various types.
Thought of that way, I think it would be strange to introduce a second style of ‘list literal’ for the sole purpose of having a different default type.
It also raises the question, should you be able to use a set literal everywhere you can use an array literal as long as the type was explicit?
For example, would this be expected to be valid?
let daysOfWeek : Array = :[“Monday”, “Tuesday”, “Wednesday"]
Would a type that currently implements ExpressibleByArrayLiteral also be expected to implement a new ExpressibleBySetLiteral protocol to be a good citizen?
If the answer to these is yes, I think that adds a good deal of complexity to enable a slightly shorter way to declare sets with a literal. If the answer is no, I think it is really odd to add a literal notation that can only be used with one type. [1]
There is the
nilliteral which is meant to be used only with optionals, but that is a much more fundamental language feature than sets. ↩︎
8 Likes
No, because Set doesn't guarantee the order of elements. The initialization you showed might create an impression that the array will be initialized with elements in that order, so I'd say array constructors should not accept sets.
Certain things in C-like syntax may be easy to miss, e.g. ! in expressions. In fact I'd argue that the case of :[...] is a less visually ambiguous one compared to the ! operator.
I've been following this thread for a little bit, but to be honest, I'm not sure I'm seeing a new set-literal syntax giving us a significant-enough advantage over the existing array-literal syntax that we already have. Theoretically, warning about duplicate elements in the literal would be nice, but in order for the compiler to do this, it needs to have static knowledge about equatability and hashability for elements in that set, which means that:
- That knowledge needs to be hard-coded into the compiler; this is limited to stdlib types, but even of those types, very few types warrant static inclusion into the compiler itself
- The elements need to be statically defined in-line in the set (e.g., can't be variable references)
i.e., you're only really likely to get this benefit for basic sets of [U]Int*/Float/Double/Strings.
// `MyIntType: ExpressibleByIntegerLiteral`, but the compiler
// has no knowledge of `MyIntType.==` and `MyIntType.has(into:)`
// so it can't warn
let a: Set<MyIntType> = :[1, 2, 1, 3] // oops
// The compiler knows about `String`, but attempting to follow
// variable definitions is a quickly-losing war
let myStr = "hi"
let b: Set<String> = :["hi", myStr, "hello"] // oops
// Theoretically, this _could_ work if all of the requisite info
// is hard-coded into the compiler, but type-checking alone for
// deeply-nested literals is already really expensive
let c: Set<Dictionary<String, Set<Array<String>>>> = :[
["s1" : :[["a", "b"], ["c"]]],
["s2" : :[["c"], ["d", "e"]]],
["s3" : :[[]],
["s4" : :[["z"]],
["s1" : :[["a", "b"], ["c"]]],
] // oops
Is there another benefit I'm not seeing here?
5 Likes
Yes and for years there has been a steady stream of forum threads by people who find the ! operator easy to miss, pitching various solutions. The current one is here.
Why would it be a good thing to proactively introduce a new easy-to-miss syntax?
2 Likes
So, by that logic though, this also would not be allowed:
let daysOfWeek : OrderedSet = :[“Monday”, “Tuesday”, “Wednesday"]
It seems odd you would not be able to use a set literal to create an ordered set, especially since the literal itself is not a set, there is a clear order to the elements.
2 Likes
As a user I wouldn't worry about the compiler's ability to detect duplicates at compile time since inserting duplicates is allowed at run time anyway, i.e. it is not an error for sets in general.
To be honest I don't quite understand what the problem is here. In fact the type of the literal above could be inferred (without type annotation) if Swift had set literals, and it's probably the biggest advantage of having them.
Fair point, but I think the compiler could make it work just for the sake of consistency, i.e. ordered set is still a set.
Yes, but by what mechanism? All other literals have an ExpressibleByXXXLiteral protocol that is implemented by types that can be initialized with that kind of literal.
Are you proposing that the set literal would have an entirely different mechanism from all other literals?
If that is the case, then since OrderedSet is not in the standard library, it sounds like the compiler would need to hard code that particular type. That also precludes someone from using the set literal syntax with something like a Swift version of NSCountedSet from Foundation.
1 Like
To be clear, are you saying that as a user,
- You don't mind if the compiler isn't able to warn about duplicate elements,
- You don't expect the compiler to try to warn about duplicate elements, or
- Something else?
The above code already works today, as-is, if you drop replace :[ with [. I'm trying to get a sense of the proposed benefit of introducing new syntax. There is a cost to introducing new syntax (and likely a new ExpressibleBySetLiteral protocol), and the question is whether the benefit outweighs that cost.
If we see the benefit as "the compiler can warn about duplicate elements inside :[...]" (presumably because duplicate elements are not intentional in a set literal), then the question is whether we would see the benefit often enough to offset that cost.
If we don't intend to have the compiler check for duplicate elements at all (since it's not a runtime error), then there'd be no difference between :[...] and [...], and I don't see the justification for introducing the change.
As I see it, the main benefits would be:
- type inference, i.e. in your gigantic nested initialization you may omit the type declaration, something that's impossible without set literals
- as a hypothesis, you will use sets more often since now you have a shortcut
- sets becoming first-class citizens and used more often means safer and more reliable (as a bonus also possibly faster) code due to enforced exclusivity where appropriate; sets also convey your intention better
It's actually completely possible today, at any level of nesting, without a type annotation as such. It's spelled [1, 2, 3] as Set. You can use this type coercion notation for any kind of literal (for example: 42 as Double, "Foo" as StaticString).
9 Likes