Possible minor optimizations for the red-black tree

[raphaelcohn]

Whilst looking through some of the code in NodePtr, I observed a couple of possible minor optimizations; I haven't had the chance to test these and its possible they are optimized out in release mode, in any event.

I found them whilst exploring whether unlikely / likely hints might make a difference for a large tree.

In last_child() and first_child() there is a null guard. The same null guard is made inside next() and previous(); refactoting out the guarded code would allow one less if statement to be executed.

There's a common pattern in last_child() and first_child() which uses a where loop which checks for either left() or right being null before looping; it should be possible to replace this with a loop like

while
            {
                let left = x.left();
                likely!(left.is_not_null())
            }
            {
                x = left
            }

to avoid a second look up from memory. Given the recently accessed value is already going to be a register or cache, it's possibly moot. Similar code that checks parent() does the same in next() / prev().

[Amanieu]

I believe these are optimized away in release mode, but please do let me know if you do find some that aren't.

Also, I would be very interested in hearing your results with likely/unlikely!

[raphaelcohn]

Closing as no longer relevant.