Re: [Libcds-user] Memory Management Methods

[Max K. <kh...@gm...>]

Hi Lucas,

The libcds uses different SMR techniques exactly. Hazard Pointer, 
Pass-the-Buck, HRC, - all of this is SMR. It is called "garbage 
collector" inside the library for short only. And yes, the main purpose 
of SMR is avoiding ABA problem.

About freelist. I thought a lot about incorporating a freelist into 
libcds but I reject this idea for the following reason:
approach based on classic freelist leads to unbounded memory 
consumption. The classic freelist (for example, that is used in tagged 
pointer technique) should be type-safe, so, for each type T a separate 
freelist should exist. The freelist may not be a non-static member of a 
lock-free container because any SMR deallocation can be deferred and can 
occur after container destruction. The lifetime of freelist must be 
greater than the lifetime of its container. If I declare freelist as a 
static member of highly templated container I can get linking problems 
in a complex project. So I try to avoid any static member in libcds 
templates.

Secondly, what is the freelist interface? We should pop an item from 
freelist and push it back when freeing.

Thus, the freelist property are:
1. It is almost-static object (to support deferred reclamation)
2. It has "pop" (allocate) and "push" (deallocate) methods.

Comparing these properties with std::allocator interface you'll see that 
freelist == allocator.
Result: you can use free-list concept in libcds. Just call the free-list 
as "allocator".

Best regards,
     Max Khiszinsky


On 06/28/2013 04:12 AM, Lucas Lersch wrote:
> I was re-reading the paper from Michael Maged, "High Performance 
> Dynamic Lock-Free Hash Tables
> and List-Based Sets" which seems to be used as the source for the 
> implementation of hash structures in libcds.
>
> The paper claims that the algorithm proposed is compatible with 
> different memory management methods. It also points that freelists and 
> safe memory reclamation are the only methods that are not extremely 
> inefficient, blocking or dependent on special system support. The 
> libcds seems to use a garbage collection memory management method 
> (probably to avoid the ABA problem). Is there a reason not to use 
> freelists or SMR? Is there an alternative? Is the garbage collection 
> environment so inefficient as it says?
>
> I would like some clarification in case I am getting it all wrong. 
> Thank you advance for the attention :)
>
>
> -- 
> Lucas Lersch
>
>
> _______________________________________________
> Libcds-user mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/libcds-user