Is there anyway to make the HConsed pointers allocate using some memory pool? For example the ArenaArc type in shared_arena looks pretty compatible with std::sync::Arc, and it would help a lot for applications where a large number of objects needs to be allocated and deallocated.

Hi,

I've been expermenting with hconsing with NBE for lambda calculus. This library is the primary inspiration, which I've mostly copied. Originally, I was using the library, but ran into some performance problems:

1. I believe the uid is not needed, the internal NonNull pointer data in the Rc is enough to act as a unique reference. As every Rc is the spoke on a fuzzy ball surrounding a RcBox, even if the location of the RcBox were to somehow move, it must move in a way such that all constructed Rc's remain sound. Of course, the Weak stored in the HConsign has the same properties, because it references the same RcBox. Moreover, once the pointer is reclaimed, that is the exact condition in which the unique id would be reusable because the original Weak would fail to upgrade.
2. The usage of Arc with no ability to switch to an Rc. In my case, there is no point in being multithreaded. Parallelization in evaluating lambda terms is not very good unless you take an optimal lambda evaluator route.

"Fixing" those two problems were about a 2-3x speedup for my benchmarks, especially because lambda terms are explosive in terms of size, so halving the pointer size ends up being a useful win.

Ideally, I'd like these changes to make it into this library, because then I can just pull it from cargo :)

Unrelated, I would prefer if the pointer types where called Hc and Ahc, but this is a minor thing that is not important to me, I can just rename the types in my project.

If you are interested I could draft a PR with the above changes.

In the introduction in the documentation it's written that

It is probably less efficient as uses Rust’s HashMaps, not a custom built structure

In what way do you think it might be inefficient because of using Rust's HashMaps? What kind of custom structure would actually be ideal?

First, thanks for writing this crate. It's been super useful!

When writing a fuzzing harness for code relying on hashconsing, I detected that HConsign increasingly accumulates state. I see tens of thousands of entries in HConsign.table even after dropping all the hashconsed elements.

I'm not sure what a good solution would be here, but options might include:

• using https://docs.rs/weak-table/0.3.0/weak_table/. It garbage collects on resize, which is a great place to do it since the operation is already O(N) due to rehasing. However, this crate has its own implementation of a hash table, and it'll likely be quite a bit slower than the stdlib's one.
• exposing a method to give users the ability to GC dropped entries whenever convenient to them.

Is there a way to use WHConsed as keys in a weak hash table like weak_table? If not I can write one and open a PR

We prefer not adding dependencies if we can avoid it, but at least two users expressed interest in integrating with weak_table (#15). While there is a reasonable workaround, actual integration would be much nicer.

This issue is to assess how big the interest for integration is, please let us know here.

Hey! This is a super cool crate. I actually just had someone introduce me to this topic and it was cool to see a crate that does it. I was curious if there had been any thought into implementing a derive macro for this? I'm not 100% on the details but I'm imagining something like

#[derive(HConsed, Debug, Hash, Clone, PartialEq, Eq)]
enum Term {
    Var(usize),
    Lam(Term),
    App(Term, Term)
}

instead of currently

type Term = HConsed<ActualTerm> ;

#[derive(Debug, Hash, Clone, PartialEq, Eq)]
enum ActualTerm {
    Var(usize),
    Lam(Term),
    App(Term, Term)
}

Currently, HConsed implements the Send and Sync traits unconditionally:

This is a possible soundness issue because it allows types T that aren't necessarily thread safe to be used across threads as long as they are wrapped in an HConsed<T>.

Sort of a contrived example but the following demonstrates a data-race that segfaults safe rust using this:

#![forbid(unsafe_code)]

use hashconsing::{HConsign, HConsed, HashConsign};

use std::hash::{Hash, Hasher};
use std::cell::Cell;
use crossbeam_utils::thread;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum RefOrInt<'a> {
    Ref(&'a u64),
    Int(u64),
}

#[derive(PartialEq, Eq)]
struct HashableCell<T: Eq + PartialEq + Copy> { cell: Cell<T> }
// Fake hashing function just so we can get a HConsed going.
impl<T: Eq + PartialEq + Copy> Hash for HashableCell<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        1024.hash(state);
    }
}

static SOME_INT: u64 = 123;

fn main() {
    let cell = Cell::new(RefOrInt::Ref(&SOME_INT));
    let hashable_cell = HashableCell { cell : cell };

    let mut factory: HConsign<_> = HConsign::empty();
    let hcons_cell_ref = factory.mk(&hashable_cell);
    thread::scope(|s| {
        s.spawn(move |_| {
            let smuggled_cell = &hcons_cell_ref.get().cell;

            loop {
                // Repeatedly write Ref(&addr) and Int(0xdeadbeef) into the cell.
                smuggled_cell.set(RefOrInt::Ref(&SOME_INT));
                smuggled_cell.set(RefOrInt::Int(0xdeadbeef));
            }
        });

        loop {
            if let RefOrInt::Ref(addr) = hashable_cell.cell.get() {
                // Hope that between the time we pattern match the object as a
                // `Ref`, it gets written to by the other thread.
                if addr as *const u64 == &SOME_INT as *const u64 {
                    continue;
                }

                // Due to the data race, obtaining Ref(0xdeadbeef) is possible
                println!("Pointer is now: {:p}", addr);
                println!("Dereferencing addr will now segfault: {}", *addr);
            }
        }
    });
}

This outputs:

Pointer is now: 0xdeadbeef

Return Code: -11 (SIGSEGV)

(Issue found by @sslab-gatech's Rust group)