Skip to content

O(1) time {Vec,VecDeque}::truncate for trivial drop types and VecDeque::truncate_front #62408

@orlp

Description

@orlp
Contributor

Currently both Vecs and VecDeques truncate implementations just call pop_back() in a loop. When std::mem::needs_drop::<T>() is false this is pretty inefficient.

Now LLVM does optimize away the loop on -O3 for Vec::truncate, however this does not happen for VecDeque::truncate.

Despite previous complaints, this exact issue has been wont-fix'd under the unofficial policy that we do not include -O0 exclusive optimizations in rust.

I would like to re-open the discussion with the following observations, in the hope that @alexcrichton might change his mind:

  1. No matter the optimization level, the optimization never happens for VecDeque::truncate.

  2. The optimization is not just a constant factor speedup, it's an asymptotic speedup changing an O(n) time operation into O(1) where O(1) could easily be guaranteed. The difference in speed could literally be several orders of magnitude.

  3. The optimizer is always fickle and ever-changing. Someone designing an algorithm using default Rust building blocks needs to rely on at least asymptotic complexities not suddenly regressing due to the optimizer not catching some pattern. Updating your Rust compiler should never have a chance to turn an O(n) algorithm into an O(n^2) one.

  4. It pushes people towards unsafe code. In the linked complaint above the user ended up using the unsafe set_len when the safe truncate could've exactly done the job.

In addition to the above, VecDeque has truncate, but is missing truncate_front. If we make these truncate operations O(1) time it should also get a truncate_front operation.

Without these changes it is impossible to implement certain algorithms using the default Rust collections for no particular good reason. For example, if I have a v: VecDeque<f64> that keeps its elements sorted, it is currently impossible to write a O(log n) time routine that removes all elements less than x in v. We can find how many elements we need to remove from the front in O(log n) time, but removing them needlessly take O(n) time.

Activity

alexcrichton

alexcrichton commented on Jul 8, 2019

@alexcrichton
Member

I would like to re-open the discussion with the following observations, in the hope that @alexcrichton might change his mind:

To clarify, all previous cases are purely -O0 optimizations. If this doesn't optimize at higher optimization levels then we can of course change the code to fix that. If this is only a -O0 optimization then that's different.

orlp

orlp commented on Jul 8, 2019

@orlp
ContributorAuthor

@alexcrichton I just tested it and the Vec::truncate operation also doesn't optimize away on opt-level=1, only 2 and higher. So even that portion isn't purely -O0.

But even for -O0 I think we shouldn't leave O(n) -> O(1) reductions on the table when they cost only a couple lines of code. Debug performance matters.

added
C-enhancementCategory: An issue proposing an enhancement or a PR with one.
I-slowIssue: Problems and improvements with respect to performance of generated code.
T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.
on Jul 28, 2019
silverweed

silverweed commented on Sep 14, 2019

@silverweed

+1: having a non-guaranteed O(1) truncate pretty much defeats the purpose of having a deque in many cases. And I agree that a truncate_front (O(1) as well) would come very handy to have built-in for VecDeque.

drdozer

drdozer commented on Oct 2, 2019

@drdozer

I was just bitten by this. Had assumed that truncate() was an O(1) op for Vec.

gendx

gendx commented on Feb 27, 2020

@gendx
Contributor

+1 for having a truncate_front as well.

And somewhat similarly, it would be useful to have a prepend method as the symmetric version of append, as well as an ExtendFront as a symmetric version of std::iter::Extend. I'm not sure whether it makes sense to track those as separate issues.

the8472

the8472 commented on Jun 6, 2020

@the8472
Member

however this does not happen for VecDeque::truncate.

That seems to be fixed since 1.41

added
C-optimizationCategory: An issue highlighting optimization opportunities or PRs implementing such
on Oct 8, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    C-enhancementCategory: An issue proposing an enhancement or a PR with one.C-optimizationCategory: An issue highlighting optimization opportunities or PRs implementing suchI-slowIssue: Problems and improvements with respect to performance of generated code.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @alexcrichton@orlp@drdozer@the8472@jonas-schievink

        Issue actions

          O(1) time {Vec,VecDeque}::truncate for trivial drop types and VecDeque::truncate_front · Issue #62408 · rust-lang/rust