boost::lockfree::queue en non-trivial types

[JeromeB]

Ik wil graag gebruik maken van een lockfree queue. Momenteel maak ik gebruik van boost::lockfree::queue (en spsc_queue). Echter vereist boost::lockfree::queue types met een copy-constructor, een trivial assignment-operator en een trivial destructor. Een groot aantal types voldoet daar natuurlijk niet aan. In mijn geval gaat het vooral om std::string. Nu heb ik dit opgelost door pointers naar strings op te slaan in de queue. Ik stuitte voor zover niet op problemen, maar ik heb dit momenteel alleen getest in een single-consumer/single-producer scenario.

C++:

boost::lockfree::queue<std::string*> queue_(64);

void producer()
{
    std::string* str = new std::string("hai");

    while (!queue_.bounded_push(str));
}

void consumer()
{
    std::string* str;

    while(queue_.pop(str))
    {
        // doe wat met str
        delete str;
    }
}

Om het één en ander eenvoudiger te maken heb ik zelf een wrapper-class geschreven.

C++:

template<typename T>
class ptr_queue
{
public:

    typedef T value_type ;
    typedef boost::lockfree::queue<value_type*> queue_type;

    ptr_queue(std::size_t size = 64) : queue_(size)
    {

    }

    bool push(const value_type& value)
    {
        value_type* new_value = new value_type(value);
        return queue_.bounded_push(new_value);
    }

    bool pop(value_type& value)
    {
        value_type* value_ptr;
        bool ret = queue_.pop(value_ptr);
        if(ret)
        {
            value = *value_ptr;
            delete value_ptr;
        }
        return ret;
    }

    bool empty() const
    {
        return queue_.empty();
    }

private:

    queue_type queue_;
};


ptr_queue<std::string> queue_(64);

void producer()
{
    std::string("hai");

    while (!queue_.bounded_push(str));
}

void consumer()
{
    std::string str;

    while(queue_.pop(str))
    {
        // doe wat met str
    }
}

Volgens dit artikel is het echter niet mogelijk om de data in een thread-veilige manier te verwijderen. Kan iemand mij duidelijk uitleggen waar eventuele gevaren schuilen of heeft iemand een linkje met een goede uitleg? Zijn er nog alternatieve mogelijkheden (buiten zelf synchronisatie toepassen) als het daadwerkelijk niet thread-veilig is?

[.oisyn]

Volgens dit artikel is het echter niet mogelijk om de data in een thread-veilige manier te verwijderen.

Dat staat er niet. Er staat dat het vrijgeven van geheugen niet lock-free is, en daardoor is de pop van je queue dus ook niet lock-free.

[PrisonerOfPain]

In dat artikel staat dat het wel mogelijk is om het thread-safe te verwijderen. Er staat, dat het kan met het nemen van een lock, of met zogenaamde hazard pointers.

Een van deze twee manieren is nodig om een thread-safe memory allocator te bouwen en het hangt af van je C++ runtime (of custom allocators) hoe en of dat gebeurt.

Nu is het zo dat de standaard MSVC allocators in de Multi-Threaded runtime een lock gebruiken en thread-safe zijn en in dat geval kun je gewoon delete aanroepen op een object.

Het nadeel van een lock in de delete is natuurlijk dat je tegen eenzelfde soort contentie aanloopt als wanneer je een locked queue gebruikt - namelijk iedere pop() heeft een lock/unlock nodig.

Daarom gebruikt men - als het echt nodig is - een custom memory allocator in dergelijke gevallen die gebouwd is op het concept van Hazard pointers om de free list te managen.


Kortom, volgens mij moet je oplossing gewoon werken mits je tegen een thread-safe C++ runtime aan runt, maar het verslaat een beetje het doel van een lockless queue. Wat je waarschijnlijk beter kunt doen als met een lockless queue aan gaan lopen knoeien is om gewoon een normale queue te gebruiken met een condition variable en zo je probleem oplossen. Mocht dat niet de gewenste performance geven kun je altijd nog verder kijken - maar het is best een karwij om het fatsoenlijk op te lossen.

[ Voor 12% gewijzigd door PrisonerOfPain op 02-05-2014 12:04 ]

[JeromeB]

Oisyn, excuses, het was me wel duidelijk dat het thread-veilig kan middels synchronisatie/locking. Het is me echter niet geheel duidelijk waarom een pop niet lock-free is. Heeft dit wellicht te maken met de onderliggende freelist? Worden objecten in de freelist niet vrij gegeven (of als vrij gemarkeerd) op het moment dat ze gepopt worden?

PrisonerOfPain, mijn eerste insteek was inderdaad om een synchronized queue te gebruiken, maar het leek me wel handig om eens met lockfree datastructuren te spelen. Performance is ook niet direct een issue. Ik ga me eens verder inlezen in die hazard pointers.

[PrisonerOfPain]

JeromeB schreef op vrijdag 02 mei 2014 @ 12:43:
Oisyn, excuses, het was me wel duidelijk dat het thread-veilig kan middels synchronisatie/locking. Het is me echter niet geheel duidelijk waarom een pop niet lock-free is. Heeft dit wellicht te maken met de onderliggende freelist? Worden objecten in de freelist niet vrij gegeven (of als vrij gemarkeerd) op het moment dat ze gepopt worden?

De delete heeft een impliete lock op de globale heap als je een Multithreaded runtime gebruikt. Daarom is je "pop" niet lock-free (ondanks dat je queue wel lock-free is, overigens). De lock vind gewoon plaats op een plek waar je hem niet ziet.

PrisonerOfPain, mijn eerste insteek was inderdaad om een synchronized queue te gebruiken, maar het leek me wel handig om eens met lockfree datastructuren te spelen. Performance is ook niet direct een issue. Ik ga me eens verder inlezen in die hazard pointers.

Ik zou van het hele idee afstappen en gewoon het originele probleem zo makkelijk mogelijk oplossen. Zelf een correcte lock-free allocator schrijven is geen walk-in-the-park.

[ Voor 6% gewijzigd door PrisonerOfPain op 02-05-2014 13:33 ]

[.oisyn]

PrisonerOfPain schreef op vrijdag 02 mei 2014 @ 13:32:
De delete heeft een impliete lock op de globale heap als je een Multithreaded runtime gebruikt. Daarom is je "pop" niet lock-free (ondanks dat je queue wel lock-free is, overigens). De lock vind gewoon plaats op een plek waar je hem niet ziet.

Dat dus. Dat is overigens niet per definitie zo, maar een typische implementatie ondersteunt geen lock-free memory management functies, en dus zijn new en delete in de regel niet lock-free. Het maakt dan niet meer uit dat de onderliggende queue lock-free is - elke ptr_queue::push() en ptr_queue::pop() doet iets met memory management en daarom zijn zij niet lock-free. Bij 2 threads die tegelijk bijvoorbeeld pop() aanroepen zal de een op de ander moeten wachten, want ze kunnen niet tegelijk delete doen.

[ Voor 8% gewijzigd door .oisyn op 02-05-2014 14:36 ]

[JeromeB]

Daar had ik zelf helemaal niet bij stil gestaan (bij gebrek aan kennis mbt memory-management). In ieder geval bedankt.