6

BTree: remove Ord bound from new by nbdd0121 · Pull Request #88040 · rust-lang/r...

 3 years ago
source link: https://github.com/rust-lang/rust/pull/88040
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Copy link

Member

dtolnay left a comment

No elements exist so there are nothing to compare anyway

I don't think "future proof" would be a blocker here

I couldn't find out any reason not to do it

This is not as clear cut as the PR description implies.

I am hesitant about this because this API change makes it impossible to selectively tackle some of the code bloat caused by monomorphizations inside the internals of these collections. According to https://www.stroustrup.com/SCARY.pdf such optimizations deliver 1.2x to 2.1x faster performance and 1x to 25x smaller code size in real applications.

I pasted below a sketch of the kind of restructure that this change hinders.

Clearly we still have bounds available via the insert and contains methods etc, so a comparator could be passed down from there as a function argument to every places that needs it, but the extra argument passing could negate a chunk of the performance benefit relative to stashing a comparator at suitable places inside of the data structure up front.

@rust-lang/libs-api @rust-lang/libs

use self::private::{Element, TypeErasedSet};
use std::cmp::Ordering;
use std::marker::PhantomData;
use std::mem;

pub struct Set<T> {
    imp: TypeErasedSet,
    marker: PhantomData<T>,
}

impl<T> Set<T> {
    pub fn new() -> Self
    where
        T: Ord,
    {
        unsafe fn erased_cmp<T: Ord>(a: &dyn Element, b: &dyn Element) -> Ordering {
            T::cmp(&*(a as *const _ as *const _), &*(b as *const _ as *const _))
        }
        Set {
            imp: unsafe { TypeErasedSet::new(erased_cmp::<T>) },
            marker: PhantomData,
        }
    }

    pub fn insert(&mut self, value: T)
    where
        T: Ord,
    {
        let boxed = Box::new(value);
        unsafe {
            let erased = mem::transmute::<Box<dyn Element>, Box<dyn Element + 'static>>(boxed);
            self.imp.insert(erased)
        }
    }

    pub fn contains(&self, value: &T) -> bool
    where
        T: Ord,
    {
        unsafe { self.imp.contains(value) }
    }
}

mod private {
    use std::cmp::Ordering;

    pub(super) trait Element {}
    impl<Sized> Element for Sized {}

    type Comparator = unsafe fn(&dyn Element, &dyn Element) -> Ordering;

    pub(super) struct TypeErasedSet {
        // Obviously you could build a more efficient representation than this.
        // Just illustrating that the concept works without a monomorphized T.
        repr: Vec<Box<dyn Element>>,
        cmp: Comparator,
    }

    impl TypeErasedSet {
        pub(super) unsafe fn new(cmp: Comparator) -> Self {
            TypeErasedSet {
                repr: Vec::new(),
                cmp,
            }
        }

        pub(super) unsafe fn insert(&mut self, value: Box<dyn Element>) {
            match self.find(&*value) {
                Ok(present) => self.repr[present] = value,
                Err(absent) => self.repr.insert(absent, value),
            }
        }

        pub(super) unsafe fn contains(&self, value: &dyn Element) -> bool {
            self.find(value).is_ok()
        }

        unsafe fn find(&self, value: &dyn Element) -> Result<usize, usize> {
            self.repr
                .binary_search_by(|elem| unsafe { (self.cmp)(&**elem, value) })
        }
    }
}

fn main() {
    let mut set = Set::new();
    set.insert(5);
    set.insert(2);
    set.insert(9);
    set.insert(4);
    set.insert(9);
    println!("{}", set.contains(&4));
    println!("{}", set.contains(&3));
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK