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

Groups > comp.programming.threads > #6317 > unrolled thread

More precision about my new inventions of scalable algorithms..

Back to article view | Back to comp.programming.threads

Contents

  More precision about my new inventions of scalable algorithms.. Amine Moulay Ramdane <aminer68@gmail.com> - 2021-02-18 11:07 -0800
    Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-19 23:27 +0100
      Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 14:48 -0800
        Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-20 00:01 +0100
          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:17 -0800
            Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-20 08:50 +0100
              Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-20 12:46 -0800
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-20 12:52 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-21 17:16 +0100
                  Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-21 13:15 -0500
                    Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-21 19:58 +0100
                      Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-21 15:58 -0500
                        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 14:35 -0800
                          Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:54 +0100
                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:00 -0800
                              Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 07:40 +0100
                              Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 09:20 +0100
                                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-22 14:54 -0800
                                  Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-23 08:38 +0100
                                    Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 00:25 -0800
                                      Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-23 20:17 +0100
                                        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 11:29 -0800
                                          Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-24 18:20 +0100
                                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 01:49 -0800
                                        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 14:13 -0800
                                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 14:14 -0800
                                    Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-23 16:51 -0500
                                      Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-24 18:22 +0100
                                        Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-24 13:28 -0500
                                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 17:16 -0800
                                          Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 07:08 +0100
                                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 23:39 -0800
                                              Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 09:49 +0100
                                                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 01:05 -0800
                                                  Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 11:43 +0100
                                                    Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 03:09 -0800
                                                      Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 03:10 -0800
                                            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 23:43 -0800
                        Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:52 +0100
                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:10 -0800
                      Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 21:47 -0800
                        Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:51 +0100
                          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:01 -0800
          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:32 -0800
            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:37 -0800
        Re: More precision about my new inventions of scalable algorithms.. Amine Moulay Ramdane <aminer68@gmail.com> - 2021-02-19 15:14 -0800

Page 3 of 3 — ← Prev page 1 2 [3]

#6336

On 2/21/2021 10:58 AM, Bonita Montero wrote:
>> 60 People come up and submit their jobs at basically the same time.
>> Each Job is going to take 1 minute of CPU time to run. Which of these
>> scheduling algorithms is 'fairer'
>> Method 1, First job in line run to completion, then the second job is
>> run to completion, then the 3rd and so on. So the first person gets his
>> results after a minute, next a minute later, and so on so the last gets
>> their results 60 minutes later.
>> Method 2, All the jobs are loaded into memory at once, and time sliced
>> between them, each getting 1 second of time, then the next, and so on.
>> Every job will finish at the end of the hour.
>> Many people will label the second method as 'fairer' as everyone gets
>> the same pain, but no one in the second example was any better off then
>> in the first, and almost everyone worse, so by most efficiency measures
>> it is clearly worse.
> 
> You can't compare that to the discussed issue because there's no
> opportunity to capture all the CPU-time by one task.

Why not?

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

#6337

>> You can't compare that to the discussed issue because there's no
>> opportunity to capture all the CPU-time by one task.

> Why not?

Not how he defined it.

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

#6341

On 2/21/2021 9:51 PM, Bonita Montero wrote:
>>> You can't compare that to the discussed issue because there's no
>>> opportunity to capture all the CPU-time by one task.
> 
>> Why not?
> 
> Not how he defined it.

Well, lets say five threads have read access... There is nothing 
stopping them from using all cpus!

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

#6326

On 2/19/2021 3:01 PM, Bonita Montero wrote:
>>>> My below powerful inventions of LW_Fast_RWLockX and Fast_RWLockX 
>>>> that are two powerful scalable RWLocks that are FIFO fair
> 
>>> RW-locks are never fair.
> 
>> There are implementations that can be starvation free.
> 
> No, impossible. Readers can hold the lock as long as they
> want and starve out writers. And writers could do the same.

Check this out:

https://vorbrodt.blog/2019/02/14/read-write-mutex/

On older rwmutex I invented. Its simple, and is starvation free wrt 
reads and writes. Here is a simple Relacy test unit:

__________________________________
// Chris M. Thomassons RW Mutex


//#define RL_DEBUGBREAK_ON_ASSERT
//#define RL_MSVC_OUTPUT
//#define RL_FORCE_SEQ_CST
#include <relacy/relacy_std.hpp>
#include <cstdio>
#include <cstddef>




#if ! defined (NDEBUG)
#   define DBG_PRINTF(e) std::printf e
#else
#   define DBG_PRINTF(e) ((void)0)
#endif



struct semaphore
{
     HANDLE m_waitset;

     semaphore(LONG count)
     {
         m_waitset = CreateSemaphore(nullptr, count, LONG_MAX, nullptr);
     }

     ~semaphore()
     {
         CloseHandle(m_waitset);
     }

     void post(LONG count = 1)
     {
         ReleaseSemaphore(m_waitset, count, nullptr);
     }

     void wait()
     {
         WaitForSingleObject(m_waitset, INFINITE);
     }
};


class ct_rw_fast_mutex
{
public:
     ct_rw_fast_mutex()
         : m_wrstate(1), m_count(INT_MAX), m_rdwake(0),
         m_rdwset(0), m_wrwset(0), m_wrmtx(0) {}

     void read_lock()
     {
         if (m_count.fetch_add(-1, std::memory_order_acquire) < 1)
             m_rdwset.wait();
     }

     void read_unlock()
     {
         if (m_count.fetch_add(1, std::memory_order_release) < 0)
             if (m_rdwake.fetch_add(-1, std::memory_order_acq_rel) == 1)
                 m_wrwset.post();
     }

     void write_lock()
     {
         if (m_wrstate.fetch_sub(1, std::memory_order_acquire) < 1)
             m_wrmtx.wait();
         int count = m_count.fetch_add(-INT_MAX, std::memory_order_acquire);
         if (count < INT_MAX)
         {
             int rdwake = m_rdwake.fetch_add(INT_MAX - count, 
std::memory_order_acquire);
             if (rdwake + INT_MAX - count)
                 m_wrwset.wait();
         }
     }

     void write_unlock()
     {
         int count = m_count.fetch_add(INT_MAX, std::memory_order_release);
         if (count < 0)
             m_rdwset.post(-count);
         if (m_wrstate.fetch_add(1, std::memory_order_release) < 0)
             m_wrmtx.post();
     }

private:
     std::atomic<int> m_wrstate;
     std::atomic<int> m_count;
     std::atomic<int> m_rdwake;

     semaphore m_rdwset;
     semaphore m_wrwset;
     semaphore m_wrmtx;
};


#define ITERS 16
#define WRITERS 3
#define READERS 5
#define THREADS (WRITERS + READERS)


struct proxy_test
     : rl::test_suite<proxy_test, THREADS>
{
     ct_rw_fast_mutex m_rwmutex;
     VAR_T(int) m_shared;

     proxy_test() : m_shared(0) {}

     ~proxy_test() { RL_ASSERT(!VAR(m_shared)); }

     void thread(unsigned int tidx)
     {
         if (tidx < READERS)
         {
             // readers

             for (unsigned long i = 0; i < ITERS; ++i)
             {
                 m_rwmutex.read_lock();
                 int shared = VAR(m_shared);
                 m_rwmutex.read_unlock();

                 RL_ASSERT(shared > -1);
             }

         }

         else
         {
             // writers
             for (unsigned long i = 0; i < ITERS; ++i)
             {
                 m_rwmutex.write_lock();
                 ++VAR(m_shared);
                 m_rwmutex.write_unlock();

                 m_rwmutex.write_lock();
                 --VAR(m_shared);
                 m_rwmutex.write_unlock();
             }
         }
     }
};


int main()
{
     {
         rl::test_params p;

         p.iteration_count = 10000000;
         p.execution_depth_limit = 10000;
         //p.search_type = rl::sched_bound;
         //p.search_type = rl::fair_full_search_scheduler_type;
         //p.search_type = rl::fair_context_bound_scheduler_type;
         rl::simulate<proxy_test>(p);
     }

     return 0;
}
__________________________________


Can you run it?

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

#6327

On 2/19/2021 3:32 PM, Chris M. Thomasson wrote:
> On 2/19/2021 3:01 PM, Bonita Montero wrote:
>>>>> My below powerful inventions of LW_Fast_RWLockX and Fast_RWLockX 
>>>>> that are two powerful scalable RWLocks that are FIFO fair
>>
>>>> RW-locks are never fair.
>>
>>> There are implementations that can be starvation free.
>>
>> No, impossible. Readers can hold the lock as long as they
>> want and starve out writers. And writers could do the same.
> 
> Check this out:
> 
> https://vorbrodt.blog/2019/02/14/read-write-mutex/
> 
> On older rwmutex I invented. Its simple, and is starvation free wrt 
> reads and writes. Here is a simple Relacy test unit:
[...]

Notice how there are no loops in the rwmutex logic?

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

#6324

On Friday, February 19, 2021 at 2:48:18 PM UTC-8, Chris M. Thomasson wrote:
> On 2/19/2021 2:27 PM, Bonita Montero wrote: 
> >> My below powerful inventions of LW_Fast_RWLockX and Fast_RWLockX that 
> >> are two powerful scalable RWLocks that are FIFO fair 
> > 
> > RW-locks are never fair.
> There are implementations that can be starvation free.


You are right Chris M. Thomasson, and my inventions of scalable RWLocks are fair and Starvation-free,
just look at the source code of them.


Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.programming.threads

csiph-web