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

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

Lock-free LRU-cache-algorithm

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

Contents

  Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-09 08:59 +0200
    Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-09 05:14 -0700
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-09 16:32 +0200
        Re: Lock-free LRU-cache-algorithm Melzzzzz <Melzzzzz@zzzzz.com> - 2019-08-09 14:38 +0000
    Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson " <ahh_f_it@crap.nothing> - 2019-08-10 02:09 -0700
      Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-08-10 02:12 -0700
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-10 11:42 +0200
        Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-10 03:48 -0700
          Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-10 13:21 +0200
            Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-10 05:30 -0700
              Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-10 15:52 +0200
                Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-08-10 09:40 -0700
                  Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-26 00:55 -0700
                  Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-26 10:02 +0200
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-12 19:48 +0200
    Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-12 16:26 -0700
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 10:24 +0200
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 23:51 -0700
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 23:55 -0700
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 10:42 +0200
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 11:19 +0200
          Re: Lock-free LRU-cache-algorithm Josef Moellers <josef.moellers@invalid.invalid> - 2019-08-13 11:42 +0200
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-13 12:47 +0200
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 15:03 -0700
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 15:17 -0700
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-08-13 15:31 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-24 18:33 +0200
      Re: Lock-free LRU-cache-algorithm scott@slp53.sl.home (Scott Lurndal) - 2019-09-24 16:53 +0000
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-24 19:00 +0200
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-24 13:58 -0700
      Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-24 13:50 -0700
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-24 13:56 -0700
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-16 15:40 +0200
          Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-16 16:25 +0200
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-16 14:16 -0700
      Re: Lock-free LRU-cache-algorithm Juha Nieminen <nospam@thanks.invalid> - 2019-09-25 06:42 +0000
        Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 09:08 +0200
          Re: Lock-free LRU-cache-algorithm Juha Nieminen <nospam@thanks.invalid> - 2019-09-25 10:12 +0000
            Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 13:37 +0200
              Re: Lock-free LRU-cache-algorithm scott@slp53.sl.home (Scott Lurndal) - 2019-09-25 12:55 +0000
                Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 15:28 +0200
                  Re: Lock-free LRU-cache-algorithm Juha Nieminen <nospam@thanks.invalid> - 2019-09-25 17:23 +0000
                    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-25 20:19 +0200
        Re: Lock-free LRU-cache-algorithm David Brown <david.brown@hesbynett.no> - 2019-09-25 10:10 +0200
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 22:59 -0700
            Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:09 -0700
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-08 13:33 +0200
        Re: Lock-free LRU-cache-algorithm Öö Tiib <ootiib@hot.ee> - 2019-10-08 08:31 -0700
          Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-08 17:45 +0200
    Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:11 -0700
      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-26 08:13 +0200
        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:33 -0700
          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:34 -0700
          Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-26 11:13 +0200
            Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-09-26 20:37 +0200
            Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-23 19:42 -0700
              Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-24 11:00 +0200
                Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-24 13:13 -0700
                  Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-24 13:14 -0700
                  Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-25 06:53 +0200
                    Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-24 23:06 -0700
                      Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-25 08:20 +0200
                        Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-25 21:35 -0700
                          Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-10-25 21:37 -0700
                          Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-26 08:39 +0200
    Re: Lock-free LRU-cache-algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-09-25 23:49 -0700
    Re: Lock-free LRU-cache-algorithm Bonita Montero <Bonita.Montero@gmail.com> - 2019-10-21 16:42 +0200

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#68655

>> Look, here, that's a similar patent to what we're talking about:
>> https://patents.google.com/patent/US5778442

> My most recent patent (Issued 9/27/2019) is numbered 10,394,730.
> Your referenced patent was granted over twenty years ago, long
> before the court case Juha has referenced.

Yes, but concrete implementations of algorithms are still
applicable for patents in the US.

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

#68660

Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> Look, here, that's a similar patent to what we're talking about:
>>> https://patents.google.com/patent/US5778442
> 
>> My most recent patent (Issued 9/27/2019) is numbered 10,394,730.
>> Your referenced patent was granted over twenty years ago, long
>> before the court case Juha has referenced.
> 
> Yes, but concrete implementations of algorithms are still
> applicable for patents in the US.

So anybody can make their own implementation of the algorithm
and it will be just fine?

Well, good luck on your attempt at becoming a patent troll.
Maybe you'll get a couple of bucks from some random company.

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

#68665

> So anybody can make their own implementation of the
> algorithm and it will be just fine?

"Implementation" doesn't iclude concrete languages.
Read the article you quoted.

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

#68642

On 25/09/2019 08:42, Juha Nieminen wrote:
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> I've found a solution that is mega-cool. I'm not gonna reveal it
>> because I'm thinking about to get an US-patent on it, but it is a
>> exotic combination of locked and lock-free programming. It scales
>> almost linear with the number of threads.
> 
> I don't think you can patent algorithms even in the US currently.
> They got rid of that loophole.
> 

You can patent all kinds of nonsense in various countries, with the US
leading in the "give us the money and we'll accept anything" stakes.

In particular, in the American system patent offices are funded based on
the number of patents they issue, not on how well they screen
applications or the validity of the patents.  The standard is to issue
the patent, and let its validity be tried in court - at vast expense to
the patent holder and the accused patent abuser.

I have heard that a rule of thumb is that you should not attempt to
patent unless the idea is worth 7 figures (i.e., over a million
dollars), and you have at least 6 figures of cash in the bank for the
legal expenses of enforcing the patent.  And that is assuming you have a
good, solid, valid patent in the first place.

I am no lawyer, of course, and I will not be the slightest offended if
someone dismisses this as cynicism or urban legend.  (Indeed I'd be
happy if someone can reasonably show the situation is not as bad as I
believe.)

(Australia tried a "fast track, low cost" patent system for a while, to
make it easier to get simple patents with less protection than normal
full patents.  I believe they stopped after someone used it to patent
the wheel.)

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

#68679

On 9/25/2019 1:10 AM, David Brown wrote:
> On 25/09/2019 08:42, Juha Nieminen wrote:
>> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> I've found a solution that is mega-cool. I'm not gonna reveal it
>>> because I'm thinking about to get an US-patent on it, but it is a
>>> exotic combination of locked and lock-free programming. It scales
>>> almost linear with the number of threads.
>>
>> I don't think you can patent algorithms even in the US currently.
>> They got rid of that loophole.
>>
> 
> You can patent all kinds of nonsense in various countries, with the US
> leading in the "give us the money and we'll accept anything" stakes.
> 
> In particular, in the American system patent offices are funded based on
> the number of patents they issue, not on how well they screen
> applications or the validity of the patents.  The standard is to issue
> the patent, and let its validity be tried in court - at vast expense to
> the patent holder and the accused patent abuser.
> 
> I have heard that a rule of thumb is that you should not attempt to
> patent unless the idea is worth 7 figures (i.e., over a million
> dollars), and you have at least 6 figures of cash in the bank for the
> legal expenses of enforcing the patent.  And that is assuming you have a
> good, solid, valid patent in the first place.
> 
> I am no lawyer, of course, and I will not be the slightest offended if
> someone dismisses this as cynicism or urban legend.  (Indeed I'd be
> happy if someone can reasonably show the situation is not as bad as I
> believe.)
> 
> (Australia tried a "fast track, low cost" patent system for a while, to
> make it easier to get simple patents with less protection than normal
> full patents.  I believe they stopped after someone used it to patent
> the wheel.)
> 
> 

for some reason, this makes me think of the following song:

https://youtu.be/1RTp1nmA4Xw?list=PLrQSYxsHzOso3PpMNKwTlNhMCK6FMDkzW

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

#68680

On 9/25/2019 10:59 PM, Chris M. Thomasson wrote:
> On 9/25/2019 1:10 AM, David Brown wrote:
>> On 25/09/2019 08:42, Juha Nieminen wrote:
>>> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>>> I've found a solution that is mega-cool. I'm not gonna reveal it
>>>> because I'm thinking about to get an US-patent on it, but it is a
>>>> exotic combination of locked and lock-free programming. It scales
>>>> almost linear with the number of threads.
>>>
>>> I don't think you can patent algorithms even in the US currently.
>>> They got rid of that loophole.
>>>
>>
>> You can patent all kinds of nonsense in various countries, with the US
>> leading in the "give us the money and we'll accept anything" stakes.
>>
>> In particular, in the American system patent offices are funded based on
>> the number of patents they issue, not on how well they screen
>> applications or the validity of the patents.  The standard is to issue
>> the patent, and let its validity be tried in court - at vast expense to
>> the patent holder and the accused patent abuser.
>>
>> I have heard that a rule of thumb is that you should not attempt to
>> patent unless the idea is worth 7 figures (i.e., over a million
>> dollars), and you have at least 6 figures of cash in the bank for the
>> legal expenses of enforcing the patent.  And that is assuming you have a
>> good, solid, valid patent in the first place.
>>
>> I am no lawyer, of course, and I will not be the slightest offended if
>> someone dismisses this as cynicism or urban legend.  (Indeed I'd be
>> happy if someone can reasonably show the situation is not as bad as I
>> believe.)
>>
>> (Australia tried a "fast track, low cost" patent system for a while, to
>> make it easier to get simple patents with less protection than normal
>> full patents.  I believe they stopped after someone used it to patent
>> the wheel.)
>>
>>
> 
> for some reason, this makes me think of the following song:
> 
> https://youtu.be/1RTp1nmA4Xw?list=PLrQSYxsHzOso3PpMNKwTlNhMCK6FMDkzW

Perhaps even this, U-neek!

https://youtu.be/fjar4qUqBcE

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

#69116

> I've found a solution that is mega-cool. I'm not gonna reveal it
> because I'm thinking about to get an US-patent on it, but it is a
> exotic combination of locked and lock-free programming. It scales
> almost linear with the number of threads.

Shit, I didn't consider cacheline ping-pong. Here's the scaling with
the number of cores on my Ryzen 7 1800X: https://bit.ly/31YgDAV
The blue graph is the scaling of my algorithm and the red algorithm
is the scaling of my algorithm when I set a certain parameter to zero
so that my algorithm very closely behaves like like updating a LRU
-list with a single mutex.
This is the relative scaling of my algorithm over the scaling of the
standard algorithm when repeatedly fetching and pinning an LRU-entry,
thereby pushing it to the head of the LRU-list, and then unpinning it:

1:   101 %
2:  1809 %
3:  1898 %
4:  1736 %
5:  1353 %
6:  1253 %
7:  1259 %
8:  1256 %
9:  1241 %
10: 1204 %
11: 1182 %
12: 1157 %
13: 1155 %
14: 1137 %
15: 1141 %
16: 1153 %

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

#69120

On Tuesday, 8 October 2019 14:34:01 UTC+3, Bonita Montero  wrote:

> Shit, I didn't consider cacheline ping-pong. Here's the scaling with
> the number of cores on my Ryzen 7 1800X: https://bit.ly/31YgDAV

403

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

#69121

>> Shit, I didn't consider cacheline ping-pong. Here's the scaling with
>> the number of cores on my Ryzen 7 1800X: https://bit.ly/31YgDAV

> 403

Try this: https://pasteboard.co/IB2vueb.png

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

#68681

On 8/8/2019 11:59 PM, Bonita Montero wrote:
> Can anyone tell how a lock-free algorithm for a LRU-cache would
> look like? LRU-caches are only possible with doubly-linked lists.
> So I thought this woudn't be possible lock-free. But maybe I'm
> wrong here and someone can give me an idea.


can I sign an NDA?

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

#68682

>> Can anyone tell how a lock-free algorithm for a LRU-cache would
>> look like? LRU-caches are only possible with doubly-linked lists.
>> So I thought this woudn't be possible lock-free. But maybe I'm
>> wrong here and someone can give me an idea.

> can I sign an NDA?

Why?

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

#68683

On 9/25/2019 11:13 PM, Bonita Montero wrote:
>>> Can anyone tell how a lock-free algorithm for a LRU-cache would
>>> look like? LRU-caches are only possible with doubly-linked lists.
>>> So I thought this woudn't be possible lock-free. But maybe I'm
>>> wrong here and someone can give me an idea.
> 
>> can I sign an NDA?
> 
> Why?

I am interested in your algorithm! Makes me think of times past.

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

#68684

On 9/25/2019 11:33 PM, Chris M. Thomasson wrote:
> On 9/25/2019 11:13 PM, Bonita Montero wrote:
>>>> Can anyone tell how a lock-free algorithm for a LRU-cache would
>>>> look like? LRU-caches are only possible with doubly-linked lists.
>>>> So I thought this woudn't be possible lock-free. But maybe I'm
>>>> wrong here and someone can give me an idea.
>>
>>> can I sign an NDA?
>>
>> Why?
> 
> I am interested in your algorithm! Makes me think of times past.

Talk some shop. Membars, efficiency, Relacy... ;^)

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

#68689

>>> can I sign an NDA?

>> Why?

> I am interested in your algorithm! Makes me think of times past.

Something different: my algorithm is fast when fetching blocks from
the lru-cache present in the cache, i.e. there can be an arbitrary
number of threads doing that. But even this needs at least three
CMPXCHGs on three 64 bit values (in a 64-bit-system, in a 32-bit
system you would have two 64- and one 32-bit exchange) if there's
no collision. I'm asking myself if this would be faster with trans-
actional memory, i.e if I'd build something similar like CMPXCHG
with TSX-RTM, if this would be faster.
I could redesign my "cachline ping pong" code to use TSX-RTM with-
out having tested this on my PC; so could anyone here run the num-
bers on that?

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

#68700

> I could redesign my "cachline ping pong" code to use TSX-RTM with-
> out having tested this on my PC; so could anyone here run the num-
> bers on that?

So here's the code:

#if defined(_MSC_VER)
     #include <Windows.h>
     #include <intrin.h>
#elif defined(__unix__)
     #include <sys/sysinfo.h>
     #include <sched.h>
     #include <pthread.h>
     #include <immintrin.h>
#endif
#include <iostream>
#include <thread>
#include <cstddef>
#include <atomic>
#include <functional>
#include <chrono>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <array>

unsigned getNumberOfProcessors();
bool hasTSX();

using namespace std;
using namespace chrono;

inline
size_t fetchAdd( size_t volatile &v, size_t a )
{
#if defined(_MSC_VER)
     #if defined(_M_X64)
     return (size_t)_InterlockedExchangeAdd64( &(__int64 &)v, (__int64)a );
     #elif defined(_M_IX86)
     return (size_t)_InterlockedExchangeAdd( &(long &)v, (long)a );
     #else
         #error unsupported architecture
     #endif
#elif defined(__GNUC__) || defined(__clang__)
     return __sync_fetch_and_add( &v, a );
#else
         #error unsupported architecture
#endif
}

inline
size_t compareExchange( size_t volatile &v, size_t c, size_t x )
{
#if defined(_MSC_VER)
     #if defined(_M_X64)
     return (size_t)_InterlockedCompareExchange64( &(__int64 &)v, 
(__int64)x, (__int64)c );
     #elif defined(_M_IX86)
     return (size_t)_InterlockedCompareExchange( &(long &)v, (long)x, 
(long)c );
     #else
         #error unsupported architecture
     #endif
#elif defined(__GNUC__) || defined(__clang__)
     return __sync_val_compare_and_swap( &v, c, x );
#else
         #error unsupported architecture
#endif
}

inline
void rtmFetchAdd( size_t volatile &v, size_t a )
{
     _xbegin();
     ++v;
     _xend();
}

int main( int argc, char **argv )
{
     if( argc < 2 )
         return -1;
     double nsPerClockCycle = 1.0 / (atof( argv[1] ) * 1.0e9);

     auto thrXadd = []( uint8_t volatile &run, size_t adds, size_t 
volatile &atm, atomic<size_t> &misses )
     {
         while( !run );
         for( size_t i = adds; i; --i )
             fetchAdd( atm, 1 );
     };
     auto thrXchg = []( uint8_t volatile &run, size_t adds, size_t 
volatile &atm, atomic<size_t> &misses )
     {
         while( !run );
         size_t missed = 0;
         for( size_t i = adds, cmp = atm; i; --i )
         {
             for( size_t res; ; )
                 if( (res = compareExchange( atm, cmp, cmp + 1 )) == cmp )
                 {
                     cmp = cmp + 1;
                     break;
                 }
                 else
                     cmp = res,
                     ++missed;
         }
         misses.fetch_add( missed );
     };
     auto rtmAdd = []( uint8_t volatile &run, size_t adds, size_t 
volatile &atm, atomic<size_t> &misses )
     {
         while( !run );
         for( size_t i = adds; i; --i )
             rtmFetchAdd( atm, 1 );
     };
     using threadfunc = void (*)( uint8_t volatile &, size_t, size_t 
volatile &, atomic<size_t> & );
     array<threadfunc, 3>   atf;
     array<char const *, 3> threadDescr;
     size_t                 nTests;
     size_t const           ADDS = 10'000'000;
     unsigned               nProcessors = getNumberOfProcessors();

     atf[0]         = thrXadd;
     atf[1]         = thrXchg;
     atf[2]         = rtmAdd;
     threadDescr[0] = "xadd-thread";
     threadDescr[1] = "cmpxchge-thread";
     threadDescr[2] = "rtm-thread";
     nTests         = hasTSX() ? atf.size() : atf.size() - 1;

     for( size_t m = 0; m != atf.size(); ++m )
     {
         cout << threadDescr[m] << ":" << endl;
         for( unsigned nThreads = 1; nThreads <= nProcessors; ++nThreads )
         {
             atomic<size_t>   misses( 0 );
             uint8_t          run = false;
             size_t           atm;

             vector<thread> threads;
             for( unsigned i = 0; i != nThreads; ++i )
             {
                 threads.emplace_back( atf[m], ref( run ), ADDS, ref( 
atm ), ref( misses ) );
#if defined(_MSC_VER)
                 SetThreadAffinityMask( threads[i].native_handle(), 
(DWORD_PTR)1 << i );
#elif defined(__unix__)
                 cpu_set_t cpuset;
                 CPU_ZERO(&cpuset);
                 CPU_SET(i, &cpuset);
                 pthread_setaffinity_np( threads[i].native_handle(), 
sizeof cpuset, &cpuset );
#endif
             }
             time_point<high_resolution_clock> start = 
high_resolution_clock::now();
             run = true;
             for( unsigned i = 0; i != nThreads; ++i )
                 threads[i].join();
             uint64_t ns = (uint64_t)duration_cast<nanoseconds>( 
high_resolution_clock::now() - start ).count();;

             double nsPerAdd = (double)ns / nThreads / ADDS / 1.0e9;
             cout << "threads: " << nThreads << " cycles: " << nsPerAdd 
/ nsPerClockCycle << " misses-ratio: " << (int)(100.0 * (size_t)misses / 
nThreads / ADDS) << "%" << endl;
         }
         cout << endl;
     }
}

unsigned getNumberOfProcessors()
{
#if defined(_MSC_VER)
     SYSTEM_INFO si;
     GetSystemInfo( &si );
     return (unsigned)si.dwNumberOfProcessors;
#elif defined(__unix__)
     return (unsigned)get_nprocs();
#endif
}

bool hasTSX()
{
#if defined(_MSC_VER)
     int regs[4];
     __cpuidex( regs, 7, 0 );
     return regs[1] & (1 << 11);
#else
     return true;
#endif
}

The code has to be compiled with -mrtm with the gcc. I was to lazy to
code a correct RTM-detection for Linux so on Linux-machines the code
would crash without RTM-support. But RTM is that what I'm about here;
so could someone with a TSX-/RTM-enabled CPU please compile that on
his machine and paste the output here? The issue I'm interested in
is if rtmFetchAdd() is faster than compareExchange() or fetchAdd().

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

#69398

On 9/26/2019 2:13 AM, Bonita Montero wrote:
>>>> can I sign an NDA?
> 
>>> Why?
> 
>> I am interested in your algorithm! Makes me think of times past.
> 
> Something different: my algorithm is fast when fetching blocks from
> the lru-cache present in the cache, i.e. there can be an arbitrary
> number of threads doing that. But even this needs at least three
> CMPXCHGs on three 64 bit values (in a 64-bit-system, in a 32-bit
> system you would have two 64- and one 32-bit exchange) if there's
> no collision.

Are you using an embedded version count within the data the CAS's work 
on? Like an ABA counter? If a CAS fails, how far back do you have to 
restart, or unroll if you will?




  I'm asking myself if this would be faster with trans-
> actional memory, i.e if I'd build something similar like CMPXCHG
> with TSX-RTM, if this would be faster.
> I could redesign my "cachline ping pong" code to use TSX-RTM with-
> out having tested this on my PC; so could anyone here run the num-
> bers on that?

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

#69403

>> Something different: my algorithm is fast when fetching blocks from
>> the lru-cache present in the cache, i.e. there can be an arbitrary
>> number of threads doing that. But even this needs at least three
>> CMPXCHGs on three 64 bit values (in a 64-bit-system, in a 32-bit
>> system you would have two 64- and one 32-bit exchange) if there's
>> no collision.

> Are you using an embedded version count within the data the CAS's work 
> on? Like an ABA counter? If a CAS fails, how far back do you have to 
> restart, or unroll if you will?

No, I'm not using ABA-counters.

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

#69429

On 10/24/2019 2:00 AM, Bonita Montero wrote:
>>> Something different: my algorithm is fast when fetching blocks from
>>> the lru-cache present in the cache, i.e. there can be an arbitrary
>>> number of threads doing that. But even this needs at least three
>>> CMPXCHGs on three 64 bit values (in a 64-bit-system, in a 32-bit
>>> system you would have two 64- and one 32-bit exchange) if there's
>>> no collision.
> 
>> Are you using an embedded version count within the data the CAS's work 
>> on? Like an ABA counter? If a CAS fails, how far back do you have to 
>> restart, or unroll if you will?
> 
> No, I'm not using ABA-counters.

Are you embedding any state with a pointer? bit stealing?

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

#69430

On 10/24/2019 1:13 PM, Chris M. Thomasson wrote:
> On 10/24/2019 2:00 AM, Bonita Montero wrote:
>>>> Something different: my algorithm is fast when fetching blocks from
>>>> the lru-cache present in the cache, i.e. there can be an arbitrary
>>>> number of threads doing that. But even this needs at least three
>>>> CMPXCHGs on three 64 bit values (in a 64-bit-system, in a 32-bit
>>>> system you would have two 64- and one 32-bit exchange) if there's
>>>> no collision.
>>
>>> Are you using an embedded version count within the data the CAS's 
>>> work on? Like an ABA counter? If a CAS fails, how far back do you 
>>> have to restart, or unroll if you will?
>>
>> No, I'm not using ABA-counters.
> 
> Are you embedding any state with a pointer? bit stealing?
> 

It can be fun to align pointers on a large boundary, and use that extra 
space for meta data.

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

#69441

>> No, I'm not using ABA-counters.

> Are you embedding any state with a pointer? bit stealing?

No.

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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

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

csiph-web