Page MenuHomePhabricator

[libcxx] adds `complexity_iterator`, `complexity_invocable`, and `test_algorithm`
AbandonedPublic

Authored by cjdb on Jul 11 2021, 11:59 PM.

Details

Reviewers
ldionne
zoecarver
Mordante
EricWF
Group Reviewers
Restricted Project
Summary

complexity_iterator is an iterator adaptor that's used to measure
the number of applications of a predicate/projection when there's no
predicate to measure (e.g. ranges::find).

complexity_invocable is an invocable adaptor that's used to measure
the number of calls to a predicate or projection. It differs from
unary_counting_predicate and binary_counting_predicate in two
ways:

  1. Most importantly, it isn't limited to predicates, and so works with invocables returning something other than Boolean values.
  2. It can store lambdas and works in constexpr contexts (this is secondary, but worth noting).

test_algorithm is an overload set that simplifies individual algorithm
test files. While working implementing ranges::lower_bound, I realised
that all test cases follow a strict pattern, for all implemented algos so
far (sometimes it can be simplified):

  1. set up subrange
  2. set up complexity instrumentation
  3. get iterator result
  4. check iterator result
  5. check complexity results
  6. reset subrange (if input iterators allowed)
  7. reset complexity instrumentation
  8. check range result matches iterator result
  9. check complexity results

A lot of this code can be factored out. In particular, this commit
abstracts away all the set-up and complexity-check stages. This in
turn elides the reset stages, individual leaving tests to focus on:

  1. get iterator result
  2. check iterator result
  3. check range result matches iterator result

An optional step 2.5 might creep in, where we check complexity results
for special cases (i.e. cases where that activate certain
optimisations).

The test_algorithm overload set isn't complete yet, but remaining
overloads can be added on an as-needed basis.

Depends on D105205.

Diff Detail

Event Timeline

cjdb requested review of this revision.Jul 11 2021, 11:59 PM
cjdb created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptJul 11 2021, 11:59 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb added a comment.Jul 12 2021, 12:16 AM

D105795 is an example of test_algorithm in action.

cjdb updated this revision to Diff 358109.Jul 12 2021, 5:27 PM
cjdb edited the summary of this revision. (Show Details)

rebases to activate CI

cjdb updated this revision to Diff 358144.Jul 12 2021, 10:01 PM

rebases to activate CI

cjdb updated this revision to Diff 358147.Jul 12 2021, 10:05 PM

rebases to activate CI

cjdb updated this revision to Diff 359366.Jul 16 2021, 9:54 AM

rebases to activate CI

cjdb updated this revision to Diff 359476.Jul 16 2021, 4:20 PM

rebasing to activate CI

I would suggest that you move complexity_iterator to the ranges::find patch so that it's added in the same patch that starts using it.

libcxx/test/support/test_iterators.h
1055

Remove [[nodiscard]]?

1084

This isn't needed, I think the default CTAD should work?

cjdb added a comment.Jul 22 2021, 2:56 PM

I would suggest that you move complexity_iterator to the ranges::find patch so that it's added in the same patch that starts using it.

Ack. Should I move the complexity_invocable stuff to the first algorithm patch it's used in too? Then we just need to make a decision about the test_algorithm stuff, and I'll inject where it's necessary so D105791 can be abandoned :)

I would suggest that you move complexity_iterator to the ranges::find patch so that it's added in the same patch that starts using it.

Ack. Should I move the complexity_invocable stuff to the first algorithm patch it's used in too? Then we just need to make a decision about the test_algorithm stuff, and I'll inject where it's necessary so D105791 can be abandoned :)

Yup, that would be my preference!

cjdb abandoned this revision.Jul 30 2021, 11:26 AM
  • complexity_iterator and complexity_invocable subsumed by D105456.
  • Abandoning test_algorithm since the feedback from ranges::find introduced a lot of complexity I don't want to add.