Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[SR-3334] for loop over array.reversed() takes much longer than over array (seems to still be in linear time with large constant factor) #45922

Closed
weissi opened this issue Dec 5, 2016 · 8 comments
Closed

[SR-3334] for loop over array.reversed() takes much longer than over array (seems to still be in linear time with large constant factor) #45922

weissi opened this issue Dec 5, 2016 · 8 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. performance standard library Area: Standard library umbrella

Comments

@weissi
Copy link
Member

weissi commented Dec 5, 2016

Previous ID SR-3334
Radar None
Original Reporter @weissi
Type Bug
Status Resolved
Resolution Done

Attachment: Download

Additional Detail from JIRA
Votes 0
Component/s Standard Library
Labels Bug, Performance
Assignee djwbrown (JIRA)
Priority Medium

md5: 3ae4c12e2c889a3ec086b41d13e1f466

Issue Description:

I have this little test program

import Darwin

func main() {
    let x = Array(repeating: 1, count: 400_000_000)
    print("\(time(nil)): array created")
    let y = x.reversed()
    print("\(time(nil)): reversed() called")
    var z = 0
    for f in x {
        z += f
    }
    print("\(time(nil)): interated forwards")
    for f in y {
        z += f
    }
    print("\(time(nil)): iterated backwards")
    print("z = \(z)")
}

main()

and the output of time swift test4.swift is:

$ time swift  /tmp/test4.swift
1480955692: array created
1480955692: reversed() called
1480955695: interated forwards
1480955883: iterated backwards
z = 800000000

real    3m13.319s
user    3m9.181s
sys 0m3.145s

so going forwards over 400M things in the array takes about 3s on my machine, going over it backwards takes about 188s. It seems to be a linear cost of iterating over it forwards and backwards with a huge constant factor for backwards 🙁. Doesn't seem to happen with optimised builds.

Swift version is

Apple Swift version 3.0.1 (swiftlang-800.0.58.6 clang-800.0.42.1)
Target: x86_64-apple-macosx10.9
@belkadan
Copy link
Contributor

belkadan commented Dec 5, 2016

Starting with the stdlib, although it may turn out to be a missed optimization the compiler should be doing.

@swift-ci
Copy link
Collaborator

swift-ci commented Dec 8, 2016

Comment by Alexis Beingessner (JIRA)

60x overhead sounds about right for all the generic abstractions that ReversedRandomAccessCollection churns through. That's truly awful, but I have no idea how to get around that given the index-based programming model that the standard library has.

Note that about 25% of this time is spent in swift_bridgeObjectRetain, so maybe this could be fixed by better ARC optimizations?

@belkadan
Copy link
Contributor

belkadan commented Dec 8, 2016

I think it's reasonable to say the compiler should be able to get through the abstraction of ReversedRandomAccessCollection all the way down to a for-loop, but whether that means simplifying the type or changing the compiler or both I don't know.

@swift-ci
Copy link
Collaborator

Comment by Dylan Brown (JIRA)

I was able to reproduce this in Swift version 3.1-dev. The -O flag solves it, but it seems like it would be a surprisingly severe penalty for the average user, if compiled without the optimization flag.

@swift-ci
Copy link
Collaborator

Comment by Dylan Brown (JIRA)

I added some code to SwiftOnoneSupport.swift which is now generating symbols for several prespecialized IndexingIterator.next() on a ReversedRandomAccessCollection of Int, Int8, Int16, etc. I believe plain Swift Int type is shown below:
sym.TTSgq5GVs30ReversedRandomAccessCollectionGSaSiGS_GSaSis14_IndexableBases_TFVs16IndexingIterator4nextfT_GSqwx8_Element
Unfortunately, Instruments shows that I'm still linking to libswiftCore.dylib rather than libswiftSwiftOnoneSupport.dylib, and spending most of my time in a call to an unspecialized IndexingIterator.next(). I also added ReversedCollection and ReversedRandomAccessCollection to the whitelist in lib/SILOptimizer/Utils/Generics.cpp.

I will keep working on it, but does anyone have a suggestion?

@swift-ci
Copy link
Collaborator

Comment by Dylan Brown (JIRA)

I have a fix ready on default optimization level -Onone.

dylan$ time ./reversed_array
real 0m4.714s
user 0m4.656s
sys 0m0.046s

dylan$ time ./reversed_array_new
real 0m0.249s
user 0m0.214s
sys 0m0.031s

See PR #6496 #6496

@swift-ci
Copy link
Collaborator

swift-ci commented Jan 6, 2017

Comment by Dylan Brown (JIRA)

Old PR #6496 closed.
Please see benchmark PR #6512, #6512
Please see new fix PR #6582, #6582

@swift-ci
Copy link
Collaborator

Comment by Dylan Brown (JIRA)

With Swift version 3.1, the provided test program outputs the following.

1500004081: array created
1500004081: reversed() called
1500004083: interated forwards
1500004085: iterated backwards
z = 800000000

Note that forward and reversed iteration take approximately 2 seconds each. Also, happy 1_500_000_000 seconds!

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. performance standard library Area: Standard library umbrella
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@weissi @belkadan @swift-ci