1419217 - Change comparison functions for red-black trees

Status: RESOLVED FIXED

(Core :: Memory Allocator, enhancement)

Comment 1

[Mike Hommey [:glandium]]

Attachment: Bug 1419217 - Change comparison functions for red-black trees.

- This makes all of them return an enum, quite similar to rust.
- This makes all of them derive from a single implementation of an
  integer comparison.
- This implements that integer comparison in terms of simple operations,
  rather than "smart" computation, which turns out to allow compilers
  to do better optimizations.
  See https://blogs.msdn.microsoft.com/oldnewthing/20171117-00/?p=97416

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

Comment 2

[Nicholas Nethercote [inactive]]

Comment on attachment 8930297 [details]
Bug 1419217 - Change comparison functions for red-black trees.

https://reviewboard.mozilla.org/r/201434/#review206604

Nice change.

::: memory/build/Utils.h:22
(Diff revision 1)
>    using mozilla::tl::CeilingLog2<N>::value;
>    static_assert(1ULL << value == N, "Number is not a power of 2");
>  };
>  #define LOG2(N) Log2<N>::value
>  
> -// Compare two addresses. Returns whether the first address is smaller (-1),
> +enum Order

enum class?

::: memory/build/Utils.h:37
(Diff revision 1)
> -int
> -CompareAddr(T* aAddr1, T* aAddr2)
> +Order
> +CompareInt(T aValue1, T aValue2)
>  {
> -  uintptr_t addr1 = reinterpret_cast<uintptr_t>(aAddr1);
> -  uintptr_t addr2 = reinterpret_cast<uintptr_t>(aAddr2);
> +  static_assert(mozilla::IsIntegral<T>::value, "Type must be integral");
> +  if (aValue1 == aValue2) {
> +    return Order::eEqual;

Won't eEqual be the least frequent result? I suggest checking for eLess and eGreater first, and have eEqual as the fallback, like in Chen's blog post.

Comment 3

[Mike Hommey [:glandium]]

(In reply to Nicholas Nethercote [:njn] from comment #2)
> Comment on attachment 8930297 [details]
> Bug 1419217 - Change comparison functions for red-black trees.
> 
> https://reviewboard.mozilla.org/r/201434/#review206604
> 
> Nice change.
> 
> ::: memory/build/Utils.h:22
> (Diff revision 1)
> >    using mozilla::tl::CeilingLog2<N>::value;
> >    static_assert(1ULL << value == N, "Number is not a power of 2");
> >  };
> >  #define LOG2(N) Log2<N>::value
> >  
> > -// Compare two addresses. Returns whether the first address is smaller (-1),
> > +enum Order
> 
> enum class?

Yes! This even found a missing change in rb.h :)

> ::: memory/build/Utils.h:37
> (Diff revision 1)
> > -int
> > -CompareAddr(T* aAddr1, T* aAddr2)
> > +Order
> > +CompareInt(T aValue1, T aValue2)
> >  {
> > -  uintptr_t addr1 = reinterpret_cast<uintptr_t>(aAddr1);
> > -  uintptr_t addr2 = reinterpret_cast<uintptr_t>(aAddr2);
> > +  static_assert(mozilla::IsIntegral<T>::value, "Type must be integral");
> > +  if (aValue1 == aValue2) {
> > +    return Order::eEqual;
> 
> Won't eEqual be the least frequent result? I suggest checking for eLess and
> eGreater first, and have eEqual as the fallback, like in Chen's blog post.

FWIW, I don't think that makes any practical difference (I think the order is dictated by how the result is used more than how the comparisons are done), but it does make the code nicer, so I'll do it anyways. I actually wrote it with eEqual last originally, then had this weird idea to account for types that have weird definitions of == (like float), but then, those types aren't integral, and eLess wouldn't be the proper fallback anyways.

Comment 4

[Mike Hommey [:glandium]]

Comment on attachment 8930297 [details]
Bug 1419217 - Change comparison functions for red-black trees.

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

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/c5f14418da24
Change comparison functions for red-black trees. r=njn

Comment 6

[Tiberius Oros[:tiberius_oros]]

https://hg.mozilla.org/mozilla-central/rev/c5f14418da24