1457728 - Support tri-state Comparator functions in nsTArray

Status: RESOLVED FIXED

(Core :: MFBT, enhancement)

Description

[Kris Maglione [:kmag]]

The comparator that nsTArray uses for sorting and binary search requires two separate comparisons for every element which isn't equal. While that probably doesn't matter much for pointer or int comparisons, it could add up to a lot of extra overhead for larger comparisons. In bug 1456035, for instance, I had to avoid it so that I wouldn't need an extra memcmp() call when binary searching.

We can solve this without much code chrun by auto-generating LessThan/Equals or tri-state Compare methods from the given comparator, depending on which is already present.

Although, now that I see bug 1443272, I'm thinking maybe it should use operator() rather than Compare().

Comment 1

[Kris Maglione [:kmag]]

Attachment: Bug 1457728: Support tri-state comparators in nsTArray.

Review commit: https://reviewboard.mozilla.org/r/240576/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/240576/

Comment 2

[Eric Rahm [:erahm]]

Comment on attachment 8971832 [details]
Bug 1457728: Support tri-state comparators in nsTArray.

https://reviewboard.mozilla.org/r/240576/#review249668

Overall looks good, sorry this took a while to get to. A few questions / comments, so clearing review for now.

::: xpcom/ds/nsTArray.h:773
(Diff revision 1)
>    }
>  };
>  
>  namespace detail {
>  
> -template<class Item, class Comparator>
> +template <typename T, typename U, typename V = int>

Can you add comments about what's going on with these template methods?

::: xpcom/ds/nsTArray.h:776
(Diff revision 1)
>  namespace detail {
>  
> -template<class Item, class Comparator>
> -struct ItemComparatorEq
> +template <typename T, typename U, typename V = int>
> +struct IsCompareMethod : mozilla::FalseType {};
> +
> +template <typename T, typename U>

Do we really need `T`? It seems like that should always be an `int`.

::: xpcom/ds/nsTArray.h:780
(Diff revision 1)
> +
> +template <typename T, typename U>
> +struct IsCompareMethod<T, U, decltype(mozilla::DeclVal<T>()(mozilla::DeclVal<U>(), mozilla::DeclVal<U>()))>
> +  : mozilla::TrueType {};
> +
> +template <typename T, typename U, bool IsCompare = IsCompareMethod<T, U>::value>

Add a comment here that this is the version that uses a comparison function.

::: xpcom/ds/nsTArray.h:808
(Diff revision 1)
>    }
> +
> +  const T& mComparator;
>  };
>  
> -template<class Item, class Comparator>
> +template <typename T, typename U>

And a comment here that this is the specialization for using a comparator object.

::: xpcom/ds/nsTArray.h:1272
(Diff revision 1)
>      using mozilla::BinarySearchIf;
> -    typedef ::detail::ItemComparatorEq<Item, Comparator> Cmp;
> +    ::detail::CompareWrapper<Comparator, Item> comp(aComp);
>  
>      size_t index;
> -    bool found = BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &index);
> +    bool found = BinarySearchIf(*this, 0, Length(),
> +                                [&] (const elem_type& aElement) { return -comp.Compare(aElement, aItem); },

Can you document why you're negating here?

::: xpcom/tests/gtest/TestTArray2.cpp:1084
(Diff revision 1)
> +  {
> +    return aLeft < aRight;
> +  }
> +};
> +
> +TEST(TArray, test_comparator_objects) {

Thanks for adding tests!

Comment 3

[Kris Maglione [:kmag]]

Comment on attachment 8971832 [details]
Bug 1457728: Support tri-state comparators in nsTArray.

https://reviewboard.mozilla.org/r/240576/#review249668

> Do we really need `T`? It seems like that should always be an `int`.

Not sure what you mean. T is the type of the comparator function/class.

> Can you document why you're negating here?

Yeah.

I don't particularly like this, to be honest. I had to do this because some existing callers pass a different polymorphic type for aItem than the element type, and expect aElement to always be the first argument to LessThan().

I thought about just fixing those callers, but I took the easy option instead.

Comment 4

[Kris Maglione [:kmag]]

Comment on attachment 8971832 [details]
Bug 1457728: Support tri-state comparators in nsTArray.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/240576/diff/1-2/

Comment 5

[Eric Rahm [:erahm]]

Comment on attachment 8971832 [details]
Bug 1457728: Support tri-state comparators in nsTArray.

https://reviewboard.mozilla.org/r/240576/#review262342

Thanks, looks good.

Comment 6

[Kris Maglione [:kmag]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e2d3d7bb9d1f7150ec3be7f8507977f7378ec541
Bug 1457728: Support tri-state comparators in nsTArray. r=erahm

Comment 7

[Andreea Pavel [:apavel]]

Backed out for build bustages at build\build\src\xpcom\ds\nsTArray.h(807)

Push with failures: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=9bb8b9e818869e1a6a9f52213aea66c085d3921a

Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=187004259&repo=mozilla-inbound&lineNumber=22478

Backout: https://hg.mozilla.org/integration/mozilla-inbound/rev/9e7746948833bf994373f7e36505482be300a582

Comment 8

[Kris Maglione [:kmag]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9aaee5070157fa81f30c9e175c5e2fbffba82599
Bug 1457728: Support tri-state comparators in nsTArray. r=erahm

Comment 9

[Arthur Iakab [arthur_iakab]]

https://hg.mozilla.org/mozilla-central/rev/9aaee5070157