Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #79947 > unrolled thread

A single linked list using a futex...

Back to article view | Back to comp.lang.c++

Contents

  A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 19:03 -0700
    Re: A single linked list using a futex... Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-26 04:35 +0200
      Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 19:42 -0700
        Re: A single linked list using a futex... Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-26 04:45 +0200
          Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 19:57 -0700
          Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 22:59 -0700
            Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 22:59 -0700
    Re: A single linked list using a futex... Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-26 08:17 +0200
      Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 23:21 -0700

#79947 — A single linked list using a futex...

Fwiw, here is some crude Windows code I just coded up for a single 
linked list using a futex. It only supports push and flush operations 
for now. flush will wait if the stack is empty. I was to lazy to 
implement an ABA counter. However, it shows an interesting way to use a 
futex for a lock-free algorihtm.

Can you get it to run? Thanks.
__________________________________________________


// Futex Single Linked List by Chris M. Thomasson
//___________________________________________________



#include <iostream>
#include <thread>
#include <vector>
#include <functional>
#include <cassert>


#define WIN32_LEAN_AND_MEAN
#include <Windows.h>


#define CT_L2_ALIGNMENT 128
#define CT_ITERS 6666666
#define CT_NODES 42


#define CT_WAITBIT 0x1UL


static LONG g_memory_allocations = 0;
static LONG g_memory_deallocations = 0;
static LONG g_futex_signals = 0;
static LONG g_futex_waits = 0;

struct ct_node
{
     ct_node* m_next;

     ct_node() : m_next(NULL)
     {
         InterlockedAdd(&g_memory_allocations, 1);
     }

     ~ct_node()
     {
         InterlockedAdd(&g_memory_deallocations, 1);
     }
};


#define CT_NODE_SET_WAITBIT(mp_ptr) ((ct_node*)(((ULONG_PTR)(mp_ptr)) | 
CT_WAITBIT))
#define CT_NODE_CHECK_WAITBIT(mp_ptr) (((ULONG_PTR)(mp_ptr)) & CT_WAITBIT)
#define CT_NODE_CLEAR_WAITBIT(mp_ptr) ((ct_node*)(((ULONG_PTR)(mp_ptr)) 
& ~CT_WAITBIT))


void ct_node_flush(ct_node* node)
{
     while (node)
     {
         ct_node* next = node->m_next;
         delete node;
         node = next;
     }
}


struct ct_futex_slist
{
     ct_node* alignas(CT_L2_ALIGNMENT) m_head;


     ct_futex_slist() : m_head(nullptr)
     {

     }


     void push(ct_node* node)
     {
         ct_node* head = m_head;

         for (;;)
         {
             ct_node* xchg = CT_NODE_CLEAR_WAITBIT(head);
             node->m_next = xchg;

             ct_node* ret = 
(ct_node*)InterlockedCompareExchangePointer((PVOID*)&m_head, node, head);

             if (ret == head)
             {
                 if (CT_NODE_CHECK_WAITBIT(ret))
                 {
                     InterlockedAdd(&g_futex_signals, 1);
                     WakeByAddressSingle(&m_head);
                 }

                 return;
             }

             head = ret;
         }
     }


     ct_node* flush()
     {
         ct_node* head_raw = 
(ct_node*)InterlockedExchangePointer((PVOID*)&m_head, NULL);
         ct_node* head = CT_NODE_CLEAR_WAITBIT(head_raw);

         if (! head)
         {
             for (;;)
             {
                 head_raw = 
(ct_node*)InterlockedExchangePointer((PVOID*)&m_head, (ct_node*)CT_WAITBIT);
                 head = CT_NODE_CLEAR_WAITBIT(head_raw);

                 if (head)
                 {
                     break;
                 }

                 InterlockedAdd(&g_futex_waits, 1);
                 ct_node* waitbit = (ct_node*)CT_WAITBIT;
                 WaitOnAddress(&m_head, &waitbit, sizeof(PVOID), INFINITE);
             }
         }

         return head;
     }
};


struct ct_shared
{
     ct_futex_slist m_slist;


     ~ct_shared()
     {
         ct_node* head_raw = m_slist.m_head;

         if (CT_NODE_CHECK_WAITBIT(head_raw))
         {
             std::cout << "\n\nWAITBIT LEAK!\n";
         }

         ct_node_flush(head_raw);

         if (g_memory_allocations != g_memory_deallocations)
         {
             std::cout << "\n\nMEMORY LEAK!\n";
         }

         std::cout << "\ng_memory_allocations = " << 
g_memory_allocations << "\n";
         std::cout << "g_memory_deallocations = " << 
g_memory_deallocations << "\n";
         std::cout << "g_futex_waits = " << g_futex_waits << "\n";
         std::cout << "g_futex_signals = " << g_futex_signals << "\n";
     }
};


void ct_thread(ct_shared& shared)
{
     for (unsigned long i = 0; i < CT_ITERS; ++i)
     {
         for (unsigned long n = 0; n < CT_NODES; ++n)
         {
             shared.m_slist.push(new ct_node());
         }

         ct_node* node = shared.m_slist.flush();
         ct_node_flush(node);
     }

     shared.m_slist.push(new ct_node());
}


int main()
{
     unsigned int threads_n = std::thread::hardware_concurrency();

     std::vector<std::thread> threads(threads_n);

     std::cout << "Futex Single Linked List by Chris M. Thomasson\n\n";

     std::cout << "Launching " << threads_n << " threads...\n";
     std::cout.flush();

     {
         ct_shared shared;

         for (unsigned long i = 0; i < threads_n; ++i)
         {
             threads[i] = std::thread(ct_thread, std::ref(shared));
         }

         std::cout << "Processing...\n";
         std::cout.flush();

         for (unsigned long i = 0; i < threads_n; ++i)
         {
             threads[i].join();
         }
     }

     std::cout << "\nCompleted!\n";

     return 0;
}
__________________________________________________



Here is my output:
__________________________________________________
Futex Single Linked List by Chris M. Thomasson

Launching 4 threads...
Processing...

g_memory_allocations = 1119999892
g_memory_deallocations = 1119999892
g_futex_waits = 21965
g_futex_signals = 55630

Completed!
__________________________________________________

[toc] | [next] | [standalone]

#79949

That aint lock-free because a futex is a kernel-facility !

[toc] | [prev] | [next] | [standalone]

#79951

On 5/25/2021 7:35 PM, Bonita Montero wrote:
> That aint lock-free because a futex is a kernel-facility !

It has 100% lock-free fast-paths. The slow paths will wait/signal only 
when the algorihtm has to. Can you tell the slow paths apart from the 
fast ones?

Adding waiting ability to a lock-free structure can be beneficial. No 
polling, we can actually wait.

[toc] | [prev] | [next] | [standalone]

#79952

> It has 100% lock-free fast-paths. ...

A lock-free algorithm is a algorithm _without any_ kernel-interventon.
Any slow paths make it not lock-free.

[toc] | [prev] | [next] | [standalone]

#79954

On 5/25/2021 7:45 PM, Bonita Montero wrote:
>> It has 100% lock-free fast-paths. ...
> 
> A lock-free algorithm is a algorithm _without any_ kernel-interventon.
> Any slow paths make it not lock-free.

Okay. Well, lets call it a hybrid then. It definitely has lock-free fast 
paths. At least it outperforms a mutex/condvar based single linked list.

[toc] | [prev] | [next] | [standalone]

#79963

On 5/25/2021 7:45 PM, Bonita Montero wrote:
>> It has 100% lock-free fast-paths. ...
> 
> A lock-free algorithm is a algorithm _without any_ kernel-interventon.
> Any slow paths make it not lock-free.

When you get some free time, can you give it a go? compile and run it? 
iI am interest in your output. Thanks Bonita.

[toc] | [prev] | [next] | [standalone]

#79964

On 5/25/2021 10:59 PM, Chris M. Thomasson wrote:
> On 5/25/2021 7:45 PM, Bonita Montero wrote:
>>> It has 100% lock-free fast-paths. ...
>>
>> A lock-free algorithm is a algorithm _without any_ kernel-interventon.
>> Any slow paths make it not lock-free.
> 
> When you get some free time, can you give it a go? compile and run it? 
> iI am interest in your output. Thanks Bonita.

God damn typos!

I am interested in your output: Thanks Bonita.

[toc] | [prev] | [next] | [standalone]

#79965

I'm too lazy to read your code.

> #define CT_L2_ALIGNMENT 128

But this is a false assumption. Except from the Intel Pentium 4 and
the IBM POWER's L4-caches (embedded DRAM) there are AFAIK no caches
that have 128 byte cacheline size. 128 byte cachelines have been pro-
ven to be inefficient below a certain cache-size because the cache-
lines become used too partitially as there's a too less reusage-be-
haviour of the working-set.
Better use this:
https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size

[toc] | [prev] | [next] | [standalone]

#79966

On 5/25/2021 11:17 PM, Bonita Montero wrote:
> I'm too lazy to read your code.
> 
>> #define CT_L2_ALIGNMENT 128
> 
> But this is a false assumption. Except from the Intel Pentium 4 and
> the IBM POWER's L4-caches (embedded DRAM) there are AFAIK no caches
> that have 128 byte cacheline size. 128 byte cachelines have been pro-
> ven to be inefficient below a certain cache-size because the cache-
> lines become used too partitially as there's a too less reusage-be-
> haviour of the working-set.
> Better use this:
> https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size 
> 

Yes, you are correct. std::hardware_constructive_interference_size is 
the way to go. Thanks for taking a look at my code to begin with Bonita!

:^)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web