Human-friendly indexed collections

Will Crichton

Last update: Nov 1, 2023

Related tags

Learning Resources indexical

Overview

Indexical: Human-Friendly Indexed Collections

Indexical is a library for conveniently and efficiently working with indexed collections of objects. "Indexed" means that the domain of objects is finite, and you can assign a numeric index to each object. This enables the use of efficient data structures like bit-sets.

Indexical is a layer on top of existing bit-set libraries like bitvec and rustc_index::bit_set. Those data structures only "understand" raw indexes, not the objects represented by the index. Indexical provides utilities for converting between the object domain and the index domain.

Example

use indexical::{IndexedDomain, IndexedValue, bitset::bitvec::IndexSet};
use std::rc::Rc;

// 1. Define a custom type.
#[derive(PartialEq, Eq, Clone, Hash)]
pub struct MyString(String);

// 2. Define a new index for your custom type.
indexical::define_index_type! {
    pub struct StringIndex for MyString = u32;
}

// 3. Create an immutable indexed domain from a collection of objects.
// By default this is Rc-wrapped, but you can also use Arc or &-refs.
let domain = Rc::new(IndexedDomain::from_iter([
    MyString(String::from("Hello")), MyString(String::from("world"))
]));

// 4. Now you can make a set! Notice how you can pass either a `MyString`
// or a `StringIndex` to `set.insert(..)` and `set.contains(..)`.
let mut set = IndexSet::new(&domain);
set.insert(MyString(String::from("Hello")));
set.insert(StringIndex::from_usize(1));
assert!(set.contains(&MyString(String::from("world"))));

Exploration of using Storage instead of Allocator to parameterize collections in Rust

storage-poc aims at exploring the usage of custom Storages, rather than custom Allocators. Goals This is a Proof-of-Concept aiming at: Demonstrating t

106 Dec 8, 2022

A number of collections, such as linked-lists, binary-trees, or B-Trees are most easily implemented with aliasing pointers.

StaticRc is a safe reference-counted pointer, similar to Rc or Arc, though performing its reference-counting at compile-time rather than run-time, and

372 Dec 19, 2022

A framework for iterating over collections of types implementing a trait without virtual dispatch

zero_v Zero_V is an experiment in defining behavior over collections of objects implementing some trait without dynamic polymorphism.

13 Jul 28, 2022

🚀 efficient approximate nearest neighbor search algorithm collections library written in Rust 🦀 .

2.3k Jan 3, 2023

visualizations/charts for media collections, based on mediainfo

Media Collection Viewer Early WIP! Demo is live Description Upload a mediainfo.json

14 Sep 14, 2022

🔎 A simple in-memory search for collections and key-value stores.

Indicium Search 🔎 A simple in-memory search for collections (Vec, HashMap, BTreeMap, etc) and key-value stores. Features autocompletion. There are ma

41 Oct 28, 2022

Some collections to store a fixed number of elements of a specific type.

This repo provide some useful data-structures, such as: Array, HashMap, HashSet, BTreeMap, BTreeSet, etc... That lives on the stack. It's a good choic

0 Nov 2, 2022

Darwinia networks' tracing runtime override collections

Darwinia Runtime Overrides USAGE: runtime-overrides [OPTIONS] --runtime CHAIN OPTIONS: -h, --help Print help information

4 Aug 3, 2022

A discord bot to view & monitor OpenSea collections, written in Rust

Titan What is this This is a discord bot to monitor OpenSea collections and get info about them, including: Floor Price Activity Sales per Hour And mo

3 Oct 11, 2022

A direct replacement for `assert_eq` for unordered collections

assert_unordered A direct replacement for assert_eq for unordered collections This macro is useful for any situation where the ordering of the collect

10 Nov 29, 2022

An interface for managing collections of labeled items and generating random subsets with specified restrictions

3 Oct 30, 2022

Lexer and parser collections.

laps Lexer and parser collections. With laps, you can build parsers by just defining ASTs and deriving Parse trait for them. Usage Add laps to your pr

11 Jan 27, 2023

Fast abstraction for converting human-like times into milliseconds.

MS converter library Fast abstraction for converting human-like times into milliseconds. Like, are 1d to 86400000. There are two ways to calculate mil

31 Nov 7, 2022

Generate easy to remember sentences that acts as human readable UUIDs 🥳

uuid-readable-rs Easy to remember unique sentences acting as UUID Generate easy to remember sentences that acts as human readable UUIDs. Built on UUID

48 Nov 8, 2022

Codemod - Codemod is a tool/library to assist you with large-scale codebase refactors that can be partially automated but still require human oversight and occasional intervention

Codemod - Codemod is a tool/library to assist you with large-scale codebase refactors that can be partially automated but still require human oversight and occasional intervention. Codemod was developed at Facebook and released as open source.

4k Dec 29, 2022

Comments

Question: why fxhash ?

I found this crate by reading your blogpost Kudos, i much enjoyed it!

I noticed you depend on fxhash. I thought was designed for highly specific use-cases, and is vulnerable to collisions in many others? Did you choose fxhash specifically over alternatives as ahash?

If you could find the time, would you consider explaining a little about this choice?

Thanks in advance

opened by thomvil 1
Speed up simd bitmask by checking against all zeros
The main goal of this PR is to introduce checking for 0 at the SIMD element level in addition to the individual lane check that already exists.

This is a direct boon when the bit set is very sparse (ie. corrset-benchmark) and there are a lot of SIMD elements without any bits set. When the bit set is relatively full, then the check shouldn't be too much of a detriment as it would only be executed when a new register is needed.

The worst case for over head it when almost all SIMD elements only have a few bits set as a the new element would be checked frequently. This may not even be impactful as each lane would also need to be checked regardless.

We can see the benefit using the fused mode from corrset-benchmark: | Change | Runtime | Total Reduction | |------------------|---------|-----------------| | Base | 264.923 | 00% | | Simd Iter Skip 0 | 202.173 | 24% |

As part of the change in this PR, I refactored the next function so that it made more sense to me:

Only get a new element when it is needed for the current result.

As apposed to the existing implementation that gets the element needed for the next result.

Unset bits using xor rather than shifting them away.

This can be done in a single pass while the existing implementation takes 2.

Also reduces the branching per pass.

I am unsure if these benefits could be achieved with a shifting approach, but an xor approach makes more sense to me

Unfortunately, a new check must now be added at the end in case there are bits set past the end of the bitset (encounted when iterating after inverting). This should be ok performance wise since it can only return true once and thus should be difficult for the branch predictor.
opened by cjcormier 0

Human-friendly indexed collections

Related tags

Overview

Indexical: Human-Friendly Indexed Collections

Example

You might also like...

Exploration of using Storage instead of Allocator to parameterize collections in Rust

A number of collections, such as linked-lists, binary-trees, or B-Trees are most easily implemented with aliasing pointers.

A framework for iterating over collections of types implementing a trait without virtual dispatch

🚀 efficient approximate nearest neighbor search algorithm collections library written in Rust 🦀 .

visualizations/charts for media collections, based on mediainfo

🔎 A simple in-memory search for collections and key-value stores.

Some collections to store a fixed number of elements of a specific type.

Darwinia networks' tracing runtime override collections

A discord bot to view & monitor OpenSea collections, written in Rust

A direct replacement for `assert_eq` for unordered collections

An interface for managing collections of labeled items and generating random subsets with specified restrictions

Lexer and parser collections.

Fast abstraction for converting human-like times into milliseconds.

Generate easy to remember sentences that acts as human readable UUIDs 🥳

Codemod - Codemod is a tool/library to assist you with large-scale codebase refactors that can be partially automated but still require human oversight and occasional intervention

🦀 Rust library for printing human readable, relative time differences

Fuzzy Index for Python, written in Rust. Works like error-tolerant dict, keyed by a human input.

A dead simple human-writable URL redirector based loosely on google's `go/` system.

Human numeric sorting program — does what `sort -h` is supposed to do!

Comments

Question: why fxhash ?

Speed up simd bitmask by checking against all zeros

Owner

Will Crichton

A developer-friendly framework for building user interfaces in Rust

RcLite: small, fast, and memory-friendly reference counting for Rust

A typesafe, flexible, simple, and user-friendly unit system library for Rust that has good error messages.

Additional Rust collections not found in std::collections

This is choose, a human-friendly and fast alternative to cut and (sometimes) awk

Grep with human-friendly search output

HTTPie: human-friendly CLI HTTP client for the API era

A simple, human-friendly, embeddable scripting language

A Google-like web search engine that provides the user with the most relevant websites in accordance to his/her query, using crawled and indexed textual data and PageRank.

VCF/BCF [un]compressed [un]indexed