Pool based allocation

[lenianiva]

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.

[lenianiva]

For example maybe we could have

let mut factory: HConsign<Expr> = HConsign::from_arena(arena);
factory.mk(Expr::Add(1, 2)); // Calls `arena.alloc_arc(Expr::Add(1,2))`

[AdrienChampion]

This sounds great, but unfortunately I don't have a lot of time to spend on this...

Would you be interested in writing a PR for this?

[lenianiva]

This sounds great, but unfortunately I don't have a lot of time to spend on this...

Would you be interested in writing a PR for this?

Yes. I can write a PR for it. Do you want to add shared_arena as a conditional dependency and use the schematic I just described?

I think this is what I would do:

1. Add a trait that is common to Arc and ArenaArc, and any Arc type implementing this trait can be fed into the HConsign.
2. Add a trait that represents an arena, and an arena type parameter to HConsign, which only needs to implement one function that returns the aforementioned Arc trait objects.

so something like

let mut factory: HConsed<Expr, Pointer=ArenaArc<Expr>, Allocator=SharedArena<Expr>> = ...

and the default behaviour is to have Allocator = (), in which case the allocation is the default allocation for Arc. This looks very verbose but we only create one factory for each type anyways.

[lenianiva]

There is currently a problem. The implementation of HConsign requires the Weak type, so it would look something like

pub struct HConsign<T: Hash + Eq + Clone, S = RandomState, Alloc: Allocator<T>=alloc::DefaultAllocator> {
    /// The actual hash consing table.
    table: HashMap<T, WHConsed<T, Alloc>, S>,
    /// Counter for uids.
    count: u64,
}

shared_arena does not have a weak type, so I'm opening an issue here and hopefully we can have one, but I read the source code there and I don't think its possible to have one. In this case maybe we need to modify the implementation so HConsign uses a table: HashMap<T, HConsed<T, Alloc>, S>. If you are fine with this, I can proceed with it. In this case we would need to give up on the WHConsed type if the allocator does not provide a weak pointer type.

The default allocator is implemented like this:

pub trait Arc<T, W>: std::ops::Deref<Target=T> + core::borrow::Borrow<T>
{
	fn downgrade(&self) -> W;
}
pub trait Weak<T, S>
{
	fn upgrade(&self) -> Option<S>;
}

impl<T> Arc<T, std::sync::Weak<T>> for std::sync::Arc<T>
{
	fn downgrade(&self) -> std::sync::Weak<T>
	{
		std::sync::Arc::downgrade(&self)
	}
}
impl<T> Weak<T, std::sync::Arc<T>> for std::sync::Weak<T>
{
	fn upgrade(&self) -> Option<std::sync::Arc<T>>
	{
		std::sync::Weak::upgrade(&self)
	}
}

pub trait Allocator<T>
{
	/// Strong `std::sync::Arc`-like pointer
	type Strong: Arc<T, Self::Weak>;

	/// `std::sync::Weak`-like pointer
	type Weak: Weak<T, Self::Strong>;

	fn alloc(data: T) -> Self::Strong;
}

pub(super) struct DefaultAllocator {}

impl<T> Allocator<T> for DefaultAllocator
{
	type Strong = std::sync::Arc<T>;
	type Weak = std::sync::Weak<T>;

	fn alloc(data: T) -> Self::Strong
	{
		Self::Strong::new(data)
	}
}

[AdrienChampion]

I'm tempted to have two parameters for Arc-like refs. One is what the consign actually creates and gives back to you, and the other is what the consign actually stores.
Then we would have a trait with the constructor(s)/conversion(s) needed.

(So assuming you use refs that don't have a weak version, both these types would be the same.)

[AdrienChampion]

On that note, it seems to me like instead of having 4 or 5 or more parameters, we could just have one trait that specifies everything (types and functions) and just take that as a parameter. (Or maybe two traits, whatever makes the most sense, I just mean some of these parameters should be aggregated.)

Then we provide a type implementing this trait that corresponds to the current behavior and make that the default. Adding shared arena is then just a feature-gated type also implementing this trait and some helpers to easily create the associated consign.

[AdrienChampion]

What do you think?

[lenianiva]

On that note, it seems to me like instead of having 4 or 5 or more parameters, we could just have one trait that specifies everything (types and functions) and just take that as a parameter. (Or maybe two traits, whatever makes the most sense, I just mean some of these parameters should be aggregated.)

Then we provide a type implementing this trait that corresponds to the current behavior and make that the default. Adding shared arena is then just a feature-gated type also implementing this trait and some helpers to easily create the associated consign.

We can do that. What do you think we should do about the Weak type? We can emulate the weak type by using two memory arenas. One arena would store the underlying data type T, and the weak arena would store ArenaArc<T>, where the deallocation of the strong type would be the responsibility of the HConsign factory.

Is the current solution good enough? The Allocator<T> type is the "one trait that specifies everything". You can take a look at the draft PR here.

[lenianiva]

I've submitted a PR for shared_arena so the ArenaArc type can expose a strong count that we can use to implement bookkeeping mechanisms.

[lenianiva]

Update: I think shared_arena is no longer being maintained. I can make a fork that includes a weak pointer.