linksplatform / doublets-rs Goto Github PK

View Code? Open in Web Editor NEW

5.0 4.0 2.0 405 KB

License: The Unlicense

Rust 99.80% Shell 0.20%

associative doublets linksplatform rust

doublets-rs's Introduction

Doublets

later

Example

A basic operations in doublets:

use doublets::{data, mem, unit, Doublets, DoubletsExt, Links};

fn main() -> Result<(), doublets::Error<usize>> {
    // use file as memory for doublets
    let mem = mem::FileMapped::from_path("db.links")?;
    let mut store = unit::Store::<usize, _>::new(mem)?;

    // create 1: 1 1 - it's point: link where source and target it self
    let point = store.create_link(1, 1)?;

    // `any` constant denotes any link
    let any = store.constants().any;

    // print all store from store where (index: any, source: any, target: any)
    store.each_iter([any, any, any]).for_each(|link| {
        println!("{link:?}");
    });

    // delete point with handler (Link, Link)
    store
        .delete_with(point, |before, after| {
            println!("delete: {before:?} => {after:?}");
            // track issue: https://github.com/linksplatform/doublets-rs/issues/4
            data::Flow::Continue
        })
        .map(|_| ())
}

doublets-rs's People

Contributors

Stargazers

Watchers

Forkers

flakeed

doublets-rs's Issues

Use `rayon` and `bump-herd` to crazy fast parallel search

You can start with this example

fn par_each_impl(..., root: T) {
    if magic_appropriate_to_join(...) {
        rayon::join(
            || par_each_impl(..., left(root)),
            || par_each_impl(..., right(root)),
        )
    } else {
        seq_each_impl(..., root)
    }
}

Unnecessary trailing Flow::Continue

At the moment, in any Handler, you need to return Try<Output = ()>. This is cool and allows interrupting operations in errors.
But it inflates the code:

// one operation handler
|link| {
    worker.work(link);
    Continue // <- :(
}

But everyone wants to:

|link| worker.work(link)

I see two ways

1. Inspired by `std::Termination` create `Termination`-like trait

It might look something like this:

trait HandlerResult {
    type Try: Try<Output = ()>;

    fn try_it(self) -> Self::Try;
}

// impl for ()
// impl for all Try

2. Discard `Handlers' outside the internal code (track it #3)

Use $OP_iter so each_iter and others
example above:

.each_iter(...).for_each(|link| worker.work(link))

What do you think about this?

In particular @Konard

Use Links trait from data

At the moment Doublets trait use Links trait. This is due to the fact that for a long time data::Links Error = Box<dyn Error>

This is now fixed at linksplatform/core-rs@a2cadfa.

However, data::Error still loses information. It may be worth impl Links for Doublets, instead of Doublets for Links

Add log level resetting for FFI

Waiting for the next version of tracing, but will use tracing_subscriber::reload::Handle to hold a global (lazy_static) handle to the level. Just can't do this currently because of issues with generic types in statics, and don't want to create a holder object for it.

Create iterators from generators with std

std has unstable iter::from_generator. This can serve as a replacement for the yield-iter crate

Use associated types in Doublets trait

Use `Doublets<Item = T>` instead of `Doublets<T>`

This is idiomatically more correct. For example – AsRef and Deref:

let string = "hello".to_string();
// we want `AsRef<[u8]>`
let bytes: &[u8] = string.as_ref();
// we want `AsRef<str>`
let str: &str = string.as_ref();

let string = "hello".to_string();
let str = &*string; // we are given `str`

This will also make generic storing doublets than easier.

struct Wrapper<T, D: Doublets<T>> {
    doublets: D,
    _marker: PhantomData<T>,
}

struct Wrapper<D: Doublets> {
    doublets: D,
}
// `T` is `D::Item`

Improve `ffi::specialize_for`

Now the specialization for all integer types looks like this:

#[ffi::specialize_for(
    types = "u8",
    types = "u16",
    types = "u32",
    types = "u64",
    convention = "rust",
    name = "doublets_constants_*"
)]

I see two ways of development:

1. Remove `convention` and add explicit annotation with more luxury style:

#[ffi::specialize_for(
    types(
        u8  => "u8",
        u16 => "uint16",
        u32 => "uint",
        u64 => "ll",
    )
    name = "doublets_constants_*"
)]

#[ffi::specialize_for(
    u8(u8), u16(uint16), u32(uint), u64(ll),
    name = "doublets_constants_*"
)]

2. Use a more limited solution with embedded annotations:

#[ffi::specialize("doublets_constants_*")]

Wrap all exported functions to catch and unwind

All panics must be catch and unwind otherwise it is UB.
I recommend use catch_unwind with the following if let:

let result = panic::catch_unwind(|| {
    // ffi function call
});

if let Err(err) = result {
    // if `err` panic in `Drop` we will be sad
    forget(err);
}

You can create macro or function to resolve it
In currently implementation:

#[ffi::specialize_for(
    . . .
)]
unsafe fn drop_links<T: LinkType>(this: *mut c_void) {
    let links: &mut WrappedLinks<T> = unnull_or_panic(this);
    drop_in_place(links);
}

We can split to:

unsafe fn drop_links_impl<T: LinkType>(this: *mut c_void) {
    // impl
}

#[ffi::specialize_for(
    . . .
)]
unsafe fn drop_links<T: LinkType>(this: *mut c_void) {
    catch_unwind(/* some */)
}

Or add this behavior to ffi::specialize_for

Inline initiative

Add #[inline] attribute to relevant places

`#[inline]` – any obvious functions:

fn try_get_link(&self, index: T) -> Result<Link<T>, Error<T>> {
    self.get_link(index).ok_or(Error::NotExists(index))
}

`#[inline(always)]` – any hard delegations:

pub fn len(&self) -> usize {
    self.0.len()
}

`#[cfg_attr(feature = "inline-more", inline)]` – some questionable or rarely used or internal functions:

// from united/store.rs:194
fn is_unused(&self, link: T) -> bool {
   // impl . . . 
}

Stacked borrows Initiative

Now the experimental miri stacked borrows consider this as Undefined Behavior

error: Undefined Behavior: not granting access to tag <83023706> because incompatible item [Unique for <83025302>] is protected by call 27318525
   --> /home/runner/.rustup/toolchains/nightly-2022-07-29-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:432:18
    |
432 |         unsafe { &mut *self.as_ptr() }
    |                  ^^^^^^^^^^^^^^^^^^^ not granting access to tag <83023706> because incompatible item [Unique for <83025302>] is protected by call 27318525
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <83023706> was created by a retag at offsets [0x0..0x4000000]
   --> /home/runner/work/doublets-rs/doublets-rs/doublets/src/mem/unit/store.rs:85:19
    |
85  |         let mem = self.mem.alloc(capacity)?.leak();
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: <83023706> was protected due to <83025299> which was created here
   --> /home/runner/work/doublets-rs/doublets-rs/doublets/src/mem/unit/store.rs:158:29
    |
158 |         self.sources.attach(&mut *root, index)
    |                             ^^^^^^^^^^

I find it very difficult to thread safety when multiple mutable pointers are stored in different places.
I recommend using Yoda notation in regard to pointer storing.

# instead of 
struct DoubletsTree {
    # ha-ha i own this data
    ptr: Pointer*
    
    fn method(link: T) {
        # touch `ptr`
    }
}

# i recommend use 
struct DoubletsTree {
    # where is my data :(

    fn method(i_m_here: Pointer*, link: T) {
        # touch ptr
    }
}

This works well with stacked borrows:

#! before

# borrow data[x..y]:2
self.touch_first_tree(leak -> root_of_tree, link)
# borrow data[z..w]:3 
self.touch_second_tree(leak -> root_of_tree, link)
# [x..y] and [z..w] overlapping :(

#! after
data = self.get_data(...) # -- borrow data:1

# borrow data[x..y]:2 (not borrow self)
Tree::touch_first_tree(data, root_of_tree, link)
# unborrow data[z..w]:2

# borrow data[z..w]:2 (not borrow self)
Tree::touch_second_tree(data, root_of_tree, link)
# unborrow data[z..w]:2

# unborrow data:1 :)

Use buffered iterators to speed up the search

Currently, op_iter functions use Vec to collect op results to vec and returns vec.into_iter().
I recommend use buffered lock-free iterator generator crate - buter or similar

For example, it will look like this:

//! before
let mut vec = Vec::with_capacity(...);
self.each(..., |link| {
    vec.push(link);
    Continue
});
vec.into_iter()

//! after
let writer = self.buter.writer();
self.each(..., |link| {
    writer.extend(Some(link));
    Continue
});
writer.into_iter()