4 ms·
Alternate proposal: in-order iterating over a set is what's causing the slowdown. let nanobuild = Swimsuit.nanotime() { for i in 1...size {
by mywittyname 10y ago
Alternate proposal: in-order iterating over a set is what's causing the slowdown.
let nanobuild = Swimsuit.nanotime() {
for i in 1...size {
d.insert(i)
}
}
vs.
let nanocopy = Swimsuit.nanotime() {
for i in d {
dcopy.insert(i)
}
}
Clearly the biggest difference between the code is how he's getting the values to insert. If he changed the later loop from for i in d, to the original for i in 1...size, I suspect he'd see equivalent performance.
This code does not demonstrate the issues with HashMaps outlined in the article. I'm not familiar with Swift's libraries, but I bet it has a load factor parameter, the author could just set that to >1.0 and load a bunch of data into it, then the code would show what the article claims.
- jwatte 10y agoTo be fair, my hash table implementations always keep a nth-key iterator cache, to make the default case of 0..n fast. If the standard library doesn't do this, I'd call that a miss in implementation.
- Gankro 10y agoThere's a load factor in Swift's Dictionary but it's hardcoded. Same for Rust. (I've maintained both implementations) I assure you the bug is as described. I wrote it up the initial bug report and what needed to be done to mitigate it here [1]. Most critically, my analysis on different sizes demonstrates that it's ultimately a consequence of how hashes are modulo truncated. Increasing the size without increasing capacity (higher load) can in fact decrease execution time. [1] https://bugs.swift.org/plugins/servlet/mobile#issue/SR-3268 https://bugs.swift.org/plugins/servlet/mobile#issue/SR-3268 (sorry this comment is poorly written, my phone was about to die; read the issue for a proper discussion)